Forskningsrådets nettsider benytter seg av informasjonskapsler for å forbedre din opplevelse av nettstedet.
Ved å lukke denne meldingen, samtykker du i vårt bruk av informasjonskapsler. Personvernerklæringen finner du her.
Lukk påminnelse
Gå direkte til innhold

Best i verden på ruteplanlegging

Norske forskere lager transportruter som knuser de fleste. Industrien kan spare opp til 40 prosent av transportkostnadene ved å la en datamaskin finne de beste rutene.

Bedre ruteplanlegging kan kutte både transport- og miljøkostnader. (Foto: Shutterstock)

– Forskningen ligger langt foran industriens praksis på dette feltet, sier Marielle Christiansen. Hun er professor ved Institutt for industriell økonomi og teknologiledelse ved NTNU, og leder prosjektet DOMinant II.

Forskerne tar for seg transportoptimering, og forsøker å redusere gapet mellom forskningsfronten og praksisen for norsk og internasjonal transport på sjø og vei. Ved NTNU, SINTEF og Høgskolen i Molde utvikler de nye modeller og algoritmer for regnetunge optimeringsproblemer.

Å planlegge en transportrute er nemlig ikke så enkelt som det kan høres ut. Selv med en superrask datamaskin er det ingen garanti for å finne den aller beste løsningen. – Grunnen er at det er så veldig mange muligheter, sier Christiansen.

En handelsreisendes problem

Marielle Christiansen er professor ved NTNU. (Foto: Silje Kristin Asbjørnsen / Fotograf Schrøder) Tenk deg en selger som skal ut og besøke kunder. Selv om det bare er snakk om 50 stoppesteder, kan han nå dem i ufattelig mange forskjellige rekkefølger. Faktisk flere enn det finnes sandkorn på jordkloden. Antallet mulige reiseruter nærmer seg mengden atomer i universet.

Utfordringen er å finne den rekkefølgen som gjør at han bruker kortest tid eller reiser den korteste distansen. – Dette er et veldig enkelt problem sammenlignet med de vi jobber med, sier Christiansen.

Ett av problemene forskerne bryner seg på, kan skisseres slik: Flere kjøretøy skal gjøre oppdragene, og vi må bestemme hvor mange kjøretøy vi skal ha, og kapasiteten til hvert av dem. Skal vi kjøre mange små biler eller færre, store lastebiler? – Dette har vi jobbet mye med innen maritim sektor, og da er det en flåte skip det dreier seg om, sier Christiansen.

En annen type problem integrerer lagerstyring og ruting. Tenk deg flere steder i verden hvor varer blir produsert, i tillegg til flere steder hvor forbrukere kjøper varene. Om det er sjøtransport, gjelder det å komme med skip til produksjonsstedene før lageret der blir fullt, og i tillegg må varene komme til butikklageret før det går tomt.

Evaluerer fornuftig

Tilbake til den handelsreisende og de ubegripelig mange mulighetene han står overfor i sitt enkle problem. Han er lykkelig uvitende om dette, setter prikker på kartet sitt, og lager ganske kjapt og intuitivt en helt grei reiserute mellom dem.

Finn den raskeste løsningen som starter i depotet (rød prikk), besøker alle kundene (svarte prikker), og returnerer til depotet. (Illustrasjon: Marielle Christiansen)

I den enorme haugen av muligheter er det nemlig veldig mange som er elendige, med tanke på å korte ned kjøreturen. For eksempel lønner det seg ikke å kjøre sikksakk mellom de punktene som ligger lengst fra hverandre. Menneskehjernen er ganske god til å planlegge sånn sett.

Når problemene blir mer kompliserte, som nevnt over, klarer ikke tenketoppen helt å henge med lenger. Det er her datamaskinene kommer inn, men selv ikke de kan regne på alt. – Vår oppgave er å evaluere mulighetene på en fornuftig måte, slik at vi ikke trenger å undersøke alle løsninger, sier Christiansen.

