Over hele landet leverer hundretusener av sjåfører pakker og pakker til kunder og bedrifter hver dag, og mange av dem har en gjennomsnittlig leveringstid på bare noen få dager. Å koordinere en forsyningskjede i denne størrelsesorden på en forutsigbar og tidsriktig måte har lenge vært et problem innen operasjonsforskning, der forskere har arbeidet med å optimalisere den siste delen av leveringsrutene. Årsaken er at den siste fasen av prosessen ofte er den mest kostbare på grunn av ineffektivitet som lange avstander mellom stoppestedene på grunn av økt etterspørsel fra netthandelen, forsinkelser på grunn av været, trafikk, mangel på parkeringsplasser, kundenes leveringspreferanser eller delvis fulle lastebiler – ineffektivitet som ble enda tydeligere under pandemien.

 

Med nyere teknologi og mer individualiserte og nyanserte data er forskerne i stand til å utvikle modeller med bedre rutealternativer, men må samtidig balansere beregningskostnadene ved å kjøre dem. Matthias Winkenbach, MIT Principal Research Scientist, forskningsdirektør for MIT Center for Transportation and Logistics (CTL) og forsker ved MIT-IBM Watson AI Lab, diskuterer hvordan kunstig intelligens kan gi bedre og mer beregningseffektive løsninger på et kombinatorisk optimeringsproblem som dette.

 

Q: Hva er problemet med kjøretøysruting, og hvordan løser tradisjonelle operasjonsforskningsmetoder (OR) det?

 

A: Så å si alle logistikk- og leveringsselskaper som USPS, Amazon, UPS, FedEx og DHL står overfor dette problemet hver eneste dag. Enkelt sagt handler det om å finne en effektiv rute som forbinder et sett med kunder som enten skal leveres til eller hentes hos. Det handler om å bestemme hvilke kunder hver av disse bilene – som du ser ute på veien – skal besøke på en gitt dag og i hvilken rekkefølge. Vanligvis er målet å finne ruter som fører til den korteste, raskeste eller billigste ruten. Men svært ofte er de også drevet av begrensninger som er spesifikke for en kunde. Hvis du for eksempel har en kunde som har et spesifikt tidsvindu for levering, eller en kunde som bor i 15. etasje i et høyhus og ikke i første etasje. Dette gjør det vanskeligere å integrere disse kundene i en effektiv leveringsrute.

 

For å løse ruteplanleggingsproblemet kan vi selvsagt ikke modellere uten riktig informasjon om etterspørselen og, ideelt sett, kunderelaterte egenskaper. Vi må for eksempel vite størrelsen eller vekten på pakkene som en gitt kunde har bestilt, eller hvor mange enheter av et bestemt produkt som skal sendes til et bestemt sted. Alt dette avgjør hvor lang tid du trenger for å betjene det aktuelle stoppet. For å løse realistiske problemer må du også vite hvor sjåføren kan parkere bilen på en trygg måte. Tradisjonelt har ruteplanleggeren vært nødt til å komme med gode estimater for disse parametrene, så ofte finner man modeller og planleggingsverktøy som gjør generelle antagelser fordi det ikke finnes stoppestedsspesifikke data.

 

Maskinlæring kan være svært interessant i denne sammenheng, for i dag har de fleste sjåfører smarttelefoner eller GPS-sporere, så det finnes massevis av informasjon om hvor lang tid det tar å levere en pakke. Du kan nå, i stor skala og på en noenlunde automatisert måte, hente ut denne informasjonen og kalibrere hvert eneste stopp slik at det modelleres på en realistisk måte.

 

En tradisjonell OR-tilnærming innebærer at du skriver en optimeringsmodell, der du starter med å definere målfunksjonen. I de fleste tilfeller er det en slags kostnadsfunksjon. Deretter følger en rekke andre ligninger som definerer hvordan ruteproblemet fungerer. Du må for eksempel fortelle modellen at hvis kjøretøyet besøker en kunde, må det også forlate kunden igjen. I akademiske termer kalles dette vanligvis flytkonservering. På samme måte må du sørge for at hver kunde besøkes nøyaktig én gang på en gitt rute. Disse og mange andre begrensninger i den virkelige verden definerer hva som utgjør en levedyktig rute. Det kan virke åpenbart for oss, men dette må kodes eksplisitt.

 

