Mitme miljardi dollariline probleem

Nagu jutustab hiljutine ÄP Novaator viitega eelmise aasta New York Timesile, suutis kullerfirma UPS 2006. aastal oma kuludes kokku hoida ligi 11 miljonit liitrit bensiini ainuüksi sellega, et muutis kullerautode marsruute nii, et teel olles ei tehtud ühtki vasakpööret.

Ajalehe väitel kasutas firma juhtide igapäevaste marsruutide koostamiseks tarkvara. Kindlasti on sellisel algoritmil, mis suudab koostada kõige efektiivsemaid marsruute selge majanduslik ja ka loodust hoidev aspekt, kirjutas LiveScience. Kuid marsruutimine on sedavõrd keeruline ülesanne, et kui teil on välja pakkuda mingi asjalik lahendus, siis saate te paugupealt kuulsaks, vähemalt arvutiteadlaste hulgas.

Kullerautojuhi ülesanne on põhimõtteliselt sama klassikalise reisiva müügimehe ülesandega, kus tuleb leida mitmete eri punktide vahel lühim tee. Sama ülesandega on tegu teekonna kavandamisel, koolibussi peatuskohtade, parkimisautomaatide asetuse valikul, elektrijuhtmete paigalduses ja arvutikiipide tootmisel, seega ei midagi uut.

Kuulus 19. sajandi Iiri matemaatik William Rowan Hamilton leiutas Icosia mängu, kus puust alusele oli uuristatud 20 lohku, mis kandsid erinevate tuntud linnade nimesid. Mängu eesmärk oli asetada nuppe lohkudesse nõnda, et järjestikuste nuppude lohud oleks omavahel joonega ühendatud ning ka esimese ja viimase nuppu vahel oleks joon.

Hiljem võttis sama idee lihtsustatud kujul üle üks mängutootja ning neist innustatuna hakkasid Viini ja Cambridge’i matemaatikud 1930. aastatel uurima nn reisiva müügimehe ülesannet.

Mõistmaks selle ülesande keerukust tuleks appi võtta arvud. Kui teekonnal tuleb läbida viis linna, siis on nende vahel võimalik valida 12 erinevat marsruuti. Kümne asula vahel on võimalik valida 181 440 võimaliku variandi vahel ja kui valida on 61 linna, siis ületab võimaluste arv universumis olevate aatomite arvu.

Ehk lisades valikusse ühe linna valikuvariantide arv laias laastus kahekordistub.

Kuigi arvutid muutuvad üha võimsamaks, ei suuda isegi IBMi superarvuti Blue Gene, mis suudab sekundis teha 500 000 miljardit tehet, lahendada ainuüksi toore jõuga reisiva müügimehe ülesannet, kus valikus on 30 linna.

Selle asemel tegelevad teadlased ülesandega teisel viisil, heuristlikult – püüdes leida umbkaudseid meetodeid, et raskesti käsitletavaid olukordi käsitleda. Ehk siis müügimees, kes koostab oma marsruuti, valib oma teekonnal lihtsalt järgmise sihtpunkti, kus ta pole veel käinud. Tihtipeale viib see selleni, et teekond ei ole kaugeltki optimaalne, kuid keskeltläbi saab sellise lähenemisega siiski hakkama.

Kuid ülesanne, mis logistikafirmadel tuleb lahendada, ei ole Icosia mäng, kui suurel firmal on näiteks 95 000 autot, mis veavad pakke laiali ning igaühele neist tuleb koostada marsruut. Need marsruudid sõltuvad üksteisest – võttes ühel autol ühe sihtkoha vähemaks tuleb teisel autol üks lisada.

Vasakpöördeid vältiva heruristika abil on võimalik mõista ka vahemaa ja sõiduaja erinevust. Ehk siis, nagu üks logistikaguru on väljendanud: „Ma tean, et mu naine hullub iga kord, kui ma sõidan mööda kolmest-neljast apteegist, mis asuvad vasakul pool teed ja keeran sisse alles sellesse apteeki, mis asub paremal teeserval.“