Technische inzichten en innovaties in slimme routeoptimalisatie

Smartroute gebruikt domein-specifieke trucs om een efficiëntere ritplanning te maken dan onze concurrenten. Maar hoe werkt dat dan echt?

Het optimaliseren van een ritplanning bestaat uit twee fases. Eerst wordt er
een eerste “geldige” planning gemaakt. Dat heet de initialisatie. Dat is een
planning die aan alle regels voldoet, maar nog niet optimaal is. Die regels
kunnen tijdvakken zijn, maar ook capaciteitsbeperkingen, milieuzones,
maximale actieradius; de lijst is lang.

Als er eenmaal een geldige planning is, dan kan deze worden verbeterd. Dat
gebeurt door een wijziging in de planning te maken, waarbij de planning
geldig blijft en efficiënter wordt. Daar zullen we in een latere blog iets over
schrijven, hier beperken we ons tot de initialisatie.

Die initialisatie is belangrijk. Veel mensen denken dat een planalgoritme “de
beste planning” berekent. Dat is niet het geval. Ritplanning is zo ontzettend
complex, dat het al een uitdaging is om een “goede planning” te berekenen. Er
is zelfs wiskundig geen praktisch haalbare methode om van een gegeven
planning te bepalen of dit de beste planning is, laat staan dat het mogelijk is
om die beste planning te vinden.

Dit komt omdat er bij een beetje planning (een paar honderd stops en enkele
chauffeurs) al een astronomisch aantal verschillende planningen mogelijk zijn.
Veel meer dan het aantal atomen in het heelal. Zelfs het beste algoritme kan
maar een te verwaarlozen aantal mogelijkheden doorrekenen. Waar het dus
om gaat is dat de mogelijkheden die geprobeerd worden, zo slim mogelijk
worden gekozen.

Wij vergelijken dit probleem vaak met een berglandschap, waarbij een
bergbeklimmer moet proberen zo hoog mogelijk te komen. De bergbeklimmer
klimt omhoog en gebruikt daarbij allerlei technieken om zo hoog mogelijk te
komen. Hoe beter de klimmer, hoe hoger deze kan komen. Dat kan je
vergelijken met de optimaliseerstappen.

Maar de keuze van de berg is natuurlijk ook heel belangrijk. Je kunt namelijk
nooit hoger klimmen dan de berg hoog is, en misschien staat er achter de berg
die gekozen wordt wel een hogere berg. We noemen dit dat de optimalisatie op
een lokaal maximum terecht komt.

In de wiskunde is dit een standaardprobleem waar door heel veel slimme
mensen al heel lang over nagedacht is. Er zijn dan ook standaard oplossingen
om een initiële planning te maken, bijvoorbeeld een “grand tour”. Dan worden
eerst alle stops in één lange keten gezet en wordt daar de kortste weg langs
bepaald. Dat kan met een Traveling Salesman Algoritme opgelost worden.
Vervolgens wordt die rit in stukken gehakt, allemaal groot genoeg zodat ze net
in de werktijd van één rit vallen. Daarmee krijg je een hele nette verdeling van
regio’s op de kaart. De planning die hier uitkomt is al een hele aardige
planning. Met deze aanpak kies je dus een hoge berg uit. Probleem opgelost.
Behalve dat het in de praktijk niet zal werken. Want, die stop in Groningen
moet in een vrachtwagen met een heftruck, en de twee stops in Amsterdam die
naast elkaar liggen kunnen niet bij elkaar in één wagen, omdat dit bij elkaar te
zwaar zou zijn. En die rit naar Arnhem moet per se door een rit met twee
medewerkers gereden worden en er is een stop in Middelburg die voor 11:00
moet, maar óók een stop die na 16:00 moet.

Wij gebruiken deze methode ook, maar deze werkt alleen als er nauwelijks
restricties zijn. Als er wél restricties zijn, dan levert deze methode simpelweg
geen geldige planning op. De echte wereld is de vijand van standaard
optimalisatietechnieken.

Hoe Smartroute in zo’n situatie een initiële planning aanpakt, is net als een
echte planner. Een mens. Smartroute gaat eerst de moeilijk inplanbare stops
inplannen, en plant de rest er dan omheen. Elke planner in Utrecht weet dat
als je een lading in Groningen hebt wat 80% van je capaciteit opslokt, je dan de
rit moet starten met die stop. Wij doen dat ook. In combinatie met alle andere
inzichten die een planner in dít domein heeft.

Het is de specifieke casus wat bepaalt wat een moeilijk inplanbare stop is.
Soms zijn dat de stops die ver weg liggen. Soms zijn dat stops die maar door
één of een beperkt aantal medewerkers gedaan kunnen worden, bijvoorbeeld
omdat er bepaalde vaardigheden nodig zijn. Soms is dat omdat een stop een
heel krap tijdslot heeft. Wat Smartroute doet, is uw planvraag analyseren en
een plan van aanpak kiezen die past bij de werkelijkheid waarin u aan het
werk bent.