Når et optimeringsproblem er formulert, finnes det algoritmer som hjelper oss med å finne den best mulige løsningen. Over tid finner de løsninger som overholder alle begrensningene. Deretter prøver den å finne ruter som blir bedre og bedre, og dermed billigere og billigere, helt til du enten sier: “OK, dette er godt nok for meg”, eller til den matematisk kan bevise at den har funnet den optimale løsningen. En gjennomsnittlig varebil i en amerikansk by gjør rundt 120 stopp. Det kan ta lang tid å løse det eksplisitt, så det er vanligvis ikke det selskapene gjør, fordi det er for dyrt å beregne. Derfor bruker de såkalte heuristikker, som er algoritmer som er svært effektive til å finne rimelig gode løsninger, men som vanligvis ikke kan kvantifisere hvor langt unna disse løsningene er fra det teoretiske optimum.

Spørsmål: Dere bruker for tiden maskinlæring til å løse problemet med kjøretøyruting. Hvordan bruker dere det for å utnytte og muligens overgå tradisjonelle OR-metoder?

 

A: Det er det vi jobber med for tiden sammen med folk fra MIT-IBM Watson AI Lab. Den generelle ideen er at du trener en modell på et stort sett med eksisterende ruteløsninger som du enten har observert i en bedrifts virkelige drift eller som du har generert ved hjelp av en av disse effektive heuristikkene. I de fleste maskinlæringsmodeller har du ikke lenger en eksplisitt målfunksjon. I stedet må du få modellen til å forstå hva slags problem den faktisk ser på, og hvordan en god løsning på problemet ser ut. På samme måte som når du trener opp en stor språkmodell på ord i et gitt språk, må du for eksempel trene opp en modell for ruteinnlæring på konseptet med de ulike leveringsstoppene og deres etterspørselsegenskaper. På samme måte som du må forstå grammatikken i et naturlig språk, må modellen forstå hvordan du kan koble sammen disse leveringsstedene på en måte som gir en god løsning – i vårt tilfelle en billig eller rask løsning. Hvis du så kaster et helt nytt sett med kundekrav på den, vil den fortsatt være i stand til å koble sammen punktene bokstavelig talt på en måte som du også ville gjort hvis du prøvde å finne en god rute for å koble sammen disse kundene.

 

Til dette bruker vi modellarkitekturer som de fleste kjenner fra språkbehandling. Det virker litt kontraintuitivt, for hva har språkbehandling med ruting å gjøre? Men faktisk er egenskapene til disse modellene, spesielt transformatormodeller, gode til å finne struktur i språket – å koble sammen ord slik at de danner setninger. I et språk har du for eksempel et bestemt ordforråd, og det er fast. Det er et diskret sett med mulige ord du kan bruke, og utfordringen er å kombinere dem på en meningsfull måte. I ruting er det på samme måte. I Cambridge er det rundt 40 000 adresser du kan besøke. Vanligvis er det en delmengde av disse adressene som må besøkes, og utfordringen er: Hvordan kombinerer vi denne delmengden – disse “ordene” – i en rekkefølge som gir mening?

 

Det er på en måte det nye med vår tilnærming – å utnytte den strukturen som har vist seg å være ekstremt effektiv i språkområdet, og bringe den inn i kombinatorisk optimalisering. Ruting er et ypperlig testområde for oss, fordi det er det mest grunnleggende problemet i logistikkbransjen.

 

Det finnes selvsagt allerede svært gode rutingsalgoritmer som er utviklet gjennom flere tiår med operasjonsforskning. Det vi prøver å gjøre i dette prosjektet, er å vise at vi med en helt annen, rent maskinlæringsbasert metodisk tilnærming er i stand til å forutsi ruter som er omtrent like gode som, eller bedre enn, rutene du ville fått ved å kjøre en heuristisk ruteoptimalisering.

 

