文章基本信息

标题：An Efficient Algorithm for Placing Electric Vehicle Charging Stations
本地全文：下载
作者：Pankaj K. Agarwal ; Jiangwei Pan ; Will Victor 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：64
页码：7:1-7:12
DOI：10.4230/LIPIcs.ISAAC.2016.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Shortest path hitting set; Charging station placement; Electric vehicle