Hoe vertaalt dit zich naar het beeld van de bergbeklimmer? Stel we zouden
deze aanpak niet doen, maar de standaardaanpak kiezen. Dan zou de zware
lading in Groningen niet in de rit passen, en is de oplossing om deze in de
initialisatie nog niet in te plannen. Dat probleem wordt dan overgelaten aan de
optimalisatiestappen. Er is dan wel een rit naar Groningen, maar die zit vol. De
optimalisatie zal dan de eerste planning behoorlijk moeten afbreken en
aanpassen, om die stop in Groningen nog een plek te kunnen geven. Dat doet
afbreuk aan het uiteindelijk haalbare resultaat.

Een goede planner begint niet met de makkelijke orders. Die bewaart hij juist
voor het laatst. Hij begint met de orders waarvan hij weet dat ze lastig worden.
Dat is precies wat Smartroute ook doet. Niet omdat daar een wetenschappelijk
artikel over bestaat, maar omdat de praktijk daarom vraagt. En juist daardoor
ontstaat uiteindelijk een efficiëntere planning.

In onze vorige blog stelden we dat de planningen die Smartroute maakt in de regel efficiënter zijn dan die van onze concurrenten. Waar baseren wij dat op?

Omdat onze klanten vaak reageren met “put your money where your mouth is”. Dat doen we dan ook. Wij bieden klanten standaard de mogelijkheid om vrijblijvend een planvraag door Smartroute te laten doorrekenen en deze te vergelijken met de planning die gemaakt wordt door het pakket wat op dat moment in gebruik is.

Dat hebben we inmiddels meer dan 100 keer gedaan, waardoor we inmiddels met alle pakketten die er zijn al meerdere vergelijkingen hebben gemaakt.

We proberen dat zo eerlijk mogelijk te doen, om echt appels met appels te vergelijken. Een conclusie trekken uit twee planresultaten is lastig, omdat de kwaliteit van het planalgoritme maar één van de factoren is. Wat ook speelt zijn dezelfde restricties, vergelijkbare kaartdata en vergelijkbare snelheden. Dat is complexer dan het lijkt.

Het is een wiskundig gegeven dat een optimalisatieresultaat in de regel beter wordt als er minder restricties zijn. Anders gezegd: restricties beperken per definitie de oplossingsruimte. Om een eerlijke vergelijking te maken, moeten de restricties dus hetzelfde zijn. Het gaat dan bijvoorbeeld om de toegestane tijdsduur van de ritten. De ritplanning die Smartroute genereert, moet als een geldige planning gezien worden door het pakket waarmee we vergelijken. Wat we daarom regelmatig doen, is onze planning importeren in het andere pakket, waarbij we dat toetsen. Daarmee borgen dat we met dezelfde restricties werken.

Een routeoptimalisatie-algoritme probeert de beste planning te vinden, gegeven de wegenkaart. En een wegenkaart is variabel. Enerzijds in de tijd: Oude kaartdata heeft andere wegen. Maar in de kaartdata zitten ook verkeersregels ingesloten die kunnen verschillen. Zo kan een bepaalde weg soms wel en soms niet geschikt geacht worden om over gereden te worden. Denk bijvoorbeeld aan een pont, of een weg in de stad die alleen in de ochtend voor laden en lossen gebruikt mag worden. Als de gehanteerde kaartdata verschilt, dan zal ook de planning verschillen. Het pakket wat de meeste wegen tot zijn beschikking heeft, heeft een voordeel.

Dit geldt nog meer voor snelheden. In kaartdata zijn natuurlijk maximale snelheden verwerkt, maar ook een inschatting van praktisch haalbare snelheden. En die verschillen ook in de tijd en per aanbieder van kaartdata. En ook hier geldt weer dat het planpakket die uitgaat van de hoogste rijsnelheden een voordeel heeft.

Het mooiste zou zijn als we zouden kunnen borgen dat we in de vergelijking precies dezelfde kaartdata en precies dezelfde snelheden gebruiken, maar dat is niet haalbaar. Daarom doen we het beste wat wél mogelijk is: Wij ijken de te gebruiken rijsnelheid, zodat de vergelijking eerlijk wordt.

Hoe doen we dat: We lezen het planresultaat wat door een ander pakket gegenereerd is in Smartroute in. Dan rekenen we deze ritplanning door in Smartroute zonder deze te veranderen. We variëren dan de snelheden, totdat Smartroute op precies dezelfde totale rijtijd uitkomt als het pakket waarmee we vergelijken. Dan vergelijken we appels met appels.

