W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi , tak więc dla 20 miast uzyskujemy wynik
Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
Przykładowe algorytmy znajdujące przybliżone rozwiązania problemu komiwojażera to algorytm najbliższego sąsiada i algorytm Christofidesa.
Historia Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832Oryginalny tytuł: Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur, który zawiera przykładową trasę po Niemczech i Szwajcarii, lecz nie zawiera żadnych matematycznych uzasadnień.
W 1859 irlandzki matematyk William Rowan Hamilton sformułował problem istnienia cyklu o długości n w grafie n-wierzchołkowym.
Za pierwszego autora, który sformalizował matematycznie problem komiwojażera uznaje się austriackiego matematyka Karla Mengera, który zdefiniował go w 1930 zwracając szczególną uwagę na trudność w obliczeniu rozwiązania. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University.