We introduce the (directed) multi-stop station location problem. The goal is to install stations such that ordered (multi-)sets of stops can be traversed with respect to range restrictions that are reset whenever a station is visited. Applications arise in telecommunications and transportation, e.g., charging station placement problems. The problem generalizes several network optimization problems such as (directed) Steiner tree problems. We show strong intractability results of the directed and undirected version under different complexity assumptions; that is, there are no constant factor approximation algorithms, unless $\P = \NP$ and there are no polylogarithmic approximation algorithms for the directed version, unless $\NP \subseteq \DTIME{}(n^{\polylog(n)})$. By a transformation from the directed version to shortest path problems we obtain a linear approximation algorithm.
Citation
@techreport{repORt:2020-60, author = {F.J.L. Willamowski and M. Ganz and E. M\"{u}hmer}, title = {The Multi-Stop Station Location Problem}, institution = {Lehrstuhl f\"{u}r Operations Research, RWTH Aachen University}, year = {2020}, type = {repORt}, number = {2020--60}, month = {Apr}, url = {https://or.rwth-aachen.de/files/research/repORt/mslp_theory_v2.pdf}}