Ceļojošā pārdevēja problēma (bieži saukta par TSP) ir klasiska algoritmiska problēma datorzinātnes un operāciju izpētes jomā. Tā ir centrāla problēma optimizācijā. TSP formulējums ir vienkāršs: dota pilsētu (mezglu) kopā un katru pāri savieno ar attālumu vai izmaksām, jāatrod īsākais maršruts, kas apmeklē katru pilsētu tieši vienu reizi un atgriežas sākumpunktā. Citiem vārdiem — jāatrod īsākais Hamiltona cikls dotajā grafikā. Praktiski “labāks risinājums” nozīmē maršrutu, kas ir lētāks, īsāks vai ātrāks pēc definētā kritērija.

Vēsture

Idejas saknes meklējamas 19. gadsimtā — vienkāršākas versijas problēmai saistās ar tādām konstrukcijām kā V. R. Hamiltona izklaides uzdevumi (Hamiltona cikls) un T. Kirkmana darbi. Sarežģītāka un sistemātiska problēmas pētīšana kļuva aktuāla 20. gadsimta sākumā un 30. gados — piemēram, Karls Mengers apskatīja vispārīgāku formulējumu, pētīja triviālos brutālā spēka paņēmienus un konstatēja, ka vienkāršas gulšas stratēģijas nav optimālas. Mengers savā rakstā norādīja, ka heuristika “iet uz tuvāko kaimiņu” nereti nedod īsāko maršrutu; šis novērojums vēl šodien kalpo kā mācību piemērs:

Ar kurjera problēmu (jo praksē šis jautājums būtu jārisina katram pastniekam, katrā ziņā arī daudziem ceļotājiem) apzīmējam uzdevumu atrast īsāko maršrutu, kas savieno punktus, fintificēti daudziem punktiem, kuru pāru attālumi ir zināmi. Protams, šis uzdevums ir atrisināms ar galīgi daudziem mēģinājumiem. Nav zināmi noteikumi, kas mēģinājumu skaitu samazinātu zem doto punktu permutāciju skaita. Noteikums, ka vispirms no sākuma punkta jāiet uz tuvāko punktu, tad uz tam tuvāko punktu utt., kopumā nedod īsāko maršrutu.

Nosaukums angļu valodā “travelling salesman problem” kļuva plašāk lietots 20. gadsimta vidū, un problēma ieguva arvien lielāku uzmanību gan teorētiskajā, gan lietišķajā pētniecībā — piemēram, darbā par lineāro programmēšanu un griezes-plāksnēm 1950. gados. Termins un problēmas izpēte tika plaši apspriesta akadēmiskajās institūcijās, tostarp Prinstonas universitātē.

Matemātiska sarežģītība

TSP vispārējā forma ir grūti atrisināma: tā ir NP-hard, un lēmuma versija (“vai eksistē maršruts ar izmaksām ≤ K?”) ir NP-complete. Tas nozīmē, ka nav zināma polinomiāla algoritma, kas risinātu visas TSP instances, un vairumā gadījumu vienkāršs brutāls meklējums (visu permutāciju pārbaudīšana) ir eksponenciāli dārgs — ~n! iespējamie ceļi n pilsētu gadījumā. Tomēr pastāv efektīvas metodes un ierobežojumi, kas ļauj atrisināt praktiski svarīgas variācijas vai iziet pie labiem aptuveniem risinājumiem lielām instanceēm.

Galvenās TSP variācijas

  • Simetrisks TSP: attālums no A uz B ir vienāds ar attālumu no B uz A.
  • Asimetrisks TSP: attālumi nav simetriski (piem., satiksmes laiki dažādos virzienos).
  • Metric/€uclidean TSP: izmaksas atbilst trijstūra nevienādībai; Eiklīda gadījumā pilsētas ir plaknē un izmanto Eiklīda attālumu.
  • Īpašas ierobežojumu versijas: kapacitātes ierobežojumi, laika logi, vairāku kravu piegādes u.c., kas tiek izmantotas loģistikā.

Metodes un algoritmi

Atkarībā no problēmas lieluma un prasībām tiek izmantotas dažādas pieejas:

  • Eksaktas metodes: brutālā spēka pārbaude, dinamikas programmēšana (Held–Karp algoritms ar laika sarežģītību apmēram O(n^2 2^n)), griešanas plakņu (cutting-plane) pieejas un kombinācija ar branch-and-bound. Slavens agrīns darbs par TSP optimizāciju izmantojot lineāro programmēšanu bija Dantzig, Fulkerson un Johnson (1954).
  • Heuristikas un aptuveni algoritmi: tuvākā kaimiņa heuristika, 2-opt un 3-opt lokālā meklēšana, Lin–Kernighan heurstika, ģenētiskie algoritmi, simulēta atdzišana u.c. Daudzas no šīm metodēm sniedz ātrus un praktiski labi risinājumus lieliem uzdevumiem, bet bez striktas optimāluma garantijas.
  • Garantētas aptuvenas metodes: Christofides algoritms (simetriskajam metric TSP) nodrošina risinājumu ne sliktāku par 1.5 reizes optimālo.
  • Praktiskie rīki: moderni solveri (piem., Concorde) apvieno griezes planes, branch-and-bound un citu optimizāciju tehnikas, ļaujot atrisināt ļoti lielas instanču kopas optimāli vai ar ļoti mazu kļūdu robežu.

Pielietojumi

TSP nav tikai teorētiska problēma — tai ir plašs praktisks pielietojums:

  • loģistika un maršrutu plānošana (piegādes, kurjeru tīkli),
  • ražošanas plānošana (piem., mikroshēmu ražošanā),
  • bioloģijas datu analīze (DNS fragmentu ķēdēšana un sekvencēšana),
  • robotikas ceļošanas un sensoru tīklu optimizācija.

Praktiski ieteikumi

Ja instance ir maza (piem., n ≤ 15–20), eksakta dinamikas vai brutālā meklēšana var būt praktiska. Vidēja lieluma problēmām (dažas desmitas līdz daži simti punktu) bieži piemēro kombinētus eksaktus/heuristiskus paņēmienus vai spēcīgus solverus. Lielām instancēm, kur nepieciešams ātrs risinājums, parasti lieto heuristikas (Lin–Kernighan, 2/3-opt, ģenētiskos algoritmus) un, ja iespējams, izmanto problēmas īpašības (Eiklīda metrika, trijstūra nevienādība), lai iegūtu labus aptuvenos rezultātus.

Ceļojošā pārdevēja problēma ir paradigmisks piemērs, kas savieno teorētisko sarežģītību ar praktiskām optimizācijas vajadzībām — tās pētījumi turpinās, attīstot gan jaunas teorētiskas pieejas, gan efektīvākas heuristikas un programmatūras rīkus.