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.
To actually ensure that drivers do not go astray on their road excursion, Google has begun installing an option to its mapping program that provides a street-level navigational view. With a system of successive panoramic snapshots of the suggested route, Google Street View allows travelers to verify the landmarks they will encounter from the driver’s seat.
Even with the best directions in hand, unforeseeable traffic can ruin a trip. IntelliOne, a company that explores ways to combine transportation and communications networks, has recently unveiled the TrafficAid, which translates anonymous cell phone signals into an accurate, real-time traffic map.
By harnessing ubiquitous cellular networks, the system avoids having to install separate sensors along traffic routes. Specific servers, instead, can detect a phone’s specific location and speed. IntelliOne transfers these signaling data to its database, where detected phones are associated with a certain road, thereby producing accurate and timely information about traffic conditions.
Freed of dependence on traffic information from video cameras, roadside radars and in-pavement monitors, the TrafficAid updates its map of bunched signals more quickly and makes a calculation to within five to eight kilometers (three to five miles) per hour of actual speed.
—Peter Sergo
