Refine
Year of publication
- 2003 (1)
Document Type
- Report (1) (remove)
Language
- English (1)
Has Fulltext
- yes (1)
Faculty / Organisational entity
In this paper we consider the location of stops along the edges of an already existing public transportation network, as introduced in [SHLW02]. This can be the introduction of bus stops along some given bus routes, or of railway stations along the tracks in a railway network. The goal is to achieve a maximal covering of given demand points with a minimal number of stops. This bicriterial problem is in general NP-hard. We present a nite dominating set yielding an IP-formulation as a bicriterial set covering problem. We use this formulation to observe that along one single straight line the bicriterial stop location problem can be solved in polynomial time and present an e cient solution approach for this case. It can be used as the basis of an algorithm tackling real-world instances.