Route Optimization and Death of a Salesman

Taking an arbitrary list of addresses and finding an optimized route has been a pretty common problem ever since traveling salesmen. It has been the bane of many computer science students leading to more than a few minor tragedies, as well as Arthur Miller’s great American tragedy. Technically known as an np-complete problem, computational time escalates quickly and tragically as the number of stops increase.

Bing includes some valuable Routing services like routing with waypoints, traffic optimization, optimization of time or distance, or even walking routes versus driving versus major routes. However, there are some limitations to Bing Routing Service , and even Bing could not prevent Willy Loman’s tragic demise.

One limitation of Bing Routing is that the maximum number of waypoint stops is 25. This is probably not a notable issue for individual users, but it is a problem for enterprise use with large numbers of stops to calculate.

Perhaps a broader issue often encountered is waypoint or stop order. Bing Route service does not attempt to reorder waypoints for optimal routing. Route segments between waypoints are optimized, but waypoints themselves are up to the user. Often stop points are coming from a SharePoint list, a contact address book, an Excel spreadsheet, or a database without benefit of sort ordering based on route optimization. This is where route optimization comes in handy.

OnTerra Systems has been involved with Fleet management for some time now and recently introduced a RouteOptimization Service.

There are of course fairly complex algorithms involved and computational scientists have been at some pains to circumscribe the limits of the problem. One simplification that makes this much easier is to ignore routing momentarily and use a shortest distance algorithm to make a first route optimization pass. One way this can be accomplished is by looking at a set of connected nodes and determining segment intersects. By recursively re–ordering nodes to eliminate segment intersects, the computer quickly turns the above node set into this:

The nodes are first ordered with the simplified assumption of straight line segment connectors, and only after a re-ordering is the usual Bing Route service triggered to get actual routes between nodes. This is one of those algorithms that take some liberties to find a solution in real time i.e. time we can live with. It doesn’t guarantee “The Absolute Best” route, but a route that is “good enough” and in the vast majority of cases will in fact be the best, just not guaranteed.

Of course mathematicians and purists cringe at the idea, however, that is ordinarily what engineering is all about, getting an approximate solution in less than the time constraint of a useable solution.

OnTerra Systems has added some other refinements to the service with the help of Bing Maps Silverlight Control. This UI uses both Bing Geocoding as well as Bing Route services. In addition it makes use of the simplified RouteOptimization service to make the route UI shown above. Users can choose whether to optimize for time or distance. Minor modifications could use traffic optimization, available in Bing, just as well. However, traffic optimization requires a different license and a bit more money.

Entering points can be accomplished several ways, with a click approach, from manually entered addresses, or even more easily from an Excel spreadsheet of addresses. Route definition can be set for round trip, one way to a known end destination, or one way to whichever end is the most efficient.

This UI is only one of many that could be used. As a WCF Service, RouteOptimization can take latitude, longitude point sets from any source and return the ordered points for display in any web UI.

This example Silverlight UI is a three step process of service chaining. First points are collected from the user. If addresses are listed rather than latitude longitude points, then Bing Geocode Service is called to arrive at the necessary list of latitude, longitude points. These in turn are handed to the RouteOptimizer Service. The returned points are now ordered and can be given to the Bing Route Service in the 3rd step of a service chain. Finally the resulting route is plotted in the Silverlight map UI.

Waypoint limit work around:
An interesting side note to RouteOptimization Service is the ability to extend the number of waypoints. Microsoft’s restriction to 25 waypoints is probably a scaling throttle to prevent service users from sending in hundreds and possibly thousands of waypoints for a single route. The Route Service could be compromised with many large count waypoint requests.

However, with the ability to order waypoints with an outside service this limit has a work around. First run an optimization on all of the stops using RouteOptimizer service. Now simply loop through the return set with multiple calls to Bing Route in 25 node chunks. This simple divide and conquer achieves a simple work around to the Waypoint limitation. Note that the public sample here is also limited to 25 stops. To use this work-around, you’ll need a licensed version.

Alternate UIs
Of course UIs may multiply. Route Savvy is primarily a service to which any number of UIs can connect and Silverlight happens to be a nice way to create useful UIs. Perhaps a more convenient UI is the Bing Map Gallery version found at Bing Maps Explore:
Bing Map Explore Route Savvy.

Linda Loman and the Parent Car Pool:
Anyone out there with kids in sports has probably run into this traveling salesman problem. (Fast forward to 2010 and Linda Loman jumps in the van with Biff ) There are 6 kids in the car pool. What is the optimal route for picking up all kids and delivering them to the playing field on time? If you want to know, just fire up RouteOptimizer and give it a whirl.

OnTerra Systems Route Optimization Service supplements the already valuable Bing Services by both optimizing input stop orders and extending the waypoint limitation. This is an illustration of the utility of web service chains. The ability to link many services into a solution chain is one of the dreams come true of web development and one reason why web applications continue to supersede the desktop world.

Please note, even though RouteOptimizer will help Linda Loman’s car pool run smoothly, it won’t prevent the death of a salesman. Sorry, only a higher plane optimization can do that.