An efficient algorithm for placing electric vehicle charging stations

Conference Paper

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