Locating Service and Charging Stations

In this paper, we consider the problem of locating service and charging stations to serve commuters. In the service station location problem we are given the paths followed by m clients and wish to locate k service stations, from a set of feasible locations, such that the maximum detour that a client has to take is minimized. We give a solution that has a maximum detour $$3\texttt{OPT}+L$$ where L is the length of the longest client-path. Electric vehicles have a limited range and charging stations need to be located so that a client can drive from the source to destination without running out of charge. We consider two variants of the problem. In the first, we are given only the source and destination of each client and have to locate facilities at some subset of locations such that every client has a feasible path. In the second variant, we are also given the path that a client wishes to take and have to locate the facilities such that each client can follow its path without any detours. For both problems, our objective is to minimize the number of charging stations. For all three problems, when the underlying graph is a tree and the facility can be located at any vertex on the tree, we show that the problem can be solved in polynomial time. On general graphs, the problem with source-destination pairs is at least as hard as the node-weighted group-Steiner tree but if we allow vehicles in our solution to have a range of 4 times that of the optimum then we obtain an 8-approximation. For the problem with specified paths, we show that finding an $$o(\log m)$$ approximation is hard even when vehicles of our solution have a range that is a constant times larger than that of the optimum solution.