TSP docs

Komivojazerio uzdavinio tyrimas Arunas Kasinskas ir Lina Stoniene, VDU, 2000.12.08 e-mail: [email protected]

Įvadas

Keliaujančio prekeivio uždavinys (TSP Traveling Salesperson Problem) viena iš plačiausiai nagrinėjamų užduočių, sprendžiant optimizavimo uždavinius. Keliaujančio prekeivio tikslas yra aplankyti tam tikrą skaičių įvairių miestų ar vietovių taip, kad nukeliautas atstumas būtų kaip galima trumpesnis. Keliaujančio prekeivio uždavinys priklauso sunkių optimizavimo užduočių klasei.

Šis uždavinys plačiai taikomas realiame gyvenime. Matematikos ir informatikos mokslo šakų atstovai dažnai nagrinėja su keliaujančio prekeivio uždaviniu susijusias optimizavimo problemas. Matematikai pradėjo domėtis šia sritimi jau nuo 1759 metų. Euleris ir Vandermonde nagrinėjo rikio turą (knigt's tour) šachmatų lentoje, kuris atitiko Hamiltono ciklą grafe su 64 viršūnėmis. 1856 metais Hamiltonas sukūrė grafų teorijoje Icosian Calculus žaidimą. Reikėjo užbaigti ciklą (Hamiltono) naudojant tam tikrą skaičių sunumeruotų vinių ir žaidimų lentą. 1930 metais Mengeris paminėjo pasiuntinuko problemą, kuri susijusi su trumpiausio kelio paieška Hamiltono cikle. Keliaujančio prekeivio terminas pirmą kartą buvo paminėtas 1931/32 metais Hasslerio Whitney iš Princetono universiteto. Jis sutapatino rikio turo, pasiuntinuko ir keliaujančio prekeivio problemas, kurios iki šiol domina daugelį mokslo srities atstovų.

Keliaujančio prekeivio uždavinio formulavimas

Keliaujantis prekeivis turi aplankyti N skirtingų miestų taip, kad viso maršruto svoris būtų kaip galima mažesnis, kai iš anksto yra žinomi visi svoriai. Maršruto svoriu gali būti įvardintas jo ilgis, kaina, trukmė.
Kiekvienas miestas gali būti aplankytas tik vieną kartą ir prekeivis turi baigti savo kelionę tame pačiame mieste, iš kurio jis pradėjo keliauti. Maršruto ilgis turi būti kiek galima trumpesnis. Keliaujančio prekeivio uždavinio tikslas yra minimizuoti viso maršruto svorinę funkciją (maršruto kainą, ilgį ar laiką):

Tai yra bendras keliaujančio prekeivio uždavinio (TSP) formulavimas. Yra daug atskirų keliaujančio prekeivio uždavinio formulavimo atvejų.

Simetrinis keliaujančio prekeivio uždavinys

Maršrutų svoriai w_ij tarp miestų i ir j gali būti atvaizduojami matrica. Matricos elementai w_ii = 0, kai i = 1, , N.

	1	2		j		N
1	0	w₁₂		w_1j		w_1N
2	w₂₁	0		w_2j		w_2N
...	...	...	0	...	...	...
i	w_i1	w_i2		w_ij		w_iN
...	...	...	...	...	0	...
N	w_N1	w_N2		w_Nj		0

Simetrinio keliaujančio prekeivio uždavinio atveju yra naudojama simetrinė maršrutų svorių matrica. Ir maršrutų svoriai tarp miestų i ir j w_ij =w_ji., kai i, j = 1, , N. Taigi gauto maršruto svoris bus toks pat, jeigu prekeivis keliaus atvirkštine tvarka.

Asimetrinis keliaujančio prekeivio uždavinys

Šiuo atveju, atstumas (kaina, svoris) iš miesto i į miestą j nebūtinai toks pats kaip iš miesto j į miestą i. Tuomet maršrutų svorių matricos elementai w_ij nelygūs w_ji,
kai i, j = 1, , N.

Daugelio keliaujančių prekeivių uždavinys

Galima nagrinėti ir tokį atvejį, kai yra m prekeivių, kurie yra mieste ir turi aplankyti kitus miestus. Kiekvienas iš N miestų turi būti aplankytas vieno iš m prekeivių. Tikslas yra surasti kiekvienam prekeiviui tokį maršrutą, kad sudėjus visų prekeivių maršrutus, gautume tokį rezultatą: kiekvienas iš N miestų bus aplankytas tik vieną kartą. Kiekvienas prekeivis turi pradėti ir baigti iš anksto nurodytoje vietoje.

Keliaujančio prekeivio maršruto optimizavimas

Keliaujančio prekeivio uždavinys priskiriamas kombinatorinių optimizavimo uždavinių klasei. Sprendžiant šį uždavinį, galima pritaikyti patį paprasčiausią sprendimo būdą perrinkimo algoritmą: sudaryti visus įmanomus maršrutus, rasti jų ilgį ir išrinkti patį trumpiausią maršrutą. Tačiau, jei mes turime n miestų, tai visų galimų maršrutų skaičius bus (n 1)! . Taigi šį algoritmą galima taikyti tik tada, kai turime labai mažai miestų. Šis algoritmas duoda patį trumpiausią maršrutą, tačiau yra pats neefektyviausias, skaičiavimų laiko prasme. Nagrinėjant TSP uždavinius reikia tokių algoritmų, kurie duotų optimalų sprendinį per polinominį laiką (lyginant su miestų skaičiumi n). Sprendžiant TSP uždavinius gali būti taikomi įvairūs algoritmai.

Apytikslūs algoritmai

Keliaujančio prekeivio uždavinio sprendimui gali būti naudojami algoritmai, kurie neduoda optimaliausio sprendinio, bet jų rezultatas - pakankamai optimalus sprendinys, gaunamas per polinominį laiką. Apytikslus algoritmas duoda sprendinį, kuris yra pakankamai arti optimalaus sprendinio. Apytikslių algoritmų atveju sprendinio paieškos laiką gan tiksliai galima numatyti iš anksto. Vienas iš apytikslių algoritmų pavyzdžių - šakų ir ribų metodas (Branch-and-Bound).

Heuristiniai algoritmai

Sprendžiant keliaujančio prekeivio uždavinį, dažniausiai naudojami heuristiniai algoritmai. Jie pateikia nebūtinai patį trumpiausią maršrutą, o tikėtinai trumpiausią. Tačiau heuristiniai algoritmai yra efektyvūs laiko prasme. Taigi heuristiniai algoritmai gali ir neduoti optimalaus sprendinio. Lyginant su apytiksliais algoritmais iš anksto nusakyti heuristinių algoritmų sprendinio paieškos laiką yra sudėtingiau.

Labai dažnai naudojami taip vadinami godūs heuristiniai algoritmai, kurie renkasi patį geriausią sprendimą tuo laiko momentu, nesirūpindami kaip tas pasirinkimas įtakos tolimesnę sprendimo eigą. Tokio algoritmo pavyzdys yra artimiausio kaimyno algoritmas (jis pateikiamas žemiau).

Genetiniai algoritmai naudoja evoliucijos proceso gamtoje metaforą. Sukuriama tam tikra populiacija individų, kurių kiekvieną apibūdina tam tikras chromosomų rinkinys (tai gali būti simbolių rinkinys). Tuomet ši populiacija gali vystytis ir augti kaip ir tikro evoliucijos proceso metu. Atskiri genetinių algoritmų atvejai taip pat gali būti taikomi sprendžiant TSP uždavinius.

Reikia paminėti, kad heuristinių algoritmų klasei priklauso tabu paieškos ir modeliuojamo atkaitinimo algoritmai. Jie taip pat gali būti naudojami spręsti keliaujančio prekeivio uždaviniui.

Realizuoti keliaujančio prekeivio uždavinio algoritmai

Išnagrinėjus šio uždavinio sprendimo metodus, ir atsižvelgiant į jų efektyvumą, buvo nuspręsta šį uždavinį realizuoti keliais metodais ir palyginti gautus rezultatus efektyvumo ir optimalumo prasme. Uždavinio realizavimui pasirinkti heuristiniai algoritmai: artimiausio kaimyno algoritmas, pasikartojantis artimiausio kaimyno algoritmas ir lankų pakeitimo (2-opt exchange) algoritmas. Pastarasis algoritmas buvo realizuotas dviem būdais: pirmas kai pradinis sprendinys artimiausio
kaimyno metodu gautas sprendinyd, antras pradinis sprendinys parinktas pseudo random būdu, pagal tai kokia tvarka buvo sužymėti miestai.

Artimiausio kaimyno algoritmas

Vienas iš godžių heuristinių algoritmų yra Artimiausio kaimyno algoritmas (Nearest Neighbour Algorythm). Pasirenkamas kelionės pradžios taškas (miestas) ir toliau einama į artimiausią jam miestą. Iš to miesto einama į kitą artimiausią miestą, nesirenkant jau aplankytų miestų, ir taip iki pat galo kai visi miestai bus aplankyti. Kelionė baigiasi, kai yra sugrįžtama į pradinį miestą.

Šio algoritmo sudėtingumas O(n³). Šis algoritmas gali ir neduoti optimaliausio maršruto. Todėl naudojamas algoritmo patobulinimas Pasikartojantis artimiausio kaimyno algoritmas (Repetitive Nearest Neighbour Algorythm).

Pasikartojantis artimiausio kaimyno algoritmas

Pasikartojantis artimiausio kaimyno algoritmas atlieka viską taip pat kaip ir artimiausio kaimyno algoritmas. Tik šiuo atveju artimiausio kaimyno algoritmas kartojamas N kartų, kaip išeities tašką pasirenkant vis kitą miestą. Tuomet iš gautų N maršrutų išrenkamas trumpiausias maršrutas. Gautas sprendinys yra optimalesnis arba sutampa su artimiausio kaimyno"algoritmo duodamu rezultatu.

Artimiausio kaimyno metodas ir pasikartojantis artimiausio kaimyno metodas yra vidutinės kokybės metodai. Norint pagerinti maršrutą, naudojamas 2-opt pakeitimo (2-opt exchange) metodas.

2- opt exchange algoritmas

Šis algoritmas priklauso lokalios paieškos heuristinių algoritmų klasei, kai duotas pradinis maršrutas H. 2-opt exchange algoritmo veikimo principas yra dviejų lankų panaikinimas, perjungiant lankų viršūnes kitokiu būdu, norint gauti geresnį , trumpesnį maršrutą. Jei naujasis maršrutas H yra trumpesnis, tuomet jis pakeičia maršrutą H. Yra tik vienintelis būdas perjungti lankus, kurie įeina į maršrutą. Tarkime turime du lankus:(i1 i2) ir (j1 j2) Perjungti lankai:(i1 j1) ir (i2 j2),

kur i1, i2, j1, j2 yra lankų viršūnės.

Jei length (i1 i2) + length(j1 j2) > length (i1 j1) + length (i2 j2), tuomet turime geresnį maršrutą H, kuris pakeičia maršrutą H.

Iš visų galimų lankų porų (vienos poros lankai neturi bendrų viršūnių), kurių 2-opt sukeitimas sumažina ilgį, pasirenkame tokią porą, kuri duoda trumpiausią maršrutą. Ši procedūra kartojama tol, kol nelieka porų, kurias galima būtų perjungti. Galutinis maršrutas vadinamas 2-optimaliu. Optimalus maršrutas taip pat yra ir 2-optimalus. Šis algoritmas tinka tik simetriniam TSP.

2-opt exchange algoritmas duoda geresnį rezultatą, jei yra pradinis maršrutas yra pakankamai optimalus. Todėl pradinis maršrutas šiame algoritme gali būti pasirenkamas kaip artimiausio kaimyno metodo rezultatas.

Išvados

Šiame darbe buvo realizuoti trys metodai, skirti spręsti keliaujančio prekeivio uždaviniui. Tai artimiausio kaimyno, pasikartojančio artimiausio kaimynoir dviejų lankų pakeitimo metodai. Savaime suprantama tokius uždavinius spręsti galima be galo daug būdų. Pats tiksliausias atsakymas būtų gautas naudojant perrinkimo metodą. Tačiau net leidžiant pažymėti tik 20 miestų, tai būtų per didelė prabanga. Norint gauti atsakymą, reiktų atlikti net 20! iteracijų. Atliekant šių skirtingų algoritmų palyginimą buvo pasirinkti du parametrai, kurie tiesiogiai atspindi algoritmų optimalumą ir efektyvumą. Visi algoritmai buvo lyginami dviem aspektais: gauto trumpiausio maršruto ir iteracijų skaičiaus. Šiuo atveju buvo skaičiujamos tik ciklo iteracijos, neatsižvelgiant į tai kiek vienoje ciklo iteracijoje atliekama matematinių ar kitokių operacijų.

Iš karto galima pastebėti, kad artimiausio kaimyno ir pasikartojančio artimiausio kaimyno metodų sudėtingumą galima nesunkiai įvertinti. Artimiausio kaimyno metodas atlieka n² iteracijų, o pasikartojančio artimiausio kaimyno metodas n³ iteracijų. Tačiau lankų pakeitimo metodo sudėtingumo teoriškai įvertinti neįmanoma. Sudėtingumas nepriklauso nuo miestų skaičiaus, o priklauso nuo to kiek bus padaryta lankų sukeitimo operacijų.

Buvo padarytos dvi lankų pakeitimo metodo modifikacijos. Pirmu atveju pradiniam maršrutui naudojamas pasikartojančio kaimyno algoritmas. Antru atveju naudojamas maršrutas, gautas vartotojui pažymėjus miestus.Toks maršrutasgali būti sąlyginai pavadintas pseudo atsitiktiniu. Beje abiejų modifikacijų sudėtingumo iš anksto įvertinti neįmanoma.

Iteracijų skaičiaus atžvilgiu visą laiką daugiausiai iteracijų atlikdavo pasikartojančio kaimyno algoritmas. Lankų pakeitimo metodas, naudojantis pasikartojančio kaimyno metodą, atlikdavo šiek tiek daugiau iteracijų, nei pasikartojančio kaimyno algoritmas, net ir tuo atveju, kai visi metodai duodavo vienodą rezultatą maršruto ir distancijos prasme. Lankų pakeitimo metodo naudojančio, pseudo atsitiktinį pradinį maršrutą, iteracijų skaičius priklauso nuo to kaip vartotojas sudėlioja miestus. Kuo pradinis maršrutas būdavo optimalesnis, tuo mažiau pakeitimų atlikdavo lankų pakeitimo metodas. Pasikartojančio kaimyno algoritmas dažniausiai atlikdavo mažiausiai iteracijų, išskyrus tuos atvejus, jei vartotojas pakankamai optimaliai sudėliodavo miestus (optimalus eiliškumas) ir pasirinkdavo lankų pakeitimo metodą, naudojantį pradinį maršrutą pagal tai, kaip vartotojas sužymėjo miestus.

Distancijos atžvilgiu artimiausio kaimyno metodas duodavo prasčiausią rezultatą (išskyrus tuos atvejus, kai visų metodų rezultatai sutapdavo). Dažniausiai geriausią rezultatą duoda lankų pakeitimo metodas. (itin retais atvejais pasikartojančio artimiausio kaimyno metodas).

Koks skirtumas tarp lankų pakeitimo metodo dviejų modifikacijų? Kuo daugiau taškų (miestų) tuo mažiau iteracijų atlikdavo šio algoritmo modifikacija su kaip pradinį maršrutą imanti pasikartojančio kaimyno metodo rezultatą. Beje kas įdomiausia, kai daug taškų išsiskirdavo šių modifikacijų rezultatai net distancijos prasme. Ir dažniausiai geresnį atsakymą duodavo modifikacija su artimiausio kaimyno metodo panaudojimu.

Remiantis stebėjimų duomenimis, galima teigti, kad iš nagrinėtų algoritmų optimaliausias yra lankų pakeitimo metodas, kuris kaip pradinį maršrutą naudoja artimiausio kaimyno metodu gaunamą rezultatą.

Papildoma literatūra:

http://itp.nat.uni-magdeburg.de/~mertens/TSP
http://saturn.vcu.edu/~gasmerom/MAT131/tsp.html
http://serendipity.nofadz.com/hermetic/misc/ts3/ts3demo.htm
http://www.ececs.uc.edu/~mnoschan/sale.html