RUC-forsker vinder international konkurrence i ruteplanlægning

RUC-forsker har sammen med to internationale kolleger vundet førstepræmien i en stor konkurrence med mere end 2.000 deltagere fra hele verden, hvor datalogerne skulle udvikle løsninger, der kan hjælpe transportfirmaer til at levere hurtigere og mere effektivt.

Selv små forbedringer i ruteplanlægning kan spare penge og energi og dermed føre til en reduktion af miljømæssige omkostninger ved varetransport.

Konkurrencen med en førstepræmie på 100.000 dollars var organiseret af internethandelsvirksomheden Amazon og det amerikanske universitet Massachusetts Institute of Technology (MIT), og deltagerne skulle udvikle innovative løsninger i form af algoritmer, som inddrager nyttig viden fra erfarne chauffører.

Vinderholdet i konkurrencen med navnet 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.

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.