Routeplanning

maandag, 20 december 2004

Ook een complexe routeplanning? Heeft u ook een ingewikkelde routeplanning? Bekijk de routeplanner voor Nederland. of neem direct contact op met SUMit!
Ongepland, ga met de muis op de kaart

Ook een complexe routeplanning?

Heeft u ook een ingewikkelde routeplanning?

Bekijk de routeplanner voor Nederland.

of neem direct contact op met SUMit!

Ongepland, ga met de muis op de kaart

En ik denk dat het onmogelijk is

Marc Wesselink kijkt me met een grote grijns aan na het poneren van zijn stelling. Hij heeft net een ongelofelijk complex routeplaningsprobleem uitgelegd. Zijn bedrijf, de VCC Groep voert controles uit voor Arbodiensten.

Een groot aantal controleurs bezoekt honderden ziek gemelde werknemers.
Elke controleur moet zo min mogelijk reizen.
Elke controleur vertrekt en eindigt thuis.
Er zijn spoedeisende huisbezoeken die voor een bepaalde tijd klaar moeten zijn.
Vaste medewerkers gaan voor oproepkrachten

Probleem: Welke controleur doet welke huisbezoeken?

Demo Handelsreiziger

En ik denk dat ik op internet een demo kan geven

Marc hoort m'n brutale antwoord lachend aan en wijst naar z'n desktop computer. Ga je gang!

De demo van de handelsreiziger duurt kort, enkele seconden.

De demo genereert razendsnel een uitstekende route voor tientallen, zelfs honderden punten. Zodra Marc een goed geplande route ziet wordt hij enthousiast.

Ter vergelijking laat hij een andere routeplanner zien, die het al zwaar heeft met vier punten voor één controleur. Routeplanning is een vak apart. De SUMit demo is heel snel, maar het heeft me 20 jaar gekost om het algoritme te bedenken.

Marc heeft duidelijk al goed research gedaan naar andere routeplanners, niets passends gevonden en is daarom nu zo aangenaam verrast. Zijn enthousiasme beschouw ik als een groot compliment, van iemand die echt beseft hoe moeilijk routeplanning is.

Maatwerk routeplanner

Een paar honderd theoretische demo punten plannen is al ingewikkeld genoeg. Een werkelijke applicatie is nog complexer door een aantal constraints:

Een deadline is pas controleerbaar als de route tot dat punt bekend is.
De reistijden zijn sterk afhankelijk van het locale wegennet. Postcode.nl levert reistijden tussen 4.000 postcodes, mooi maar wel een flinke matrix van wel 16 miljoen cellen.
Het aantal mogelijke routes is astronomisch voor de honderden punten en tientallen controleurs, een potentieel performance issue. Het kost menselijke planners één tot anderhalf uur om efficiënte routes te plannen.

Liggend met potlood en papier puzzel ik in alle rust een algoritme uit. Wekenlang ligt het grote kleed in m'n werkkamer bezaaid met schetsen van punten, matrixen, getallen, reistijden en routes. De kikker moet diverse keren bijspringen.

Uiteindelijk komt er een variant op m'n handelsreiziger algoritme boven borrelen. Het is te complex om uit het hoofd te controleren. Op papier test ik het met een handjevol punten. Hoera, het algoritme lijkt te werken, maar ik twijfel nog over een performance optimalisatie. Ik moet afstand nemen van deze puzzel om het te overzien. Starend over de weilanden vanuit een treincoupé valt het laatste puzzelstukje op z'n plaats.

Binnen 1 minuut een uitstekende planning

De programmeerfase is relatief kort. Een maand later is de Java routeplanning applet klaar, inclusief een PHP systeem dat alle data via een interface in bulk aanlevert.

De routeplanning werkt, goed en razendsnel. Binnen een minuut staat de gegenereerde planning voor 400 huisbezoeken in beeld.

De kwaliteit van de routes is goed.

Het wegennet wordt goed gebruikt, snelwegen voorop, vooral buiten de Randstad. De dijk naar Lelystad wordt bijvoorbeeld mooi in de routes opgenomen.
Controleurs in de grote steden maken vooral veel korte ritten.
Aan de constraints is voldaan. Alle deadlines zijn gehaald en het overwerk is tot nul gereduceerd.

Door de snellere planning kunnen de controleurs eerder de weg op. Dus heeft u zich ziek gemeld? Zet dan vooral een wekker, want de controleur komt voortaan een uurtje eerder langs!

Tot de volgende noot,
Henk Jan Nootenboom

Grafische vormgeving offerte: Mohamed Gelle (Grafisch Lyceum Rotterdam)
Grafische vormgeving routeplanning applet: (Sara Borremans)