License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2015.29
URN: urn:nbn:de:0030-drops-54559
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5455/
Go to the corresponding OASIcs Volume Portal

Merting, Sören ; Schwan, Christian ; Strehler, Martin

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

pdf-format:
6.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{merting_et_al:OASIcs:2015:5455,
  author =	{S{\"o}ren Merting and Christian Schwan and Martin Strehler},
  title =	{{Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{29--41},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5455},
  URN =		{urn:nbn:de:0030-drops-54559},
  doi =		{10.4230/OASIcs.ATMOS.2015.29},
  annote =	{Keywords: routing of electric vehicles, constrained shortest paths, FPTAS, con- strained network flow}
}

Keywords: routing of electric vehicles, constrained shortest paths, FPTAS, con- strained network flow
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI