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
Routeplanning probleem
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.

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: 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.

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)