Optimization Online


The Multi-Stop Station Location Problem

Felix J. L. Willamowski(willamowski***at***or.rwth-aachen.de)
Miriam Ganz(ganz***at***or.rwth-aachen.de)
Erik Mühmer(muehmer***at***or.rwth-aachen.de)

Abstract: 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.

Keywords: Approximation Algorithms, Computational Complexity, Network Design, E-Mobility, Combinatorial Optimization

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Network Optimization

Category 3: Applications -- OR and Management Sciences (Transportation )

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}, }

Download: [PDF]

Entry Submitted: 04/25/2020
Entry Accepted: 04/25/2020
Entry Last Modified: 04/25/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society