Document Open Access Logo

Dynamic Traffic Assignment for Electric Vehicles

Authors Lukas Graf , Tobias Harks, Prashant Palkar

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.6.pdf
  • Filesize: 1.4 MB
  • 15 pages

Document Identifiers

Author Details

Lukas Graf
  • Universität Augsburg, Germany
Tobias Harks
  • Universität Augsburg, Germany
Prashant Palkar
  • Universität Augsburg, Germany

Funding

Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - HA 8041/1-2.

Acknowledgements

We are grateful to the anonymous reviewers for their valuable feedback on this paper. Additionally, we thank the organizers and participants of the 2022 Dagstuhl seminar on "Dynamic Traffic Models in Transportation Science" where we had many helpful and inspiring discussions on the topic of this paper.

Cite As Get BibTex

Lukas Graf, Tobias Harks, and Prashant Palkar. Dynamic Traffic Assignment for Electric Vehicles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/OASIcs.ATMOS.2022.6

Abstract

We initiate the study of dynamic traffic assignment for electrical vehicles addressing the specific challenges such as range limitations and the possibility of battery recharge at predefined charging locations. We pose the dynamic equilibrium problem within the deterministic queueing model of Vickrey and as our main result, we establish the existence of an energy-feasible dynamic equilibrium. There are three key modeling-ingredients for obtaining this existence result:  
1) We introduce a walk-based definition of dynamic traffic flows which allows for cyclic routing behavior as a result of recharging events en route. 
2) We use abstract convex feasibility sets in an appropriate function space to model the energy-feasibility of used walks. 
3) We introduce the concept of capacitated dynamic equilibrium walk-flows which generalize the former unrestricted dynamic equilibrium path-flows.  Viewed in this framework, we show the existence of an energy-feasible dynamic equilibrium by applying an infinite dimensional variational inequality, which in turn requires a careful analysis of continuity properties of the network loading as a result of injecting flow into walks.
We complement our theoretical results by a computational study in which we design a fixed-point algorithm computing energy-feasible dynamic equilibria. We apply the algorithm to standard real-world instances from the traffic assignment community illustrating the complex interplay of resulting travel times, energy consumption and prices paid at equilibrium.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Network flows
  • Networks → Traffic engineering algorithms
Keywords
  • Electromobility
  • Dynamic Traffic Assignment
  • Dynamic Flows
  • Fixed Point Algorithm

Metrics

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

Related Versions

Supplementary Materials

