Problem komiwojażera

Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym^[1][2].

Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie^[1][2].

Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.

Główną trudnością problemu jest duża liczba danych do analizy. W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi ${\displaystyle {\frac {(n-1)!}{2}}}$^[3], tak więc dla 20 miast uzyskujemy wynik ${\displaystyle {\frac {19!}{2}}\approx 6\times 10^{16}}$

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.

Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832^[a], 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^[4].

Za pierwszego autora, który sformalizował matematycznie problem komiwojażera uznaje się austriackiego matematyka Karla Mengera, który zdefiniował go w 1930^[5] zwracając szczególną uwagę na trudność w obliczeniu rozwiązania^[6]. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University^[5]. Natomiast pierwsza próba rozwiązania problemu miała miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych^[5].

Z uwagi na bardzo prosty opis problemu oraz opinię o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny^[5]. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów^[5][2].

Miasta: Kutno, Warszawa, Poznań, Kraków

Odległości:

	Kutno	Warszawa	Poznań	Kraków
Kutno	0	130	180	300
Warszawa	130	0	320	350
Poznań	180	320	0	360
Kraków	300	350	360	0

Należy znaleźć najkrótszą trasę zaczynającą się np. z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.

Problem ten jest NP-trudny^[1].

W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.

Tak sformułowany problem jest NP-zupełny.

• Maciej MarekM.M. Sysło Maciej MarekM.M., NarsinghN. Deo NarsinghN., Janusz S.J.S. Kowalik Janusz S.J.S., Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0 .

• Traveling Salesman Problem   (ang.).