2026-07-23T04:52:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4750 2024-03-06T10:29:38Z ddc:004 open_access

Locating Battery Charging Stations to Facilitate Almost Shortest Paths Arkin, Esther M. Carmi, Paz Katz, Matthew J. Mitchell, Joseph S. B. Segal, Michael approximation algorithms; geometric spanners; transportation networks 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther M. Arkin and Paz Carmi and Matthew J. Katz and Joseph S. B. Mitchell and Michael Segal 2014 Is Part Of OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2014.25 urn:nbn:de:0030-drops-47500 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.25 eng https://creativecommons.org/licenses/by/3.0/legalcode