ADVERTISEMENT

The Fastest Way to Get There

Novel ways of calculating routes and predicting traffic jams promise less time in the car
THIS IS A PREVIEW.
or subscribe to access the full article.

Providing directions instantly online has until recently meant that navigational mapping programs, such as MapQuest and Google Maps, often simplify the problem by not considering every possible route to a destination. Scientists at the University of Karlsruhe in Germany have designed a computer application that can quickly calculate the most expedient of all possible driving routes without the need for excessive computation.

Dominik Schultes, one of the project's scientists, designed the program around a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. Figuring the best route occurs by precomputing the connections between a starting point (or destination) and its nearest major intersections and between all locations where major routes cross each other's paths—so-called transit nodes. When this parsimonious algorithm was tested on densely routed maps of western Europe and the U.S., the route calculations improved by a factor of 100.

THIS IS A PREVIEW.
or subscribe to access the full article.
Buy Digital Issue $7.99
Print + Digital
All Access
$99.99 Subscribe
Rights & Permissions
Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.

Email this Article

X