Personalized Route Planning with Recharging for Electric Vehicles
Translated title
Personaliseret Ruteplanlægning med Genopladning for Elektriske Køretøjer
Authors
Strandfelt, Andreas ; Lau, Andreas Thor ; Højsleth, Mathias
Term
4. term
Education
Publication year
2016
Submitted on
2016-06-13
Pages
24
Abstract
This thesis investigates personalized route planning for electric vehicles that balances travel time and monetary cost while accounting for charging and energy recuperation. As newer EVs have longer range and denser charging networks, the focus shifts from purely energy-efficient routes toward user-preferred routes that are fast or inexpensive. We propose a user-specified preference function that weights time and price and returns the path with the lowest weighted cost, while respecting battery constraints and heterogeneous charging rates and prices. We present three Dijkstra-based query algorithms: a baseline without preprocessing, a method using a preprocessed partitioned graph inspired by customizable route planning, and an adapted version of our prior auxiliary-graph approach. Two speed-ups—optimal substructure and A* search—are applied. Experiments on real-world data evaluate precomputed graph sizes and query times, indicating that the proposed methods are practical on smaller graphs and that the preprocessing-based variants are orders of magnitude faster than the baseline.
Denne afhandling undersøger personlig ruteplanlægning for elbiler, hvor rejsetid og pris afvejes under hensyn til opladning og energirekuperation. Med udgangspunkt i, at nyere elbiler har længere rækkevidde og at ladenetværk er blevet tættere, argumenterer vi for at skifte fokus fra rent energieffektive ruter til ruter, der er hurtige eller billige efter brugerens præferencer. Vi foreslår en brugerspecificeret præferencefunktion, der vægter rejsetid og pris og returnerer den rute med lavest vægtet omkostning, samtidigt med at batteribegrænsninger og varierende ladehastigheder og priser respekteres. Vi præsenterer tre Dijkstra-baserede forespørgselsalgoritmer: en baseline uden forbehandling, en metode med forbehandlet partitioneret graf inspireret af customizable route planning, samt en tilpasset version af vores tidligere løsning baseret på en hjælpegraf. Derudover anvendes to hastighedsoptimeringer, optimal sub-struktur og A*-søgning. Eksperimenter på virkelige data vurderer forbehandlede grafstørrelser og svartider og viser, at de foreslåede algoritmer er praktiske for mindre grafer, og at de forbehandlede varianter er størrelsesordener hurtigere end baseline.
[This apstract has been generated with the help of AI directly from the project full text]