Saltzaile ibiltariaren problema

Saltzaile ibiltariaren problemaren soluzioa: puntu gorri guztietatik behin bakarrik pasa eta hasierakoan amaitzen den ibilaldirik motzena.

Saltzaile ibiltariaren problema edo Bidaiariaren problema (ingelesez, Travelling Salesperson Problem, TSP), honakoa da: "hirien multzo bat izanik eta haien arteko distantziak ezagunak izanik, zein da hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik laburrena?". Ikerketa operatiboan eta konputazioaren zientzian garrantzia handia duen optimizazio konbinatorioko problema da. "Erosle Ibiltariaren Problema"-ren (Travelling Purchaser Problem, TPP) eta "Ibilgailuak Bideratzearen Problema"-ren (Vehicle Routing Problem, VRP) kasu partikularra da.

Problema 1930ean planteatu zen lehen aldiz eta optimizazio-problema konbinatorioen artean gehien aztertua izan denetako bat da. Haren ebazpenak duen konplexutasun konputazional altuagatik NP-Hard moduan sailkatua izan da. Hori dela eta, optimizazio-konbinatorioko problemen ebazpenerako sortzen diren metodo berrien eraginkortasuna neurtzeko erabiltzen da. Hain aztertua izan denez, ebazpen-metodo (zehatz eta heuristiko) asko ezagutzen dira. Horri esker, gaur egun tamaina handiko Bidaiariaren Problemak ebaztea posiblea da, milaka hirikoak barne. Problemaren bertsio hau NP-osoa da: "hirien multzo bat, haien arteko distantziak eta L luzera jakin bat emanik, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik existitzen al da, gehienez L luzerakoa dena?".

Problemak aplikazio ugari ditu: plangintza-problemak, logistikako problemak, zirkuitu elektrikoen fabrikazioan agertzen direnak, etab. Gainera, problemaren planteamendua pixka bat aldatuta, jakintza-eremu askotan azpiproblema gisa agertu ohi da: DNAren sekuentziazioan, etab. Aplikazio horietan, “hiria” bezeroa izan daiteke, adibidez, edo soldadura-puntua, DNA zatia, etab. eta ibilbiderik laburrena aurkitzeko neurtu beharreko “distantzia” bidaia egiteko behar den denbora, ekoizpenaren kostua, DNA zatien arteko antzekotasuna, etab. Aplikazio askotan, problemaren ohiko murrizketez gain murrizketa gehigarriak egoten dira (mugatuta dauden baliabideak, kontuan hartu beharreko denbora-leihoak, etab.). Halakoetan, berez zaila den problemaren ebazpena are zailagoa gertatzen da.

Historia

Bidaiariaren problemaren jatorria ez dago argi. 1832an saltzaile ibiltarientzat idatzitako gida batean problema aipatzen da eta Alemanian eta Suitzan barrena diseinatutako ibilaldi batzuen adibideak ematen dira, baina ez da problema modu matematikoan aztertzen.^[1]

William Rowan Hamilton

Problemaren formulazio matematikoa W. R. Hamilton matematikari irlandarrak eta Thomas Kirkman matematikari britainiarrak eman zuten XIX. mendean. Hamiltonek "Icosian game" izeneko jokoa asmatu zuen. Puzzle moduko bat zen eta ziklo hamiltondar bat aurkitzea zuen helburu^[2]. Badirudi, matematikariek problemaren forma orokorra lehen aldiz 1930eko hamarkadan aztertu zutela Vienan eta Harvarden. Karl Menger-ek egindako lana aipagarria da, problema definitzeaz gain "indar gordinaren" algoritmo nabaria aztertu baitzuen, ingelesez "brute-force" izenez ezagutzen dena. Gainera, konturatu zen hiri batean hasi eta urrats bakoitzean gertuen dagoen hirira joateak ez duela ziurtatzen hiri guztietatik pasatzen den ibilbide motzena aurkituko denik. Horrela adierazi zuen:

