×

zbMATH — the first resource for mathematics

Discrete optimization in public rail transport. (English) Zbl 0887.90055
Summary: Many problems arising in traffic planning can be modelled and solved using discrete optimization. We will focus on recent developments which were applied to large scale real world instances. Most railroad companies apply a hierarchically structured planning process. Starting with the definition of the underlying network used for transport one has to decide which infrastructural improvements are necessary. Usually, the rail system is periodically scheduled. A fundamental base of the schedule are the lines connecting several stations with a fixed frequency. Possible objectives for the construction of the line plan may be the minimization of the total cost or the maximization of the passengers’s comfort satisfying certain regulations. After the lines of the system are fixed, the train schedule can be determined. A criterion for the quality of a schedule is the total transit time of the passengers including the waiting time which should be minimized satisfying some operational constraints. For each trip of the schedule a train consisting of a locomotive and some carriages is needed for service. The assignment of rolling stock to schedule trips has to satisfy operational requirements. A comprehensible objective is to minimize the total cost. After all strategic and tactical planning the schedule has to be realized. Several external influences, for example delayed trains, force the dispatcher to recompute parts of the schedule on-line.

MSC:
90B06 Transportation, logistics and supply chain management
90C90 Applications of mathematical programming
90B35 Deterministic scheduling theory in operations research
90C06 Large-scale problems in mathematical programming
90C35 Programming involving graphs or networks
Software:
PESPLib; CPLEX; GENCOL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Adamski, Real-time computer aided adaptive control in public transport from the point of schedule reliability, in: J.R. Daduna, I. Branco and J.M.P. Paixão, eds.,Computer-Aided Transit Scheduling: Proceedings of the 6th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 430 (Springer, New York, 1995) 278–295. · Zbl 0852.90064
[2] R.N. Anthony,Planning and Control Systems: A Framework for Analysis (Harvard, Boston, 1965).
[3] R. Barbour and J.D. Fricker, Estimating an origin-destination table using a method based on shortest augmenting paths,Transportation Research. Part B 28 (1994) 77–89.
[4] R. Battiti and G. Tecchiolli, The reactive tabu search,ORSA J. Comput. 6 (2) (1994) 126–140. · Zbl 0807.90094
[5] A.A. Bertossi, P. Carraresi and G. Gallo, On some matching problems arising in vehicle scheduling models,Networks 17 (1987) 271–281. · Zbl 0646.90042
[6] R.E. Bixby, Private communication, 1995.
[7] U. Blasum, M.R. Bussieck, W. Hochstättler, C. Moll, H.-H. Scheel and T. Winter, Scheduling trams in the morning is hard, Technical Report, TU Braunschweig, 1996. · Zbl 0947.90044
[8] A. Bouma and C. Oltrogge, Linienplanung und Simulation für öffentliche Verkehrswege in Praxis und Theorie,ETR - Eisenbahntechnische Rundschau 43 (6) (1994) 369–378.
[9] P. Brucker, R.E. Burkard and J. Hurink, Cyclic schedules forr irregularly occuring events,Journal of Compututational and Applied Mathematics 30 (1990) 173–189. · Zbl 0718.90043
[10] M.R. Bussieck, P. Kreuzer and U.T. Zimmermann, Optimal lines for railway systems,European Journal of Operation Research 96 (1) (1997) 54–63. · Zbl 0926.90005
[11] M.R. Bussieck, Optimal lines in public rail transport, Ph.D. Thesis, TU Braunschweig (1997), to appear. · Zbl 0887.90055
[12] A. Caprara, M. Fischetti, P. Toth, D. Vigo and P.L. Guida, Algorithms for railway crew management,Mathematical Programming 79 (1997) 125–141. · Zbl 0887.90056
[13] M. Carey, A model and strategy for train pathing with choice of lines, platforms, and routes,Transportation Research. Part B 28 (5) (1994) 333–353.
[14] G. Carpaneto and P. Toth, Some new branching and bounding criteria for the asymmetric travelling salesman problem,Management Science 26 (1980) 736–743. · Zbl 0445.90089
[15] G. Carpaneto, M. Dell’Amico, M. Fischetti and P. Toth, A branch and bound algorithm for the multiple depot vehicle scheduling problem,Networks 19 (1989) 531–548. · Zbl 0672.90073
[16] E. Cascetta and S. Nguyen, A unified framework for estimating or updating origin/destination matrices from traffic counts,Transportation Research, Part B 21 (1987) 437–455.
[17] A. Ceder, A procedure to adjust transit trip departure times through minimizing the maximum headway,Computers and Operations Research 18 (5) (1991) 417–431. · Zbl 0744.90028
[18] A. Ceder and Y. Israeli, Scheduling considerations in designing transit routes at the network level, in: M. Desrochers and J.M. Rousseau, eds.,Computer-Aided Transit Scheduling: Proceedings of the 5th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 386 (Springer, New York, 1992) 113–136.
[19] P. Cenek, Simulation of processes in a marshalling yard, in:Computers in Railways V, Vol. I, Chapter ”Marshalling and Distribution” (Computational Mechanics Publications, 1996) 501–510.
[20] M.T. Claessens, N.M. van Dijk and P.J. Zwaneveld, Cost optimal allocation of passenger lines, Technical Report 231, Erasmus Universiteit, Rotterdam, 1995. · Zbl 0948.90097
[21] CPLEX Optimization, Inc., Using the CPLEX callable library, Manual, 1995.
[22] J.R. Daduna and A. Wren, eds.,Computer-aided transit scheduling: Proceedings of the 4th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 308 (Springer, New York, 1988). · Zbl 0687.90093
[23] J.R. Daduna, I. Branco and J.M.P. Paixão, eds.,Computer-Aided Transit Scheduling: Proceedings of the 6th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 430 (Springer, New York, 1995). · Zbl 0829.90052
[24] J.R. Daduna and S. Voß, Practical experiences in schedule synchronization, in: J.R. Daduna, I. Branco and J.M.P. Paixão, eds.,Computer-Aided Transit Scheduling: Proceedings of the 6th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 430 (Springer, New York, 1995) 39–55. · Zbl 0853.90041
[25] M. Desrochers and J.M. Rousseau, eds.,Computer-Aided Transit Scheduling: Proceedings of the 5th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 386 (Springer, New York, 1992). · Zbl 0790.90030
[26] J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis, Time constrained routing and scheduling, in:Handbooks in Operations Research and Management Science, Vol. 8 (Elsevier, Amsterdam, 1995) Chapter 2, 35–139. · Zbl 0861.90052
[27] H. Dienst, Linienplanung im spurgeführten Personenfernverkehr mit Hilfe eines heuristischen Verfahrens, Ph.D. Thesis, TU Braunschweig, 1978.
[28] W. Domschke, Schedule synchronization for public transit networks,OR Spektrum 11 (1989) 17–24. · Zbl 0658.90034
[29] W. Domschke, P. Forst and S. Voß, Tabu search techniques for the quadratic semi-assignment problem, in: G. Fandel, T. Gulledge and A. Jones, eds.,New Directions for Operations Research in Manufacturing (Springer, Berlin, 1992) 389–405.
[30] M.A. Forbes, J.N. Holt and A.M. Watts, An exact algorithm for multiple depot bus scheduling,European Journal of Operations Research 72 (1994) 115–124. · Zbl 0800.90569
[31] M. Grötschel, A. Löbel and M. Völker, Optimierung des Fahrzeugumlaufs im öffentlichen Nahverkehr, in: K.-H. Hoffmann, W. Jäger, Th. Lohmann and H. Schnuck, eds.,Mathematik – Schlüsseltechnologie für die Zukunft (Springer, Berlin, 1997) 609–624. · Zbl 0872.90033
[32] K. Hoffman and M. Padberg, LP-based combinatorial problem solving,Annals of Operations Research 4 (1985) 145–194. · Zbl 0568.90061
[33] J.S. Hooghiemstra, Design of regular interval timetables for strategic and tactical railway planning, in: J. Allan, C.A. Brebbia, R.J. Hill, G. Sciutto and S. Sone, eds.,Computers in Railways V, Vol. 1 (Computational Mechanics Publications, 1996) 393–402.
[34] K. Jörnsten and S.W. Wallace, Overcoming the (apparent) problem of inconsistency in origin-destination matrix estimations,Transportation Science 27 (4) (1993) 374–380. · Zbl 0800.90416
[35] W.-D. Klemt and W. Stemme, Schedule synchronization for public transit networks, in: J.R. Daduna and A. Wren, eds.,Computer-aided transit scheduling: Proceedings of the 4th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 308 (Springer, New York, 1988) 327–335.
[36] V. Klima and A. Kavicka, RBSIM – simulation model of marshalling yard operation,Computers in Railways V, Vol. 1, Chapter ”Marshalling and Distribution” (Computational Mechanics Publications, 1996) 493–500.
[37] A. Kokott and A. Löbel, Lagrangean relaxations and subgradient methods for multiple-depot vehicle scheduling problems, Technical Report SC 96-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), 1996.
[38] M. Krista, Verfahren zur Fahrplanoptimierung dargestellt am Beispiel der Synchronzeiten, Dissertation, TU Braunschweig, 1996.
[39] L.G. Kroon and P.J. Zwaneveld, Routing trains through railway stations including shunting decisions, in: P. Kleinschmidt, A. Bachem, U. Derigs, D. Fischer, U. Leopold-Wildburger and R. Möhring, eds.,Operations Research Proceedings 1995 (Springer, Berlin, 1995) 438–444.
[40] L.G. Kroon, H.E. Romeijn and P.J. Zwaneveld, Routing trains through railway stations: Complexity issues,European Journal on Operations Research 98 (3) (1997) 485–598. · Zbl 0930.90010
[41] C. Lardinois, T. Crainic and J. Dion, An interactive graphic approach for the integrated design of intercity transportation timetables and vehicle operations,Computers and Operations Research 19 (2) (1992) 139–149. · Zbl 0825.90351
[42] Y. Li, J.-M. Rousseau and M. Gendreau, Real-time dispatching of public transit operations with and without bus location information, in: J.R. Daduna, I. Branco and J.M.P. Paixão, eds.,Computer-Aided Transit Scheduling: Proceedings of the 6th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 430 (Springer, New York, 1995) 296–308. · Zbl 0852.90067
[43] A. Löbel, Solving large-scale real-world minimum-cost flow problems by a network simplex method, Technical Report SC 96-7, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), 1996.
[44] A. Löbel, Solving the LP relaxations of large-scale multiple-depot vehicle scheduling problems exactly, Technical Report SC 96-26, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), 1996.
[45] A. Löbel, Optimal vehicle scheduling in public transit, Ph.D. Thesis, Technical University Berlin (1997), to appear.
[46] W.D. Middleton, New York megalopolis plans regional rail expansion,Railway Gazette International, 1997.
[47] K. Nachtigall, Exact solution methods for periodic programs, Technical Report 14, Universität Hildesheim, 1993.
[48] K. Nachtigall, Cutting planes for a polyhedron associated with a periodic network, Technical Report IB 112-96/17, Institut für Flugführung Braunschweig, 1996.
[49] K. Nachtigall, Periodic network optimization with different arc frequencies,Discrete Applied Mathematics 69 (1996) 1–17. · Zbl 0856.90118
[50] K. Nachtigall and S. Voget, Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks, Technical Report, Universität Hildesheim, 1996; also in:European Journal on Operations Research, to appear. · Zbl 0921.90068
[51] B. Neng, Zur Erstellung von optimalen Triebfahrzeugumläufen,Zeitschrift für Operations Research Ser. A–B 25 (1981) 159–185.
[52] M.A. Odijk, A constraint generation algorithm for the construction of periodic railway timetables,Transportation Research. Part B 30 (6) (1996) 455–464.
[53] C. Oltrogge, Linienplanung für mehrstufige Bedienungssyteme im öffentlichen Personenverkehr, Ph.D. Thesis, TU Braunschweig, 1994.
[54] U. Pape, Y.-S. Reinecke and E. Reinecke, Line network planning, in: J.R. Daduna, I. Branco and J.M.P. Paixão, eds.,Computer-Aided Transit Scheduling: Proceedings of the 6th International Workshop on Computer-aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 430 (Springer, New York, 1995) 1–7. · Zbl 0853.90049
[55] A. Patz, Die richtige Auswahl von Verkehrslinien bei großen Straßenbahnnetzen,Verkehrstechnik 50/51 (1925).
[56] K. Pierick and K.-D. Wiegand, Methodische Ansätze für eine Optimierung des schienengebundenen Personenfernverkehrs,Schienen der Welt 46 (1976) 197–203.
[57] A. Radtke, Dispositionsmodell für den optimierten Betriebsmitteleinsatz der Eisenbahn, Ph.D. Thesis, Universität Hannover, 1995.
[58] C.C. Ribeiro and F. Soumis, A column generation approach to the multiple-depot vehicle scheduling problem,Operations Research 42 (1) (1994) 41–52. · Zbl 0798.90038
[59] R.T. Rockafellar,Network Flows and Monotropic Optimization (John Wiley and Sons, New York, 1984). · Zbl 0596.90055
[60] B. Sansó, M. Desrochers, J. Desrosiers, Y. Dumas and F. Soumis, Modeling and solving routing and scheduling problems: GENCOL’s user guide, Technical Report, GERAD Montreal, 1990.
[61] A. Schrijver,Theory of Linear and Integer Programming (John Wiley and Sons, Chichester, 1986). · Zbl 0665.90063
[62] A. Schrijver, Minimum circulation of railway stock,CWI Quarterly 6 (3) (1993) 205–217. · Zbl 0800.90397
[63] P. Serafini and W. Ukovich, A mathematical model for periodic scheduling problems,SIAM Journal on Discrete Mathematics 2 (4) (1989) 550–581. · Zbl 0676.90030
[64] H.D. Sherali, R. Sivanandan and A.G. Hobeika, A linear programming approach for synthesizing origin-destination trip tables from link traffic volumes,Transportation Research. Part B 28 (3) (1994) 213–233.
[65] S. Voß, Network design formulations in schedule synchronization, in: M. Desrochers and J.-M. Rousseau, eds.,Computer-aided Transit Scheduling, Lecture Notes in Economic and Mathematical Systems, Vol. 386 (Springer, Berlin, 1992) 137–152.
[66] M. van Witsen, The Netherlands and new international rail infrastructure,Tijdschrift voor Economische en Sociale Geografie 87 (2) (1996) 181–187.
[67] U. Zimmermann, Linear and combinatorial optimization in ordered algebraic structures,Annals of Discrete Mathematics, Vol. 10 (North-Holland, Amsterdam, 1981). · Zbl 0466.90045
[68] U.T. Zimmermann, M.R. Bussieck, M. Krista and K.-D. Wiegand, Linienoptimierung – Modellierung und praktischer Einsatz, in: K.-H. Hoffmann, W. Jäger, Th. Lohmann and H. Schunck, eds.,Mathematik – Schlüsseltechnologie für die Zukunft (Springer, Berlin, 1997) 595–607. · Zbl 0869.90020
[69] P.J. Zwaneveld, M.T. Claessens and N.M. van Dijk, A new method to determine the cost optimal allocation of passenger lines, in:Defence or Attack: Proceedings 2nd TRAIL PhD Congress 1996, Part 2, Delft/Rotterdam (TRAIL Research School, 1996). · Zbl 0948.90097
[70] P.J. Zwaneveld, S. Dauzère-Pérès, S.P.M. van Hoesel, L.G. Kroon, H.E. Romeijn, M. Salomon and H.W. Ambergen, Routing trains through railway stations: Model formulation and algorithms,Transportation Science 30 (3) (1996) 181–194. · Zbl 0884.90079
[71] P.J. Zwaneveld, Private communication, 1997.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.