DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2015.29

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

Authors: Sören Merting, Christian Schwan, and Martin Strehler

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

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.

Cite as

Sören Merting, Christian Schwan, and Martin Strehler. Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 29-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{merting_et_al:OASIcs.ATMOS.2015.29,
  author =	{Merting, S\"{o}ren and Schwan, Christian and Strehler, Martin},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.29},
  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}
}

Search Results

Documents authored by Merting, Sören

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

Abstract

Cite as

Thanks for your feedback!

Could not send message