Document Open Access Logo

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

Authors Sören Merting, Christian Schwan, Martin Strehler

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.29.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Sören Merting
Christian Schwan
Martin Strehler

Cite As Get BibTex

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) https://doi.org/10.4230/OASIcs.ATMOS.2015.29

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.

Subject Classification

Keywords
  • routing of electric vehicles
  • constrained shortest paths
  • FPTAS
  • con- strained network flow

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Georg Baier. Flows with Path Restrictions. PhD thesis, TU Berlin, 2003. Google Scholar
  2. Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, and Martin Skutella. Length-bounded cuts and flows. In Automata, Languages and Programming, LNCS 4051, pages 679-690. Springer Berlin Heidelberg, 2006. Google Scholar
  3. Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, and Dorothea Wagner. Speed-consumption tradeoff for electric vehicle route planning. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14), OpenAccess Series in Informatics (OASIcs), pages 138-151, 2014. Google Scholar
  4. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-optimal routes for electric vehicles. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 54-63. ACM Press, 2013. Google Scholar
  5. John E. Beasley and Nicos Christofides. An algorithm for the resource constrained shortest path problem. Networks, 19(4):379-394, 1989. Google Scholar
  6. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning. In P. M. Pardalos and S. Rebennack, editors, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11), LNCS 6630, pages 376-387. Springer, 2011. Google Scholar
  7. Geoffrey Exoo. On line disjoint paths of bounded length. Discrete Mathematics, 44(3):317-318, 1983. Google Scholar
  8. Lisa Fleischer and Martin Skutella. Quickest flows over time. SIAM Journal on Computing, 36(6):1600-1630, 2007. Google Scholar
  9. Lisa K. Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13(4):505-520, 2000. Google Scholar
  10. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  11. Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing, 37(2):630-652, 2007. Google Scholar
  12. Gabriel Handler and Israel Zang. A dual algorithm for the constrained shortest path problem. Networks, 10(4):293-309, 1980. Google Scholar
  13. Refael Hassin. Approximation schemes for the restricted shortest path problem. Math. Oper. Res., 17(1):36-42, February 1992. Google Scholar
  14. László Lovász, Víctor Neumann-Lara, and Michael Plummer. Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica, 9(4):269-276, 1978. Google Scholar
  15. Kurt Mehlhorn and Mark Ziegelmann. Resource constrained shortest paths. In Mike S. Paterson, editor, Algorithms - ESA 2000, LNCS 1879, pages 326-337. Springer Berlin Heidelberg, 2000. Google Scholar
  16. Katta G. Murty and Santosh N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117-129, 1987. Google Scholar
  17. Ludovít Niepel and Daniela Šafaříková. On a generalization of Menger’s theorem. Acta Mathematica Universitatis Comenianae, 42:275-284, 1983. Google Scholar
  18. Cynthia A. Phillips. The network inhibition problem. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC'93, pages 776-785, New York, NY, USA, 1993. ACM. Google Scholar
  19. Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. Efficient energy-optimal routing for electric vehicles. In Conference on Artificial Intelligence, Special Track on Computational Sustainability. AAAI, 2011. Google Scholar
  20. Sabine Storandt. Quick and energy-efficient routes: computing constrained shortest paths for electric vehicles. In Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pages 20-25. ACM, 2012. Google Scholar
  21. Sabine Storandt and Stefan Funke. Enabling e-mobility: Facility location for battery loading stations. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. AAAI Press, 2013. Google Scholar
  22. Arthur Warburton. Approximation of pareto optima in multiple-objective, shortest-path problems. Operations Research, 35(1):70, 1987. Google Scholar
  23. Mark Ziegelmann. Constrained shortest paths and related problems. Phd thesis, Universität des Saarlandes, Saarbrücken, 2001. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact