Electric Vehicle Charging Coverage

Bachelor Project - Winter 2021/22

People from the Algorithm Engineering group: Prof. Dr. Tobias Friedrich, Dr. Katrin Casel, Dr. Davis Issac, Dr. Pascal Lenzner, Philipp Fischbeck, Simon Krogmann
Link: Bachelor Projects IT-Systems Engineering

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.

The route of an EV depends on the available charging stations.

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.

Left: A map of EV charging stations in Den Haag. Right: A coverage map for mobile phone service in Germany. We are interested in a version for electric charging stations, that emphasizes service quality.

Contribution of the external partner

TomTom is a Dutch multinational developer & creator of navigation technology and consumer electronics, founded in 1991 and headquartered in Amsterdam. Besides their location in Amsterdam, TomTom is strongly represented in Berlin and opened a site in 2006 with more than 100 developers and researchers working on routing algorithms, traffic information, and autonomous driving. We will work together with the navigation research team in Berlin. The company will provide the team with real-world traffic data and the location and properties of charging stations. During the project, they will support the team with the required background in navigation and traffic systems as well as providing different approaches for tackling 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 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.

Results

The results of this bachelor project have been accepted at the Symposium on Algorithm Engineering and Experiments (ALENEX).

Clean Citation Style 005

{ "authors" : [{ "lastname":"Bläsius" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/thomas-blaesius.html" , "mail":"thomas.blasius(at)hpi.de" }, { "lastname":"Casel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/katrin-casel.html" , "mail":"katrin.casel(at)hpi.de" }, { "lastname":"Chauhan" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ankit-chauhan.html" , "mail":"ankit.chauhan(at)hpi.de" }, { "lastname":"Cohen" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/sarel-cohen.html" , "mail":"sarel.cohen(at)hpi.de" }, { "lastname":"Cseh" , "initial":"�" , "url":"https://hpi.de/friedrich/publications/people/agnes-cseh.html" , "mail":"agnes.cseh(at)hpi.de" }, { "lastname":"Doskoč" , "initial":"V" , "url":"https://hpi.de/friedrich/publications/people/vanja-doskoc.html" , "mail":"vanja.doskoc(at)hpi.de" }, { "lastname":"Elijazyfer" , "initial":"Z" , "url":"https://hpi.de/friedrich/people/ziena-elijazyfer.html" , "mail":"ziena.elijazyfer(at)hpi.de" }, { "lastname":"Fischbeck" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/philipp-fischbeck.html" , "mail":"philipp.fischbeck(at)hpi.de" }, { "lastname":"Friedrich" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/tobias-friedrich.html" , "mail":"friedrich(at)hpi.de" }, { "lastname":"Göbel" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andreas-goebel.html" , "mail":"andreas.goebel(at)hpi.de" }, { "lastname":"Issac" , "initial":"D" , "url":"https://hpi.de/friedrich/publications/people/davis-issac.html" , "mail":"davis.issac(at)hpi.de" }, { "lastname":"Katzmann" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/maximilian-katzmann.html" , "mail":"maximilian.katzmann(at)hpi.de" }, { "lastname":"Khazraei" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ardalan-khazraei.html" , "mail":"ardalan.khazraei(at)hpi.de" }, { "lastname":"Kötzing" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/timo-koetzing.html" , "mail":"timo.koetzing(at)hpi.de" }, { "lastname":"Krejca" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-krejca.html" , "mail":"martin.krejca(at)hpi.de" }, { "lastname":"Krogmann" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/simon-krogmann.html" , "mail":"simon.krogmann(at)hpi.de" }, { "lastname":"Krohmer" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anton-krohmer.html" , "mail":"none" }, { "lastname":"Kumar" , "initial":"N" , "url":"https://hpi.de/friedrich/publications/people/nikhil-kumar.html" , "mail":"nikhil.kumar(at)hpi.de" }, { "lastname":"Lagodzinski" , "initial":"G" , "url":"https://hpi.de/friedrich/publications/people/gregor-lagodzinski.html" , "mail":"gregor.lagodzinski(at)hpi.de" }, { "lastname":"Lenzner" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/pascal-lenzner.html" , "mail":"pascal.lenzner(at)hpi.de" }, { "lastname":"Melnichenko" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anna-melnichenko.html" , "mail":"anna.melnichenko(at)hpi.de" }, { "lastname":"Molitor" , "initial":"L" , "url":"https://hpi.de/friedrich/publications/people/louise-molitor.html" , "mail":"louise.molitor(at)hpi.de" }, { "lastname":"Neubert" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/stefan-neubert.html" , "mail":"stefan.neubert(at)hpi.de" }, { "lastname":"Pappik" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/marcus-pappik.html" , "mail":"marcus.pappik(at)hpi.de" }, { "lastname":"Quinzan" , "initial":"F" , "url":"https://hpi.de/friedrich/publications/people/francesco-quinzan.html" , "mail":"francesco.quinzan(at)hpi.de" }, { "lastname":"Rizzo" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/manuel-rizzo.html" , "mail":"manuel.rizzo(at)hpi.de" }, { "lastname":"Rothenberger" , "initial":"R" , "url":"https://hpi.de/friedrich/publications/people/ralf-rothenberger.html" , "mail":"ralf.rothenberger(at)hpi.de" }, { "lastname":"Schirneck" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-schirneck.html" , "mail":"martin.schirneck(at)hpi.de" }, { "lastname":"Seidel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/karen-seidel.html" , "mail":"karen.seidel(at)hpi.de" }, { "lastname":"Sutton" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andrew-m-sutton.html" , "mail":"none" }, { "lastname":"Weyand" , "initial":"C" , "url":"https://hpi.de/friedrich/publications/people/christopher-weyand.html" , "mail":"none" }]}

Böther, Maximilian; Kißig, Otto; Weyand, Christopher Efficiently Computing Directed Minimum Spanning TreesSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023

[ Abstract ] [ BibTeX ]

Khomutovskiy, Ivan; Dunker, Rebekka; Dierking, Jessica; Egbert, Julian; Helms, Christian; Schöllkopf, Finn; Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Isaac, Davis; Krogmann, Simon; Lenzner, Pascal Applying Skeletons to Speed Up the Arc-Flags Routing AlgorithmSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023: 110–122

[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]

@inproceedings{casel2023applying,
  abstract = {The Single-Source Shortest Path problem is classically solved by applying Dijkstra's algorithm. However, the plain version of this algorithm is far too slow for real-world applications such as routing in large road networks. To amend this, many speed-up techniques have been developed that build on the idea of computing auxiliary data in a preprocessing phase, that is used to speed up the queries. One well-known example is the Arc-Flags algorithm that is based on the idea of precomputing edge flags to make the search more goal-directed. To explain the strong practical performance of such speed-up techniques, several graph parameters have been introduced. The skeleton dimension is one such parameter that has already been used to derive runtime bounds for some speed-up techniques. Moreover, it was experimentally shown to be low in real-world road networks. We introduce a method to incorporate skeletons, the underlying structure behind the skeleton dimension, to improve routing speed-up techniques even further. As a proof of concept, we develop new algorithms called SKARF and SKARF+ that combine skeletons with Arc-Flags, and demonstrate via extensive experiments on large real-world road networks that SKARF+ yields a significant reduction of the search space and the query time of about 30\% to 40\% over Arc-Flags. We also prove theoretical bounds on the query time of SKARF, which is the first time an Arc-Flags variant has been analyzed in terms of skeleton dimension.},
  author = {Khomutovskiy, Ivan and Dunker, Rebekka and Dierking, Jessica and Egbert, Julian and Helms, Christian and Schöllkopf, Finn and Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and Isaac, Davis and Krogmann, Simon and Lenzner, Pascal},
  booktitle = {SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)},
  keywords = {alenex davisissac katrincasel pascallenzner philippfischbeck simonkrogmann tobiasfriedrich year2023},
  pages = {110-122},
  title = {Applying Skeletons to Speed Up the Arc-Flags Routing Algorithm},
  year = 2023
}

Hasso Plattner Institute

E-Mail: Finn.Schoellkopf(at)student.hpi.de

Electric Vehicle Charging Coverage

Bachelor Project - Winter 2021/22

Background

Challenge

Vision

Contribution of the external partner

Our Contribution

Your Contribution

Results

Project Team

Prof. Dr. Tobias Friedrich

Dr. Katrin Casel

Dr. Davis Issac

Dr. Pascal Lenzner

Philipp Fischbeck

Simon Krogmann

Jessica Dierking

Rebekka Dunker

Julian Egbert

Christian Helms

Ivan Khomutovskiy

Finn Schöllkopf

Algorithm Engineering

News

02.06.2023 | Four Papers accepted at IJCAI

31.05.2023 | Three Papers accepted at WG

02.05.2023 | Five Papers accepted at GECCO

28.04.2023 | Three Papers accepted at ICALP

25.04.2023 | PhD awarded to Vanja Doskoč

21.04.2023 | Five Papers accepted at PODC, SEA, FORC and WADS

Contact

Apply