Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes

  • We consider a constrained shortest path problem with the possibility to refill the resource at certain nodes. This problem is motivated by routing electric vehicles with a comparatively short cruising range due to the limited battery capacity. Thus, for longer distances the battery has to be recharged on the way. Furthermore, electric vehicles can recuperate energy during downhill drive. We extend the common constrained shortest path problem to arbitrary costs on edges and we allow regaining resources at the cost of higher travel time. We show that this yields not shortest paths but shortest walks that may contain an arbitrary number of cycles. We study the structure of optimal solutions and develop approximation algorithms for finding short walks under mild assumptions on charging functions. We also address a corresponding network flow problem that generalizes these walks.

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Sören Merting, Christian Schwan, Martin StrehlerORCiDGND
URN:urn:nbn:de:0030-drops-54559
URL:http://drops.dagstuhl.de/opus/volltexte/2015/5455
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2015.29
ISBN:978-3-939897-99-6
Title of the source (English):15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Publisher:Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl, Germany
Editor: Giuseppe F. Italiano, Marie Schmidt
Document Type:Conference Proceeding
Language:English
Year of publication:2015
Tag:routing of electric vehicles, constrained shortest paths, FPTAS, con- strained network flow
First Page:29
Last Page:41
Series ; volume number:OASIcs - OpenAccess Series in Informatics ; 48
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Algorithmische Mathematik
Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Diskrete Mathematik und Grundlagen der Informatik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.