Keliaujančio pardavėjo problema (TSP) — apibrėžimas, istorija ir algoritmai

Keliaujančio pardavėjo problema (dažnai sutrumpintai TSP) yra klasikinis algoritminis uždavinys informatikos ir operacijų tyrimų srityje. Ji priklauso optimizavimo uždavinių klasei ir dažnai interpretuojama kaip paieška trumpiausio maršruto per tam tikrą mazgų (taškų) aibę. Paprastai problema formuluojama ant pilno svorinėto grafo: duota mazgų aibė V ir kiekvienai mazgų porai priskirtas svoris (atstumas) w(u,v); užduotis – rasti Hamiltono ciklą (kelionę, kuri aplanko kiekvieną mazgą tik vieną kartą ir grįžta į starto tašką), kurio bendras svoris minimaliu.

Šioje srityje geresnis sprendimas dažnai reiškia sprendimą, kuris yra pigesnis, trumpesnis arba greitesnis. TSP yra tiek teorinė, tiek labai praktinė problema: sprendimai taikomi maršrutų planavimui, logistikai, gamybos procesams ir net biotechnologijose.

Istorija

XIX a. keliaujančio pardavėjo problemą pirmaisiais paminėjimais sieja airių matematikas W. R. Hamiltonas ir britų matematikas Thomas Kirkmanas. Hamiltono Icosian Game buvo pramoginis galvosūkis, pagrįstas Hamiltono ciklo radimu. Svarbesnis formalus TSP nagrinėjimas prasidėjo XX a. trečiajame dešimtmetyje – matematikai Vienoje ir Harvarde (tarp jų Karlas Mengeris) aiškiai formulavo problemos variacijas, aptarė paprastas (brutalios jėgos) strategijas ir pastebėjo kai kurias euristikas kaip neoptimalias. Mengerio citata iš to laikotarpio iliustruoja probleminį pobūdį:

Pašnekovo uždaviniu (nes praktiškai šį klausimą turėtų spręsti kiekvienas paštininkas, bet kokiu atveju ir daugelis keliautojų) vadiname uždavinį rasti trumpiausią maršrutą, jungiantį ﬁziškai daug taškų, kurių poriniai atstumai yra žinomi. Žinoma, šis uždavinys išsprendžiamas baigtinai daug bandymų. Taisyklės, dėl kurių bandymų skaičius būtų mažesnis už duotų taškų permutacijų skaičių, nėra žinomos. Taisyklė, kad iš pradinio taško pirmiausia reikia eiti į artimiausią tašką, tada į artimiausią tašką ir t. t., apskritai neduoda trumpiausio maršruto.

Netrukus Prinstono universitete Hassleris Whitney pavadino šį uždavinį keliaujančio pardavėjo problema. Vėliau, XX a. viduryje, Dantzigas, Fulkersonas ir Johnsonas (1954) demonstravo praktinius sprendimo metodus (šakų ir ribų metodus bei LP formuluotes) ir parodė, kad su kompiuterine pagalba galima išspręsti gana dideles instancijas. Vėlesni darbai – Held–Karp (dinaminio programavimo riba ir 2^n n^2 laiko algoritmas), Christofides (1.5 aproksimacija metric TSP) ir galingi komerciniai bei akademiniai sprendėjai (pvz., Concorde, LKH) – gerokai išplėtė galimybes.

Formalus apibrėžimas ir variacijos

Standartiškai TSP apibrėžiama taip: duotas pilnas svorinėtas grafas G=(V,E) su |V|=n ir svoriais w: E → R_+. Raskite Hamiltono ciklą su mažiausia svorių suma. Dažniausios variacijos:

Simetrinis TSP – w(u,v)=w(v,u) visoms poroms (dažnai modeliuoja euklidinę geometriją).
Asimetrinis TSP – w(u,v) ≠ w(v,u) (pvz., skrydžių ar vienpusių kelių tinklai).
Metric TSP – svoriai tenkina trikampio nelygybę: w(u,v) ≤ w(u,x)+w(x,v) (daug praktinių atvejų, pvz., Euklidiniai atstumai).
Kita – papildomos sąlygos: laiko langai, kelių maršrutų (VRP), apribojimai dėl krovinio ir pan.

Skaičiavimo sudėtingumas

TSP yra skaičiavimo požiūriu sudėtinga: optimizavimo versija yra NP-sunki, o sprendimo egzistavimo (ar yra maršrutas, kurio ilgis ≤ B) versija yra NP-pilna. Tai reiškia, kad greito (polinominio laiko) algoritmo, kuris visada rastų optimalų sprendimą, kol kas nežinoma; manytina, jog toks algoritmas neegzistuoja (nebent P=NP).

