Preprocessing-Based Pareto Search for Scalable EV Routing
Authors
Jensen, Thomas Emil ; Povlsen, Christian ; Christensen, Casper Bruun
Term
4. term
Education
Publication year
2026
Submitted on
2026-06-04
Pages
15
Abstract
As electric vehicles become more common, planning routes between charging stations must balance travel time, energy use, and charging behavior. The fastest route is not always best: a slightly slower segment that uses less energy can make later parts of the trip quicker or more feasible. To handle such trade-offs, we use a multi-criteria search that considers several costs at once, such as time and energy. Pareto-based methods keep only routes that are not dominated (no other route is better in all criteria) and discard the rest to shrink the search. This work combines preprocessing and Pareto-style search to efficiently compute Pareto-optimal paths between charging stations, with a primary focus on minimizing travel time. The approach builds shortest-path trees on a simplified network that contains only charging stations, applies an epsilon-dominance threshold (a small tolerance used to decide when one route effectively dominates another), and tests multiple charging strategies, including an adaptive, rate-aware strategy. We extend these ideas with precomputed combinations of shortest-path trees for pairs of stations and explore different mixes of strategies and parameter settings. The results show that these design choices deliver reasonable runtimes and high-quality Pareto-optimal paths, highlighting the flexibility and effectiveness of the proposed multi-criteria optimization framework.
Efterhånden som elbiler bliver mere udbredte, kræver ruteplanlægning mellem ladestationer en balance mellem rejsetid, energiforbrug og ladeadfærd. Den hurtigste rute er ikke altid den bedste: en lidt langsommere strækning, der bruger mindre energi, kan gøre senere dele af turen hurtigere eller mere gennemførlig. For at håndtere sådanne kompromiser anvendes en multikriteriel søgning, der vurderer flere omkostninger samtidig, såsom tid og energi. Pareto-baserede metoder bevarer kun ruter, der ikke er dominerede (ingen anden rute er bedre på alle kriterier), og frasorterer resten for at reducere søgeområdet. Dette arbejde kombinerer forbehandling og Pareto-stil søgning for effektivt at beregne Pareto-optimale ruter mellem ladestationer, med primært fokus på at minimere rejsetid. Tilgangen bygger korteste-sti-træer på et forenklet netværk, der kun indeholder ladestationer, anvender en epsilon-dominans-tærskel (en lille tolerance til at afgøre, om én rute reelt dominerer en anden), og afprøver flere ladningsstrategier, inklusive en adaptiv, ladehastighedsbevidst strategi. Vi udvider idéerne med forudberegnede kombinationer af korteste-sti-træer for par af ladestationer og undersøger forskellige kombinationer af strategier og parameterindstillinger. Resultaterne viser, at disse designvalg giver rimelige beregningstider og højkvalitets Pareto-optimale ruter, hvilket understreger fleksibiliteten og effektiviteten i den foreslåede multikriterielle optimeringsramme.
[This apstract has been rewritten with the help of AI based on the project's original abstract]