Til hovedinnhold

Rute-esset

Rute-esset

Publisert 15. februar 2012

Dette er en verdensrekord – i ruteplanlegging.

Vrien nøtt! Hvordan ordne vareutkjøringen sånn at total kjørelengde blir kortest mulig når 25 biler skal ut til 260 kunder (punkter på dette «kartet») fra ett lager? Her ses deler av verdens beste løsning på denne akademiske standardoppgaven (farger = biler).

Torsdag 27. mai 2004 forteller norske aviser om rettssaken mot Knutby-pastoren i Sverige. Amerikansk tortur i Irak får også mye spalteplass. Det står ingenting om et uvanlig rekordforsøk i Oslo dagen før.

Så er det heller ikke på Bislett konkurransen har stått. I et traust, grått murbygg ved foten av Holmenkollåsen har en ung mann ved navn Erik Zijp drevet rekordjakt i øvelsen rute- og transportplanlegging.

Zijp er masterstudent fra Nederland. I to lyse måneder har han sommerjobb ved SINTEFs Oslo-kontor. Utstyrt med PC og en «optimeringsmotor» – søkeverktøy unnfanget av vertskapet – går gjesten løs på følgende nøtt:

Fra ett depot skal et firma levere varer til 261 mottakere som er inntegnet på et enkelt «kart». Selskapet har 25 kjøretøyer til jobben, alle like store. Hvordan fordele oppdragene mellom bilene – og hvordan ordne rekkefølgen på leveringsstedene for hvert kjøretøy – slik at den totale kjørelengden blir kortest mulig?

For forskere med sans for fagfeltet optimering pluss effektiv og dermed miljøvennlig transport er dette en akademisk standardoppgave. De har brynt seg på den siden 1976.

Ingen har klart å finne det beviselig beste svaret, men 26. mai 2004 spytter PC-en til Zijp ut en unik løsning. I korridorene bryter jubelen løs. Rutene maskinen hans har foreslått, er samlet ni prosent kortere enn den gjeldende verdensrekorden.

«Ny-rekorden» (bildet øverst i saken) står den dag i dag.

Den handelsreisendes problem

På rekordarenaen, sju år etter regnebragden, treffer jeg Geir Hasle, sjefforsker i avdelingen Anvendt matematikk hos SINTEF. En blid kar med dongeribukse og rutet skjorte. Ingen tjukke brilleglass eller andre nerdetrekk der i gården. Det til tross for at han er en av av fedrene til «Spider», optimeringsmotoren nederlenderen brukte.

Hasle snakker ivrig om noe han kaller den handelsreisendes problem. Ikke om forsinkede ferger – men om å finne den rekkefølgen kunder må besøkes i for at rundturen mellom dem skal bli kortest mulig. En del av jobben som rekordholder Zijp og Spider gjøv løs på våren 2004, handlet om å løse sånne problemer. Og skal du regne på denslags, øker antallet mulige rekkefølger raskere enn du aner.

Tre kunder på lista gir seks mulige besøksrekkefølger når du starter fra et depot. Fire kunder gir tjuefire rekkefølger. Fem kunder gir 120 kombinasjonsmuligheter. Med ti kunder på lista har antallet mulige besøksrekkefølger vokst til over 3,6 millioner. Og med 50 stoppesteder er det ifølge Hasle like mange løsningsmuligheter som det finnes atomer i Melkeveien!

Wow!

– Kan dette kobles til vanlige folks hverdag?

– Javisst! Vi har utviklet løsningsmetoder som knekker slike nøtter for avisdistributører og avisbud landet over. Sånn bidrar Spider til at avisene havner i folks postkasser innen tidsfristen på morrakvisten, uten at distribusjonsselskapet bruker mer penger og budet mer tid og bensin enn det som er nødvendig.

Regnetung materie

Men aller først: Hva er optimering?

Hasle bruker nettopp logistikk som eksempel når han svarer. Optimering kan bety å minimere – eksempelvis sørge for at transportoppdrag utføres med færrest mulig kjørte kilometer, som i rekordstuntet. Det er synonymt med å begrense drivstofforbruk og tilhørende miljøutslipp. Alternativt kan målet være å maksimere for eksempel profitt.

Optimeringsjobbene Spider er utviklet for å håndtere, kalles «Vehicle Routing». Flåtestyring på norsk. Rekordstuntet viser hva dette går ut på: fordele transportoppdrag mellom kjøretøy, pluss finne rekkefølgen på stoppestedene for hver bil. Ekstremt beregningstunge oppgaver, og mye vanskeligere enn «Handelsreisendeproblemet», ifølge Hasle.

«Skulle vi regnet gjennom alle mulige planer én for én, ville ikke universets levetid gitt oss tid nok.»

Forsker Geir Hasle

I prinsippet er problemet enkelt. Et endelig antall ruteplaner skal undersøkes.

– Men skulle vi regnet gjennom alle mulige planer én for én, ville ikke universets levetid gitt oss tid nok. Det er riktignok mulig å skjære bort uaktuelle muligheter. De fleste av dem er jo helt idiotiske. Men selv med slike metoder vil den kraftigste datamaskin raskt kjøre seg fast hvis målet er den garantert optimale løsningen. For de fleste formål, som flåtestyring, holder det imidlertid å finne en løsning innen rimelig tid som er god nok.

Fiktive rom