“Mezulariaren problema” (praktikan mezulariei edo bidaiariei sortuko baitzaie problema ebazteko beharra) horrela defini daiteke: puntuen multzo finitu bat izanik eta haietako edozein biren arteko distantzia ezaguna izanik, puntuak konektatuko dituen biderik laburrena aurkitzea. Jakina, saiakera kopuru finitu batean problema ebaztea lortzen da. Hirien permutazio guztiak aztertzeak eskatzen duen saiakera kopurua baino gutxiagotan biderik laburrena aurkitzeko baliagarriak diren erregelak ez dira ezagutzen. Honako erregela jarrai daiteke: hasierako puntutik gertuen dagoen puntura joatea, hortik hurbilen dagoen beste puntura, etab. Hala ere, erregela horrekin, oro har, ez du biderik laburrena aurkitzen.^[3]

1930eko hamarkadan Merrill M. Floode-ek lehen planteamendu matematikoa egin zuen, eskola-autobusen bideratzearen problema aztertzen ari zenean.^[4] Gerora, Princetongo Unibertsitateko Hassler Whitney-k problemarako interesa piztu zuen. Berak problema "48 states problem" moduan izendatu zuen. Julia Robinson-ek 1949an RAND korporaziorako idatzi zuen txosten batean argitaratu zen lehen aldiz problemaren aipamena "Travelling Salesman Problem" izenarekin, "On the Hamiltonian game (a traveling salesman problem)".^[5]^[6]

1950eko eta 1960ko hamarkadetan Santa Monicako RAND korporazioa problemaren ebazpenean aurrerapausoak ematen zituzten zientzialariei sariak eskaintzen hasi zenean, problema gero eta ezagunagoa bihurtu zen Europan eta Estatu Batuetan^[4]. Korporazioko George Dantzig-ek, Delbert Ray Fulkerson-ek eta Selmer M. Johnson-ek ekarpen nabarmenak egin zituzten. Problema lineal oso gisa planteatu zuten eta ebazpenerako ebaki-planoen metodoa garatu zuten. Metodo berri horren bidez 49 hiriko instantzia bat ebaztea lortu zuten, hiriak konektatzen zituen ibilbidea osatu zuten eta frogatu zuten ibilbide hori baino motzagorik ez dela existitzen. Haien argitalpena problemaren ikerketarako hazia izan zela esaten da, ebazpen-metodoetan emankorra izan den ikerketa-arlo baten hasiera. Pentsatu zuten ia optimoa den soluzio bat izanik posiblea izango zela soluzio optimoa aurkitzea edo optimaltasuna frogatzea, desberdintza (inekuazio, murrizketa, ebaki-plano) kopuru txiki bat erantsiz. Ideia horretan oinarritu ziren 49 hiriko problema ebazteko, eta konturatu ziren 26 ebaki-plano besterik ez zirela behar. Artikulu horretan Bidaiariaren Problemaren ebazpenerako algoritmorik eman ez zuten arren, bertan argitaratu zituzten ideiak ezinbestekoak izan ziren gerora ebazpen-metodo zehatzak garatzeko. Beste 15 urte behar izan ziren ebaki-plano egokiak aurkitzeko metodo algoritmikoa garatzeko.^[4] Ebaki-planoen metodoaz gain, Dantzigek, Fulkersonek eta Johnsonek adarkatze- eta bornatze-algoritmoak erabili zituzten, historian lehen aldiz, agian.^[4]

1972. urtean, Richard M. Karp-ek frogatu zuen grafo batean ziklo Hamiltondarra aurkitzearen problema NP-osoa dela, eta horrek esan nahi du Saltzaile Ibiltariaren Problema NP-Hard dela. Horrela, Bidaiariaren Problemarako ibilbide motzena aurkitzeak itxuraz zuen zailtasun konputazionalari azalpen matematiko bat ematea lortu zen.

1970eko hamarkadaren amaieran eta 1980ko hasieran aurrerapen handiak lortu ziren, Grötschel-ek, Padberg-ek, Rinaldi-k eta beste ikerlari batzuek ebaki-planoen metodoa eta adarkatze- eta bornatze-algoritmoa erabiliz 2.392 hiriko instantziak ebazteaz lortu zutenean.

1990eko hamarkadan, Applegate-k, Bixby-k, Chvátal-ek eta Cook-ek "Concorde" programa garatu zuten eta hura erabiliz problema asko ebaztea lortu zen. 1991ean Gerhard Reineltek "TSPLIB, A Traveling Salesman Problem Library" izeneko liburutegia argitaratu zuen. Zailtasun-maila desberdineko problemen bilduma bat da eta ikerketa-talde askok probarako erabiltzen dituzte, haien metodoekin lortutako emaitzak beste ikerlariek lortutakoekin alderatzeko.

