KIT | KIT-Bibliothek | Impressum | Datenschutz

Speed-Consumption Tradeoff for Electric Vehicle Route Planning

Baum, M.; Dibbelt, J.; Hübschle-Schneider, L.; Pajor, T.; Wagner, D.

Abstract (englisch):

We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second—several orders of magnitude faster than the exhaustive algorithm.


Verlagsausgabe §
DOI: 10.5445/IR/1000045831
Veröffentlicht am 01.08.2018
Originalveröffentlichung
DOI: 10.4230/OASIcs.ATMOS.2014.138
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2014
Sprache Englisch
Identifikator ISBN: 978-3-939897-75-0
ISSN: 2190-6807
urn:nbn:de:swb:90-458313
KITopen-ID: 1000045831
Erschienen in 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’14), Wroclaw, Poland, September 11, 2014. Ed.: S. Funke
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 138-151
Serie OpenAccess Series in Informatics ; 42
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page