Met die gevonden correctie(factor) maakt Smartroute dan een eigen ritplanning. Daarmee borgen we dat verschillen in kaartdata en gebruikte snelheden gemiddeld genomen geen oorzaak van een optimalisatieverschil kunnen zijn.

Elke keer als we op deze manier benchmarken dan blijkt consequent dat Smartroute tussen de 7% en 15% efficiëntere planningen maakt dan andere pakketten.

Eén van onze USP’s is dat wij gemiddeld zo’n 10% betere planningen maken dan onze concurrenten. We merken wel eens dat klanten dat met een korreltje zout nemen, want hoezo zouden wij opeens iets beters hebben dan alle andere partijen?

Het eerste deel van het antwoord is dat “alle andere partijen” in werkelijkheid meevalt, omdat bijna alle pakketten in onze branche niet zelf de optimalisatie van de ritten berekent, maar deze technologie in huis haalt bij een zeer klein aantal aanbieders, zoals Google en Graphhopper. Het aantal partijen dat feitelijk zelf een algoritme hebben ontwikkeld is zeer klein.

Maar dan nog is het gek dat grote partijen zoals Google tot minder efficiënte planningen komen? Ook dat valt mee, wij zijn niet slimmer dan Google – wij spelen een beetje vals.

Er is natuurlijk een enorme basis aan wiskundige kennis (algoritmes en heuristieken) om tot de beste optimalisatieresultaten te komen en ook onze collega’s zetten dat allemaal in. Maar, die standaardoplossingen zijn gericht op generieke problemen, en niet per se op ritplanning in het bijzonder. Want, en dit is belangrijk, de algoritmes die gebruikt worden voor ritplanning (het Vehicle Routing Problem) worden niet alleen gebruikt voor het plannen van routes. Ook bij het ontwerpen van chips en netwerkcommunicatie worden dit soort algoritmes gebruikt.

In de wetenschap worden vooral algoritmes beschreven die in elke situatie werken. En de bouwers van transportplanning-algoritmes gebruiken normaal gesproken deze algemeen toepasbare algoritmes.

Hier snijden wij de bocht af: wij hebben ons algoritme aangepast aan de vraagstukken die in de praktijk van routeoptimalisatie echt spelen. Wij anticiperen er dus op dat we geen planvraag krijgen waarin 10000 stops in een rit terecht kunnen komen, of er 1000 chauffeurs ingezet moeten worden. Althans, dat laatste kan bij Smartroute zeker wel, maar dat hoeft niet per se in één planning, dat lossen we op met segmentering. Het algoritme hoeft er dus geen rekening mee te houden.

Waarom werkt dat? Ritoptimalisatie is erg groot probleem, in de zin dat er een onvoorstelbaar aantal mogelijke planningen gegenereerd kunnen worden aan de hand van een redelijk normale planvraag, van bijvoorbeeld 3000 stops over 40 ritten verdelen. Wij vergelijken het aantal oplossingen wel eens met het aantal atomen in het heelal, maar eigenlijk is dat een gekke vergelijking. Zoveel atomen zijn er by far niet.

Geen enkel plansysteem kan dan ook maar de kleinste fractie van het aantal mogelijkheden doorrekenen. En geen enkel planpakket kan de beste oplossing geven. Sterker nog: Er bestaat geen praktische wiskundige oplossing om te bepalen of een bepaalde oplossing de beste oplossing is, ook al laat je alle computers op de wereld 100 jaar rekenen.

Waar het dus om gaat is de keuze welke opties er worden doorgerekend en hoe dat gebeurt. Smartroute neemt een voorschot op mogelijkheden die bij voorbaat al afvallen. Daarmee zijn er al veel minder mogelijkheden.

Maar belangrijker: Met hoe meer mogelijkheden een algoritme rekening moet houden, hoe langer de rekentijd. Heel veel trucs die algoritmes kunnen doen om een net iets betere planning te maken zouden een enorme rekentijd vergen, als ze zouden moeten kunnen werken onder alle omstandigheden. Om die reden worden in de wetenschap deze methodes nauwelijks beschreven, omdat ze niet generiek toepasbaar zijn. En dat leidt er weer toe dat dit soort methodes niet breed gebruikt worden in ritoptimalisatie-algoritmes.

Wij doen dat wel. We zetten ook nog een andere ongebruikelijke stap: Ons algoritme begint met het analyseren van de planvraag. Afhankelijk van de omvang en het karakter van de planvraag (veel of weinig stops, beperkende tijdvensters, kleine actieradius, moeite om binnen de maximale capaciteit te blijven, etc.) worden verschillende heuristieken (de trucs) wel of niet ingezet. Daardoor levert ons algoritme een betere planning op, en is de rekentijd ook heel kort.