International konkurrence: Forsker fra Roskilde Universitet udviklede bedste løsning til ruteplanlægning

Selv små forbedringer i ruteplanlægning kan spare eksempelvis transportfirmaer en masse penge samtidig med, at det sparer energi og dermed kan føre til en reduktion af miljømæssige omkostninger.

I en nyligt afholdt international konkurrence, organiseret af internethandelsvirksomheden Amazon og det amerikanske universitet Massachusetts Institute of Technology (MIT), skulle deltagerne udvikle innovative løsninger i form af algoritmer, som inddrager nyttig viden fra erfarne chauffører.

Vinderholdet i Amazon Last Mile Routing Research Challenge bestod af lektor emeritus Keld Helsgaun, Institut for Mennesker og Teknologi på Roskilde Universitet, professor William Cook, University of Waterloo, Canada, og lektor Stephan Held, Universität Bonn, Tyskland.

I det virkelige liv følger erfarne chauffører ikke nødvendigvis matematisk optimerede ruter, fordi chaufførerne i stedet udnytter deres viden om, hvilke veje der er vanskelige at køre på, hvor trafikken er tæt, hvor og hvornår det er let at finde en parkeringsplads, hvilke kunder der bekvemt kan leveres til i umiddelbar rækkefølge efter hinanden, pakkestørrelser og mange andre faktorer, der ikke bliver taget højde for i eksisterende ruteoptimeringsmetoder.

Derfor blev deltagerne i konkurrencen bedt om at bestemme ruter, der – så godt som muligt – matchede ruter, som erfarne chauffører havde valgt, og den bedste løsning blev belønnet med førstepræmien på 100.000 dollars.

”Det udviklede software kan meget hurtigt – på få sekunder – opnå ruter, der matcher ruter bestemt af erfarne chauffører. Denne hastighed muliggør optimering i realtid, hvor køretider og leveringer løbende kan opdateres,” siger lektor emeritus Keld Helsgaun om den løsning, der sikrede ham og hans hold konkurrencens førstepræmie.

Mere end 2.000 deltagere

Konkurrencen var delt op i to dele. I den første del skulle deltagernes algoritmer lære chaufførernes viden ud fra cirka 6.000 historiske ruter, og i den anden del skulle de udviklede modeller benyttes til at planlægge cirka 3.000 ruter, hvor chaufførernes ruter var ukendte for deltagerne. Deltagernes beregnede ruter blev tildelt en score ud fra, hvor meget de afveg fra chaufførernes ruter.

Vinderholdets metode er baseret på en udvidelse af Keld Helsgauns løsning af et velkendt problem inden for den videnskabelige disciplin operationsanalyse, kaldet ’Den rejsende sælgers problem’, som kort fortalt går ud på at bestemme den korteste rundtur mellem en række byer. Keld Helgauns udvidelse gør det blandt andet muligt at løse generelle ruteplanlægningsproblemer.

Mere end 2.000 deltagere fra hele verden tog del i konkurrencen.

Mere information

Vinderholdets metode er beskrevet i artiklen ’Local Search with Learned Constraints for Last Mile Routing’, som indgår i publikationen Technical Proceedings of the Amazon Last Mile Routing Research Challenge, som MIT Center for Transportation & Logistics har udgivet.

Læs artiklen ’Local Search with Learned Constraints for Last Mile Routing’.