Forskerne utvikler altså metoder som dominerer vekk noen løsninger underveis i søket etter de som virkelig er gode. – Både det å utvikle matematiske modeller, og hvordan løse de matematiske modellene, handler veldig mye om hvordan vi kan klare å fjerne mange av løsningene som ikke er gode, og søke i en retning som ligger opp mot det optimale, sier prosjektlederen.

Papir og blyant

I dag finnes det veldig få kommersielt tilgjengelige systemer for beslutningsstøtte for denne typen problemer. – Det er helt i forskningsfronten å utvikle systemer som industrien kan ta i bruk, sier Christiansen.

Fremdeles lages transportruter ved hjelp av veldig enkle tommelfingerregler og regneark, eller bare papir og blyant. – De siste årene er det mange bedrifter som har tatt kontakt med oss, fordi de ser behovet for å utvikle systemer for beslutningsstøtte, sier prosjektlederen.

Geir Hasle er sjefforsker ved SINTEF IKT. (Foto: Mari Hasle Hagelund) For lagerstyrt ruteplanlegging har SINTEF utviklet et system kalt Invent (inventory routing solver). Dette har blitt videreutviklet i DOMinant II, og er sentralt i prosjektet. Systemet har allerede sørget for store innsparinger innen transport av flytende naturgass (LNG). Det brukes av GDF SUEZ, et av verdens største energiselskap.

– Vi har langsiktig samarbeid med dem om videreutvikling av Invent, og er i ferd med å inngå lisensavtale. SINTEF har også inngått lisensavtale med Tieto for spredning til andre energiselskap, sier sjefforsker Geir Hasle ved SINTEF IKT.

Miljøgevinster

Christiansen forteller også om prosjekter i samarbeid med Statoil, med inntjening på opptil 40 prosent av transportkostnadene. Et tidligere prosjekt for Yara (tidligere Norsk Hydro) viste potensial for inntjening på rundt 25 prosent med planlegging ved hjelp av systemer for beslutningsstøtte.

– Det er vanskelig å si noe generelt om hva potensialet er, både når det gjelder innsparinger og miljøgevinst, for det kommer an på planleggingsproblemet og hvor godt planleggingen gjøres før datasystemene kommer inn, sier Christiansen.

Når det gjelder miljøgevinster, jobber forskerne for eksempel med variert hastighet på skipene. Jo saktere de går, jo mindre er utslippene. – Skip ligger ofte og venter utenfor havnen. Isteden kan de redusere farten underveis, og dermed redusere forbruket av drivstoff. Det gir både store miljøgevinster og reduserte transportkostnader, sier Christiansen.

Hun understreker at mange manuelle planleggere er uhyre dyktige, men jo mer komplisert og uoversiktlig problemet blir, jo større blir også forskjellen mellom manuell planlegging og et beslutningsstøttesystem.

Kombinerer metoder

Et dataprogram finner den beste ruta når aviser og pakker skal leveres. (Foto: Distribution Innovation) Forskerne har også drevet mye med grunnforskning knyttet til å finne gode modeller og løsningsmetoder, slik at disse i utgangspunktet uhyre kompliserte optimeringsproblemene kan angripes med metoder som enkelt kan benyttes i den praktiske verden.

Arbeidet går langs to akser - det som kalles eksakte metoder, hvor man er garantert å finne den optimale løsningen på et problem hvis det lar seg løse, og noe som kalles heuristikker, som er intelligente tommelfingerregler. Heuristikkene brukes når problemet er så komplisert at man ikke er garantert å finne den optimale løsningen innen tiden som er til rådighet. – Da jobber vi for å komme så nær som mulig, forklarer prosjektlederen.

Ved å blande disse to aksene, får de norske forskerne til noe som er bedre enn før. Det norske miljøet er veldig langt framme internasjonalt. – Innenfor flere problemer er vi verdensmestere, forteller Christiansen.

