Lost in transportation

From Science News, May 5th, 2007; Vol.171 #18 (p. 285)

Online map programs such as MapQuest or Google Maps have made it easier for many people to plan road trips. But to handle large numbers of requests for driving directions, such systems often don’t search the entire range of possible routes, says Dominik Schultes, a computer scientist at the University of Karlsruhe in Germany. For example, the systems may overlook shorter routes for the sake of following major highways, he says.

Schultes and his collaborators have now invented an algorithm that can efficiently deliver the best directions with mathematical certainty—save for traffic jams—the researchers say.

Schultes says that the new algorithm exploits a common-sense observation no other algorithm had used before: Each route into or out of a city typically passes through one of a handful of major intersections.

The new algorithm works out the location of such traffic nodes. It then plots individual routes by calculating how to get to the most convenient node from a specified starting or finishing point. The result appears in the April 27 issue of Science.

Andrew Goldberg of Microsoft Research in Mountain View, Calif., agrees with Schultes’ group that the new algorithm could improve map programs for travelers.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s