2006an, Cook-ek eta beste ikerlari batzuek mikrotxipen diseinuaren problematik sortutako 85.900 hiriko instantzia ebaztea lortu zuten, ebaztea lortu den TSPLIB liburutegiko instantziarik luzeena. Milioika hiriko problemetarako, hirien arteko ibilbide bat aurkitzen duten metodoak badaude, baina ez da bermatzen hirien arteko bide motzena izango denik.^[7]

Sarrera

Problema konbinatorioa

Saltzaile ibiltariaren problema optimizazio konbinatorioko problema bat da. $n$ hiriren arteko distantziak izanik, hiri guztietatik pasa eta hasierakoan amaitzen den biderik laburrena aurkitu behar da. Hiri guztietatik pasatzen diren ibilbide asko daude. Zenbat diren kontatzeko, konbinatoria erabil daiteke: $n$ elementuren ordenazio posible guztiak $n$ -ren permutazioak dira. Optimizazio problema bat da, guztien artetik optimoa aurkitu nahi delako, kasu honetan, ibilbiderik motzena. $n$ -ren balioa handitzen bada, aukera posibleen kopurua asko hazten da.

Adibidez, 3 hiriko saltzaile ibiltariaren probleman 6 ibilbide daude: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Hiru elementuren permutazioak dira, hau da, elementuen ordenazio posible guztiak. Bidaiariaren probleman, (1, 2, 3) permutazioarekin zera adierazten da: bidea 1 hirian hasten da, ondoren 2 hirira doa, gero 3 hirira eta 1 hirian amaitzen da. Permutazio kopurua $n$ -ren faktoriala da, normalean n! ikurraz adierazten dena. Hirien kopurua handitzean, ordenazio kopurua asko hazten da. 3!=6 da, 10!=3628800, 100!=9.33 × 10¹⁵⁷.

Kopuru hori murriztu daiteke, bidea hasi eta bukatu hiri berean egiten denez eta abiapuntua zein den adierazten ez denez, (1, 2, 3), (2, 3, 1) eta (3, 1, 2) permutazioek bide bera adierazten dute: 1tik 2ra, 2tik 3ra eta 3tik 1era. Gauza bera gertatzen da beste hiru permutazioekin, hirien arteko ibilbide bera adierazten dute: (1, 3, 2), (3, 2, 1), (2, 1, 3). Hortaz, berez hiru hiriren artean 2 ibilbide desberdin besterik ez daudela esan daiteke. Ibilbide kopuruaren kontaketa murrizten da, aukera posible guztiak zati $n$ , hau da, $n$ !/ $n$ = ( $n$ -1)! ibilbide dira. $n$ =3ren kasuan, 2!=2 ibilbide.

Gainera, saltzaile ibiltariaren probleman bidaiaria zein norabidetan mugitzen den ez du axola, hau da, 1tik 2ra, 2tik 3ra eta 3tik 1era joatea edo 3tik 2ra, 2tik 1era eta 1etik 3ra joatea ibilbide bera egitea dela interpretatzen da. Horrek aztertu beharreko ibilbideen kopurua erdira murrizten du. Beraz, ( $n$ -1)!/2 ibilbide posible hartu behar dira kontuan.

$n$ =10 hiriko probleman, (10-1)!/2=181.440 ibilbide desberdin daude
$n$ =30 hiriko probleman, (30-1)!/2=4.42 × 10³⁰ ibilbide baino gehiago daude. Segundoko milioi bat ibilbide kalkulatzen dituen ordenagailuak 10¹⁷ urte beharko lituzke ebazteko. Bestela esanda, unibertsoaren sorreraren hasieran kalkulatu izan balitz (duela 13.400 milioi urte inguru) kalkulua oraindik amaitu gabe egongo litzateke.

Ikus daitekeenez, problemari gehitzen zaion hiri bakoitzeko, ibilbide kopurua $n$ faktoreaz biderkatzen da, eta bide motzenaren problemaren ebazpena modu faktorialean hazten da. Horregatik, esaten da problema NP-osoa dela.

