Why Routing Ain't Easy

Users of our ZIP code and location analysis software, CDXZipStream, may have noticed that some calculations take longer than others, especially driving calculations and route optimization.  On average, calculating the driving distance between two addresses takes about one second, and a route optimization problem can take a few seconds up to several minutes.  

Straight-line “as the crow flies” distance calculations, on the other hand, are very fast, and we always recommend that when doing an analysis with a large data set, to consider straight-line calculation first if it fits the needs of the project.  It’s even possible to use a compromise approach with radius analysis, where a first-pass can use straight-calculations to narrow down the data set, followed by driving distance calculations for the final result.  Please see our article CDXZipStream Straight-Line and Driving Distance Calculations for more information.

So why are routing calculations so hard?  CDXZipStream utilizes either Bing Maps or Microsoft MapPoint running in the background for route calculations, and the short answer is they are simply much more complex.  There are lots of ways a driver can get from point A to point B; a crow flying along a straight path has no other option.  And the farther the distance between A and B, the more route options there are.

Route optimization is particularly difficult, and the problem quickly grows in complexity as the number of stops increases.  This is a classic problem in mathematics called the Travelling Salesman Problem, or TSP.   If a salesman has five cities to visit, the number of possible routes is 5 x 4 x 3 x 2 x 1 = 120 routes.  It’s pretty easy to use a computer to analyze all 120 routes and identify the one that results in the shortest distance or travel time.  But as the number of cities increases, analyzing all possible routes to find the best one quickly (exponentially) becomes too difficult, even for the most powerful computers. Just increasing the number of stops in the example above from five to six will increase the number of possible routes by six-fold.  So for a large number of stops, route optimization must use short-cuts or “heuristic” approaches to find a good solution to the problem in a reasonable amount of time.  Note the result is “only” good; heuristic approaches use experience-based techniques for problem solving, but there’s no guarantee the result will be the best one.

We don’t know what heuristic models Microsoft MapPoint applies when solving a route optimization problem.  There are a number of approaches covered in the literature, even one based on how ant colonies search for food.  But since all optimization software must use shortcuts for these complex problems, there will always be some variation on the “optimal” route that’s found.  Even the same software will come up with different answers depending upon the chosen start point of a route.  Currently the only way to find “the” answer is to use brute force calculation to analyze all possibilities, and for long routes that can take a very, very long time.

We have developed a few free Excel templates that perform driving calculations and route optimization, and can be evaluated using the free trial version of CDXZipStream, which in turn works with either a free basic Bing Maps key or the free trial of Microsoft MapPoint.  (For route optimization, MapPoint must be used.)  All  free templates can be downloaded from our website here. Just paste your data into the templates and the calculated values are automatically returned to the worksheet.  Since the Visual Basic code embedded in the templates have direct access to CDXZipStream functionality, this approach is a bit faster than entering worksheet formulas.   Please see the tutorials below to see how they work:

Driving Distance and Time for a Matrix of Addresses

Route Optimization with One Click

Route Optimization with Latitude and Longitude

Driving Distance and Time Calculations in an Excel Template

As an aside, the TSP is an important problem, not only for route optimization but for a wide range of problems in computer science and math. (The Clay Mathematics Institute will give one million dollars to anyone who can solve it without using brute force – click here if you’re feeling lucky.)  And for an interesting spin on the larger consequences of solving the TSP, watch the 2012 movie Travelling Salesman.

Add comment