Smarttelefonen har lastet ned budruta som Magnus Akerholt skal ut på i mørket, utenfor Tønsberg. Rekkefølgen på leveringsstedene er resultatet av en optimeringsjobb med mange milliarder mulige løsninger.
Optimering:
• Er en gren av anvendt matematikk. Brukes til å minimere eller maksimere størrelser som er funksjoner av andre størrelser.
• Innen logistikk kan optimering eksempelvis sørge for at transportoppdrag utføres med færrest mulig kjørte kilometer (minimering). Dette er synonymt med å begrense drivstofforbruk og tilhørende miljøutslipp.
• Alternativt kan målet være å maksimere størrelser som kapasitetsutnyttelse og profitt.
Distribution Innovation AS:
• Etablert i 2001. Eies av Aftenposten AS, A-Pressen Lokale Medier AS og Edda Media AS.
• Leverer løsninger for distribusjon av medieprodukter.
• Har bl.a. utviklet “eBudboka”, en dynamisk elektronisk budbok, som erstatning for den papirbaserte boka til budene, pluss en web-basert løsning for planlegging av logistikken.
• Via smarttelefoner brukes eBudboka av mer enn 7000 bud i Norge Sverige og Finland.
Verdensrekord:
I to lyse måneder våren 2004 har den nederlandske masterstudenten Erik Zijp sommerjobb ved SINTEFs Oslo-kontor. Utstyrt med PC og regneverktøyet Spider 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, og rekorden hans står fortsatt.
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.
OPPGAVE: Klarer du denne oppgaven? (Velkjent akadamisk standardoppgave for eksperter på optimering). Du driver et firma og skal levere varer fra et lager (det røde punktet på dette «kartet») til 261 kunder (de grå punktene). Du har 25 jevnstore varebiler til disposisjon. Hvordan fordele bilene mellom kundene og ordne leveringsrekkefølgen for hver bil slik at total kjørelengde blir kortest mulig?
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:
LØSNING: Her er verdens beste løsning til nå på denne optimeringsoppgaven, som eksperter i faget har brynt seg på siden 1976. Fargene viser fordelingen av kunder mellom bilene. Strekene er ruta for hver bil.
– 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.
Annonse
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.
