Technische inzichten en innovaties in slimme routeoptimalisatie

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.