Abstract
In this paper we consider the location of stops along the edges of an already existing public transportation network. This can be the introduction of bus stops along given 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 bicriteria problem is in general NP-hard. We present a finite dominating set yielding an IP-formulation as a bicriteria set covering problem. Using this formulation we discuss cases in which the bicriteria stop location problem can be solved in polynomial time. Extensions for tackling real-world instances are mentioned.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bellman, R. (1958). “On a Routing Problem.” Quarterly Applied Mathematics 16, 87–90.
Bruno, G., G. Ghiani, and G. Improta. (1998). “A multi-Modal Approach to the Location of a Rapid Transit Line.” European Journal of Operational Research 104(2), 321–332.
Caprara, A., M. Fischetti, and P. Toth (1999). “A Heuristic Method for the Set Covering Problem.” Operations Research 47(5), 730–743.
Church, R. and C. ReVelle (1974). “The Maximal Covering Location Problem.” Papers of the Regional Science Association 32, 101–118.
Current, J., C. ReVelle, and J. Cohon. (1987). “The Median Shortest Path Problem: A Multiobjective Approach to Analyze Cost vs. Accessibility in the Design of a Transportation Network.” Transportation Science 21(3), 490–503.
Ehrgott, M. (2000). Multiple Criteria Optimization. Vol. 491 of Lecture Notes in Economics and Mathematical Systems Springer, Berlin.
Ford, L.R. and D.R. Fulkerson (1962). Flows in Networks. Princeton University Press.
Galil, Z. and K. Park (1990). “A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.” Information Processing Letters 33, 309–311.
Haimes, Y.Y. and V. Chankong (1983). Multiobjective Decision Making—Theory and Methodology. North Holland, New York.
Hamacher, H.W., A. Liebers, A. Schöbel, D. Wagner, and F. Wagner (2001). “Locating New Stops in a Railway Network.” Electronic Notes in Theoretical Computer Science 50(1).
Hassin, R. and A. Tamir (1991). “Improved Complexity Bounds for Location Problems on the Real Line.” Operations Research Letters 10, 395–402.
Kranakis, E., P. Penna, K. Schlude, D.S. Taylor, and P. Widmayer (2002). “Improving Customer Proximity to Railway Stations.” Technical report, ETH Zürich.
Laporte, G., J.A. Mesa, and F.A. Ortega (2002a). “Locating Stations on Rapid Transit lines.” Computers and Operations Research 29, 741–759.
Laporte, G., J.A. Mesa, and F.A. Ortega (2002b). “Maximizing Trip Coverage in the Location of a Single Rapid Transit Alignment.” ISOLDE IX, Fredericton & St. Andrews, New Brunswick, Canada.
Minkowski, H. (1967). Gesammelte Abhandlungen, Band 2. Chelsea Publishing Company, New York.
Murray, A. (2001a). “Coverage Models for Improving Public Transit System Accessibility and Expanding Access.” Technical report, Department of Geography, Ohio State University.
Murray, A. (2001b). “Strategic Analysis of Public Transport Coverage.” Socio-Economic Planning Sciences 35, 175–188.
Murray, A., R. Davis, R.J. Stimdon, and L. Ferreira (1998). “Public Transportation Access.” Transportation Research D 3(5), 319–328.
Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. Wiley.
Ruf, N. and A. Schöbel. (2004). “Set Covering Problems with almost Consecutive ones Property.” Discrete Optimization 1(2), 215–228.
Schöbel, A. (2003). Customer-Oriented Optimization in Public Transportation. Habilitationsschrift, Universität Kaiserslautern.
Schöbel, A., H.W. Hamacher, A. Liebers, and D. Wagner. (2002). “The Continuous Stop Location Problem in Public Transportation.” Technical report, Universität Kaiserslautern. Report in Wirtschaftsmathematik 81.
Schöbel A., and M. Schröder. (2003). “Covering Population Areas by Railway Stops.” In Proceedings of OR 2002, Klagenfurt, Springer.
Steuer, R.E. (1989). Multiple Criteria Optimization: Theory, Computation, and Application. Krieger Publishing Company, Malabar, Florida.
Toregas, C. (1971). “ The Location of Emergency Service Facilities.” Operations Research 19, 1363–1373.
Toregas, C., R. Swain, C. ReVelle, and L. Bergman. (1971). “The Location of Emergency Facilities.” Operations Research 19, 1363–1373.
White, J. and K. Case. (1974). “On Covering Problems and the Central Facility Location Problem.” Geographical Analysis 6, 281–293.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Schöbel, A. Locating Stops Along Bus or Railway Lines—A Bicriteria Problem. Ann Oper Res 136, 211–227 (2005). https://doi.org/10.1007/s10479-005-2046-0
Issue Date:
DOI: https://doi.org/10.1007/s10479-005-2046-0