Hasle ser flåtestyring som en ferd mellom punkter i fiktive rom. Hvert punkt representerer én mulig løsning. Optimeringsmotoren Spider starter med å lage én transportplan fra bunnen av. Så flytter den oppdrag fra én bil til en annen, eller endrer leveringsrekkefølgen for ett kjøretøy. Slik dannes nabolag av beslektede planer som raskt kan undersøkes – med én lokal vinner. Med jevne mellomrom hopper motoren til nye steder i «rommet» for å spre søket etter gode løsninger.

– I arbeidet med Spider er vi blitt flinke til å navigere smart gjennom slike rom. Denne tilnærmingen gir løsninger som erfaringsmessig er gode, selv om ingen vet nøyaktig hvor nært de ligger et optimum.

Iskrem, brød og aviser

Spider er én av en mange optimeringsmotorer på markedet for transportplanlegging. Første versjon så dagens lys ved SINTEF i 1998. Motoren er blant annet brukt til å optimalisere ruter for distribusjon av iskrem og brød – og for transport av pasienter og blod.

Drevet av ønsket mitt om å finne bruksområder nær din og min dørstokk, havner sjefforsker Hasle og jeg i det tidligere Postgirobygget. Der holder selskapet Distribution Innovation (DI) til, nær en av sine mødre – Aftenposten.

Firmaet ble født i 2001, tuftet på ideen om å gi avisbud elektroniske hjelpemidler. Budene hadde gått fra å betjene én avis til å levere alt vi abonnerer på. Hva de skal putte i postkassene, varierer fra dag til dag. DI så derfor for seg en dynamisk elektronisk budbok som erstatning for den papirbaserte ordreboka til budene.

Løsningen ble «eBudboka» pluss en web-basert løsning for toveis-kommunikasjon. Via smarttelefoner brukes eBudboka av 6200 bud som daglig betjener 80 prosent av norske husstander. SINTEF hjalp DI med den krevende jobben å designe eBudboka slik at den skulle bli så enkel og god som mulig for budene. Med Forskningsrådet i ryggen startet samarbeidspartnerne et nytt prosjekt i 2005. Kunne Spiders optimeringsferdigheter gjøre rutene mer effektive og planleggingsjobben mindre tidkrevende?

30 prosents tidsgevinst

Geir Hasle og DI-sjef Tone Løyland oppsummerer denne andreetappen slik – hovedmålet først: Å minimere det totale tidsforbruket til avisbudene, en avgjørende størrelse for lønnsutgiftene til distributøren og for avisenes økonomi.

Skal tidsforbruket ned, må rutene gjøres mer effektive. Dette må også til for å nå mål nummer to: reduserte eksosutslipp fra dagens bilbaserte bud.

Det er imidlertid flere optimeringsutfordringer: Hvert bud skal være ute omtrent like lenge. Områdene budene dekker, skal ikke overlappe hverandre. Det blir kaos om budene går «oppå» hverandre.

Spider takler alt dette. Og resultatet?

Løyland: – Vi slet lenge med å få distributørene til å ta optimeringsløsningen i bruk, fordi stikkveier og bommer mangler i det elektroniske kartgrunnlaget. Gjennombruddet kom i 2010. Da ble vi enige om at 80 prosent automatisk ruteplanlegging er godt nok. Nå bruker alle kundene løsningen.

Hasle: – Prosjektet nådde målet. Distributører registrerer besparelser på opptil 30 prosent i total ombæringstid. Pluss drastisk reduksjon av tiden som går med til å planlegge ruter.

Revisjon av rutenettverk

Løsningen til Distribution Innovation brukes både til jevnlig oppdatering av rutene og til å revidere hele ruteinndelingen med visse mellomrom. Det forteller Arne Sletholt, adm. direktør i Edda Distribusjon. Jeg besøker kontoret hans en grå førjulsdag, i Stokke i Vestfold. Sletholt forklarer at revisjoner var tidkrevende før:

– Det tok måneder å revidere budrutene i et område. Derfor utsatte vi det i det lengste. Med hyppige endringer i opplagstall og produkter må vi kjøre revisjoner oftere. Spider-løsningen har gjort dette mulig.

Dagen går mot kveld, og natt. Klokka 02.45 står jeg ved en folketom bensinstasjon i utkanten av Tønsberg. En blafrende vimpel med pizza-reklame er alt jeg hører. Så knaser det i piggdekk. Bil etter bil med avisbud kjører inn. En varebil med henger dukker opp. Så blir det omlasting.

Magnus Akerholt, bud på si, fyller nær hele kupeen i den lille personbilen sin med aviser. Jeg får så vidt plass i baksetet, ved siden av et tårn med Tønsberg Blad. Så kjører vi ut i mørket.

– Noen feilleveringer ble det da vi hadde den gamle budboka. Det er ikke mange klagene nå lenger, sier Akerholt og peker på smart-telefonen som henger i frontruta, med denne nattas budrute nedlastet. Han kjører med åpent vindu. Fra postkasse til postkasse, med stor presisjon. På det meste har han 400 mottakere å betjene.

– Visste du at det finnes flere rekkefølger mellom leveringsstedene enn det er atomer i Melkeveien?

Latteren runger ut av bilvinduet.

– Nei, det har jeg ikke tenkt på, gitt!

 

 

Sjefforsker
+47 930 58 703