SINTEF: SPIDER speeder opp transportoptimaliseringen
SINTEF:
SPIDER speeder opp transportoptimaliseringen
Mange transportører og distributører legger fremdeles inn sine transportplaner manuelt. Selv for relativt små virksomheter medfører dette ofte unødvendig bruk av ressurser. - En del større transportører har innført bruk av IT-baserte planleggingsverktøy som støtte i denne planleggingen, sier Atle Riise, seniorforsker ved SINTEF IKT, avdeling for anvendt matematikk. SPIDER er et slikt planleggingsverktøy utviklet av SINTEF.
- Med verktøy for transportoptimalisering snakker vi bl.a. om programvare som en transportplanlegger kan bruke for å oppnå best mulig oversikt og ressursutnyttelse, sier Atle Riise. Foto: Trond Schieldrop
Trond Schieldrop
I denne artikkelen forklarer Atle Riise hva slike verktøy gjør, hva de kan brukes til og hvorfor bruk av slike verktøy ofte kan gi store besparelser og bedre kundeservice.
For transportører og distributører går transportoptimalisering ut på å lage en plan for hvordan transporten kan bli billigst mulig, samtidig som den tilfredsstiller alle relevante føringer.
- Med verktøy for transportoptimalisering snakker vi bl.a. om programvare som en transportplanlegger kan bruke for å oppnå best mulig oversikt og ressursutnyttelse. Slike verktøy kan benyttes på flere nivåer. På det mest detaljerte nivået i den daglige planleggingen for å utnytte ressursene man har tilgjengelig i løpet av dagens transportoppdrag best mulig. På et mer strategisk nivå kan slike verktøy brukes til å bestemme behovet for ressurser (for eksempel antall biler) som er nødvendig for virksomheten. Det er også mulig å simulere konsekvensen av forskjellige valg av terminalplasseringer, forklarer seniorforskeren.
Optimaliseringsproblemer
Det fundamentale optimaliseringsproblemet som må løses kjennetegnes i optimaliseringslitteraturen som «the Vehicle Routing Problem» (VRP). En transportør utfører daglig et antall transportoppdrag med sine kjøretøy. Et VRP kan formuleres slik: Fordel flest mulig transportoppdrag på bilene og velg rekkefølge på utføring av oppdragene for hver bil. Målet er at de totale transportkostnadene blir minst mulig samtidig som kapasitetsbegrensningene på bilene overholdes.
- Allerede her oppstår det problemer fordi VRP hører til en type optimaliseringsproblemer der antall mulige løsninger (planer) eksploderer når størrelsen på problemet, gitt ved antall oppdrag, vokser. La oss for illustrasjonens skyld ta for oss et enklere og mer akademisk problem med samme egenskap - det såkalte handelsreisendeproblemet. Det kan formuleres på følgende måte:
«En handelsreisende skal besøke N byer. I hvilke rekkefølge skal byene besøkes for å minimalisere total reisedistanse?»
Eksempel på problemet med 14 byer er tegnet i figur 1. Her er også én mulig løsning tegnet inn som en strek mellom byene.
Det som gjør det vanskelig å løse VRP og handelsreisendeproblemet er at antall løsninger vokser enormt når størrelsen på problemet øker. Dette er illustrert i figur 2. Her ser vi hvor sterkt antall løsninger vokser selv ved kun moderate økninger i antall byer.
----------------------------------------------------------------------------------------------------------------
Figur 2: Antall mulige løsninger av handelsreisendeproblemet som funksjon av antall byer, N
----------------------------------------------------------------------------------------------------------------
En triviell måte å løse dette optimaliseringsproblemet på, er å måle total distanse for alle løsninger og så velge den beste. Beregningstid for dette vil være direkte avhengig av antall mulige løsninger. Figur 3 viser at selv datamaskiner som er én million ganger raskere en dagens maskiner aldri kan løse slike problemer på denne måten dersom de er av en viss størrelse.
----------------------------------------------------------------------------------------------------------------
Figur 3: Beregningstid for evaluering av alle mulige løsninger for handelsreisendeproblemet, avhengig av antall byer, N
----------------------------------------------------------------------------------------------------------------
SPIDER angriper problemet
SINTEF har gjennom mange år, og i tett samarbeid med store norske transportører, utviklet en avansert programvare for transportoptimalisering. Programvaren går under navnet SPIDER, og løser VRP-problemet ved bruk av moderne heuristiske metoder.
- Dette er metoder som kan finne gode løsninger på kort tid. Det er helt nødvendig for at programvaren kan anvendes til daglig planlegging, sier Riise, som hevder at SPIDER angriper transportoptimaliseringsproblemet med en kombinasjon av avanserte konstruksjons- og forbedringsalgoritmer.
Gitt et konkret problem, som beskrivelse av oppdrag og bilpark m.m., kan SPIDER først konstruere en initialløsning. Dette gjøres ved hjelp av en konstruktiv algoritme, som for eksempel Clark & Wrights «savings»-algoritme som Tommy Stub beskrev i forrige nummer av Logistikk & Ledelse.
- SPIDER har et repertoar av slike algoritmer, sier Riise. - Hvilken som er best, egnet avhenger av problemets art.
Riktig planleggingsstøtte
- Etter denne konstruksjonen har vi altså en transportplan, men den er neppe veldig god. SPIDER forbedrer denne planen suksessivt gjennom å prøve enkle endringer. Slike endringer kan være å flytte et oppdrag fra én tur til en annen, eller å prøve en litt annen rute for én av turene. Når en endring gir en bedre plan adopteres denne som «gjeldende plan». SPIDER prøver igjen å forbedre denne gjennom nye endringer, sier Riise.
Dette foregår interativt inntil man når en løsning som ikke kan forbedres. Da kan det hende at man har funnet den absolutt beste planen. Det er imidlertid stor sannsynlighet for at man har funnet et lokalt optimum, og at det finnes andre slike optima som gir bedre planer.
Vekselvis dialog med brukeren
SPIDER har ifølge Riise funksjonalitet til å løfte søket ut av slike lokale optima og søker videre etter enda bedre løsninger. Slik fortsetter den automatiske planleggingen til planleggeren stopper programmet etter en bestemt tid, eller når det ikke ser ut til å være mer å hente. Så returneres den ferdige planen som kan presenteres i kart, Gantt-chart eller liknende.
- En fordel med denne metodikken er at brukeren kan gjøre manuelle endringer i planen og låse disse. Deretter kan man igjen sette i gang optimaliseringen for å søke etter bedre planer, samtidig som de låste aspektene ved planen holdes fast. Gjennom en slik vekselvis dialog med brukeren gir SPIDER riktig planleggingsstøtte uten at man mister muligheten til å nyttiggjøre seg planleggerens kompetanse.
Den virkelige verden
En transportplanleggers hverdag er betydelig mer kompleks en det som fremgår i definisjonen av VRP ovenfor. Gode verktøy for transportoptimalisering må derfor håndtere en rikholdig modell av virkeligheten.
SPIDER håndterer bl.a.:
------------
SPIDER markedsføres og selges i godstransportmarkedet gjennom det SINTEF-eide selskapet GreenTrip AS ( ). Selskapet står for utvikling av planleggingsapplikasjonen SPIDER Designer hvor SPIDER inngår som optimaliseringskjernen. Andre forhandlere er TransWare AB, Locus AS og Nor-Link AS.www.greentrip.no
www.logistikk-ledelse.no© 2004