Document Open Access Logo

An Efficient Algorithm for Placing Electric Vehicle Charging Stations

Authors Pankaj K. Agarwal, Jiangwei Pan, Will Victor

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.7.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
Jiangwei Pan
Will Victor

Cite As Get BibTex

Pankaj K. Agarwal, Jiangwei Pan, and Will Victor. An Efficient Algorithm for Placing Electric Vehicle Charging Stations. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.7

Abstract

Motivated by the increasing popularity of electric vehicles (EV) and a lack of charging stations in the road network, we study the shortest path hitting set (SPHS) problem. Roughly speaking, given an input graph G, the goal is to compute a small-size subset H of vertices of G such that by placing charging stations at vertices in H, every shortest path in G becomes EV-feasible, i.e., an EV can travel between any two vertices of G through the shortest path with a full charge. In this paper, we propose a bi-criteria approximation algorithm with running time near-linear in the size of G that has a logarithmic approximation on |H| and may require the EV to slightly deviate from the shortest path. We also present a data structure for computing an EV-feasible path between two query vertices of G.

Subject Classification

Keywords
  • Shortest path hitting set
  • Charging station placement
  • Electric vehicle

Metrics

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

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. VC-dimension and shortest path algorithms. In Proc. 38th Int'l Colloq. Conf. Automata, Languages and Programming, pages 690-699, 2011. Google Scholar
  2. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension and provably efficient shortest path algorithms. Tech. Report MSRTR-2013-91, Microsoft Research, 2013. Google Scholar
  3. Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proc. 21st Annual ACM-SIAM Symp. Discrete Algorithms, pages 782-793, 2010. Google Scholar
  4. Pankaj K Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. In Proc. 30th Annual Symp. Comput. Geo., page 271, 2014. Google Scholar
  5. Boris Aronov, Esther Ezra, and Micha Sharir. Small-size ε-nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248-3282, 2010. Google Scholar
  6. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. Route planning in transportation networks. arXiv preprint, 2015. Google Scholar
  7. Moritz Baum, Julian Dibbelt, Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf. Shortest feasible paths with charging stops for battery electric vehicles. In Proc. 23rd SIGSPATIAL Int'l Conf. Advances in Geo. Info. Syst., page 44, 2015. Google Scholar
  8. Moritz Baum, Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. Energy-optimal routes for electric vehicles. In Proc. 21st ACM SIGSPATIAL Int'l Conf. Advances in Geo. Info. Syst., pages 54-63, 2013. Google Scholar
  9. Vasek Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233-235, 1979. Google Scholar
  10. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proc. 46th Annual ACM Symp. Theory of Computing, pages 624-633. ACM, 2014. Google Scholar
  11. Inês Frade, Anabela Ribeiro, Gonçalo Gonçalves, and António Antunes. Optimal location of charging stations for electric vehicles in a neighborhood in lisbon, portugal. Transportation Res. Record: J. Transportation Res. Board, 2252(2252):91-98, 2011. Google Scholar
  12. Stefan Funke, André Nusser, and Sabine Storandt. On k-path covers and their applications. Proc. VLDB Endowment, 7(10):893-902, 2014. Google Scholar
  13. Stefan Funke, André Nusser, and Sabine Storandt. Placement of loading stations for electric vehicles: No detours necessary! J. Arti. Intelli. Res., pages 633-658, 2015. Google Scholar
  14. Michael T Goodrich and Paweł Pszona. Two-phase bicriterion search for finding fast and efficient electric vehicle routes. In Proc. 22nd ACM SIGSPATIAL Int'l Conf. Advances in Geo. Info. Syst., pages 193-202, 2014. Google Scholar
  15. Sariel Har-Peled. Geometric Approximation Algorithms. American Math. Soc., 2011. Google Scholar
  16. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete &Comput. Geo., 2(2):127-151, 1987. Google Scholar
  17. RM Karp. Reducibility among combinatorial problems. Complexity Comp. Comput., 1972. Google Scholar
  18. Nabil H Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete &Comput. Geo., 44(4):883-895, 2010. Google Scholar
  19. Martin Sachenbacher, Martin Leucker, Andreas Artmeier, and Julian Haselmayr. Efficient energy-optimal routing for electric vehicles. In Proc. 25th AAAI Conf. Arti. Intelli., 2011. Google Scholar
  20. Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comp. Syst. Sci., 26(3):362-391, 1983. Google Scholar
  21. Sabine Storandt and Stefab Funke. Enabling e-mobility: Facility location for battery loading stations. In Proc. 27th AAAI Conf. Arti. Intelli., 2013. Google Scholar
  22. Moby Khan T. Donna Chen, Kara M. Kockelman. The electric vehicle charging station location problem: a parking-based assignment method for seattle. In Proc. 92nd Annual Meet. Transportation Res. Board, 2013. Google Scholar
  23. Yufei Tao, Cheng Sheng, and Jian Pei. On k-skip shortest paths. In Proc. ACM SIGMOD, pages 421-432. ACM, 2011. Google Scholar
  24. VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971. Google Scholar
  25. Vijay V Vazirani. Approximation algorithms. Springer Sci. &Business Media, 2013. Google Scholar
  26. Yanhai Xiong, Jiarui Gan, Bo An, Chunyan Miao, and Ana LC Bazzan. Optimal electric vehicle charging station placement. In Proc. 24th Int'l Joint Conf. Arti. Intelli., pages 2662-2668, 2015. 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