1 Search Results for "Schwan, Christian"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Merting, Sören
  • 1 Schwan, Christian
  • 1 Strehler, Martin

  • Refine by Classification

  • Refine by Keyword
  • 1 FPTAS
  • 1 con- strained network flow
  • 1 constrained shortest paths
  • 1 routing of electric vehicles

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail