Background

With the ongoing trend of decarbonization in the transportation sector, electric vehicles are on the rise: In March 2023, the number of registered electric vehicles in Germany passed the 1 million mark. Despite these rising numbers, many people are still hesitant to switch to an electric vehicle due to worries about estimating the driving range. Good software that computes and visualizes the remaining driving range in an intuitive way can reassure and empower them.

Simplified EV range visualization. For computing the remaining driving range, the specific car that is used and the dependence of battery depletion on the type of road need to be taken into account. Moreover, besides the computation, an important problem is to efficiently visualize the area that can still be reached by a specific car with its current battery status at any given time. Such a visualization should be precise enough to guide the drivers and at the same time it should also be easy to understand. Finding good trade-offs between efficiency, precision, and "beauty" of the computed polygon is the key.

Challenge

Our industry partner TomTom is one of the largest routing providers. While they already have sophisticated solutions for individual routing with petrol-powered cars, TomTom is interested in improving their service for electric vehicles. Their software is used in built-in car navigation systems as well as in apps for smart devices.

TomTom currently has a prototype implementation for computing and visualizing the reachable area, but there is room for improvement. For example, this prototype can compute the exact polygon (see the figures below), but this computation is very slow. They also have a much faster implementation that computes a simplified polygon with less precision, i.e., it may mark points as reachable that actually cannot be reached without charging.

Vision

Our goal is to find a suitable middleground between efficiency, precision, and "beauty" for the range visualization problem. On the one hand, this requires lots of domain knowledge on routing, such as the employed power consumption model. On the other hand, given the large underlying graph that models the street network, efficient algorithms and a suitable implementation are needed. Visualizations of the reachable area for a given EV. Finally, there's the human interaction aspect: How do people want to use these visualizations and how can we support that best? Which visualizations look good and inspire confidence?

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 the 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 datasets, you will create the necessary code infrastructure and efficient algorithms for range estimation and visualization. Besides team experience in an industrial context, you will learn about efficient data processing and the practical use of graph algorithms, geometry, and other related fields.