Background

With the ongoing trend of decarbonization in the transportation sector, electric vehicles are on the rise: In 2020, the number of of registered electric vehicles in Germany has doubled compared to the previous year. As opposed to petrol-powered cars, such vehicles use batteries that require electric charging stations, which differ from petrol stations in that charging usually takes longer, and the infrastructure is lagging behind the uptake in vehicles.

These restrictions, the dependence of battery depletion on the type of road and the limited range of electric vehicles need to be taken into account for routing. There should be charging stations along the route, reachable without long detours. Additionally, alternatives should be available in case the targeted charging station is broken or fully occupied.

Challenge

Our industry partner TomTom is one of the largest routing providers, and as such wants to provide solutions for electric vehicles as well. While they have good solutions for individual routing already, they are interested in analyzing and possibly improving the charging infrastructure in general. In particular, there is no general coverage map available yet. This is due to the unclear definition of what good charging station coverage means. Such a map would allow for targeted improvement of the infrastructure as well as better routing.

Vision

We want to develop a sensible measure for charging station coverage that reflects the influence of the local charging station infrastructure on travel times. We also want to incorporate the robustness to charging station failure and traffic peaks. This requires lots of domain knowledge on routing, such as the relation between traffic density and travelling speed. Together with our project partner, we will choose suitable models for routing that makes use of the charging station infrastructure. We will analyze and visualize the results in order to find weaknesses in the infrastructure and gain a better understanding of the coverage. Finally, we want to use this knowledge to improve routing with respect to the infrastructure density and robustness.

Our Contribution

The research group will work closely with you on the project and will provide expertise in algorithm engineering, graph theory and data science. We will help you develop theoretical models to investigate the provided data and quality of solution approaches. As in previous bachelor and master projects of our group, we plan to write a joint scientific publication about our research findings. For that and for your bachelor theses, we will offer a workshop on scientific writing in March.

Your Contribution

In your work as a team, you will develop and customize a bundle of algorithms for solving the problem at hand. For exploring industrial-size maps and traffic datasets, you will create the necessary code infrastructure and efficient algorithms for routing approaches and coverage maps. Besides team experience in an industrial context, you will learn about efficient data processing and the practical use of graph theory and other related fields.