Route Planning in Road Networks

The continuously increasing demand for mobility more and more frequently asks for the best driving directions to one's destination saving time and money. Using simple-minded approaches to the computation of suitable routes yields slow response times or suboptimal results. Therefore, there is considerable interest in exact and fast speedup techniques, which typically invest some time into a preprocessing step in order to generate auxiliary data that can be used to accelerate all subsequent route planning queries. We present three highly-efficient and provably accurate point-to-point route planning algorithms and one generic many-to-many approach, which computes for given source and target node sets the optimal distances between all source-target node pairs in a very efficient way. The performance is evaluated in an extensive experimental study using large real-world road networks with up to 33 million junctions. This book addresses students, researchers, and software developers that are interested in car navigation systems, route planning services, logistics, or any other application where route planning in road networks plays a crucial role.