An efficient algorithm for placing electric vehicle charging stations
Published
Conference Paper
© Pankaj K. Agarwal, Jiangwei Pan, and Will Victor. 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.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Pan, J; Victor, W
Published Date
- December 1, 2016
Published In
Volume / Issue
- 64 /
Start / End Page
- 7.1 - 7.12
International Standard Serial Number (ISSN)
- 1868-8969
International Standard Book Number 13 (ISBN-13)
- 9783959770262
Digital Object Identifier (DOI)
- 10.4230/LIPIcs.ISAAC.2016.7
Citation Source
- Scopus