Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2014.25
URN: urn:nbn:de:0030-drops-47500
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4750/
Arkin, Esther M. ; Carmi, Paz ; Katz, Matthew J. ; Mitchell, Joseph S. B. ; Segal, Michael
Locating Battery Charging Stations to Facilitate Almost Shortest Paths
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{arkin_et_al:OASIcs:2014:4750,
author = {Esther M. Arkin and Paz Carmi and Matthew J. Katz and Joseph S. B. Mitchell and Michael Segal},
title = {{Locating Battery Charging Stations to Facilitate Almost Shortest Paths}},
booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
pages = {25--33},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-75-0},
ISSN = {2190-6807},
year = {2014},
volume = {42},
editor = {Stefan Funke and Mat{\'u}{\v{s}} Mihal{\'a}k},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4750},
URN = {urn:nbn:de:0030-drops-47500},
doi = {10.4230/OASIcs.ATMOS.2014.25},
annote = {Keywords: approximation algorithms; geometric spanners; transportation networks}
}
| Keywords: | approximation algorithms; geometric spanners; transportation networks | |
| Seminar: | 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems | |
| Issue date: | 2014 | |
| Date of publication: | 19.09.2014 |
