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.