Route Planning

Monday, 20th December 2004
Unplanned, move mouse to the map
Route Planning Problem

Complex route planning?

Got a complex route planning problem?
Contact SUMit!
So, I think it is bloody impossible

Marc Wesselink gives me a big, big grin after posting his opinion. He just explained an incredible complex route planning problem. His company, the Dutch VCC Groep performs medical inspections on employees who reported ill.

Problem: Which inspector performs which visits?

Demo Travelling Salesman

Well, I think I can give you an Internet demo

Marc smiles as he hears my bold answer an points at his desktop computer. Be my guest!

The Travelling Salesman demo lasts just a few seconds.

The demo quickly generates an excellent route for dozens, even hundreds of points. As soon as he sees a well planned route, Marc gets enthusiastic.

As a reference he shows another route planner, having a tough time with only four points for one single inspector. Well, route planning is a tough job. The SUMit demo may be fast, but it took me 20 years to invent the algorithm.

Obviously Marc has done thorough research and evaluated several other route planners. He must be so delighted now, as this is the first suitable solution he sees. I take his enthusiasm as a great compliment, from a bloke who really understands how tough excellent route planning really is.

Tailor made route planner

Planning a few hundred hypothetical points for a demo is tough enough as it is. A real application is even more complex as several constraints apply: I lay down with paper and pencil to invent an algorithm. For weeks the big carpet in my office is covered with sketches of points, matrices, numbers, travel times and routes. I need the frog's assistance several times.

A variation to my own travelling salesman algorithm bubbles up. It is too complex to validate it by thought alone. On paper I test it with just a couple of points. Hurray, the algorithm seems to work, but I still have a bit of doubt on a performance optimisation. I need to stand back to get the overview. Staring at the flat Dutch country side from a train the last piece of the puzzle drops into it's place.

An excellent planning in 1 minute

The programming phase is shorter. After a month the Java route planning applet is ready, including a PHP system that supplies all data via an interface in bulk.

The route planning works, fast and good. Within a minute it shows the generated planning for 400 visits.

The quality of the routes is good.

As planning is now a matter of just minutes, the inspectors hit the road earlier. So, are you reported ill in the Netherlands? Set an alarm clock, as the inspector will arrive an hour earlier.

Till next nut,
Nut

Graphic design quotation: Mohamed Gelle (Grafisch Lyceum Rotterdam)
Graphic design route planning applet: (Sara Borremans)