Dynamisches Rerouting im Kontext von Navigationssystemen

In times of anthropogenic climate change and dwindling oil resources, changing over to electric vehicles is absolutely essential to ensure that nature and the environment are sustained for future generations. In order to cover as large distances as possible, the driver of an electric car is interested in energy-efficient routes instead of conventional shortest paths. Sachenbacher et al. [SLAH11] and Schönfelder [Sch12] have already described corresponding routing and computation models which are used in GreenNav, a prototypical route planner for electric vehicles. A concept to extend GreenNav by adding navigation functionalities is developed throughout this thesis. Particular attention is paid to rerouting techniques, i.e. algorithms for calculating a new energy-optimal route as fast as possible if the driver deviates from the current path. Besides, several optimization techniques are presented to speed up the algorithms, e.g. by using contraction hierarchies and bidirectional search. The performance of the routing and rerouting approaches is analyzed in both theoretical and practical manner by examining the worst case scenario as well as tests on real data. While the asymptotic runtime is identical for both methods, the tests show that rerouting algorithms can reduce runtime by approximately 90 percent in many cases. The concept of contraction hierarchies still needs to be implemented and tested since it promises an even greater potential for optimization.