Stochastic Models and Acceleration Techniques for Green Routing in Car Navigation Systems

The author of this thesis is Rene Schönfelder.

Drivers of electric vehicles are interested in energy-optimal routes not only to reduce anthropogenic carbon dioxide but also to extend the limited reach. This thesis describes different shortest path models for energy-optimal routing in order to extend these models with stochastic aspects as well as extending existing algorithms to handle these models.

A new perspective on the simple shortest path problem will be presented. Using an arbitrary set of states, for example the battery charge of an electric vehicle, sufficient properties of edge weights, namely monotonicity and extensivity, are discussed and applied, such that efficient algorithms can be developed. The main utility to extend existing algorithms is an abstract datatype describing partial preorder queues. The leading example of such algorithms are contraction hierarchies. Basic implementations yield correct results for the described models, but various algorithms and approximation techniques still need to be tested. A thorough implementation for the use in the GreenNav system is planned.