@mappingtoolsMapPoint can find the shortest route connecting a list of waypoints. Using the Optimize Stops function on the Route Planner, it can also find the best (‘optimum’) waypoint order that results in the shortest route. For example, you might need to visit three customers. The exact order is not important, but you want to do it with the shortest route possible in order to minimize costs. This is where MapPoint’s Optimize Stops function comes in.
Another name for this general function is the Travelling Salesman Problem – this finds the shortest route through a set of waypoints. The MapPoint implementation works with fixed start and end waypoints, and finds the optimum order of the intermediate waypoints. The Travelling Salesman Problem is notoriously difficult for all but the most trivial problems. Therefore MapPoint uses a number of heuristics so that the majority of routes can be optimized in seconds or minutes.
Here is an example route which needs to be optimized:
A long route before optimization
It starts in Houston, ends in Shreveport, and includes three intermediate waypoints. The total distance is 711.2 miles with an estimated driving time of 12 hours 20 minutes (every 8 hours of driving time counts as one travel day due to an overnight stop).
Press the Optimize stops button to start the optimization process. Depending on the route distance and number of waypoints, this might take a few minutes. The following animated dialog box is displayed during the optimization process:
The route optimization process
And here is the optimized route:
The optimized route
As you can see, the route is much more logical and does not include any backtracking. The new route has a distance of 605.8 miles with an estimated driving time of 14 hours 8 minutes. This new route is almost 15% shorter than the original.
Is there a possibility to consider time window contraints in the optimisation – meaning e.g. two customers at the same post code, but customer A is meant to be delivered in the morning, and customer B in the evening?
No, unfortunately it does not have these kinds of constraints. Adding constraints such as time constraints or vehicle capacities makes the problem more complicated. There are products that will do it, but they will also do multi-route optimization. solving the combined complex problem is difficult and they charge accordingly – typically a few thousand dollars for a basic license. Of course this is small money for a trucking company that could save that much in fuel in a week.