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 internethandelstt备用网址en 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’.