文章基本信息

标题：Locating Battery Charging Stations to Facilitate Almost Shortest Paths
本地全文：下载
作者：Esther M. Arkin ; Paz Carmi ; Matthew J. Katz 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2014
卷号：42
页码：25-33
DOI：10.4230/OASIcs.ATMOS.2014.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.
关键词：approximation algorithms; geometric spanners; transportation networks