Problem komiwojażera (często skracany do TSP) to klasyczny problem optymalizacyjny w informatyce i badaniach operacyjnych, dotyczący znalezienia najkrótszej możliwej trasy odwiedzającej zadany zbiór punktów i wracającej do punktu startowego. W praktyce celem jest minimalizacja całkowitego kosztu trasy (np. odległości, czasu lub ceny), dlatego problem jest często opisywany jako zadanie optymalizacji.

Definicja i model matematyczny

Standardowe sformułowanie TSP wykorzystuje wykres ważony: wierzchołki odpowiadają punktom do odwiedzenia, a krawędzie mają przypisaną wartość kosztu przejścia między punktami. Szukamy cyklu przechodzącego przez każdy wierzchołek dokładnie raz — to właśnie cykl Hamiltona w sensie grafowym — o najmniejszym możliwym sumarycznym koszcie.

Krótka historia

  • W XIX wieku pojawiły się zagadki związane z odwiedzaniem punktów, m.in. problem cyklu Hamiltona, znany z rekreacyjnych gier i łamigłówek.
  • W XX wieku matematycy i ekonomiści sformalizowali warianty problemu i rozważyli algorytmiczne podejścia; Hans Menger opisał problem i zwrócił uwagę, że jedynym oczywistym podejściem gwarantującym dokładne rozwiązanie jest przegląd wszystkich permutacji punktów.
  • Menger zauważył również, że tzw. strategia „przechodź zawsze do najbliższego punktu” — czyli heurystyka najbliższego otoczenia — nie gwarantuje rozwiązania optymalnego; tę uwagę formułowano także w odniesieniu do heurystyk heurystycznych ogólnie.
  • Nazewnictwo „problem podróżującego sprzedawcy” rozpowszechnił m.in. Hassler Whitney z Princeton University.

Złożoność obliczeniowa

TSP jest problemem trudnym obliczeniowo. Decyzyjna wersja problemu (czy istnieje trasa krótsza niż zadana granica) jest jednym z problemów NP‑zupełnych, a znalezienie optymalnej trasy należy do klasy problemów NP‑trudnych. W praktyce dla n punktów przegląd wszystkich możliwych tras wymaga rozważenia n! możliwości, co szybko staje się niepraktyczne.

Algorytmy i podejścia

W literaturze i praktycznych zastosowaniach rozróżnia się kilka grup metod:

  • Algorytmy dokładne
    • Brute force — sprawdzenie wszystkich permutacji (gwarantowana optymalność, złożoność czynnikowa).
    • Programowanie dynamiczne (algorytm Held–Karp) — złożoność O(n^2 2^n), stosowany do umiarkowanych n.
    • Metody branch and bound i programowanie całkowite — praktyczne do średnich instancji, gdy zastosuje się silne ograniczenia i cięcia.
  • Algorytmy przybliżone i aproksymacyjne
    • Wersje metryczne (spełniające nierówność trójkąta) pozwalają na aproksymacje z gwarancją błędu; przykładem jest algorytm Christofides dający aproksymację 1.5.
    • Algorytmy heurystyczne bez formalnych gwarancji, ale efektywne w praktyce (opisane poniżej).
  • Heurystyki i algorytmy lokalnego przeszukiwania
    • Heurystyka najbliższego sąsiada — szybka, lecz nieskuteczna w najgorszym wypadku (Menger i inni wskazywali na jej ograniczenia).
    • Operacje poprawiające trasę: 2‑opt, 3‑opt, heurystyka Lin–Kernighan — polepszają istniejące rozwiązania przez lokalne modyfikacje.
    • Metaheurystyki: algorytmy genetyczne, symulowane wyżarzanie, algorytmy mrówkowe — znajdują dobre rozwiązania dla dużych instancji.

Warianty i zastosowania

Istnieje wiele wariantów TSP, dostosowanych do różnych ograniczeń i zastosowań:

  • Symetryczny i asymetryczny TSP (koszty mogą zależeć od kierunku).
  • Euclidean TSP — wierzchołki w przestrzeni euklidesowej, koszty równają się odległościom geometrycznym.
  • Warianty z dodatkowymi ograniczeniami: okna czasowe, wielokrotni komiwojażerowie, koszty związane z ładunkiem, zadania typu „prize‑collecting”.

Praktyczne zastosowania obejmują optymalizację tras w logistyce i transporcie, planowanie produkcji i montażu (np. obróbka ścieżek w maszynach CNC), projektowanie obwodów drukowanych, a także zadania w bioinformatyce (np. porównywanie sekwencji genetycznych). W każdej z tych dziedzin wybór metody zależy od wielkości problemu i wymagań dotyczących jakości rozwiązania.

Uwagi końcowe

  • Pomimo prostego sformułowania, Problem komiwojażera pozostaje jednym z najważniejszych i najczęściej badanych problemów w teorii algorytmów i optymalizacji.
  • W praktyce łączy się teorię (klasyczna analiza złożoności) z inżynierskimi praktykami (heurystyki, metaheurystyki oraz specjalistyczne implementacje algorytmów dokładnych).
  • Historyczne uwagi o trudnościach rozwiązania i zawodności prostych reguł, jak przechodzenie „do najbliższego sąsiada”, można znaleźć w pracach klasycznych autorów i komentarzach Mengera.