zaterdag 5 januari 2013

The Great Journey Planner

It was that time of year again. Just before Christmas I wanted to visit all my local business contacts and bring around small presents to thank them for the work done. So, we made a list of all addresses we needed to go by. We had some 82 destinations to drive to, but we did not know the optimal order to visit them.

Visual

How so you plan a route to multiple locations? We started with a visual apprach, mapping all addresses on a map. But there were some addresses of suppliers that we only called and e-mailed with. We had no good idea where to put them on the map exactly.

The next thing we did, was to draw a route from each place to the next, trying to minimize the length of the path. That went okay for the first 10 addresses, but after that there was always a next choice that made us wonder if we had the optimal route so far. To make a long story short: this didn't work out at all.

Algorithm

After that, we tried to build a algorithm to generate all possible roundtrips and select the fastest. But the amount of possibile roundtrips was nearly endless. For the first destination there were 82 choices. For the second 81, the third 80, and so on. In the end there were 5E122 roundtrips. That's a five with 122 zeros. Even with a superfast computer, it would take days, if not weeks, to calculate them all.

Also, we needed all the intermediate travel distances between all places for this. There as no way we could get over 6600 distances (82 x 81) in reasonable time without entering all seperate pairs apart in our navigation system.

Solution

Both the visual and algorythmic approach did not solve the problem. We got a tip to use this great online route optimizer RouteXL at www.routexl.com. That was the best thing that happened to us. We tried it for free up till 20 destinations and it worked great.

After we paid a small amount via paypal we could import all out addresses from Excel, calculate the fastest journey with the optimized order of waypoints in a snap, and download the multi stop route to load on our navigation device. I wished we'd knew about it before we spent several days working on our own solution.

Geen opmerkingen:

Een reactie posten