EV hitting sets in road networks

Abstract

As electric vehicles (EVs) become more and more popular, there also has to exist an appropriate infrastructure of battery loading stations to allow for a widespread usage. Especially long distance routes are still not covered, due to the short cruising range of EVs. In this thesis we develop an algorithm for placing such stations so that every shortest path can be driven without running out of energy, assuming an adjustable initial and maximum battery charge. Considering an initial roll-out of battery loading stations, we aim at placing as few as possible, while still meeting the above constraint. Therefore, we rely on a theoretical hitting set formulation of the problem to be able to precisely analyze and evaluate it, followed by a - at first - naive algorithm which is then improved in the course of the thesis. A dual problem is introduced to allow a computation of instance-based bounds. Finally we evaluate our implementation practically in regard to memory usage, runtime and quality of the results and furthermore theoretically prove general upper bounds. The final algorithm is capable of computing a battery loading station positioning on the graph of Germany in less than one day on our testing machine, with evidentially good quality.