Navigation is faster

New method speeds up navigation systems 100 times

Navigation system MMCD
Read out

Even navigation aids sometimes get hectic - for example, when the driver missed a trendy branch. For quite a while, the navigation program calculates before it announces a new path. Now scientists have developed a method that could accelerate navigation aids 100 times. For logistics companies as well as route planners in the network, this process, which is now published in "Science", would be a great step forward

Anyone who has controlled his car from the local garage, usually happens again and again the same prominent points. If he wants to head north, this may be a nearby motorway exit, perhaps also heading south. And to all western destinations, it may bring him a circle of divers, while he always crosses a certain intersection to the east. From this idea, scientists from the Max Planck Institute for Computer Science have developed a method that beats the currently fastest route planner by a factor of 100.

Fewer nodes - faster result

"We are drastically reducing the number of nodes that such a program must take into account, " explains Stefan Funke from the Max Planck Institute for Computer Science in Saarbrücken. Together with researchers from the University of Karlsruhe, he and his colleagues developed the new method. Of just under 20 million nodes in the road network of Western Europe, only about 11, 000 transit nodes remain. The distances between these nodes need to look up a route planner only in a table. "The program will be faster by orders of magnitude, which would not have been possible with previous approaches, " says Holger Bast, the other part of the Saarbrücken research duo.

So far, a route planner scans from node to node in the road network. And although he only considers highways and federal highways in the middle between two destinations, he needs 100 times longer than for the bill with transit nodes. "Some commercial navigation aids are fast but do not always determine the best route, " says Bast. In contrast, the new method always delivers the best route, which pays off in cash, especially at logistics companies. "With our algorithm, even relatively weak mobile navigation systems can redefine the route in fractions of a second, which now sometimes takes minutes, " says Funke.

Node net at close range finer

There is one more detail: Between Berlin and Barcelona, ​​the route planner works quickly and reliably, if he only considers the rough network of transit nodes. However, if the start and finish are too close together, for example Berlin Tiergarten and Berlin Mitte, the researchers must proceed differently. You could use conventional methods here because they calculate relatively quickly for short distances. display

"But we favor a hierarchical query, " says Funke. By that he means that in this case the program should count on a slightly finer network of transit nodes. For example, the scientists have made the finer grid for Western Europe from more than 300, 000 transit nodes. And even shorter distances are followed by a network of almost three million nodes. "That way, we can quickly determine the best route between any points, " says Bast.

(MPG, 30.04.2007 - NPO)