Grafo-adierazpena

4 hiriko Saltzaile Ibiltariaren problema baten grafo-adierazpena, grafo haztatu ez-zuzendu eta simetriko baten bidez

Saltzaile Ibiltariaren Problema grafo haztatu ez-zuzendu gisa adieraz daiteke, non grafoko erpinak hiriak diren, ertzak hirien arteko bideak diren eta ertzen pisuak (edo kostuak) bideen distantziak diren. Grafoko ertzek noranzkorik ez badute, hau da, bi noranzkoetan zeharka badaitezke, ez-zuzendua dela esaten da. Minimizazio-problema bat da, erpin guztiak behin bakarrik zeharkatu eta hasierako erpinean amaitzen den distantzia minimoko ibilaldia bilatzen delako.

Problemaren ohiko planteamenduan, eredua grafo oso bat da, hau da, erpin-pare guztiak daude konektatuta ertzen bidez. Problema partikular batean bi hiriren artean biderik ez badago eta grafo oso baten bidez adierazi nahi bada, bi hiri horien artean pisu handia esleitua duen ertz bat jar daiteke, bi hiri horiek haien artean oso urruti daudela adierazi nahiko balitz bezala. Horrela, grafo osoetarako ebazpen-metodoak aplikatu ahal izango dira. Pisua nahiko handia bada, metodoak aurkituko duen ibilbide motzena ez da bi hiri horien artetik pasako, berez existitzen ez den bidetik ez da pasako, eta ez da arazorik sortuko.

Saltzaile ibiltariaren problema matrize baten bidez ere adieraz daiteke, grafoei lotutakoauzokidetasun-matrizeen bidez.

Simetria

Hirien arteko distantzia bi noranzkoetan berdina bada, Saltzaile ibiltariaren problema simetrikoa dela esaten da eta grafo ez-zuzendu baten bidez adierazten da. Horrek aztertu beharreko ibilbideen kopurua erdira murrizten du, ibilaldia noranzko batean egitea edo kontrakoan egitea gauza bera dela ulertzen delako. Problema auzokidetasun-matrize baten bidez adieraziz gero, hura adierazten duen matrizea simetrikoa izango da.

Bidaiariaren problema asimetrikoa izan daiteke, hau da, gerta daiteke bi hiriren artean bidea egotea noranzko batean baina ez egotea kontrako noranzkoan, edo distantziak desberdinak izatea noranzko bakoitzean. Halako problemak grafo zuzenduen bidez adierazten dira eta ertzak gezien bidez ematen dira. Zirkulazio-istripuak, noranzko bakarreko kaleak edo abiatze- eta lehorreratze-kostu desberdinak dituzten aire-tarifek, adibidez, problemaren simetria hausten dute.

Erlazionatutako problemak

Saltzaile ibiltariaren problemarekin erlazioa duten hainbat problema daude. Hona hemen batzuk:

Grafoen teorian, bidaiariaren problema ebaztea grafo oso eta haztatu batean (erpinak hiriak dira, ertzak bideak dira eta kostuak distantziak dira), kostu minimoko ziklo hamiltondarra aurkitzea da. Ibilbidea ixteko hasierako hirira itzuli behar izateak ez du aldatzen problemaren konplexutasun konputazionala eta ondorioz, grafoan bide hamiltondar bat aurkitzearen problemak konplexutasun bera du.

"Bidaiariaren Problema Botila-lepoduna" (ingelesez, Bottleneck, TSP): Grafo oso eta haztatu batean kostu handieneko ertzaren pisua minimizatzen duen ziklo hamiltondarra aurkitu behar da. Problema horrek garrantzi handiko aplikazioak ditu, garraioaren arloan eta logistikan, autobusek kale estuak edo trafiko handienekoak ekiditeko, adibidez. Beste aplikazio klasiko bat zirkuitu inprimatuen fabrikazioa da (ingelesez, printed circuit board, PCB). Osagaiak bertan kokatzeko plaka zulatu behar da eta zulagailuaren ibilbidea planifikatu behar da. Halako zulagailu edo robotetan bidaiariaren problema aplikatzen denean, “hiriak” egin beharreko zuloak dira (tamaina desberdinekoak izan daitezke), eta “kostuak” zulo bat egitetik bestera pasatzeak eskatzen duen berrantolaketa, denbora barne. Azken batean, makina batean hainbat lanen sekuentziazioa optimizatzearen problema da^[8]

