Ceļojošā pārdevēja problēma (TSP): definīcija, vēsture un optimizācija

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, ﬁntificē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.

Pārdevējs vēlas apmeklēt visas pilsētas A, B, C un D. Kāds ir labākais veids, kā to izdarīt (lētākās aviobiļetes un minimāls ceļojuma laiks)?

Pārdevēja optimālais maršruts, apmeklējot 15 lielākās Vācijas pilsētas. Parādītais maršruts ir īsākais no 43 589 145 600 iespējamiem maršrutiem.

Viljams Rovans Hamiltons

Problēmas formulēšana

Ceļojošā pārdevēja problēma apraksta pārdevēju, kuram jāceļo starp N pilsētām. Viņam ir vienalga, kādā secībā viņš to darīs, ja vien viņš ceļojuma laikā apmeklē katru no tām vienu reizi un pabeidz ceļojumu tur, kur viņš bija sākumā. Katra pilsēta ir savienota ar citām tuvējām pilsētām jeb mezgliem, izmantojot lidmašīnas, autoceļus vai dzelzceļu. Katram no šiem savienojumiem starp pilsētām ir viens vai vairāki svari (vai izmaksas). Izmaksas raksturo, cik "grūti" ir šķērsot šo grafika šķautni, un tās var norādīt, piemēram, lidmašīnas vai vilciena biļetes cena vai, iespējams, šķautnes garums, vai laiks, kas nepieciešams, lai veiktu šķautni. Pārdevējs vēlas, lai gan ceļošanas izmaksas, gan nobrauktais attālums būtu pēc iespējas mazāks.

Ceļojošā pārdevēja problēma ir raksturīga lielai "smagu" optimizācijas problēmu klasei, kas jau gadiem ilgi intriģē matemātiķus un datorzinātniekus. Vissvarīgākais ir tas, ka tā ir pielietojama zinātnē un inženierzinātnēs. Piemēram, shēmas plates izgatavošanā ir svarīgi noteikt labāko secību, kādā lāzers izurbj tūkstošiem caurumu. Efektīvs šīs problēmas risinājums samazina ražošanas izmaksas ražotājam.

Grūtības

Kopumā ceļojošā pārdevēja problēma ir grūti atrisināma. Ja ir veids, kā šo problēmu sadalīt mazākās sastāvdaļās, tad tās būs vismaz tikpat sarežģītas kā sākotnējā problēma. Datorzinātnieki to sauc par NP-grūtām problēmām.

Daudzi cilvēki ir pētījuši šo problēmu. Visvienkāršākais (un visdārgākais) risinājums ir vienkārši izmēģināt visas iespējas. Problēma ir tāda, ka N pilsētām ir (N-1) faktoriāla iespēja. Tas nozīmē, ka tikai 10 pilsētām var izmēģināt vairāk nekā 180 tūkstošus kombināciju (tā kā sākuma pilsēta ir definēta, pārējām deviņām pilsētām var būt permutācijas). Mēs skaitām tikai pusi, jo katram maršrutam ir vienāds maršruts pretējā virzienā ar tādu pašu garumu vai izmaksām. 9! / 2 = 181 440

Problēmas precīzus risinājumus var atrast, izmantojot zaru un robežu algoritmus. Pašlaik tas ir iespējams līdz 85 900 pilsētām.
Eiristiskās pieejas izmanto vadlīniju kopumu nākamā mezgla izvēlei. Taču, tā kā heiristikas rezultātā tiek iegūtas aproksimācijas, tās ne vienmēr sniedz optimālo risinājumu, lai gan augstas kvalitātes pieļaujamās heiristikas var atrast noderīgu risinājumu daļā laika, kas nepieciešams pilnīgai problēmas risināšanai ar brutālu spēku. Eiristikas piemērs mezglam varētu būt summēšana par to, cik daudz neapmeklētu mezglu atrodas "tuvu" savienotajam mezglam. Tas varētu mudināt pārdevēju apmeklēt tuvumā esošo mezglu grupu, kas sagrupēti kopā, pirms pāriet uz citu dabisku grafa kopu. Skatīt Monte Karlo algoritmus un Lasvegasas algoritmus.

Jautājumi un atbildes

J: Kas ir ceļojošā pārdevēja problēma?

A: Ceļojošā pārdevēja problēma (TSP) ir klasiska algoritmiska problēma datorzinātnes un operāciju izpētes jomā. Tā ir vērsta uz optimizāciju, un labāki risinājumi bieži nozīmē lētākus, īsākus vai ātrākus risinājumus.

J: Kā tiek izteikta TSP?

A: TSP visvieglāk izteikt kā grafiku, kas apraksta mezglu kopas atrašanās vietas.

J: Kas pirmais definēja TSP?

A: Ceļojošā pārdevēja problēmu 19. gadsimta 19. gadsimtā definēja īru matemātiķis V. R. Hamiltons un britu matemātiķis Tomass Kirkmans.

J: Kurš to tālāk pētīja 20. gadsimta 30. gados?

A: 20. gadsimta 30. gados matemātiķi Karls Mengers Vīnē un Hārvardā turpināja pētīt šo problēmu.

J: Ko drīz pēc tam ieviesa Haslers Vitnijs?

A.: Haslers Vitnijs Prinstonas universitātē drīz pēc tās definēšanas ieviesa nosaukumu "ceļojošā pārdevēja problēma".

J: Ko šajā kontekstā nozīmē "labāks risinājums"?

A: Šajā kontekstā labāks risinājums bieži nozīmē lētāku, īsāku vai ātrāku risinājumu.

J: Kādu algoritmu Mengers, pētot TSP, uzskatīja par acīmredzamu?

A: Mengers, pētot TSP, uzskatīja par acīmredzamu brutālā spēka algoritmu un novēroja, ka, izmantojot tuvākā kaimiņa heiristiku, ne vienmēr iegūst optimālus rezultātus.