Saltzaile ibiltariaren problema-en iturria ikusi

[[Fitxategi:GLPK solution of a travelling salesman problem.svg|thumb|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?". [[Ikerkuntza eragilea|Ikerketa operatiboan]] eta [[Konputazioaren zientziak|konputazioaren zientzian]] garrantzia handia duen [[Optimizazio (matematika)|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 konputazionalaren teoria|konplexutasun konputazional]] altuagatik [[P vs NP problema|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 [[heuristika|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|plangintza-problemak]], [[logistika|logistikako problemak]], [[Zirkuitu elektriko|zirkuitu elektrikoen]] fabrikazioan agertzen direnak, etab. Gainera, problemaren planteamendua pixka bat aldatuta, jakintza-eremu askotan azpiproblema gisa agertu ohi da: [[DNA sekuentziazio|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.<ref>"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—)</ref>[[Fitxategi:William Rowan Hamilton painting.jpg|thumb|William Rowan Hamilton]]Problemaren formulazio matematikoa [[William Rowan Hamilton|W. R. Hamilton]] matematikari irlandarrak eta Thomas Kirkman matematikari britainiarrak eman zuten [[XIX. mendea|XIX. mendean]]. Hamiltonek "''Icosian game"'' izeneko jokoa asmatu zuen. Puzzle moduko bat zen eta [[Grafo teoria#Zikloak eta bide hamiltondarrak|ziklo hamiltondar]] bat aurkitzea zuen helburu<ref>Hamilton eta Kirkmanen lan goiztiarrari buruzko eztabaida aurki daiteke Graph Theory-n (1736-1936)</ref>. Badirudi, matematikariek problemaren forma orokorra lehen aldiz [[1930eko hamarkada|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:
<blockquote>“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.<ref>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."</ref></blockquote>[[1930eko hamarkada|1930eko hamarkadan]] Merrill M. Floode-ek lehen planteamendu matematikoa egin zuen, eskola-autobusen bideratzearen problema aztertzen ari zenean.<ref name="Wiley">{{Cite book|url={{google books |plainurl=y |id=qbFlMwEACAAJ}}|title=The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization|last=Lawler|first=E. L.|date=1985|publisher=John Wiley & sons|isbn=978-0471904137|edition=Repr. with corrections.}}</ref> Gerora, [[Princetongo Unibertsitatea|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)".<ref name="Robinson1949">{{cite journal |last1=Robinson |first1=Julia |title=On the Hamiltonian game (a traveling salesman problem) |date=5 December 1949 |issue=RM-303 |url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0204961 |archive-url=https://web.archive.org/web/20200629071813/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0204961 |url-status=dead |archive-date=29 June 2020 |access-date=2 May 2020 |publisher=The RAND Corporation |journal=Project RAND |location=Santa Monica, CA |language=en}}</ref><ref name="Schrijver2005">A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in {{harvp|Schrijver|2005}}.</ref>

[[1950eko hamarkada|1950eko]] eta [[1960ko hamarkada|1960ko hamarkadetan]] [[Santa Monica (Kalifornia)|Santa Monicako]] RAND korporazioa problemaren ebazpenean aurrerapausoak ematen zituzten zientzialariei sariak eskaintzen hasi zenean, problema gero eta ezagunagoa bihurtu zen Europan eta Estatu Batuetan<ref name="Wiley"/>. 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 [[ebaketa-planoaren metodoa|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.<ref name="Wiley"/> Ebaki-planoen metodoaz gain, Dantzigek, Fulkersonek eta Johnsonek [[adarkatze- eta bornatze-algoritmoak]] erabili zituzten, historian lehen aldiz, agian.<ref name="Wiley"/>

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

[[1970eko hamarkada|1970eko hamarkadaren]] amaieran eta [[1980ko hamarkada|1980]]<nowiki/>ko 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 hamarkada|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 [[Txip|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.<ref name="rggo">{{citation
 | last1 = Rego | first1 = César
 | last2 = Gamboa | first2 = Dorabela
 | last3 = Glover | first3 = Fred
 | last4 = Osterman | first4 = Colin
 | doi = 10.1016/j.ejor.2010.09.010
 | issue = 3
 | journal = [[European Journal of Operational Research]]
 | mr = 2774420
 | pages = 427–441
 | title = Traveling salesman problem heuristics: leading methods, implementations and latest advances
 | volume = 211
 | year = 2011}}.</ref>

== Sarrera ==

=== Problema konbinatorioa ===
Saltzaile ibiltariaren problema optimizazio konbinatorioko problema bat da. <math>n</math> 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: <math>n</math> elementuren ordenazio posible guztiak <math>n</math>-ren permutazioak dira. [[Optimizazio (matematika)|Optimizazio]] problema bat da, guztien artetik optimoa aurkitu nahi delako, kasu honetan, ibilbiderik motzena. <math>n</math>-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 [[Permutazio|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 {{Math|''n''}}-ren [[Faktorial|faktoriala]] da, normalean n! ikurraz adierazten dena. Hirien kopurua handitzean, ordenazio kopurua asko hazten da. 3!=6 da, 10!=3628800, 100!=9.33 × 10<sup>157</sup>.

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 <math>n</math>, hau da, <math>n</math>!/<math>n</math>= (<math>n</math>-1)! ibilbide dira. <math>n</math>=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, (<math>n</math>-1)!/2 ibilbide posible hartu behar dira kontuan.

* <math>n</math>=10 hiriko probleman, (10-1)!/2=181.440 ibilbide desberdin daude
* <math>n</math>=30 hiriko probleman, (30-1)!/2=4.42 × 10<sup>30</sup> ibilbide baino gehiago daude. Segundoko milioi bat ibilbide kalkulatzen dituen ordenagailuak 10<sup>17</sup> 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 <math>n</math> faktoreaz biderkatzen da, eta bide motzenaren problemaren ebazpena modu faktorialean hazten da. Horregatik, esaten da problema [[NPproblema osoen|NP-osoa]] dela.

=== Grafo-adierazpena ===
[[Fitxategi:Weighted K4.svg|thumb|4 hiriko Saltzaile Ibiltariaren problema baten grafo-adierazpena, grafo haztatu ez-zuzendu eta simetriko baten bidez]]
Saltzaile Ibiltariaren Problema [[grafo]] [[Haztapen (prozedura kuantitatiboa)|haztatu]] ez-zuzendu gisa adieraz daiteke, non grafoko [[Erpin (grafo teoria)|erpinak]] hiriak diren, [[Ertz (grafo teoria)|ertzak]] hirien arteko bideak diren eta ertzen [[Haztapen (prozedura kuantitatiboa)|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 lotutako[[Auzokidetasun-matrize|auzokidetasun-matrizeen]] bidez. 

=== Simetria ===
Hirien arteko distantzia bi noranzkoetan berdina bada, Saltzaile ibiltariaren problema '''simetrikoa''' dela esaten da eta [[Grafo|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 [[Matrize simetriko|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. [[Trafiko-istripu|Zirkulazio-istripuak]], [[Zirkulazio-noranzkoaren arau|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:
* [[Grafo teoria|Grafoen teorian]], bidaiariaren problema ebaztea [[grafo oso]] eta [[Haztapen (prozedura kuantitatiboa)|haztatu]] batean (erpinak hiriak dira, ertzak bideak dira eta kostuak distantziak dira), kostu minimoko [[Grafo teoria#Zikloak eta bide hamiltondarrak|ziklo hamiltondarra]] aurkitzea da. Ibilbidea ixteko hasierako hirira itzuli behar izateak ez du aldatzen problemaren [[Konplexutasun konputazionalaren teoria|konplexutasun konputazionala]] eta ondorioz, grafoan [[Grafo teoria#Zikloak eta bide hamiltondarrak|bide hamiltondar]] bat aurkitzearen problemak konplexutasun bera du.

* "Bidaiariaren Problema Botila-lepoduna"  (ingelesez, ''Bottleneck, TSP''): [[Grafo oso]] eta [[Haztapen (prozedura kuantitatiboa)|haztatu]] batean kostu handieneko ertzaren pisua minimizatzen duen [[Grafo teoria#Zikloak eta bide hamiltondarrak|ziklo hamiltondarra]] aurkitu behar da. Problema horrek garrantzi handiko aplikazioak ditu, garraioaren arloan eta [[Logistika|logistikan]], autobusek kale estuak edo trafiko handienekoak ekiditeko, adibidez. Beste aplikazio klasiko bat [[Zirkuitu inprimatu|zirkuitu inprimatuen]] fabrikazioa da (ingelesez, ''printed circuit board'', PCB). Osagaiak bertan kokatzeko plaka zulatu behar da eta [[Zulagailu|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<ref>{{Erreferentzia|izena=Bin|abizena=Hu|izenburua=Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem|argitaletxea=IEEE|abizena2=Raidl|izena2=Günther R.|data=2008-09|url=http://dx.doi.org/10.1109/his.2008.30|aldizkaria=2008 Eighth International Conference on Hybrid Intelligent Systems|doi=10.1109/his.2008.30|sartze-data=2023-03-27}}</ref>

* "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.
== Problemaren formulazioa ==
Saltzaile ibiltariaren problema programazio lineal osoko problema gisa formula daiteke. Hiriak 1-etik <math>n</math>-rako zenbakien bidez izendatzen dira eta <math>i</math> hiritik <math>j</math> hirira dagoen distantzia (joateak eragiten duen kostua) <math>c_{ij}</math> notazioaz adierazten da, <math>i,j \in \{ 1,\cdots, n \}</math> izanik.  

Erabaki-aldagaiak bitarrak dira, hau da, 0 (zero) edo 1 (bat) balioetara mugatzen dira, eta horrela definitzen dira: 

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>x_{ij} = \begin{cases} 1 & \text{baldin bidaiaria} \ i \ \text{hiritik} \ j \ \text{hirira badoa} \\ 0 & bestela \end{cases}</math>
</div>

Horrela, <math>x_{ij}=1</math> bada, ibilbidea <math>i</math> hiritik <math>j</math> hirira doala esan nahi du. Problemaren helburua kostu txikieneko ibilbidea aurkitzea denez, helburu-funtzioa horrela definitzen da:

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>min \ z = \sum_{i=1}^n \sum_{j \neq i,j=1}^n c_{ij}x_{ij}</math>
</div>

Bidaiariak egingo duen ibilbidea hiri guztietatik pasa behar da, eta bakoitzetik behin bakarrik. Hori hala izan dadin, hainbat murrizketa gehitu behar dira formulazioan. Alde batetik, bidaiaria <math>j</math> hiri bakoitzera <math>i</math> hiri bakar batetik joango dela ziurtatzeko, <math>j</math> bakoitzerako <math>x_{ij}</math> aldagaien batura 1 dela adierazten duen murrizketa idazten da. Bidaiariak <math>n</math> hiri bisitatu behar dituenez, <math>j</math>-ren balio bakoitzerako (<math>j=1,\dots, n</math>) horrelako murrizketa bat dago:

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>\sum_{i=1, i \neq j}^n x_{ij} = 1 </math>
</div>
Bestalde, ibilbidea <math>i</math> hiri bakoitzetik <math>j</math> hiri bakar batera joango dela ziurtatzeko, <math>i</math> bakoitzerako <math>x_{ij}</math> aldagaien batura 1 dela adierazten duen murrizketa idazten da. Bidaiaria <math>n</math> hirietatik irtengo denez, <math>i</math>-ren balio bakoitzerako (<math>i=1,\dots, n</math>) horrelako murrizketa bat dago:
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>\sum_{j=1, j \neq i}^n x_{ij} = 1 </math>
</div>

Murrizketa horiek ziurtatzen dute bidaiaria hiri batean dagoenean ez dela beste bi hiritara joango, edo hiri batera ez dela beste bi hirietatik iritsiko. Funtzio eta ekuazio horiek guztiak linealak direnez eta erabaki aldagaiak osoak (bitarrak) direnez, programazio lineal osoko formulazioa lortzen da.

Hala ere, murrizketa horiek ez dira nahikoak saltzaile ibiltariaren problema adierazteko, ez delako bermatzen hiri guztiak ibilaldi bakar batean bisitatuko direnik. Adibide gisa, hurrengo taulan <math>n=4</math> hirirako soluzio bat aurkezten da: <math>x_{12}=1</math>, <math>x_{21}=1</math>, <math>x_{34}=1</math>, <math>x_{43}=1</math>, eta gainerako aldagai guztiak zero. Taulan ikusten den bezala, 1eko bakarra dago zutabeetan (hiri bakoitzera beste bakar batetik iristen da) eta 1eko bakarra errenkadetan (hirietatik beste hiri bakar batera doa). Planteatu diren murrizketa guztiak betetzen ditu, baina ez du ibilaldi bakar bat osatzen, bi azpi-ziklo baizik: 1etik 2ra eta 2tik 1era (azpi-ziklo bat), 3tik 4ra eta 4tik 3ra (beste azpi-ziklo bat). Hortaz, soluzio horrek ez du bidaiariaren problema ebazten.
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
{| class="wikitable"
|+<math>n=4 \ \text{hiri}, \ x_{ij} \ \text{soluzio bat} </math>
!
!<math>1</math>
!<math>2</math>
!<math>3</math>
!<math>4</math>
|-
|<math>1</math>
|<math>0</math>
|<math>1</math>
|<math>0</math>
|<math>0</math>
|-
|<math>2</math>
|<math>1</math>
|<math>0</math>
|<math>0</math>
|<math>0</math>
|-
|<math>3</math>
|<math>0</math>
|<math>0</math>
|<math>0</math>
|<math>1</math>
|-
|<math>4</math>
|<math>0</math>
|<math>0</math>
|<math>1</math>
|<math>0</math>
|}
</div>

Problemaren soluzio ez diren horrelako kasuak baztertzeko, beste murrizketa bat gehitu behar da formulazio matematikoan. Planteamendu desberdinak egin izan diren arren, honako biak nabarmentzen dira: "Miller–Tucker–Zemlin (MTZ)" formulazioa eta "Dantzig–Fulkerson–Johnson (DFJ)" formulazioa. Bigarrena sendoagoa bada ere, lehenengoa hainbat egoeratan erabilgarria da.  

=== Miller–Tucker–Zemlin formulazioa (MTZ) ===
MTZ formulazioan <math>x_{ij}</math> aldagaiak erabiltzeaz gain, honako <math>u_i</math> aldagaiak definitzen dira hiriak zein ordenatan bisitatuko diren kontrolatzeko: 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>u_{i} = i \ \text{hirira zenbat urratsetan iritsiko den}, i=2,\cdots , n</math>
</div>

Ibilbidea 1 hirian hasten dela suposa daiteke, orokortasunik galdu gabe. Horregatik, <math>u_i</math> aldagaiaren azpi-indizeak ez du 1 balioa hartzen. Aldagaietan urrats kopurua adierazten denez, <math> u_i \in \{ 1, \dots, n-1 \}</math> balioak har ditzake. Izan ere, <math>n</math> hiriko ibilbidea osatzeko <math>n-1</math> urrats eman behar dira eta horri jakina den azken urrats bat gehitu: hasierako hirira itzultzea, 1 hirira, alegia.

<math>u_j > u_i</math> desberdintzak zera adierazten du: <math>j</math> hirira iristeko eman behar den urrats kopurua <math>i</math> hirira iristeko eman behar dena baino handiagoa da. Horrek hirien artean ordena bat finkatzen du. <math>x_{ij}</math> aldagaiak <math>u_i</math> eta <math>u_j</math> aldagaiekin erlazionatu behar dira, ibilaldi bakar batean hiri guztiak zeharkatzen direla ziurtatzeko, hau da, azpi-zikloak ekiditeko. Hori honako murrizketarekin lortzen da: 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>u_i - u_j + (n-1)x_{ij} \leq n-2, </math>
</div>

<math> i,j = 2,\dots,n, \ i \neq j </math> izanik. Egiazta daiteke <math>x_{ij}=1</math> denean <math>u_j \geq u_i +1</math> betetzen dela. Koherentea da esatea ibilaldia <math>i</math> hiritik <math>j</math> hirira doala eta <math>j</math> hirira iristeko behar den urrats kopurua <math>i</math> hirira iristeko behar dena baino handiagoa dela. Bestalde, <math>x_{ij}=0</math> denean <math>u_j +n-1 \geq u_i+1</math> erlazioa lortzen da, hau da, <math>u_i</math> eta <math>u_j</math> aldagaien artean ez da murrizketarik ezartzen, <math>u_j +n-1 \geq u_i+1</math> beti betetzen delako (kasurik okerrenean <math>u_j = 1</math> eta <math>u_i = n-1</math> izanik, erlazioa <math>n = n</math> izango da). Gainera, egiazta daiteke ibilbidea azpi-zikloz osatzen bada, murrizketa horiek kontraesanera eramaten dutela, <math>k</math> luzerako azpi-zikloetarako <math>k(n-1) \leq k(n-2)</math> kontraesera.

Miller-Tucker-Zemlin formulazioaren arabera, eredu lineala bere osotasunean horrela geratzen da: <div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>min \ z = \sum_{i=1}^n \sum_{j \neq i,j=1}^n c_{ij}x_{ij} </math>

<math>\text{hauen mende:} \quad \quad \quad \quad \quad \quad \quad  </math>

<math>\begin{cases}
\displaystyle\sum_{i=1, i \neq j}^n x_{ij} = 1 & \ j = 1,\dots,n; \\
\displaystyle\sum_{j=1, j \neq i}^n x_{ij} = 1 & \ i = 1,\dots,n; \\
u_i - u_j + (n-1)x_{ij} \leq n-2 & \ i,j = 2,\dots,n, \ i \neq j; \\
u_i \in \{ 1, \dots, n-1 \} & i = 2, \dots, n; \\
x_{ij} \in \{ 0,1 \} & i,j = 1, \dots, n.
\end{cases}</math>
</div>

Aurreko adibidearekin segituz, <math>n=4</math> hiri daude, <math>x_{12}=1</math>, <math>x_{21}=1</math>, <math>x_{34}=1</math>, <math>x_{43}=1</math> dira eta gainerakoak zero. Egiazta daiteke MTZ formulazioan erantsitako aldagaien eta murrizketaren eragina.

<math>x_{34}=1 \quad \rightarrow  \quad u_3 - u_4 + (n-1)x_{34} \leq n-2  \quad \rightarrow  \quad u_3 - u_4 + n-1 \leq n-2  \quad \rightarrow   \quad u_4 \geq u_3+1 </math>

<math>x_{34}</math>, <math>u_3</math> eta <math>u_4</math> aldagaien artean erlazio koherentea ezartzen da. 

<math>x_{23}=0 \quad \rightarrow  \quad u_2 - u_3 + (n-1)x_{23} \leq n-2  \quad \rightarrow   \quad u_2 \leq u_3+(n-2)</math>

<math>n=4</math> izanik, kasurik okerrenean <math>u_3=1</math> bada <math>u_2\leq 3</math> geratzen da. Beraz, <math>u_2</math> eta <math>u_3</math> aldagaien balio guztietarako murrizketa betetzen da. Ibilbidea ez doanez 2 hiritik 3ra, ez da haien artean ordenarik ezartzen.  

Bestalde, <math>x_{34}=1</math> eta <math>x_{43}=1</math> azpi-ziklorako kontraesana sortzen da. 

<math>x_{34}=1 \quad \rightarrow  \quad u_3 - u_4 + (n-1)x_{34} \leq n-2, \quad \quad \text{ eta } \quad \quad  x_{43}=1 \quad \rightarrow  \quad u_4 - u_3 + (n-1)x_{43} \leq n-2  </math>

Bi ekuazioak berdintzaren bi ataletan batuz <math>2(n-1) \leq 2(n-2)</math> kontraesana den erlazioa lortzen da (sinplifikatuz, <math>n \leq n-1</math>). Beraz, azpi-zikloak ez dira sortuko.  

=== Dantzig–Fulkerson–Johnson formulazioa (DFJ) ===
DFJ formulazioan "azpi-ibilbideak ezabatzeko murrizketak" (ingelesez, ''subtour elimination constraint'') gehitzen dira. <math>n</math> hiriko bidaiariaren problemarako, <math>Q \subsetneq\{ 1, \dots, n \} </math> [[azpimultzo]] propioak definitzen dira. <math>Q</math> azpimultzoen [[Multzo#Multzo baten kardinala|kardinalak]] (elementu kopuruak) gutxienez bikoa izan behar du, <math>|Q| \geq 2</math>. Sor daitezkeen azpi-ziklo guztiak ezabatzeko, <math>n</math> elementurekin osa daitezkeen halako <math>Q </math> azpimultzo posible guztietarako definitzen diren murrizketak honakoak dira:

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>\sum_{i \in Q} \sum_{j \neq i, j \in Q} x_{ij} \leq |Q|-1 </math>
</div>

[[Inekuazio|Inekuazioaren]] ezkerraldeko bi [[batukari]] horien bidez <math>Q</math> azpi-zikloan dagoen ertz kopurua kontatzen da eta kopuru hori azpi-zikloan dagoen hiri kopurua baino txikiagoa dela ziurtatzen du murrizketak. Horrela lortzen da azpi-zikloak baztertzea eta hiri guztietatik behin igarotzen den ziklo bakar batez osatutako ibilaldia aurkitzea.  

Dantzig–Fulkerson–Johnson formulazioa honakoa da: 

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
<math>min \ z = \sum_{i=1}^n \sum_{j \neq i,j=1}^n c_{ij}x_{ij} </math>

<math>\text{hauen mende:} \quad \quad \quad \quad \quad \quad \quad  </math>

<math>\begin{cases}
\displaystyle\sum_{i=1, i \neq j}^n x_{ij} = 1 & \ j = 1,\dots,n; \\
\displaystyle\sum_{j=1, j \neq i}^n x_{ij} = 1 & \ i = 1,\dots,n; \\
\displaystyle\sum_{i \in Q} \sum_{j \neq i, j \in Q} x_{ij} \leq |Q|-1 & \forall Q \subsetneq\{ 1, \dots, n \}, \ |Q| \geq 2 \\
x_{ij} \in \{ 0,1 \} & i,j = 1, \dots, n.
\end{cases}</math>
</div>

<math>n</math> handitzearekin batera, ereduari gehitzen zaion murrizketa kopurua izugarri hazten da. Formulazioa proposatu zuten ikerlariek ikusi zuten guztiak gehitzea ez dela beharrezkoa, formulazioa sinplifikatuz.

Aurreko adibidearekin segituz, <math>n=4</math> izanik, <math>Q \subsetneq\{ 1, 2,3,4 \} </math>, <math>|Q| \geq 2</math> [[Azpimultzo#Azpimultzo propioa|azpimultzo propioak]] definitu behar dira. Hainbat aukera daude, bi hirik osatutako azpimultzoak (<math>Q =\{ 1, 2 \} </math>, adibidez) edo hiru hirik osatutakoak (<math>Q =\{ 2,3,4 \} </math>, adibidez). Adibidean bi azpi-zikloz osatutako <math>x_{12}=1</math>, <math>x_{21}=1</math>, <math>x_{34}=1</math>, <math>x_{43}=1</math> soluziorako, har dezagun <math>Q =\{ 3, 4 \} </math> azpimultzo propioa, non <math>|Q| = 2</math> den. 3 eta 4 hirien arteko azpi-zikloan, egiazta daiteke DFJ formulazioan gehitutako murrizketak sortzen duen eragina:

<math>\sum_{i \in Q} \sum_{j \neq i, j \in Q} x_{ij} \leq |Q|-1 \quad \quad \rightarrow \quad \quad x_{34}+x_{43} \leq 2-1 \quad \quad \rightarrow \quad \quad 2 \leq 1</math>

Azpi-zikloan 2 ertz daude (3tik 4ra eta 4tik 3ra) eta 2 erpin (3a eta 4a). Dagoen ertz kopurua erpin kopurua baino txikiagoa izatera behartzeak kontraesanera eramaten du, azpi-zikloaren sorrera ekidinez. Azpi-ziklo posible guztiak kontraesanera eramanez, problemaren ebazpenean hiri guztietatik pasatzen den ziklo bakarreko ibilaldia lortuko da. 

== Problemaren ebazpena ==

Bidaiariaren problemaren ebazpenak duen konplexutasunagatik, problema [[P vs NP problema|NP-gogor]] moduan sailkatua izan da. Horrelako problemen soluzio optimoa aurkitzeko ahaleginean, estrategia desberdinak erabili izan dira:

* Algoritmo zehatzak diseinatzea soluzio optimoa aurkitzeko. Tamaina txikiko problemekin gai dira soluzioa aurkitzeko zentzuzko denbora erabiliz.
* Algoritmo [[Heuristika|heuristikoak]] diseinatzea, soluzio optimoaren hurbilketa aurkitzeko gai direnak zentzuzko denbora erabiliz. Tamaina handiko problemen ebazpenean eraginkorrak izan daitezke, baina ez dute bermatzen soluzio optimoa (optimo globala) aurkituko dutenik; optimo lokalak aurkitzen dituzte.
* Problemaren kasu partikularrak (azpiproblemak) bilatzea, non horiek ebazteko algoritmo zehatzak edo metodo heuristiko hobeak aplikatzea posiblea den.

=== Algoritmo zehatzak ===
[[Fitxategi:Bruteforce.gif|thumb|609x609px|n=7 hiriko instantzia baten ebazpena indar gordinaren algoritmoa erabiliz. Permutazio kopurua n!=7!= 5040 da.  (7-1)!/2 = 360 ibilbide desberdin aztertzen dira.]]
Lehen begiratuan, problema ebazteko metodo zuzenena ibilbideen konbinaketa guztiak aztertzea dela pentsa daiteke, hau da, hirien [[permutazio]] (ordenazio) desberdin guztiak aztertzea eta haien artean kosturik txikienekoarekin (ibilbide motzenarekin) geratzea. Estrategia horri "indar gordinaren" algoritmoa esaten zaio (ingelesez ''"brute-force"''), aukera guztiak aztertzen direlako. Hortaz, soluzio optimoa aurkitzea bermatzen da, baina  [[Konplexutasun konputazionalaren teoria|konplexutasun-konputazionalaren]] ikuspegitik bideraezina da, <math>n</math> hiriko problema ebazteko algoritmoak <math>O(n!)</math> ordeneko konplexutasuna duelako. Esaterako, 20 hiriko problema bat indar gordinaz ebaztea praktikan ezinezkoa litzateke, zentzuzko denboran soluzio optimoa aurkitu nahi bada, behintzat.

Hori kontuan izanik, algoritmo konplexuagoak diseinatu izan dira. Held-Karp algoritmoa, adibidez, [[Programazio dinamiko|programazio dinamikoan]] oinarritzen da eta problema <math>O(n^22^n)</math> denboran ebaztea lortzen da. Antzeko konplexutasun-ordeneko algoritmo zehatzak diseinatu izan dira, baina denbora-muga hori gainditzea zaila gertatzen da. Izan ere, oraindik ez da frogatu  <math>O(1,999^n)</math> konplexutasun-ordena baino txikiagoa duen algoritmo zehatzik existitzen den.
[[Fitxategi:Branchbound.gif|thumb|608x608px|n=7 hiriko instantzia baten ebazpena adarkatze- eta bornatze-algoritmo bat erabiliz. Aztertzen den permutazio kopurua askoz txikiagoa da indar gordinaren algoritmoan baino.]]
Hona hemen bidaiariaren problema ebazteko garatu izan diren beste algoritmo zehatz batzuk:

* Adarkatze- eta bornatze-algoritmoaren hainbat bertsio daude <math>n=40</math> eta <math>n=60</math> hiri arteko bidaiariaren problema ebaztean ondo moldatzen direnak.

* Hobekuntza progresiboko algoritmoek [[Programazio lineal|programazio linealaren]] antzeko teknikak erabiltzen dituzte. <math>n=200</math> hirira arteko problemen ebazpenean ondo dabiltza.
* Badira adarkatze- eta bornatze-algoritmoaren bertsio batzuk eta baita problemarako mozte espezifikoak sortzeko diseinatutako algoritmoak (adarkatze- eta ebakitze-algoritmoak) tamaina handiko instantziak ebaztean ondo funtzionatzen dutenak. Algoritmo horiek erabiliz <math>n=85.900</math> hiriko saltzaile ibiltariaren problemaren instantzia bat ebaztea lortu da.

Algoritmo zehatz horiek bizitza errealeko bidaiariaren problemaren instantziak ebazteko erabili izan dira historian zehar. Adibidez, 2001ean 15.112 hiri alemaniarrez osaturiko problemaren soluzio zehatza aurkitzea lortu zen ebaki-planoen metodoa erabiliz. 2004ean Suediako 24.978 hiriko problema ebatzi zen, 72.500 kilometro inguruko ibilbide bat aurkitu zen eta frogatu zen ibilbide hori baino motzagorik ez dela existitzen.

=== Algoritmo heuristikoak ===
Algoritmo [[Heuristika|heuristikoak]] soluzio optimoaren hurbilketak aurkitzen dituzten algoritmoak dira. Ez dute bermatzen soluzio optimoa (optimo globala) aurkituko denik, eta ondorioz, optimo lokalak ematen dituzte emaitza moduan. Normalean algoritmo horiek tamaina handiko problemak ebazteko erabiltzen dira, optimora iristeko beharko litzatekeen denboragatik metodo zehatzak erabiltzea ezinezkoa gertatzen den kasuetan. Halakoetan, algoritmo heuristikoak erabiltzea eraginkorra izan daiteke.

Azken urteotan soluzio optimora asko hurbiltzen diren algoritmo heuristiko anitz diseinatu dira saltzaile ibiltariaren problema ebazteko. Helburua tamaina handiko instantziekin ahalik eta soluzio onena lortzea da, zentzuzko denbora erabiliz. Ikusi da algoritmo heuristiko modernoak soluzio optimo globaletik <math>\%3</math> inguru besterik ez direla aldentzen. Algoritmo heuristikoen artean, mota desberdinekoak daude.

==== Algoritmo eraikitzaileak (irenskorrak) ====
 [[Fitxategi:Weighted K4.svg|thumb|Auzokide hurbilenaren algoritmoak hasierako hiri desberdinetatik hasita ibilbide desberdinak eraikitzen ditu. Adibidez, A-B-C-D eta bueltan Ara (97ko distantzia) edo C-D-B-A eta bueltan Cra (108koa)]] Algoritmo eraikitzaileek (ingelesez, "''constructive''") soluzioa urratsez urrats eraikitzen dute, normalean urrats bakoitzean aukerarik onena hautatuz eta problemaren ezaugarriak kontuan hartuz, hau da, intuizioa erabiliz. Algoritmo hauei [[algoritmo irenskor]] (ingelesez, "''greedy algorithm"'') ere deitu ohi zaie, soluzioa eraikitzean urrats guztietan aukerarik onena hautatzen dutelako. Eraginkorrak izaten dira soluzio onak aurkitzeko, baina problema espezifiko bakoitzerako diseinatzen direnez, beste problemetara egokitzeko zailak izaten dira.   

Saltzaile ibiltariaren problemarako algoritmo eraikitzaile bat "'''auzokide hurbilenaren algoritmoa'''" da. Algoritmo horretan ibilbidea hasteko hiri bat aukeratzen da, eta hirien arteko distantziak aztertuz, oraindik bisitatua izan ez den eta gertuen dagoen hirira joatea erabakitzen da, urratsez urrats.  [[Fitxategi:Nearestneighbor.gif|thumb|356x356px|Auzokide hurbilenaren algoritmoaren aplikazio dinamikoa 7 hiriko instantzia batean. Hasierako hiriaren arabera, algoritmoak eraikitzen duen soluzioa aldatzen dela ikusten da.]]

Oro har, denbora laburrean soluzio onak lortzen diren arren, ausaz banatutako <math>n</math> hirirentzat, batez beste ibilbide optimoa baino <math>\%25</math> luzeagoak diren ibilbideak lortzen dira. Hala ere, problemaren instantzia berezi batzuetarako ibilbiderik okerrena (luzeena) itzultzen du. Problema simetrikoetan eta asimetrikoetan gerta daiteke hori. 

Auzokide hurbilenaren algoritmoaren aldaerak existitzen dira. Horietako bat "'''zati hurbilenaren eragilea'''" da (ingelesez, "''Nearest Fragment operator''" edo "''NF operator''"). Aldaera horretan, bisitatuak izan ez diren hirien artean hurbil dauden hirien multzoak haien artean konektatzen dira, eta iterazioz iterazio ibilbide motzagoak aurkitzea lortzen da. 

Bi algoritmoak konbina daitezke, hau da, auzokide hurbilenaren algoritmoa aplikatu soluzio bat eraikitzeko eta ondoren zati hurbilenaren eragilea aplikatu soluzio hori hobetzeko. Konplexutasun-ordenari dagokionez, <math>O(n^2)</math> eta <math>O(n^2 \text{log}n)</math> denboran exekutatzen dira, hurrenez hurren.

Beste heuristiko eraikitzaile bat "Match Twice and Stitch" algoritmoa da (euskaraz "Birritan Parekatu eta Josi"). Algoritmo honek hirietatik pasatzen diren ziklo multzoak sortzen ditu eta gero zikloak elkartzen ditu hiri guztietatik pasatzen den ibilbide bat osatzeko.

==== Christofides-Serdyukov algoritmoa ====
Algoritmo hau bidaiariaren problemaren instantzia berezi batzuetan soilik aplika daiteke: [[espazio metriko]] batean kokatzen diren instantzietan bakarrik, hau da, <math>i.</math> hiria <math>H_i</math> izanik, hurrengo propietateak betetzen dituzten instantzietan (informazio gehiagorako, ikus kasu berezien ebazpena): 

* <math>\forall H_i,H_j, \ d(H_i,H_j) \geq 0 \ \text{eta} \ d(H_i,H_j) = 0 \Longleftrightarrow H_i=H_j, \ i,j=1,\dots,n </math>

* <math>\forall H_i, H_j, \ d(H_i,H_j) = d(H_j, H_i), \ i,j=1,\dots,n</math>
* <math>\forall H_i, H_j, H_k,\ \ d(H_i,H_j) \leq d(H_i,H_k) + d(H_k,H_j), \ \ \ i,j=1,\dots,n \ \ \ \rightarrow \ (\mbox{desberdintza triangeluarra}) </math>

Algoritmoak kasurik okerrenean soluzio optimoa baino 1,5  aldiz luzeagoa den ibilbidea bueltatzen duela frogatu da. Hori lortzeko, [[Grafo teoria|grafo teoriako]] emaitzak erabiltzen dira. Izan ere, [[Eulertar grafo|grafo eulertar]] batean zirkuitu eulertar bat aurki daiteke <math>O(n) </math> denboran. Hortaz, saltzaile ibiltariaren instantzia batetik abiatuz grafo eulertar bat osa badaiteke (hiriak erpinak izanik), algoritmoa aplika daiteke zirkuitu eulertarra aurkitzeko, eta ondoren zirkuitutik bidaiariaren problemarako soluzioa aurkitu. Espazio metrikoaren propietateetatik erraz ondoriozta daiteke bidaiariaren problemarako soluzioa ezin dela zirkuitu eulertarra baino luzeagoa izan (desberdintza triangeluarra). Horri esker, soluziorako behe-borne bat kalkula daiteke. Christofides-Serdyukov-en algoritmoak ideia hori erabiltzen du.

==== Bikoteak ordezkatzea (2-opt) ====
[[Fitxategi:Showing a step of the two-opt heuristic.png|thumb|Bikoteak ordezkatzearen teknika: soluzio batean bi ertz ezabatu eta beste bi ertzez ordezkatu. Irudian algoritmoaren iterazio bat ikusten da.]]
Bikoteak ordezkatzearen teknikak (ingelesez, "''pairwise exchange''" edo "''2-opt''") ertz bikoteak ezabatzen ditu eta deskonektatuta geratu diren zatiak beste ertz batzuen bidez konektatzen ditu, iterazioz iterazio ibilbide motzagoak eraikitzen joateko helburuarekin. [[Distantzia]] euklidestarrekin lan egitean, batezbeste Christofides-Serdyukov algoritmoak baino <math>\%5</math> hobeak diren ibilbideak lortzen direla ikusi da. Algoritmo hau eta antzeko beste batzuk asko erabiltzen dira saltzaile ibiltariaren problemaren orokorpena den "Ibilgailuak Bideratzearen Problema" (''Vehicle Routing Problem'', VRP) ebazteko.

Hasierako soluzioa algoritmo irenskor batekin kalkulatzen bada, egin behar den bikoteen ordezkatze kopurua jaisten da eta algoritmoaren eraginkortasuna hobetzen da, haren konplexutasuna <math>O(n)</math> ordenakoa izango delarik. Baina hasierako soluzioa ausaz kalkulatzen bada, algoritmoaren konplexutasuna <math>O(n \ \text{log} n)</math> ordenakoa izango da. Horrela esanda, pentsa daiteke konplexutasunaren maila ez dela asko igotzen, baina algoritmoaren hasierako urratsetan, bereziki, ausaz sortutako soluzio batetik hasteak ertzak 10 aldiz gehiagotan ordezkatzea suposa dezake. 2-opt algoritmoak soluzioen atalik okerrenak (ertzen gurutzaketak dauden puntuak) sakon aztertzen dituelako gertatzen da hori.

==== k-koteak ordezkatzea (k-opt) ====
k-koteak ordezkatzearen algoritmoa edo "''k-opt''" bikoteak ordezkatzearen orokorpen bat da. Izan ere, bi ertz ezabatu eta zatien muturretako erpinak modu desberdinean elkartu ordez, <math>k</math> ertz kenduz egiten da. Beraz, <math>k=2</math> denean, k-koteak ordezkatzearen metodoa bikoteak ordezkatzearen metodo bihurtzen da. k-koteak ordezkatzeko algoritmoen artean, <math>k=3</math> kasua da ezagunena: ''3-opt''. [[Bell Laborategiak|Bell laborategietan]] lanean ari zen Shen Lin-ek proposatu zuen 1965. urtean. 

''k-opt a''lgoritmoa honakoa da:

# Hiri guztiak behin bakarrik zeharkatzen dituen iIbilbide bat emanik, haien artean alboko ez diren <math>k</math> ertz ezabatzen dira.
# Deskonektatuta geratu diren ibilbidearen <math>k</math> zatiak elkartu behar dira, ibilbide berri bat eraikiz. Ibilbidearen <math>k</math> zatien muturretako erpinak beste ibilbide zatien muturretako erpinetara  lotu behar dira ertzak gehituz, beti ere azpi-ibilbiderik sortzen ez dela ziurtatuz (ibilbide zati bereko muturreko erpinak ezin dira konektatu haien artean, azpi-ibilbidea sortuko litzatekeelako). Prozedura horrek bidaiariaren problema beste problema sinpleago batean eraldatzen du.
# <math>k</math> ertz kendu ondoren solte geratu diren ibilbide zatien muturretako erpin bakoitza beste <math>2k-2</math> erpinetara konekta daiteke (guztira <math>2k</math> erpin geratu dira zatien muturretan, eta horietako bakoitza ezin da ez bere buruarekin ezta ibilbide-zati bereko beste muturreko erpinarekin konektatu). Indar gordinaren metodoa erabil daiteke ibilbidea osatzeko konfigurazio berri optimoa aurkitzeko, hau da, erpinak konektatzeko aukera posible guztiak aztertu eta distantzia edo kosturik txikienekoarekin geratu.
Bada ''k-opt'' algoritmoaren aldaera bat, alboko diren ertzak ezabatzea onartzen duena. <math>k=3</math> kasurako, ''2-opt'' algoritmoarekin lortu ahal izango liratekeen soluzioak baina dezente hobeak lortzen dira, 3-opt algoritmo estandarrak suposatzen duen kostu konputazionala ekidinez (bikoteak ordezkatzearen metodoa edo ''2-opt'' aplikatzeak suposatzen duen kostutik gertuago). Aldaera horri "''bi-eta-erdi-opt''" deitu ohi zaio, ''2-opt'' eta ''3-opt'' algoritmoen artean dagoelao, bai kostu konputazionalaren ikuspegitik eta baita lortzen diren soluzioen kalitateari dagokionez ere.

==== v-opt metodoa (variable-opt) ====
''v-opt'' metodoan ordezkatzen den ertz kopurua finkoa izan beharrean, aldakorra da. Ibilbide motzenaren bilaketa prozesua aurrera doan neurrian, ordezkatzen den ertz kopurua handitzen da, iterazioz iterazio. Hortik datorkio metodoari "''variable-opt''" edo "''opt-aldakor''" izena. k-opt metodoaren orokorpen bat da. 

Metodo honetan oinarritzen den algoritmorik ezagunena "''Lin-Kernighan''" izenekoa da. Shen Lin eta Brian Kernighan ikerlariek argitaratu zuten 1972an eta bidaiariaren problemarako heuristikorik fidagarriena izan zen ia 20 urtez. 80ko hamarkadaren amaieran Bell laborategietan David Johnson eta bere ikerketa taldeak algoritmoaren hobekuntzak eta aldaera konplexuagoak garatu zituen. Hobekuntza horiek egiteko [[tabu bilaketa]] eta [[algoritmo ebolutiboak]] erabili ziren. Metodo horiek "''Lin-Kernighan-Johnson''" izenez ezagutzen dira. 

Bidaiariaren problema ebazteko ahalmen handiena duen metodo heuristikoa v-opt dela esan ohi da. Oinarrizko bertsioarekin lortzen diren emaitzak 3-opt metodoarekin lortzen direnak bezain onak direla frogatu da.

==== Hobekuntza ausazkotua ====
Metodo hauek [[Markov kate|markov kateetan]] oinarritzen diren algoritmo optimizatuak dira. Bilaketa lokalerako heuristikoak dituzten azpi-algoritmoak erabiltzen dituzte eta ibilbide optimora asko gerturatzen diren soluzioak aurkitzeko gai dira 700-800 hiriko instantzien ebazpenean.

==== Inurri-kolonien optimizazioa ====
[[Adimen artifizial|Adimen Artifizialeko]] ikerlari Marco Dorigok bidaiariaren problema ebazteko metodo heuristiko berri bat proposatu zuen 90eko hamarkadan: ''Ant Colony System'' (ACS) edo inurri-kolonien sistema. Algoritmoak [[Inurri|inurrien]] kolonien funtzionamendua [[Simulazio|simulatzen]] du. Inurriek beste inurrien [[Feromona|feromonen]] arrastoak jarraitzen dituzte inurritegiaren eta elikagai-iturrien arteko bide motzena aurkitzeko.  

Inurrien kolonien algoritmoak hirien arteko ibilbide posibleak aztertzeko hainbat inurri birtual jartzen ditu martxan. Inurriek modu probabilistikoan eta heuristiko batean oinarrituz erabakitzen dute zein izango den bisitatuko duten hurrengo hiria. Heuristiko horrek hirira iristeko dagoen distantzia eta hirira iristeko dauden ertzetan kokatu den feromona kopurua kontuan hartzen ditu. Inurriek ertzak zeharkatzean feromona uzten dute. Inurri guztiek hirien arteko ibilaldi osoa amaitzen dutenean, ibilbide motzena egin duen inurriak feromona utziko du ibilaldi osoan eta feromonen eguneratze orokor bat egiten da. Jartzen den feromona kopurua ibilbidearen distantziarekiko alderantziz proportzionala da, hau da, zenbat eta motzagoa izan egindako ibilaldiaren distantzia osoa orduan eta feromona gehiago jartzen dute ertzetan. [[Fitxategi:Aco TSP.svg|erdian|thumb|704x704px|1) Inurriak ausazko ibilbide bat osatzen du aukera desberdinen artean, feromona arrastoak utziz. 2) Inurri bakoitza bere ibilbidea egiten ari da, utzitako feromona-kopurua ibilbidearen luzeraren araberako izanik. 3) Ibilbideen ertz batzuk beste batzuk baino feromona gehiago dute. 4) Ebaporazio-teknikak soluzio desegokiak baztertzen ditu. Yves Aubry-k sorturiko mapa.]]
[[Fitxategi:AntColony.gif|erdian|thumb|715x715px|Inurri-kolonien optimizazio-algoritmo baten aplikazioa 7 hiriko bidaiariaren problema batean. Feromonen mapako marra gorri lodiek feromona-kopurua handiagoaren presentzia adierazten dute.]]

=== Kasu bereziak ===

==== Problema metrikoa ====

Bidaiariaren problema metrikoan (ingelesez, ''delta-TSP'' edo ''Δ-TSP''), hirien arteko distantziek [[Desberdintza triangeluar|desberdintza triangeluarra]] betetzen dute. Egia esan,  hirien arteko distantziek desberdintasun triangeluarra betetzen duen [[Metrika (matematika)|metrika]] bat osatzea oso murrizketa naturala da bidaiariaren probleman. Saltzaile ibiltariaren problemaren instantzia askotan betetzen da desberdintza triangeluarra. Horrek esan nahi du, <math>H_i</math> eta <math>H_j</math> hiriak ertz batez konektaturik badaude, <math>H_i</math>-tik <math>H_j</math>-ra dagoen [[distantzia]] <math>H_k</math> hiritik pasata dagoena baino txikiagoa dela:
:<math>d(H_i, H_j) \leq d(H_i,H_k) + d(H_k,H_j)</math>.

Tarteko <math>H_k</math> hiri batetik pasatzean, ertzak zabaldu egiten dira eta ondorioz [[Metrika (matematika)|metrika]] bat osatzen dute erpin multzoaren gainean. Bidaiaren problemako hiriak planoko puntu direla kontsideratzen bada, hainbat [[espazio metriko]] agertzen dira. Hona hemen hainbat adibide, puntuen arteko distantzia metrika desberdinak erabiliz neurtuta:

* Euklidestarra: puntuen arteko distantzia [[euklidesen distantzia]] da.

* Lerrozuzena ([[Manhattanen distantzia]]): puntuen arteko distantzia puntuen <math>x</math> eta <math>y</math> koordenatuen arteko diferentzien balio absolutuen batura da.

* Maximoaren metrika (Chebyshev distantzia): puntuen arteko distantzia puntuen <math>x</math> eta <math>y</math> koordenatuen arteko diferentzien balio absolutuen maximoa da.

Azken bi metrikak, adibidez, bidaiariaren problemaren aplikazio klasiko batean erabiltzen dira: [[Zirkuitu inprimatu|zirkuitu inprimatuen]] fabrikazioan (ingelesez, ''Printed Circuit Board'', ''PCB''). Aplikazio horretan, plaka zulatu egin behar da osagaiak plakan kokatzeko eta [[Zulagailu|zulagailuaren]] ibilbidea planifikatu behar da. “Hiriak” egin beharreko zuloak dira, beraz. Makina zulagailua Manhattanen metrika erabiliz lan egiteko diseinatzen bada, lehenengo koordenatu batean (horizontalean, adibidez) doituko ditu bere mugimenduak eta gero beste koordenatuan (bertikalean). Horrela, puntu batetik bestera mugitzeko denbora bi koordenatuetan egindako mugimenduen batura izango da. Makina zulagailua Chebyshev distantzia (maximoaren metrika) erabiliz lan egiteko diseinatzen bada, aldiz, mugimendua bi koordenatuetan aldiberean doituko da; horrela, puntu batetik bestera mugitzeko denbora bi mugimenduen (horizontalaren eta bertikalaren) arteko maximoa da (motelena). 

Berez, saltzaile ibiltariaren probleman hiriak ezin dira bi aldiz bisitatu. Hala ere, hainbat aplikaziotan ez da beharrezkoa murrizketa hori ezartzea. Kasu horietan, metrikoa ez den instantzia simetriko bat instantzia metriko bihur daiteke, horrela: jatorrizko [[Grafo|grafoa]] [[grafo oso]] bihurtzen da, eta  jatorrizko grafoan <math>A</math>tik <math>B</math>ra joateko [[Bide motzenaren problema|bide motzenaren]] luzera izango da <math>A</math> eta <math>B</math> hirien arteko ertzaren <math>d_{AB}</math> distantzia grafo osotuan.

Bestalde, [[Desberdintza triangeluar|desberdintza triangeluarra]] betetzen duten bidaiariaren problemetan, posiblea da grafoaren [[Zuhaitz estaltzaile minimo|zuhaitz estaltzaile minimoetan]] oinarritutako algoritmoak diseinatzea problema ebazteko (grafoan ziklo hamiltondarra aurkitzeko). Izan ere, zuhaitz horien hedapeneko ertzen distantzien batura bidaiariaren problemarako soluzioaren luzeraren behe-borne bat da. Kontuan izan behar da bidaiariaren ibilbide optimoan ertz bat kenduz [[Grafo teoria#Zikloak eta bide hamiltondarrak|bide Hamiltondar]] bat lortzen dela, hau da, zuhaitz estaltzaile minimo bat grafoan. Horrela, zuhaitz estaltzaile minimoen goi-borneak kontuan hartuz, ibilbidearen hedapenak aztertzen dituen algoritmoa diseina daiteke. Ideia horretan oinarrituz argitaratu den algoritmo bat honakoa da:
#Grafoan zuhaitz estaltzaile minimo bat aurkitu.
#Zuhaitzaren ertz guztiak bikoiztu, hau da zuhaitzean ''<math>u</math>'' erpinetik ''<math>v</math>'' erpinera ertza dagoen guztietan, ''<math>v</math>''-tik ''<math>u</math>''-ra doan beste ertz bat gehitu. Eragiketa horren ondorioz [[Eulertar grafo|grafo eulertarra]] lortzen da.
#Grafo eulertar horretan zirkuitu eulertar bat aurkitu. Hedapen hori zuhaitzaren hedapenaren bikoitza da.
#Zirkuitu eulertar horretatik hasierako grafoaren ziklo hamiltondar bat lortu behar da, prozedura honi jarraituz: zirkuitu eulertarra zeharkatu, eta jada bisitatu den erpin batera iristen den bakoitzean, jauzi egin eta hurrengora joaten saiatu zirkuitu eulertarra zeharkatuz.

Froga daiteke azken urratsak funtzionatzen duela. Gainera, desberdintza triangeluarrari esker, 4. urratseko jauzi bakoitza bide laburra da, hau da, zikloaren luzera ez da handitzen. Beraz, bidaiariaren problemaren ibilbide baterako, ibilbide optimoaren bikoitza baino motzagoa da.

[[Christofidesen algoritmo|Christofidesen algoritmoaren]] diseinua antzekoa da, baina zuhaitz estaltzaile minimoa beste problema baten soluzioarekin konbinatzen da, parekatze perfektuarenarekin. Algoritmoak gehienez soluzio optimoa baino 1.5 aldiz luzeagoa den ibilaldia itzultzen du. Christofidesen algoritmoa hurbilketa-algoritmoen artean sortu zen lehenetarikoa izan zen. Gertakaria garrantzitsua izan zen, ebazten zailak ziren problemetarako ikuspuntu desberdin bat proposatzen zelako: soluzio optimoa bermatu ordez, hurbilketa on bat lortzea zen helburua. Hasiera batean, Christofidesen algoritmoari Christofidesen heuristikoa esaten zitzaion, "algoritmo" terminoa ez zelako hurbilketa algoritmoetarako erabiltzen.

==== Problema Euklidestarra ====

'''Bidaiariaren problema Euklidestarra''' edo '''laua''' [[distantzia euklidestarra|Euklidesen distantzian]] oinarritzen da. Bidaiariaren problema metrikoaren kasu partikular bat da, distantziak planoan desberdintza triangeluarra betetzen baitu.

Problema orokorra bezala, hau ere NP-gogorra da. Metrika diskretura bihurtutako problema (distantzia zenbaki oso bihurtzea gora biribilduz) NP-osoa da. Hala ere, problema metriko orokorra baino errazagoa da. Adibidez, bidaiariaren problema euklidestarraren instantzia bati dagokion zuhaitz estaltzaile minimoa euklidestarra da eta O (''n'' log ''n'') ordenakoko denboran kalkula daiteke, ''n'' izanik hiri kopurua.

==== Problema asimetrikoa ====

Kasu gehienetan, hirien arteko distantzia ez da aldatzen noranzkoaren arabera, baina batzuetan ''<math>A</math>''-tik ''<math>B</math>''-rako distantzia eta ''<math>B</math>''-tik ''<math>A</math>''-rako distantzia ez da berdina. Problema horiek asimetrikoak direla esaten da. Halako problemen aplikazio praktiko bat  "Ibilgailuak Bideratzearen Problema" da (''Vehicle Routing Problem'', VRP), noranzko bakarrean zeharka daitezkeen kaleak daudenean. Problema asimetrikoak ebaztea zaila izan daitekeenez, aukera bat simetriko bihurtzea da, ''n'' tamainako matrize asimetriko batetik ''2n''  tamainako matrize simetriko bat lortuz. 

Izan bedi ''<math>A</math>'', ''<math>B</math>'' eta ''<math>C</math>'' puntuen arteko distantziak jasotzen dituen honako 3 × 3 tamainako matrizea.<ref>Roy Jonker and Ton Volgenant. "Transforming asymmetric into symmetric traveling salesman problems". ''[[Operations Research Letters]]'' '''2''':161–163, 1983. {{doi|10.1016/0167-6377(83)90048-2}}</ref> Matrizeak adierazten duen grafo zuzenduan bi ziklo hamiltondar daude (bi ibilbide posible bidaiariarentzat): <math>\mathrm{A \to B \to C \to A}</math> (9ko distantzia) eta <math>\mathrm{A \to C \to B \to A}</math> (12ko distantzia).<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
:{| class="wikitable"
|- style="text-align:center;"
|+ Matrize asimetrikoa

! !! ''A'' !! ''B'' !! ''C''
|- style="text-align:center;"

! ''A''
| || 1 || 2
|- style="text-align:center;"

! ''B''
| 6 || || 3
|- style="text-align:center;"

! ''C''
| 5 || 4 ||
|}
</div>

Matrizearen errenkada eta zutabe kopurua bikoizten da, puntu bakoitzarentzat beste puntu "''mamu''" bat sortuz, ''<math>A</math>'' puntuarentzat ''<math>A'</math>'' puntu mamua, adibidez. Puntuen eta puntu mamuen arteko distantziari oso balio baxua esleitzen zaie (adibidean −∞), puntu mamu guztiak soluzio optimoan ager daitezen. Jatorrizko matrize asimetrikoa matrize bikoiztuaren behealdeko ezkerreko zatian ikusten da (diagonalean −∞ balioekin), eta matrizea bera baina diagonal nagusiarekiko iraulita goialdeko eskuineko zatian (hau ere bere diagonalean −∞ duelarik). Matrize berrian jatorrizko ''<math>A</math>'', ''<math>B</math>'' eta ''<math>C</math>'' puntuen artean ez dago ertz bidezko konexio zuzenik, ezta ''<math>A'</math>'', ''<math>B'</math>'' eta ''<math>C'</math>'' puntu mamuen artean ere. Erraz ikus daiteke matrize berria simetrikoa dela diagonal nagusiarekiko.
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;">
:{| class="wikitable"
|- style="text-align:center;" class="wikitable"
|+ Matrize simetrikoa

! !! ''A'' !! ''B'' !! ''C'' !! ''A&prime;'' !! ''B&prime;'' !! ''C&prime;''
|- style="text-align:center;"

! ''A''
| || || || −∞ || 6 || 5
|- style="text-align:center;"

! ''B''
| || || || 1 || −∞ || 4
|- style="text-align:center;"

! ''C''
| || || || 2 || 3 || −∞
|- style="text-align:center;"

! ''A&prime;''
| −∞ || 1 || 2 || || ||
|- style="text-align:center;"

! ''B&prime;''
| 6 || −∞ || 3 || || ||
|- style="text-align:center;"

! ''C&prime;''
| 5 || 4 || −∞ || || ||
|}
</div>

6 × 6 tamainako matrizeak adierazten duen grafo zuzenduan honako ziklo hamiltondarra existitzen da: <math>\mathrm{A \to A' \to B \to B' \to C \to C' \to A}</math>. Ikusten den bezala, ibilbidean puntu batetik dagokion puntu mamura joaten da, hau da,  ''<math>A</math>'', ''<math>B</math>'', ''<math>C</math>'' puntuak eta horien puntu mamu diren ''<math>A'</math>'', ''<math>B'</math>'', ''<math>C'</math>'' puntuak txandakatzen dira. <math>\mathrm{A \to A'}</math> moduko bikoteetan "jauzi" egiten da, distantzia zero dela interpreta daitekeelako. Horrela, <math>\mathrm{A \to A' \to B \to B' \to C \to C' \to A}</math> zikloa <math>\mathrm{A \to B \to C \to A}</math> bihurtuko da (9ko distantziakoa).

== Konplexutasun konputazionala ==
Saltzaile ibiltariaren problema [[NP-gogor|NP-gogorra]] dela frogatu da (zehatzago esanda, [[NP-oso|NP-osoa]] da FP<sup>NP</sup> [[Konplexutasun-klasea|konplexutasun-klaserako]]; ikus [[Funtzio-arazoa|funtzioaren problema]]), eta problemaren honako bertsioa [[NP-oso|NP-osoa]] da: distantzien matrize bat eta <math>x</math> zenbaki bat emanik, erabaki <math>x</math> distantzia baino txikiagoa den ibilbidea existitzen den. "Bidaiariaren Problema Botila-lepoduna" (ingelesez, ''Bottleneck TSP'') ere NP-gogorra da. Problemak NP-gogor izaten jarraitzen du hirien arteko distantziak planoan [[Euklidearen distantzia|distantzia euklidestarra]] erabiliz kalkulatzen badira ere. Problemaren planteamendutik hiri bakoitza "behin bakarrik" bisitatzeko eskakizuna kenduta ere problemak NP-gogor izaten jarraitzen du.

=== Hurbiltze-algoritmoen konplexutasuna ===
Problemaren planteamendu orokorra, hau da, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik laburrena aurkitzea, [[NPO-osoa]] da (''NP-Optimization problem, NPO'').<ref> Orponen, P.; Mannila, H. (1987). On approximation preserving reductions: Complete problems and robust measures' (Report). Department of Computer Science, University of Helsinki. Technical Report C-1987–28.</ref> Distantziaren neurria [[Espazio metriko|metrika]] bada (eta, beraz, simetrikoa), problema APX-oso bihurtzen da (ingelesez, APproXimable-complete), hau da, NP optimizazio problema da baina konstante batez mugatutako hurbilketa bat kalkulatzea posiblea da hurbilketa-algoritmo baten bidez denbora polinomialean.<ref> Papadimitriou & Yannakakis (1993).</ref> Christofidesen algoritmoak gehienez ibilbide laburrena baino 1.5 aldiz luzeagoa den ibilaldia itzultzen du.<ref> Christofides (1976).</ref><ref> Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in Russian), 17: 76–79</ref><ref>van Bevern, René; Slugina, Viktoriia A. (2020). "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem". Historia Mathematica. 53: 118–127. arXiv:2004.02437. doi:10.1016/j.hm.2020.04.003. S2CID 214803097.</ref>

Distantziak 1era eta 2ra mugatzen badira (metrika bat izanik), hurbilketa-ratioa 8/7-ekoa bihurtzen da, hau da gehienez 8/7 aldiz luzeagoa den ibilaldia aurkitzen da. <ref> Berman & Karpinski (2006).</ref> Desberdintza triangeluarra betetzen duten problema asimetrikoetan, duela gutxira arte emaitza denbora logaritmikoan itzultzen zuten algoritmoak besterik ez ziren ezagutzen. <ref> Kaplan et al. (2004).</ref> 2018an, Svensson-ek, Tarnawski-k eta Végh-ek faktore konstante bateko hurbilketa metodoa garatu zuten.<ref>Svensson, Ola; Tarnawski, Jakub; Végh, László A. (2018). "A constant-factor approximation algorithm for the asymmetric traveling salesman problem". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2018. Stoc 2018. Los Angeles, CA, USA: ACM Press: 204–213. doi:10.1145/3188745.3188824. ISBN 978-1-4503-5559-9. S2CID 12391033.</ref> Gaur egungo algoritmo onena Traub-ek eta Vygen-ek garatu zutena da, <math>22+\varepsilon</math> errendimendua lortzen du.<ref> Traub, Vera; Vygen, Jens (8 June 2020). "An improved approximation algorithm for ATSP". Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Stoc 2020. Chicago, IL: ACM: 1–13. arXiv:1912.00670. doi:10.1145/3357713.3384233. ISBN 978-1-4503-6979-4. S2CID 208527125.</ref> Ezagutzen den hurbiltasunerako bornerik onena 75/74-koa da.<ref> Karpinski, Lampis & Schmied (2015).</ref>

Bidaiariaren problemaren maximizatze-bertsiorako, hau da, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik luzeena aurkitzearen problemarako, soluzioa 63/38-an hurbil daiteke.<ref> Kosaraju, Park & Stein (1994).</ref> Distantziaren funtzioa simetrikoa bada, algoritmo determinista bat erabiliz ibilbide luzeena 4/3-ean hurbil daiteke <ref> Serdyukov (1984).</ref> eta ausazkotasuna erabiltzen duen algoritmo baten bidez <math>\tfrac{1}{25}(33+\varepsilon)</math> -ean.<ref> Hassin & Rubinstein (2000).</ref>

== Gizakien eta animalien errendimendua==
Bidaiariaren problemaren ebazpenak [[Psikologia kognitibo|psikologia kognitiboko]] ikertzaileen arreta erakarri du. Izan ere, [[Gizaki|gizakia]] problemaren soluziotik oso gertu dauden ibilbideak azkar (ia denbora linealean) aurkitzeko gai dela ikusi da. Hiri kopuruaren arabera errendimendua aldatzen da: 10-20 hiriko problemetan (10-20 erpin dituzten grafoetan) aurkitutako ibilbidea optimotik %1 aldendu daiteke eta problema handiagoetan (120 erpineko grafoetan) %11.<ref> Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics, 58 (4): 527–539, doi:10.3758/BF03213088, PMID 8934685.</ref><ref> Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes". The Journal of Problem Solving. 1 (1). CiteSeerX 10.1.1.360.9763. doi:10.7771/1932-6246.1004. ISSN 1932-6246.</ref> Gizakiek problema ebazteko eta optimotik gertu dauden soluzioak erraz (itxuraz behintzat) aurkitzeko erakutsi duten ahalmenak ikertzaileak hipotesiak egitera eraman ditu. Hipotesi horietako batek dio, gizakiek heuristikoak erabiltzen ditutela. Horren inguruko teoriarik ezagunenak [[Multzo konbexu|ganbiltasunaren]] hipotesia (ingelesez, ''convex-hull hypothesis'') eta gurutzatzea saihestearen heuristikoa (ingelesez, ''crossing-avoidance heuristic'') dira.<ref> Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 March 2003). "Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies". Memory & Cognition. 31 (2): 215–220. CiteSeerX 10.1.1.12.6117. doi:10.3758/bf03194380. ISSN 0090-502X. PMID 12749463. S2CID 18989303.</ref><ref>MacGregor, James N.; Chu, Yun (2011). "Human Performance on the Traveling Salesman and Related Problems: A Review". The Journal of Problem Solving. 3 (2). doi:10.7771/1932-6246.1090. ISSN 1932-6246.</ref><ref> MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 March 2004). "Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem". Memory & Cognition. 32 (2): 260–270. doi:10.3758/bf03196857. ISSN 0090-502X. PMID 15190718.</ref> Hala ere, giza errendimendua askotarikoa dela ikusi da, gizaki batzuek trebetasun handia erakusten duten arren beste batzuek traketsak dira soluzio onak aurkitzen. Gainera, grafoaren geometriak ere eragin handia sortzen du problemaren ebazpenaren errendimenduan.<ref> Vickers, Douglas; Mayo, Therese; Heitmann, Megan; Lee, Michael D; Hughes, Peter (2004). "Intelligence and individual differences in performance on three types of visually presented optimisation problems". Personality and Individual Differences. 36 (5): 1059–1071. doi:10.1016/s0191-8869(03)00200-9.</ref><ref> Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva (12 June 2017). "Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem". Psychological Research. 82 (5): 997–1009. doi:10.1007/s00426-017-0881-7. ISSN 0340-0727. PMID 28608230. S2CID 3959429.</ref><ref>Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 January 2017). "Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem". Heliyon. 3 (11): e00461. doi:10.1016/j.heliyon.2017.e00461. PMC 5727545. PMID 29264418.</ref> Gizakiek erabiltzen dituzten estrategiak ulertu eta emulatuz gero, bidaiariaren problema ebazteko algoritmo hobeak aurkitu ahal izango direla ondorioztatu da egindako ikerketetatik.<ref> Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva; Din, Shahab Ud (December 2018). "Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects". Cognitive Systems Research. 52: 387–399. doi:10.1016/j.cogsys.2018.07.027. S2CID 53761995.</ref> Horrekin batera, giza pentsamenduaren mekanismoak hobeto ezagutzea lortu da.<ref> MacGregor, James N.; Chu, Yun (2011), "Human performance on the traveling salesman and related problems: A review", Journal of Problem Solving, 3 (2), doi:10.7771/1932-6246.1090.</ref> "''Journal of Problem Solving"'' aldizkari zientifikoaren lehen alea bidaiariaren problemaren ebazpenean gizakiek erakutsitako errendimenduari buruzkoa izan zen,<ref> Journal of Problem Solving 1(1), 2006, retrieved 2014-06-06.</ref> eta 2011ko argitalpen batean gaiari buruzko dozenaka artikulu zientifiko zerrendatzen dira.<ref> MacGregor, James N.; Chu, Yun (2011), "Human performance on the traveling salesman and related problems: A review", Journal of Problem Solving, 3 (2), doi:10.7771/1932-6246.1090.</ref>

2011ean [[Animalia|animalien]] [[Kognizio|kognizioari]] buruzko ikerketa bat egin zen. Ikerketaren izenburua  "''Let the Pigeon Drive the Bus''" zen, euskaraz "Utzi usoari autobusa gidatzen".  "''Don't let the Pigeon Drive the Bus!''" haurrentzako liburu ezagunaren izenburutik abiatuz jarri zitzaion izen hori ikerketa proiektuari. Helburua [[Uso|usoek]] espazioari buruz duten ezagutza aztertzea zen. Haien hegaldi-ereduak aztertu nahi zituzten, bidaiariaren problemaren ebazpenerako estrategia berriak bilatzeko asmoz. Horretarako, [[laborategi]] batean [[Hegazti|txorientzako]] hainbat elikagailu jarri zituzten [[Ilar|ilarrekin]]. Hasierako esperimentuan, usoak laborategiko txoko batean kokatu eta aske utzi zituzten, elikagailuetako ilarrak jatera joan zitezen. Ikertzaileek ikusi zuten usoak hurbilen zegoen elikatzailera joaten zirela, gehienetan. Bigarren esperimentuan ez zuten ilar kopuru bera jarri elikagailu guztietan, gertuen zeudenetan oso gutxi jarri zuten eta urrutiago zeudenetan gehiago. Usoak askatzean, haiek egindako hegaldiak aztertuz konturatu ziren hurbilen zegoen elikagailura joateak elikagailu guztiak bisitatu behar izatea eragiten zuen kasuetan, usoek haien jokaera aldatzen zutela. Horrela, usoek nora joan erabaki behar zutenean hurbil egoteak garrantzia bazuela ikusi zuten arren, haien hegaldia hainbat urratsetan planifikatzeko gai zirela ondorioztatu zuten eta batzuetan urrunago dagoen elikagailura joatea erabakitzen zutela. Hori horrela egiten zuten, batez ere beti hurbilenera joatea eraginkorra ez zenean (ilar gutxi zegoenean hurbilenekoetan). <ref>Gibson, Brett; Wilkinson, Matthew; Kelly, Debbie (1 May 2012). "Let the pigeon drive the bus: pigeons can plan future routes in a room". Animal Cognition. 15 (3): 379–391. doi:10.1007/s10071-011-0463-9. ISSN 1435-9456. PMID 21965161. S2CID 14994429.</ref> Emaitza horiek bat datoz [[Primate|primateak]] ez diren beste animalia batzuekin egindako esperimentuetako emaitzekin, eta frogatzen dute primateak ez diren animalia batzuek gai direla ibilbide konplexuak planifikatzeko. Hortaz, badirudi primate ez diren animaliek espazioa kudeatzeko trebetasun kognitibo sofistikatu samarra izan dezaketela.

== Konputazio naturala ==
Badira naturan inspiratuta garatu izan diren ebazpen metodoak. Bidaiariaren problema euklidestarrerako hurbilpen soluzio bat aurkitzeko, adibidez, partikulen populazio bat difusio-sare batean zehar mugitzean materialaren portaera morfologikoa nola egokitzen den aztertu izan da. Ikerketa lan batean ''Physarum polycephalum'' motako [[Amoeba|ameba]] hainbat puntuz (elikadura-iturriz) osatutako sare batean kokatu zuten, eta ikusi zen ameba tamainaz txikitzen zela elikadura-puntuen konfiguraziora egokituz zioan neurrian. Eskuz amebaren perimetroa jarraituz gero, elikadura-puntuen arteko ibilbide bat aurkitu ahal izango litzateke. Ibilbide hori saltzaile ibiltariaren problemarako soluzio optimoaren hurbilpen moduan ikus daiteke.<ref> Jones, Jeff; Adamatzky, Andrew (2014), "Computation of the travelling salesman problem by a shrinking blob" (PDF), Natural Computing: 2, 13, arXiv:1303.4969, Bibcode:2013arXiv1303.4969J</ref>

== Algoritmoen ebaluazioa ==
Bidaiariaren problema ebazteko algoritmoak ebaluatzeko, badira liburutegi estandarrak. . [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ '''TSPLIB'''] liburutegian hainbat adibideren instantziak eta erlazionatutako problemak aurki daitezke (ikus TSPLIB kanpo erreferentzien atalean)<ref>"TSPLIB". comopt.ifi.uni-heidelberg.de. Retrieved 10 October 2020.</ref> Instantzia horietako asko egungo hirien zerrendak eta gaur egungo [[Zirkuitu inprimatu|zirkuitu inprimatuen]] diseinuak dira.  

==Kulturan eta zineman==
*"''Travelling Salesman''" Timothy Lanzone-k 2012an zuzendutako filma da. [[Ameriketako Estatu Batuak|Ameriketako Estatu Batuetako]] gobernuak kontratatutako lau matematikariren istorioa kontatzen da. Informatikaren historiako problemarik zailena ebazteko kontratatuak izan dira: [[P vs NP problema|P vs NP problema]] ebazteko<ref> Geere, Duncan (26 April 2012). "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. Retrieved 26 April 2012.</ref> 

*Bob Bosch matematikariak eta Tom Wexler informatikariak bidaiariaren problemaren soluzioak erabiltzen dituzte artelanak puntuen eta haietatik pasatzen diren ibilbideen bidez adierazteko. "''Optimization art''" edo "''opt-art''" deitzen zaio teknika horri. <ref> When the Mona Lisa is NP-HardBy Evelyn Lamb, Scientific American, 31 April 2015</ref>

== Erreferentziak ==
{{erreferentzia_zerrenda|30em}}

==Ikus, gainera==
*[[Postari txinatarraren ebazkizun]]
*[[Königsbergeko zazpi zubietako ebazkizuna]]

== Kanpo estekak ==

{{autoritate kontrola}}

[[Kategoria:Grafo teoria]]
[[Kategoria:Ikerketa operatiboa]]
[[Kategoria:Optimizazio matematikoa]]