Algoritmai

Yra trys pagrindinės sprendimo priėmimo kryptys: tikslūs metodai, aproksimacinės algoritmai ir euristikos / metaeuristikos.

Tikslūs algoritmai

Brutalios permutacijos: išbandomos visos (n-1)! maršrutų permutacijos — garantuoja optimalumą, bet laiko sudėtingumas O(n!) greitai tampa nevaldoma.
Dinaminis programavimas (Held–Karp): laikas O(n^2 2^n), atmintis O(n 2^n) — praktinis iki n ≈ 30–40.
Šakų ir ribų (branch-and-bound) bei karpymo plokščių metodai (cutting planes, LP): naudojami profesionaliuose sprendžiuose (pvz., Concorde) ir leidžia išspręsti labai dideles instancijas optimaliai.

Aproksimaciniai algoritmai

Christofides algoritmas (1976): suteikia 1.5 aproksimaciją metric versijai (simetrinis TSP su trikampio nelygybe).
Double-tree (2-approx): paprastas dvigubinimo ir sutrumpinimo metodas.
Asimetrinė versija turi savus aproksimacijos rezultatus, tačiau sunkiau pasiekti mažus koeficientus.

Euristikos ir metaeuristikos

Dažnai praktiškai sprendžiant dideles instancijas prioritetas yra gera kokybinė sprendimo greitai (nebūtinai optimalu). Populiarūs metodai:

Artimiausio kaimyno (nearest neighbor): paprasta, bet gali duoti prastą rezultatą (kaip pastebėjo Mengeris).
Įterpimo euristikos (insertion) – greitos pradinės sprendimo konstrukcijos.
Lokalus tobulinimas: 2-opt, 3-opt (keitimai, kurie pašalina kryžmius), Lin–Kernighan heuristika (labai efektyvi praktikoje).
Metaeuristikos: genetiniai algoritmai, sukimo atitirpinimas (simulated annealing), skruzdžių kolonijų optimizavimas (ant colony optimization) — tinkami didelėms, realioms problemoms.

Praktinės įgyvendinimo priemonės

Yra kelios plačiai naudojamos bibliotekos ir sprendėjai: Concorde (galingas tikslus sprendėjas), LKH (Lin–Kernighan heuristikos implementacija), įvairūs komerciniai optimizavimo paketai. Šios priemonės naudoja mišrias strategijas: LP relaxacijas, šakų ir ribų, karpymo plokštes bei pažangias lokalaus tobulinimo heuristikas.

Panaudojimo sritys

TSP ir jos variacijos taikomos:

krovinių ir maršrutų planavimui, logistikai;
gamybos procesų optimizavimui (pvz., gręžimo tvarka)
mikrograndinių (PCB) gamybai ir litografijai;
genetinių duomenų apdorojimui (kai kurias problemas galima modeliuoti kaip eiliškumą ar sutapimus);
robotikos maršrutų planavimui ir kt.

Išvados

Keliaujančio pardavėjo problema – fundamentali ir plačiai nagrinėjama optimizavimo užduotis: ji turi stiprų teorinį pagrindą, įdomią istoriją ir daugybę praktinių pritaikymų. Nors optimalus sprendimas yra skaičiavimo požiūriu sunkus, plati įrankių ir algoritmų įvairovė leidžia rasti gerus sprendimus įvairioms realioms situacijoms.

Pardavėjas nori aplankyti visus miestus: A, B, C ir D. Koks geriausias būdas tai padaryti (pigiausi lėktuvo bilietai ir trumpiausias kelionės laikas)?

Optimalus 15 didžiausių Vokietijos miestų lankančio pardavėjo maršrutas. Parodytas maršrutas yra trumpiausias iš 43 589 145 600 galimų maršrutų.

Viljamas Rovanas Hamiltonas

Problemos įvardijimas

Keliaujančio pardavėjo uždavinys aprašo pardavėją, kuris turi keliauti tarp N miestų. Jam nerūpi, kokia tvarka jis tai darys, jei tik kelionės metu aplankys kiekvieną iš jų po vieną kartą ir baigs kelionę ten, kur buvo iš pradžių. Kiekvienas miestas yra sujungtas su kitais artimais miestais, arba mazgais, lėktuvais, keliais arba geležinkeliais. Kiekvienam iš šių ryšių tarp miestų priskiriamas vienas ar daugiau svorių (arba sąnaudų). Sąnaudos nusako, kaip "sunku" kirsti šią grafo briauną, ir gali būti išreikštos, pavyzdžiui, lėktuvo ar traukinio bilieto kaina, arba galbūt briaunos ilgiu, arba laiku, kurio reikia norint ją kirsti. Pardavėjas nori, kad kelionės išlaidos ir nuvažiuojamas atstumas būtų kuo mažesni.

