Electric Vehicle Routing with Realistic Recharging Models (2014)

We study the problem of electric vehicle routing in road networks. Careful route planning is important, especially when planning far trips, because the battery capacity of electric vehicles is limited and charging stations are rare compared to gas stations. This makes it necessary to plan the route and all charging stops beforehand, so that the battery does not deplete along the way. While considering the battery’s state of charge is important, it is still desirable to reach the target as fast as possible. In this thesis we address the problem of finding a route with minimal travel time which never violates battery constraints. We extend previous work on this problem by realistically modeled charging stations. Thereby, we take different types of charging stations into account. Our approach is capable of modeling battery swapping stations as well as regular charging stations with various charging power supplies. Our algorithm is based on a multi-objective search using Pareto-sets. Since the size of these Pareto-sets can get very large in practice, we propose several speed-up techniques in order to make the algorithm practicable. Furthermore we show heuristics leading to even faster algorithms. This thesis is concluded with a detailed evaluation of the proposed algorithm. Our experiments show that our algorithms can compete with existing algorithms, which can only solve certain special cases of our problem. Furthermore using our heuristics it is for the first time possible to find a fast and feasible routes on a continental graph. Deutsche Zusammenfassung Wir untersuchen das Problem der Routenplanung fur Elektroautos in Strasennetzwerken. Das sorgsame Planen der Route ist im Besonderen auf langeren Strecken wichtig, da die Akkukapazitat begrenzt ist und Ladestationen im Vergleich zu herkommlichen Tankstellen selten sind. Daher ist es wichtig, die Route mit allen Ladestopps im Vorfeld zu planen, um zu verhindern, dass die Batterie unterwegs erschopft wird. Wahrend es wichtig ist, den Ladezustand des Akkus zu berucksichtigen, gilt es weiterhin, das Ziel so schnell wie moglich zu erreichen. In dieser Arbeit befassen wir uns mit dem Problem eine Route mit minimaler Reisezeit zu finden, welche nie die Akku-Randbedingungen verletzt. Wir erweitern fruhere Arbeiten zu diesem Problem um realistisch modellierte Ladestationen. Dabei berucksichtigen wir verschiedene Arten von Ladestationen. Unser Ansatz ermoglicht die Modellierung von Battery swapping sowie normale Ladestationen mit verschiedenen Ladeleistungen. Unser Algorithmus basiert auf einer Suche mit mehreren Zielfunktionen, welche Pareto Mengen benutzt. Da diese Pareto Mengen in der Praxis sehr gros werden konnen, schlagen wir verschiedene Beschleunigungstechniken vor, welche den Algorithmus praktikabel machen. Daruber hinaus stellen wir Heuristiken vor, die zu noch schnelleren Algorithmen fuhren. Wir schliesen diese Arbeit mit einer detaillierten Auswertung der vorgestellten Algorithmen ab. Unsere Experimente zeigen das unser Algorithmus mit existierenden Algorithmen, welche nur Spezialfalle von unserem Problem losen, konkurrieren kann. Daruber hinaus ist es durch die Nutzung unserer Heuristiken zum ersten Mal mogliche schnelle und zulassige Routen fur kontinentale Graphen zu berechnen.