Maailma raskeim ülesanne

05. november 2008, 17:45

Möödunud aastal kirjutas New York Times, et
kullerfirma UPS suutis 2006. aastal 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.

UPSi 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, mida UPS püüab lahendada ei ole Icosia mäng. Firmal on 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 vahemaa ja sõiduaja erinevust. UPSi asepresident Jim Winestock väljendab seda nii: „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.“

Raadio ettevõtlikule inimesele

Äripäeva raadio 92.4

Hetkel eetris

Kava

Vaata kogu kava
Äripäev http://www.aripaev.ee/img/id-aripaev.svg
07. January 2009, 17:18
Otsi:

Ava täpsem otsing