"Saltzaile ibiltariaren problema orokortua" edo "Politikari Bidaiariaren Problema". Problemaren planteamendu orokortuan, “hiri” bat edo gehiago dituzten “estatuak” daude eta bidaiariak bere ibilbidean “estatu” bakoitzeko hiri bat bisitatu behar du. Planteamendu honek ere aplikazioak ditu erdieroaleen fabrikazioan, zulagailuaren ibilbidearen planifikazioan (ikus USPTO patentea, 7054798 zk.). Harrigarria badirudi ere, Behzad-ek eta Modarres-ek frogatu zuten problemaren planteamendu orokortua hiri kopuru bera duen bidaiariaren problema estandar bihur daitekeela, hirien arteko distantzien matrizea aldatuz.

"Ordenazio Sekuentzialaren Problema" bidaiariaren problemaren antzekoa da, baina hirien artean dauden lehentasun-erlazioak (hiri bat bisitatu aurretik zein beste hiri bisitatu behar diren) ere kontuan hartu behar dira.
Google-i sortzen zaion problema bat hau da: nola bideratu datuak datu-prozesaketarako nodoen artean. Kontuan izan behar da, datuak nodoen artean transferitzeko behar den denbora desberdina izan daitekeela, baita nodoen kalkulu-ahalmena eta biltegiratze-ahalmena ere. Horren arabera, ibilbideak aldatu egiten dira eta datuak nodoetara bideratzearen problema zailagoa gertatzen da.

"Erosle Ibiltariaren Problema" (ingelesez, Travelling Purchaser Problem, TPP). Erosle batek produktu batzuk erosi behar ditu. Produktu horiek hainbat hiritan eros daitezke, baina hiri guztiek ez dituzte produktu berak eskaintzen. Gainera, produktu berak hiri desberdinetan prezio desberdinak izan ditzake. Hirien azpimultzo batetik pasatzen den ibilbidea aurkitzea da helburua, ibilbideko hirietan erosi beharreko produktu guztiak erostea posiblea dela bermatuz eta kostu totala (bidaiarena + erosketarena) minimizatuz.

↑ "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (Bidaiaria — nolakoa izan behar duen eta zer egin behar lukeen komisioak lortzeko eta negozioetan arrakasta izatea bermatzeko —lehengo merkataritza-bide baten bidez—)
↑ Hamilton eta Kirkmanen lan goiztiarrari buruzko eztabaida aurki daiteke Graph Theory-n (1736-1936)
↑ Schrijver (2005) eta euskerara itzulia. Jatorrizkoa alemanez: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
↑ ^a ^b ^c ^d ISBN 978-0471904137..
↑ .
↑ A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in Txantiloi:Harvp.
↑ doi:10.1016/j.ejor.2010.09.010...
↑ Hu, Bin; Raidl, Günther R.. (2008-09). «Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem» 2008 Eighth International Conference on Hybrid Intelligent Systems (IEEE) doi:10.1109/his.2008.30. (Noiz kontsultatua: 2023-03-27).

[1] "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (Bidaiaria — nolakoa izan behar duen eta zer egin behar lukeen komisioak lortzeko eta negozioetan arrakasta izatea bermatzeko —lehengo merkataritza-bide baten bidez—)

[2] Hamilton eta Kirkmanen lan goiztiarrari buruzko eztabaida aurki daiteke Graph Theory-n (1736-1936)

[3] Schrijver (2005) eta euskerara itzulia. Jatorrizkoa alemanez: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."

[Wiley-4] ISBN 978-0471904137..

[Robinson1949-5] .

[Schrijver2005-6] A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in Txantiloi:Harvp.

[rggo-7] :10.1016/j.ejor.2010.09.010...

[8] Hu, Bin; Raidl, Günther R.. (2008-09). «Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem» 2008 Eighth International Conference on Hybrid Intelligent Systems (IEEE) doi:10.1109/his.2008.30. (Noiz kontsultatua: 2023-03-27).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Lankide:NaroaIpar/Proba orria

Eduki-taula