Keliaujančio pardavėjo problema yra tipiška didelės klasės "sunkių" optimizavimo problemų, kurios jau daugelį metų domina matematikus ir informatikus, problema. Svarbiausia yra tai, kad ji taikoma mokslo ir inžinerijos srityse. Pavyzdžiui, gaminant spausdintinę plokštę, svarbu nustatyti geriausią tvarką, kuria lazeris išgręš tūkstančius skylučių. Efektyvus šios problemos sprendimas sumažina gamintojo gamybos sąnaudas.

Sudėtingumas

Apskritai keliaujančio pardavėjo uždavinį sunku išspręsti. Jei yra būdas suskaidyti šį uždavinį į mažesnius komponentinius uždavinius, komponentai bus ne mažiau sudėtingi nei pradinis uždavinys. Tai informatikos specialistai vadina NP sunkiais uždaviniais.

Šią problemą tyrinėjo daugybė žmonių. Paprasčiausias (ir brangiausias) sprendimas - tiesiog išbandyti visas galimybes. Problema ta, kad N miestų atveju turite (N-1) faktorių galimybių. Tai reiškia, kad tik 10 miestų galima išbandyti daugiau kaip 180 tūkstančių kombinacijų (kadangi pradinis miestas yra apibrėžtas, gali būti likusių devynių miestų permutacijų). Skaičiuojame tik pusę, nes kiekvienas maršrutas turi tokį pat maršrutą atvirkščiai, kurio ilgis arba kaina yra tokia pati. 9! / 2 = 181 440

Tikslius uždavinio sprendinius galima rasti naudojant šakų ir ribų algoritmus. Šiuo metu tai įmanoma iki 85 900 miestų.
Euristiniuose metoduose kitam mazgui parinkti naudojamas pagrindinių taisyklių rinkinys. Tačiau kadangi euristikos rezultatai yra apytiksliai, jos ne visada duoda optimalų sprendimą, nors kokybiškos leistinos euristikos gali surasti naudingą sprendimą per dalį laiko, reikalingo visiškam problemos išsprendimui brutalia jėga. Euristikos pavyzdys mazgui būtų suma, kiek neaplankytų mazgų yra "arti" sujungto mazgo. Tai galėtų paskatinti pardavėją aplankyti artimų mazgų grupę, susitelkusią kartu, ir tik tada pereiti prie kito natūralaus grafo klasterio. Žr. Monte Karlo algoritmus ir Las Vegaso algoritmus

Klausimai ir atsakymai

K: Kas yra keliaujančio pardavėjo problema?

A: Keliaujančio pardavėjo problema (angl. Traveling Salesman Problem, TSP) yra klasikinis algoritminis uždavinys informatikos ir operacijų tyrimų srityje. Jame daugiausia dėmesio skiriama optimizavimui, o geresni sprendimai dažnai reiškia pigesnius, trumpesnius arba greitesnius sprendimus.

K: Kaip išreiškiama TSP?

A: TSP lengviausia išreikšti kaip grafą, kuriame aprašomos mazgų aibės vietos.

K: Kas pirmasis apibrėžė TSP?

A: Keliaujančio pardavėjo problemą XIX a. apibrėžė airių matematikas W. R. Hamiltonas ir britų matematikas Thomas Kirkmanas.

K: Kas ją toliau tyrinėjo XX a. trečiajame dešimtmetyje?

A: XX a. trečiajame dešimtmetyje ją toliau tyrinėjo Vienos ir Harvardo matematikai Karlas Mengeris.

K: Ką netrukus po to įvedė Hasleris Vitnis?

A: Hassler Whitney Prinstono universitete netrukus po apibrėžimo įvedė "keliaujančio pardavėjo problemos" pavadinimą.

K: Ką šiame kontekste reiškia "geresnis sprendimas"?

A: Šiame kontekste geresnis sprendimas dažnai reiškia pigesnį, trumpesnį ar greitesnį sprendimą.

Klausimas: Kokį algoritmą Mengeris, nagrinėdamas TSP, laikė akivaizdžiu?

Atsakymas: Mengeris, tirdamas TSP, akivaizdžiu laikė brutalios jėgos algoritmą ir pastebėjo, kad naudojant artimiausio kaimyno euristiką ne visada gaunami optimalūs rezultatai.