Bidaiariaren problema[aldatu | aldatu iturburu kodea]

Problemaren formulazioa[aldatu | aldatu iturburu kodea]

Saltzaile ibiltariaren problema programazio lineal osoko problema gisa formula daiteke. Hiriak 1-etik $n$ -rako zenbakien bidez izendatzen dira eta $i$ hiritik $j$ hirira dagoen distantzia (joateak eragiten duen kostua) $c_{ij}$ notazioaz adierazten da, $i,j\in \{1,\cdots ,n\}$ izanik.

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

$x_{ij}={\begin{cases}1&{\text{baldin bidaiaria}}\ i\ {\text{hiritik}}\ j\ {\text{hirira badoa}}\\0&bestela\end{cases}}$

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

$min\ z=\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}$

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 $j$ hiri bakoitzera $i$ hiri bakar batetik joango dela ziurtatzeko, $j$ bakoitzerako $x_{ij}$ aldagaien batura 1 dela adierazten duen murrizketa idazten da. Bidaiariak $n$ hiri bisitatu behar dituenez, $j$ -ren balio bakoitzerako ( $j=1,\dots ,n$ ) horrelako murrizketa bat dago:

$\sum _{i=1,i\neq j}^{n}x_{ij}=1$

Bestalde, ibilbidea $i$ hiri bakoitzetik $j$ hiri bakar batera joango dela ziurtatzeko, $i$ bakoitzerako $x_{ij}$ aldagaien batura 1 dela adierazten duen murrizketa idazten da. Bidaiaria $n$ hirietatik irtengo denez, $i$ -ren balio bakoitzerako ( $i=1,\dots ,n$ ) horrelako murrizketa bat dago:

$\sum _{j=1,j\neq i}^{n}x_{ij}=1$

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 $n=4$ hirirako soluzio bat aurkezten da: $x_{12}=1$ , $x_{21}=1$ , $x_{34}=1$ , $x_{43}=1$ , 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.

$n=4\ {\text{hiri}},\ x_{ij}\ {\text{soluzio bat}}$
	$1$	$2$	$3$	$4$
$1$	$0$	$1$	$0$	$0$
$2$	$1$	$0$	$0$	$0$
$3$	$0$	$0$	$0$	$1$
$4$	$0$	$0$	$1$	$0$

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)[aldatu | aldatu iturburu kodea]

MTZ formulazioan $x_{ij}$ aldagaiak erabiltzeaz gain, honako $u_{i}$ aldagaiak definitzen dira hiriak zein ordenatan bisitatuko diren kontrolatzeko:

$u_{i}=i\ {\text{hirira zenbat urratsetan iritsiko den}},i=2,\cdots ,n$

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

$u_{j}>u_{i}$ desberdintzak zera adierazten du: $j$ hirira iristeko eman behar den urrats kopurua $i$ hirira iristeko eman behar dena baino handiagoa da. Horrek hirien artean ordena bat finkatzen du. $x_{ij}$ aldagaiak $u_{i}$ eta $u_{j}$ aldagaiekin erlazionatu behar dira, ibilaldi bakar batean hiri guztiak zeharkatzen direla ziurtatzeko, hau da, azpi-zikloak ekiditeko. Hori honako murrizketarekin lortzen da:

$u_{i}-u_{j}+(n-1)x_{ij}\leq n-2,$

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

Miller-Tucker-Zemlin formulazioaren arabera, eredu lineala bere osotasunean horrela geratzen da:

$min\ z=\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}$

${\text{hauen mende:}}\quad \quad \quad \quad \quad \quad \quad$

${\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}}$

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

$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$

$x_{34}$ , $u_{3}$ eta $u_{4}$ aldagaien artean erlazio koherentea ezartzen da.

$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)$

$n=4$ izanik, kasurik okerrenean $u_{3}=1$ bada $u_{2}\leq 3$ geratzen da. Beraz, $u_{2}$ eta $u_{3}$ aldagaien balio guztietarako murrizketa betetzen da. Ibilbidea ez doanez 2 hiritik 3ra, ez da haien artean ordenarik ezartzen.

Bestalde, $x_{34}=1$ eta $x_{43}=1$ azpi-ziklorako kontraesana sortzen da.

$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$

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

Dantzig–Fulkerson–Johnson formulazioa (DFJ)[aldatu | aldatu iturburu kodea]