Q: Hvilke fordeler har en metode som deres i forhold til andre moderne OR-teknikker?

 

A: Akkurat nå er de beste metodene fortsatt svært ressurskrevende når det gjelder beregningsressurser som kreves for å trene opp disse modellene, men du kan legge noe av denne innsatsen på forhånd. Da er den opplærte modellen relativt effektiv når det gjelder å produsere en ny løsning etter hvert som det blir behov for det.

 

Et annet aspekt som må tas i betraktning, er at driftsmiljøet på en rute, spesielt i byer, er i stadig endring. Tilgjengelig veiinfrastruktur, trafikkregler og fartsgrenser kan endres, den ideelle parkeringsplassen kan være opptatt av noe annet, eller en byggeplass kan blokkere en vei. Med en ren OR-basert tilnærming kan du faktisk få problemer, fordi du i utgangspunktet må løse hele problemet umiddelbart når ny informasjon om problemet blir tilgjengelig. Siden det operative miljøet endrer seg dynamisk, må du gjøre dette om og om igjen. Hvis du derimot har en godt trent modell som har sett lignende problemer før, kan den potensielt foreslå den nest beste løsningen nesten umiddelbart. Det er snarere et verktøy som kan hjelpe bedrifter med å tilpasse seg stadig mer uforutsigbare endringer i omgivelsene.

 

I tillegg er optimeringsalgoritmer ofte laget manuelt for å løse det spesifikke problemet til en gitt bedrift. Kvaliteten på løsningene man får fra slike eksplisitte algoritmer, avhenger av hvor detaljert og sofistikert algoritmen er utformet. En læringsbasert modell, derimot, lærer kontinuerlig en rutingpolicy fra data. Når du først har definert modellstrukturen, vil en godt utformet modell for rutelæring finne potensielle forbedringer av rutingpolicyen din ut fra den enorme mengden ruter den blir trent på. Enkelt sagt vil et læringsbasert ruteverktøy fortsette å finne forbedringer i rutene dine uten at du trenger å investere i eksplisitt utforming av disse forbedringene i algoritmen.

 

Til slutt er optimeringsbaserte metoder vanligvis begrenset til å optimere for en klart definert målfunksjon, som ofte går ut på å minimere kostnadene eller maksimere fortjenesten. I virkeligheten er bedriftenes og sjåførenes mål mye mer komplekse enn som så, og ofte er de også motstridende. Et selskap ønsker for eksempel å finne effektive ruter, men også å ha et lavt utslippsfotavtrykk. Sjåføren vil også være trygg og ha en praktisk måte å betjene kundene på. På toppen av alt dette er selskapene også opptatt av konsistens. En godt utformet rutelæringsmodell kan til slutt fange opp disse høydimensjonale målene på egen hånd, og det er noe du aldri ville kunne oppnå på samme måte med en tradisjonell optimeringsmetode.

 

Så dette er en type maskinlæringsapplikasjon som faktisk kan ha en konkret innvirkning på industrien, samfunnet og miljøet. Logistikkbransjen har problemer som er mye mer komplekse enn dette. Hvis du for eksempel ønsker å optimalisere en hel forsyningskjede – la oss si flyten av et produkt fra produsenten i Kina via nettverket av ulike havner rundt om i verden, gjennom distribusjonsnettverket til en stor forhandler i Nord-Amerika til butikken der du faktisk kjøper det – er det så mange beslutninger involvert, noe som åpenbart gjør det til en mye vanskeligere oppgave enn å optimalisere en enkelt kjørerute. Håpet vårt er at vi med dette innledende arbeidet kan legge grunnlaget for forskning og utviklingsarbeid i privat sektor for å utvikle verktøy som etter hvert vil gjøre det mulig å optimalisere forsyningskjeden fra ende til annen.