Verdens forskere innen transportoptimering jobber nemlig på måter som kan tilsvare verdensmesterskap. De bruker definerte testinstanser som forskere verden rundt bryner seg på. Gruppen ved SINTEF har for eksempel definert flere nye instanser innen noe som kalles Mixed Capacitated General Routing Problem, og utviklet en metode som er så effektiv at den produserer de beste kjente løsninger på nesten alle standard testeksempler.

Så langt har industrien nølt med å ta i bruk beslutningsstøttesystemer for transportoptimering, men forskerne mener det er i ferd med å skje en endring. Det skjer en rasende utvikling innen hardware, slik at selskapene får råd til å kjøpe nok datakraft. Selskaper vokser og fusjonerer, noe som gjør planleggingsproblemene mer kompliserte, og vanskeligere å takle manuelt.

– Planleggerne er dessuten av en annen type enn tidligere, med akademisk bakgrunn. De er mer åpne i forhold til å ta i bruk slike systemer. Det er viktig å understreke at det fortsatt er bruk for planleggeren. Noen har vært redde for jobbene sine, men de vil bare få en litt annerledes jobb, sier Christiansen.

Avisbud

Spider er et optimeringsverktøy som bedrer rutene for budene i avisbransjen. Slik ser det ut på smarttelfonen som budet bærer med seg. (Foto: Distribution Innovation) Tone Løyland er administrerende direktør i Distribution Innovation, et selskap som lager logistikkløsninger til avisbransjen. De har vært med på utviklingen av et kommersielt tilgjengelig optimeringsverktøy kalt Spider, sammen med SINTEF.

– Det som het avisbud før, leverer nå i tillegg bøker, magasiner og pakker. De har med seg en smarttelefon som forteller hvem de skal levere til, i hvilken rekkefølge, hvilken nøkkel de trenger, og hvilken etasje og leilighet de skal til, forklarer hun.

– De som drev med manuell planlegging tidligere, hadde en veldig yrkesstolthet, og kunne ofte geografiene veldig godt. I dag har de fått ansvar for større geografier enn tidligere, så det er ingen som har mistet jobben på grunn av dette. Tvertimot har virksomheten blitt utvidet fordi budene har fått tid til pakkelevering også, sier Løyland.

Hun forteller at den største utfordringen er datagrunnlaget. Ikke alle har adresse, og veinettet er ikke fullstendig. I tillegg er det ikke alt datamaskinen skjønner ut fra kartene. Når budene skal inn i bakgårder i byene, kan det for eksempel hende at de ikke trenger gå ut igjen, men kan komme til neste dør via en gang. Selskapet har også jobbet mye med tidsparameterne for å få gode anslag på hvor lang tid leveringen vil ta, men her har de kommet frem til en modell som nå fungerer ganske bra.

– Vi har samarbeidet med SINTEF i mange år, så forskerne er etter hvert godt kjent med våre behov. Vi har vært veldig heldige og fått mye ut av samarbeidet, sier Løyland.

Fakta om prosjektet

Navn: Discrete Optimization Methods in Maritime and Road-based Transport II
Periode: 2011-2015
Ansvarlig institusjon: Institutt for industriell økonomi og teknologiledelse ved NTNU
Prosjektleder: Marielle Christiansen
Finansiering: 10,7 millioner fra Forskningsrådets program eVITA
Samarbeidspartnere: SINTEF, Høgskolen i Molde, CIRRELT og GERAD i Canada, INRIA i Frankrike, University of Aveiro og CIDMA i Portugal

Se også DOMinant II-prosjektets hjemmeside

 

eVITA

Forskningsrådets program for eVitenskap – eVITA – handler om å utvikle nye arbeidsformer og forskningsmetoder basert på elektronisk infrastruktur for å håndtere store mengder digitale data.

eVITA støtter forskning på beregnings- og dataintensive vitenskapelige og industrielle utfordringer.

 

Skrevet av:
Kristin S. Grønli
Publisert:
24.11.2014
Sist oppdatert:
13.09.2016