Abstract
The problem of defining suitable lines in a public transportation system (bus, railway, tram, or underground) is an important real-world problem that has also been well researched in theory. Driven by applications, it often lacks a clear description, but is rather stated in an informal way. This leads to a variety of different published line planning models. In this paper, we introduce some of the basic line planning models, identify their characteristics, and review literature on models, mathematical approaches, and algorithms for line planning. Moreover, we point out related topics as well as current and future directions of research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja RK, Möhring RH, Zaroliagis CD (eds) (2009) Robust and online large-scale optimization. Lecture Note on Computer Science, vol 5868. Springer, Berlin
ARRIVAL. Future and emerging technologies unit of EC (IST priority, 6th FP), under contract no. FP6-021235-2. http://arrival.cti.gr
Baaj MH, Mahmassani H (1991) An AI-based approach for transit route system planning and design. J Adv Transp 25(2): 187–210
Babonneau F, Vial J-P (2008) Test instances for the traffic assignment problem. Technical report, Ordecsys
Barber F, Ingolotti L, Lova A, Marin A, Mesa J, Ortega F, Perea F, Tormos P (2008) Integrating timetabling, network and line design. Technical report, ARRIVAL project
Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization. Princeton University Press, Princeton
Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1): 35–53
Bielli M, Caramia M, Caratenuto P (2002) Genetic algorithms in bus network optimization. Transp Res Circ 10(1): 19–34
Borndörfer R, Pfetsch ME (2006) Routing in line planning for public transportation. In: Operations research proceedings 2005, pp 405–410. Springer, Berlin
Borndörfer R, Grötschel M, Pfetsch ME (2007) A column generation approach to line planning in public transport. Transp Sci 41: 123–132
Borndörfer R, Grötschel M, Pfetsch ME (2008) Models for line planning in public transport. In: Computer-aided scheduling of public transport (CASPT). Lecture notes in economics and mathematical systems, vol 600, pp 363–378
Borndörfer R, Neumann M, Pfetsch ME (2009) The line connectivity problem. In: Operations research proceedings 2008, pp 557–562. Springer, Berlin
Bouma A, Oltrogge C (1994) Linienplanung und simulation für öffentliche verkehswege in praxis und theorie. Eisenbahntechnische Rundschau 43(6): 369–378 (in German)
Bussieck MR (1998) Optimal lines in public transport. PhD thesis, Technische Universität Braunschweig
Bussieck MR, Kreuzer P, Zimmermann UT (1996) Optimal lines for railway systems. Eur J Oper Res 96(1): 54–63
Bussieck MR, Lindner T, Lübbecke ME (2004) A fast algorithm for near cost optimal line plans. Math Methods Oper Res 59(3): 205–220
Caimi G, Laumanns M, Schüpbach K, Wörner S, Fuchsberger M (2009) The periodic service intention as a conceptual frame for generating timetables with partial periodicity. In: Proceedings of the international seminar on railway operations reserach (ISROR)
Carey M (1994) A model and strategy for train pathing with choice of lines, platforms and routes. Transp Res B 28(5): 333–353
Carraresi P, Malucelli F, Pallottino S (1995) On the regional mass transit assignment problem. In: Sciomachen A (ed) Optimization in industry. 3. Mathematical programming and modeling techniques in practice. Wiley, New York, pp 19–34
Ceder A, Wilson NHM (1986) Bus network design. Transp Res B 20(4): 331–344
Chakroborty P (2003) Genetic algorithms for optimal urban transit network design. Comput Aided Civ Infrastruct Eng 18(3): 184–200
Chua TA (1984) The planning of urban bus routes and frequencies: a survey. Transportation 12(2): 147–172
Cicerone S, D’Angelo G, Di Stefano G, Frigioni D, Navarra A, Schachtebeck M, Schöbel A (2009) Recoverable robustness in shunting and timetabling. In: Robust and online large-scale optimization. Lecture notes in computer science, vol 5868, pp 28–60. Springer, Berlin
Claessens MT (1994) De kost-lijnvoering. Master’s thesis, University of Amsterdam, Amsterdam (in Dutch)
Claessens MT, van Dijk NM, Zwaneveld PJ (1998) Cost optimal allocation of rail passenger lines. Eur J Oper Res 110: 474–489
Desaulniers G, Hickman M (2007) Public transit. In: Laporte G, Barnhart C (eds) Transportation. Handbooks in operations reserch and management science, vol 14. Elsevier, Amsterdam, pp 69–127
Dienst H (1978) Linienplanung im spurgeführten Personenverkehr mit Hilfe eines heuristischen Verfahrens. PhD thesis, Technische Universität Braunschweig (in German)
Dubois D, Bell G, Llibre M (1979) A set of methods in transportation network synthesis and analysis. J Oper Res Soc 30(8): 797–808
Erera AL, Morales JC, Svalesbergh M (2009) Robust optimization for empty repositioning problems. Oper Res 57(2): 468–483
Fan W, Machemehl RB (2006) Optimal transit route network design problem with variable transit demand: genetic algorithm approach. J Transp Eng 132: 40–51
Fischetti M, Monaci M (2009) Light robustness. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Lecture note on computer science, vol 5868, pp 61–84. Springer, Berlin
Goerigk M, Schachtebeck M, Schöbel A (2011) LinTim—integrated optimization in public transportation. http://lintim.math.uni-goettingen.de/
Goossens J (2004) Models and algorithms for railway line planning problems. PhD thesis, University of Maastricht, Maastricht
Goossens J, van Hoesel CPM, Kroon LG (2004) A branch and cut approach for solving line planning problems. Transp Sci 38: 379–393
Goossens J, van Hoesel CPM, Kroon LG (2006) On solving multi-type railway line planning problems. Eur J Oper Res 168(2): 403–424
Hamacher, HW, Drezner, Z (eds) (2001) Location theory—applications and theory. Springer, Berlin
Israeli Y, Ceder A (1995) Transit route design using scheduling and multiobjective programming techniques. In: Computer-aided scheduling of public transport (CASPT). Lecture notes in economics and mathematical systems, vol 430, pp 56–75. Springer, Berlin
Kepaptsoglou K, Karlaftis M (2009) Transit route network design problem: Review. J Transp Eng 135(8): 491–505
Kim D, Barnhart C (1997) Transportation service network design: models and algorithms. In: Computer-aided scheduling of public transport (CASPT). Lecture notes in economics and mathematical systems, vol 471, pp 259–283. Springer, Berlin
Klier MJ, Haase K (2008) Line optimization in public transport systems. In: Operations research proceedings 2007, pp 473–478. Springer, Berlin
Kontogiannis S, Zaroliagis C (2008a) Robust line planning through elasticity of frequencies. Technical report, ARRIVAL project
Kontogiannis S, Zaroliagis C (2008b) Robust line planning under unknown incentives and elasticity of frequencies. In: Fischetti M, Widmayer P (eds) ATMOS 2008—8th workshop on algorithmic approaches for transportation modeling, optimization, and systems, Dagstuhl, Germany
Lampkin W, Saalmans PD (1967) The design of routes, service frequencies and schedules for a municipal bus undertaking: a case study. Oper Res Q 18: 375–397
Laporte G, Mesa JA, Ortega FA (2005) Maximizing trip coverage in the location of a single rapid transit alignment. Ann Oper Res 136: 49–63
Laporte G, Marín A, Mesa JA, Ortega FA (2007) An integrated methodology for rapid transit network design. In: Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359, pp 187–199. Springer, Berlin
Laporte G, Mesa JA, Ortega F, Pozo M (2009) Locating a metro line in a historical city centre: application to sevilla. Technical report, ARRIVAL Project
Liebchen C (2008) Linien-, Fahrplan-, Umlauf- und Dienstplanoptimierung: Wie weit können diese bereits integriert werden? In: Friedrich M (ed) Heureka’08—Optimierung in Transport und Verkehr, Tagungsbericht. FGSV Verlag (in German)
Liebchen C, Möhring R (2007) The modeling power of the periodic event scheduling problem: railway timetables—and beyond. In: Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359, pp 3–40. Springer, Berlin
Liebchen C, Lüebbecke M, Möhring RH, Stiller S (2009) The concept of recoverable rrobustness, linear programming recoery, and railway applications. In: Ahuja RK, Möhring RH, Zaroliagis CD (eds) Robust and online large-scale optimization. Lecture notes in computer science, vol 5868. Springer, Berlin
Lindner T (2000) Train schedule optimization in public rail transport. PhD thesis, Technische Universität Braunschweig
Mandl CE (1980) Evaluation and optimization of urban public transportation networks. Eur J Oper Res 5: 396–404
Marin ÁG, Jaramillo P (2009) Urban rapid transit network design: accelerated benders decomposition. Ann Oper Res 169(1): 35–53
Martínez FJ, Melián B, Garzón A, Mesa JA, Moreno J, Ortega FA (2005) Grasp metaheuristic for the rapid transit network design. In: Actas del IV Congreso Español sobre Metaheurísticos (MAEB), pp 601–608 (in Spanish)
Mauttone A, Urquharta ME (2009) A route set construction algorithm for the transit network design problem. Comput Oper Res 36(8): 2440–2449
Michaelis M, Schöbel A (2009) Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented approach. Public Transp 1(3): 211–232
Nachtigall K, Jerosch K (2008) Simultaneous network line planning and traffic assignment. In: Fischetti M, Widmayer P (eds) ATMOS 2008—8th workshop on algorithmic approaches for transportation modeling, optimization, and systems, Dagstuhl, Germany. http://drops.dagstuhl.de/opus/volltexte/2008/1589
Oltrogge C (1994) Linienplanung für mehrstufige Bedienungssysteme im öffentlichen Personenverkehr. PhD thesis, TU Braunschweig (in German)
Pape U, Reinecke Y-S, Reinecke E (1995) Line network planning. In: Computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems, vol 430
Patriksson M (1994) The traffic assignment problem: models and methods. Topics in transportation, VSP
Patz A (1925) Die richtige Auswahl von Verkehrslinien bei großen Strassenbahnnetzen. Verkehrstechnik, 50/51 (in German)
Peeta S, Ziliaskopoulos A (2001) Foundations of dynamic traffic assignment: the past, the present and the future. Netw Sp Econ 1: 233–265
Puhl C, Stiller S (2007) The maximum capacity of a line plan is inapproximable. Technical report, ARRIVAL Project
Quak CB (2003) Bus line planning. Master’s thesis, TU Delft
Schmidt M, Schöbel A (2009) Location of speed-up networks. Technical report, Institut für Numerische und Angewandte Mathematik, Georg-August Universität Göttingen (submitted)
Schmidt M, Schöbel A (2010) The complexity of integrating routing decisions in public transportation models. In: Erlebach T, Lübbecke M (eds) Proceedings of ATMOS10, Dagstuhl, Germany. OpenAccess series in informatics (OASIcs), vol 14, pp 156–169, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
Scholl S (2005) Customer-oriented line planning. PhD thesis, Technische Universität Kaiserslautern
Schöbel A (2010) Light robustness and the trade-off between robustness and nominal quality. Technical report, Preprint-Reihe, Institut für Numerische und Angewandte Mathematik, Georg-August Universität Göttingen, Nr. 2010.08 (submitted)
Schöbel A, Scholl S (2003) Planung von Linien mit minimalen Umsteigevorgängen. In: Mattfeld D (ed) Proceedings of the GOR-workshop on “Optimierung im öffentlichen Nahverkehr”, pp 69–89. http://server3.winforms.phil.tu-bs.de/gor/tagung34/
Schöbel A, Scholl S (2006a) Line planning with minimal travel time. In: 5th workshop on algorithmic methods and models for optimization of railways, number 06901, Dagstuhl seminar proceedings
Schöbel A, Schwarze S (2006b) A game-theoretic approach to line planning. In: 6th workshop on algorithmic methods and models for optimization of railways, number 06002, Dagstuhl Seminar proceedings
Schwarze S (2008) Path player games: analysis and applications. Springer, Berlin
Silman LA, Brazily Z, Passy U (1974) Planning the route system for urban busses. Comput Oper Res 1: 201–211
Simonis C (1981) Optimierung von Omnibuslinien. Technical report, Berichte Stadt-Region-Land, Institut für Stadtbauwesen, RWTH Aachen (in German)
Sonntag H (1977) Linienplanung im öffentlichen Personennahverkehr. PhD thesis, TU Berlin (in German)
Sonntag H (1979) Ein heuristisches Verfahren zum Entwurf nachfrageorientierter Linienführung im öffentlichen Personenverkehr. Z Oper Res 23 (in German)
Torres LM, Torres R, Borndörfer R, Pfetsch ME (2008a) Line planning on paths and tree networks with applications to the quito trolebús system. In: Fischetti M, Widmayer P (eds) ATMOS 2008—8th workshop on algorithmic approaches for transportation modeling, optimization, and systems, Dagstuhl, Germany. http://drops.dagstuhl.de/opus/volltexte/2008/1583
Torres LM, Torres R, Borndörfer R, Pfetsch ME (2008b) On line planning problem in tree networks. ZIB-Report 08-52
Wegel H (1974) Fahrplangestaltung für taktbetriebene Nahverkehrsnetze. PhD thesis, TU Braunschweig (in German)
Zhao F, Zeng X (2006) Optimization of transit network layout and headway with a combined genetic algorithm and simulated annealing method. Eng Optim 38(6): 701–722
Zimmermann UT, Bussieck MR, Krista M, Wiegand K-D (1997) Linienoptimierung—modellierung und praktischer einsatz. In: Hoffmann K-H, Jaeger W, Lohmann T, Schunck H (eds) Mathematik—Schlüsseltechnologie fuer die Zukunft, pp 595–607 (in German)
Zwaneveld PJ (1997) Railway planning—routing of trains and allocation of passenger lines. PhD thesis, School of Management, Rotterdam
Zwaneveld PJ, Claessens MT, van Dijk NM (1996) A new method to determine the cost optimal allocation of passenger lines. In: Defence or attack: proceedings of 2nd TRAIL PhD congress 1996, Part 2, Delft/Rotterdam. TRAIL Research School
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Schöbel, A. Line planning in public transportation: models and methods. OR Spectrum 34, 491–510 (2012). https://doi.org/10.1007/s00291-011-0251-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-011-0251-6