Flinsenberg, I: Route Planning Algorithms for Car Navigation

Car navigation systems provide the driver with advice on how to reach a destination. The first advice has to be determined quickly and the driver expects that the presented route is the best route to his destination. Because the road network can be very large, determining an optimum route fast is still a major challenge. This book describes algorithms that address this challenge, and also takes daily congestion on motorways into account. First, we partition a road network into regions. We present several algorithms to do so, which are tested on real-world road networks. Using this partitioning, an optimum route can be planned fast for very large road networks. Furthermore, we formulate a model for daily congestion on motorways. Using real-world data, we determine the consequences of congestion on the driver‘s arrival time and on the optimum route. Finally, the results of the presented algorithms are compared with those of algorithms used in commercial car navigation systems. The results show that our algorithms lead to faster route planning and routes of higher quality.