Hvordan skal man legge opp ruter for landets avisleveringer slik at budene samlet sett bruker så lite tid og drivstoff som mulig?

Skulle noen prøvd å løse oppgaven ved å regne seg gjennom alle mulige rutekombinasjoner, ville de ifølge forskere trengt mer enn universets levetid på å bli ferdig, selv for et avgrenset geografisk område.

I stedet har 28 distribusjonsselskaper som samlet betjener 80 prosent av norske husstander, tatt i bruk et nytt, smart verktøy for å perfeksjonere sin ruteplanlegging.

Tidsbesparelser på 30 prosent

– Distribusjonsselskaper som har tatt i bruk systemet, har registrert besparelser på opptil 30 prosent i total ombæringstid. Tidsforbruket er en avgjørende størrelse for lønnskostnadene til distributørene, og nivået på disse utgiftene er i sin tur viktige også for avisenes økonomi, sier sjefforsker Geir Hasle ved SINTEF IKT.

Han er en av arkitektene bak regneverktøyet Spider.

Spider er blitt til etter forskning på optimering (se faktaboks), som er en gren av anvendt matematikk. Verktøyet så dagens lys i 1998, og er utviklet for å gjøre transportnæringen i stand til å løse komplekse oppdrag så raskt, rimelig og miljøvennlig som mulig.

I avisverdenen har Spider gjort sitt inntog både i Norge, Sverige og Finland. Med Norges forskningsråd i ryggen startet SINTEF og selskapet Distribution Innovation i 2005 et prosjekt for å uforske om Spider også kunne gjøre løypenett av avisbudruter mer effektive.

Spesialhensyn

Mer effektive ruter var en forutsetning både for å nå prosjektets hovedmål – reduksjon av den totale ombæringstida for aviser, og mål nummer to – reduserte eksosutslipp fra dagens bilbaserte avisbud.

Oppgaven innebar flere optimeringsutfordringer som avisbransjen er alene om – spesialhensyn som Spider må ivareta i alle sine ruteforslag for avisdistributørene:

Som for eksempel det at hvert bud skal være ute omtrent like lenge, og at området som ett bud dekker, ikke må overlappe området til naboruta. Det blir kaos om budene går oppå hverandre.

Etter videreutvikling av metodene har Spider klart å takle alt dette, ifølge prosjektdeltakerne.

Tjenesten som Distribution Innovation dermed kunne tilby, brukes nå av avisdistributørene til to formål: jevnlig oppdatering av leveringsrekkefølgen på hver enkelt rute, og revisjon av hele ruteinndelingen med visse mellomrom. Hele tjenesten leveres til kundene via internett.

Tone Løyland, administrerende direktør i Distribution Innovation, forklarer at gjennombruddet i markedet kom i 2010.

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

Mye raskere ruterevisjon

Edda Distribusjon, som distribuerer alle abonnementsavisene i Østfold, Buskerud, Vestfold, Telemark og deler av Rogaland, er en av brukerne av systemet. Arne Sletholt, administrerende direktør i Edda Distribusjon, forklarer at revisjoner av ruteinndelingen 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.


Ifølge Geir Hasle fra SINTEF skal det ikke skal så mange kunder til på ei liste for utkjøring av varer, før det blir svært “regnetungt” å minimere tidsforbruk eller total kjørelengde.

Hasle snakker ivrig om noe han kaller den handelsreisendes problem - en klassisk optimeringsutfordring som handler om å finne rekkefølgen kunder må besøkes i for at rundturen mellom dem skal bli kortest mulig.

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.

Flåtestyring

Optimeringsjobbene Spider er utviklet for å håndtere, kalles vehicle routing, eller flåtestyring på norsk, som vil si å fordele transportoppdrag mellom kjøretøy, og finne rekkefølgen på stoppestedene for hver bil. Ekstremt beregningstunge oppgaver, og mye vanskeligere enn problemet til den handelsreisende, ifølge 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.