Faster processing, more accurate information on lengthy trips, traffic snarls

Did the cross-country drive that you planned using an online mapping service take twice as long as expected?

In a new study published in the Articles in Advance section of Transportation Science, a journal of the Institute for Operations Research and the Management Sciences (INFORMS), Microsoft researchers working on a project for Bing Maps explain how they developed the first routing engine that satisfies a large number of algorithmic requirements that overcome barriers to generating directions on multi-stage trips like coast-to-coast drives.

Customizable Route Planning (CRP), according to the researchers, brings far greater speed and accuracy to planning routes with many stages, and more accurately estimates the time needed for turns, U-turns, road closures, and traffic snarls. The research also provides more accurate information for walking and bicycle routes, and identifies more reliable alternate routes.

Surprisingly, the research culminates interest in a classic algorithm published in 1959 by Edsger Dijkstra that was thought to perform too slowly to calculate online map routes.

The study, Customizable Route Planning in Road Networks, is by Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, all employed by Microsoft when the research was submitted for publication.

"CRP incorporates traffic data and new personal preferences much faster - orders of magnitude faster," says Thomas Pajor.

"The resulting routing engine is a flexible and practical solution to many real-life variants of the problem, making it a perfect fit for Bing Maps."

Microsoft started using CRP for Bing Maps in 2012.

A key ingredient of modern online map applications is a routing engine that can find best routes between two given locations of a road network. Beneath the map that online viewers see, algorithms find point-to-point shortest paths in a graph representing the road network. Since the introduction of online maps, considerable research has gone into algorithms with two phases: (1) preprocessing portions of routes that can be used again and again, and (2) providing answers to pinpoint queries that are generated in a millisecond or less.

The authors write that a modern real-world routing engine must satisfy several requirements. It must incorporate every last detail of a road network - previous work often neglected time lost in making turns and observing traffic restrictions due, for example, to road repairs. The authors found that most methods have a significant "performance penalty," often due to the way that turns are represented. Also, a practical algorithm must calculate travel times while also factoring in shortest distance, walking, biking, avoiding U-turns, height and weight restrictions - and other problems that pop up. These new metrics must be calculated fast enough to match real-time traffic information with information about the roads. Updates to the time lost on road closures, for example, should be handled even more efficiently. The engine should support not only the calculation of point-to-point shortest paths but also suggest several alternate routes.

The authors found that no previous technique met all the requirements. By combining new concepts - using separator-based methods rather than the traditional methods that exploit the hierarchical structure of roads - with careful engineering, they significantly improved the performance in their approach, easily enabling interactive applications.

Another innovation - the explicit separation of metric customization from metric-independent preprocessing - allows Bing Maps to answer arbitrary questions about a trip in milliseconds.

In Round-Based Public Transit Routing, a paper published in 2014 by Transportation Science, authors Delling, Pajor, and Werneck, solved similar problems facing bus and train systems in London and other major metropolitan areas.