Prof. Dr. Tobias Friedrich

Efficient Reachability Computation for Electric Vehicles

Bachelor Project - Winter 2023/24


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.


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.


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?

Industry partner contribution

TomTom is a Dutch multinational developer and creator of navigation technology and consumer electronics. It was founded in 1991 and is headquartered in Amsterdam. In addition to its main location in Amsterdam, TomTom has a strong presence in Berlin. In 2006, they opened a site with more than 200 developers and researchers dedicated to working on routing algorithms and traffic information. For our collaborative efforts, we will be partnering with TomTom's navigation research team in Berlin. The company will generously provide our team with real-world map data and offer valuable support throughout the project. This support includes sharing their expertise in navigation and traffic systems, as well as providing various approaches to address this exciting challenge.

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.

Project Team

The bachelor project is organized by the Algorithm Engineering group. The following group members and students are participating:

Project Supervisor

Hasso Plattner Institute

Office: K-2.15
Tel.: +49 331 5509-410
E-Mail: Friedrich(at)hpi.de

Dr. Pascal Lenzner

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.17
Tel.: +49 331 5509-418

E-Mail: Pascal.Lenzner(at)hpi.de

Dr. Kirill Simonov

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.06
E-Mail: Kirill.Simonov(at)hpi.de
Links: Homepage, Publications

Nadym Mallek

Chair for Algorithm Engineering
Hasso Plattner Institute
Prof.-Dr.-Helmert-Str. 2-3
D-14482 Potsdam

Office: K-2.08

E-Mail: nadym.mallek(at)hpi.de



Chair for Algorithm Engineering
Hasso Plattner Institute
Prof.-Dr.-Helmert-Str. 2-3
D-14482 Potsdam

Office: K-2.09/10
E-Mail: Paraskevi.Machaira(at)hpi.de