References

  1. Moritz Baum, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Consumption profiles in route planning for electric vehicles: Theory and applications. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors, 16th International Symposium on Experimental Algorithms, SEA 2017, June 21-23, 2017, London, UK, volume 75 of LIPIcs, pages 19:1-19:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  2. Roberto Cominetti, José R. Correa, and Omar Larré. Dynamic equilibria in fluid queueing networks. Oper. Res., 63(1):21-34, 2015. Google Scholar
  3. Roberto Cominetti, José R. Correa, and Neil Olver. Long term behavior of dynamic equilibria in fluid queuing networks. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 161-172, 2017. Google Scholar
  4. Guy Desaulniers, Fausto Errico, Stefan Irnich, and Michael Schneider. Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res., 64(6):1388-1405, 2016. Google Scholar
  5. Terry L. Friesz, David Bernstein, Tony E. Smith, Roger L. Tobin, and B. W. Wie. A variational inequality formulation of the dynamic network user equilibrium problem. Oper. Res., 41(1):179-191, January 1993. Google Scholar
  6. Aurélien Froger, Ola Jabali, Jorge E. Mendoza, and Gilbert Laporte. The electric vehicle routing problem with capacitated charging stations. Transportation Science, 56(2):460-482, 2022. URL: https://doi.org/10.1287/trsc.2021.1111.
  7. Ke Han, Gabriel Eve, and Terry L Friesz. Computing dynamic user equilibria on large-scale networks with software implementation. Networks and Spatial Economics, 19(3):869-902, 2019. Google Scholar
  8. Ke Han, Terry L. Friesz, and Tao Yao. Existence of simultaneous route and departure choice dynamic user equilibrium. Transportation Research Part B: Methodological, 53:17-30, 2013. Google Scholar
  9. Ronald Koch and Martin Skutella. Nash equilibria and the price of anarchy for flows over time. Theory Comput. Syst., 49(1):71-97, 2011. URL: https://doi.org/10.1007/s00224-010-9299-y.
  10. Torbjörn Larsson and Michael Patriksson. An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems. Transportation Research Part B: Methodological, 29(6):433-455, 1995. Google Scholar
  11. Jacques-Louis Lions. Quelques méthodes de résolution des problémes aux limites non linéaires. Etudes mathématiques. Dunod, Paris, 1969. Google Scholar
  12. Frédéric Meunier and Nicolas Wagner. Equilibrium results for dynamic congestion games. Transportation Science, 44(4):524-536, 2010. An updated version (2014) is available on Arxiv. Google Scholar
  13. Payas Rajan and Chinya V. Ravishankar. Stochastic Route Planning for Electric Vehicles. In Christian Schulz and Bora Uçar, editors, 20th International Symposium on Experimental Algorithms (SEA 2022), volume 233 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:17, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SEA.2022.15.
  14. Bin Ran and David E. Boyce. Dynamic urban transportation network models: theory and implications for intelligent vehicle-highway systems. Lecture notes in economics and mathematical systems. Springer, Berlin, New York, Paris, 1996. Google Scholar
  15. Michael Schneider, Andreas Stenger, and Dominik Goeke. The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci., 48(4):500-520, 2014. Google Scholar
  16. Statista 2021. https://www.statista.com/statistics/1167538/electricity-prices-charging-stations-electric-cars-by-provider-germany/. Accessed: 2022-03-14.
  17. Sabine Storandt and Stefan Funke. Cruising with a battery-powered vehicle and not getting stranded. In Jörg Hoffmann and Bart Selman, editors, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press, 2012. Google Scholar
  18. Martin Strehler, Sören Merting, and Christian Schwan. Energy-efficient shortest routes for electric and hybrid vehicles. Transportation Research Part B: Methodological, 103:111-135, 2017. Green Urban Transportation. URL: https://doi.org/10.1016/j.trb.2017.03.007.
  19. AVERE the European Association for Electromobility. Pricing of electric vehicle recharging in Europe, 2020. Study prepared by European Alternative Fuels Observatory. Google Scholar
  20. Yi Wang, W.Y. Szeto, Ke Han, and Terry L. Friesz. Dynamic traffic assignment: A review of the methodological advances for environmentally sustainable road transportation applications. Transportation Research Part B: Methodological, 111:370-394, 2018. Google Scholar
  21. Yiyong Xiao, Yue Zhang, Ikou Kaku, Rui Kang, and Xing Pan. Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption. Renewable and Sustainable Energy Reviews, 151:111567, 2021. Google Scholar
  22. Yanhai Xiong, Jiarui Gan, Bo An, Chunyan Miao, and Ana L. C. Bazzan. Optimal electric vehicle fast charging station placement based on game theoretical framework. IEEE Transactions on Intelligent Transportation Systems, 19(8):2493-2504, 2018. Google Scholar
  23. Hong Zheng, Xiaozheng He, Yongfu Li, and Srinivas Peeta. Traffic Equilibrium and Charging Facility Locations for Electric Vehicles. Networks and Spatial Economics, 17(2):435-457, 2017. Google Scholar
  24. Renxin Zhong, Agachai Sumalee, Terry L. Friesz, and William H.K. Lam. Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm. Transportation Research Part B: Methodological, 45(7):1035-1061, 2011. Google Scholar
  25. Daoli Zhu and Patrice Marcotte. On the existence of solutions to the dynamic user equilibrium problem. Transportation Science, 34(4):402-414, 2000. 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