DFJ formulazioan "azpi-ibilbideak ezabatzeko murrizketak" (ingelesez, subtour elimination constraint) gehitzen dira. $n$ hiriko bidaiariaren problemarako, $Q\subsetneq \{1,\dots ,n\}$ azpimultzo propioak definitzen dira. $Q$ azpimultzoen kardinalak (elementu kopuruak) gutxienez bikoa izan behar du, $|Q|\geq 2$ . Sor daitezkeen azpi-ziklo guztiak ezabatzeko, $n$ elementurekin osa daitezkeen halako $Q$ azpimultzo posible guztietarako definitzen diren murrizketak honakoak dira:

$\sum _{i\in Q}\sum _{j\neq i,j\in Q}x_{ij}\leq |Q|-1$

Inekuazioaren ezkerraldeko bi batukari horien bidez $Q$ 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:

$min\ z=\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}$

${\text{hauen mende:}}\quad \quad \quad \quad \quad \quad \quad$

${\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}}$

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

$\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$

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[aldatu | aldatu iturburu kodea]

Bidaiariaren problemaren ebazpenak duen konplexutasunagatik, 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 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[aldatu | aldatu iturburu kodea]

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 ikuspegitik bideraezina da, $n$ hiriko problema ebazteko algoritmoak $O(n!)$ 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 dinamikoan oinarritzen da eta problema $O(n^{2}2^{n})$ 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 $O(1,999^{n})$ konplexutasun-ordena baino txikiagoa duen algoritmo zehatzik existitzen den.

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 $n=40$ eta $n=60$ hiri arteko bidaiariaren problema ebaztean ondo moldatzen direnak.

Hobekuntza progresiboko algoritmoek programazio linealaren antzeko teknikak erabiltzen dituzte. $n=200$ 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 $n=85.900$ 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[aldatu | aldatu iturburu kodea]

Algoritmo 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 $\%3$ inguru besterik ez direla aldentzen. Algoritmo heuristikoen artean, mota desberdinekoak daude.

Algoritmo eraikitzaileak (irenskorrak)[aldatu | aldatu iturburu kodea]

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.

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 $n$ hirirentzat, batez beste ibilbide optimoa baino $\%25$ 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, $O(n^{2})$ eta $O(n^{2}{\text{log}}n)$ 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[aldatu | aldatu iturburu kodea]

Algoritmo hau bidaiariaren problemaren instantzia berezi batzuetan soilik aplika daiteke: espazio metriko batean kokatzen diren instantzietan bakarrik, hau da, $i.$ hiria $H_{i}$ izanik, hurrengo propietateak betetzen dituzten instantzietan (informazio gehiagorako, ikus kasu berezien ebazpena):

$\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$

$\forall H_{i},H_{j},\ d(H_{i},H_{j})=d(H_{j},H_{i}),\ i,j=1,\dots ,n$
$\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}})$

Algoritmoak kasurik okerrenean soluzio optimoa baino 1,5 aldiz luzeagoa den ibilbidea bueltatzen duela frogatu da. Hori lortzeko, grafo teoriako emaitzak erabiltzen dira. Izan ere, grafo eulertar batean zirkuitu eulertar bat aurki daiteke $O(n)$ 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)[aldatu | aldatu iturburu kodea]

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 $\%5$ 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 $O(n)$ ordenakoa izango delarik. Baina hasierako soluzioa ausaz kalkulatzen bada, algoritmoaren konplexutasuna $O(n\ {\text{log}}n)$ 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)[aldatu | aldatu iturburu kodea]

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, $k$ ertz kenduz egiten da. Beraz, $k=2$ denean, k-koteak ordezkatzearen metodoa bikoteak ordezkatzearen metodo bihurtzen da. k-koteak ordezkatzeko algoritmoen artean, $k=3$ kasua da ezagunena: 3-opt. Bell laborategietan lanean ari zen Shen Lin-ek proposatu zuen 1965. urtean.

k-opt algoritmoa honakoa da:

Hiri guztiak behin bakarrik zeharkatzen dituen iIbilbide bat emanik, haien artean alboko ez diren $k$ ertz ezabatzen dira.
Deskonektatuta geratu diren ibilbidearen $k$ zatiak elkartu behar dira, ibilbide berri bat eraikiz. Ibilbidearen $k$ 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.
$k$ ertz kendu ondoren solte geratu diren ibilbide zatien muturretako erpin bakoitza beste $2k-2$ erpinetara konekta daiteke (guztira $2k$ 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. $k=3$ 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)[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

Metodo hauek 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[aldatu | aldatu iturburu kodea]

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 inurrien kolonien funtzionamendua simulatzen du. Inurriek beste inurrien 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.