zbMATH — the first resource for mathematics

Simultaneous disruption recovery of a train timetable and crew roster in real time. (English) Zbl 1068.90065
Summary: This paper describes the development and implementation of an optimization model used to resolve disruptions to an operating schedule in the rail industry. Alterations to the existing train timetable and crewing roster are made simultaneously in real time-previous treatments in the literature have always decoupled these two problems and solved them in series. An integer programming model is developed that constructs a train timetable and crew roster. This model contains two distinct blocks, with separate variables and constraints for the construction of the train timetable and crew roster, respectively. These blocks are coupled by piece of work sequencing constraints and shift length constraints, which involve variables from both blocks. This unique parallel construction process is then used as the basis of a method to deal with the resolution of train disruptions in realtime. Favourable results are presented for both the combined train/driver scheduling model and the real-time disruption recovery model.

90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Cordeau, J.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transportation science, 32, 380-406, (1998) · Zbl 0987.90507
[2] Smith, B.M.; Wren, A., A bus driver scheduling system using a set covering formulation, Transportation science, 22A, 97-108, (1988)
[3] Rousseau JM, Lessard R, Blais JY. Enhancements to the HASTUS crew scheduling algorithm. Computer scheduling of public transport-2. Amsterdam: North-Holland; 1985. p. 295-310.
[4] Fores S, Proll L. Driver scheduling by integer linear programming—the TRACS II approach. Proceedings CESA’98 Computational Engineering in Systems Applications, Symposium on Industrial and Manufacturing Systems, vol. 3. 1998. p. 213-8.
[5] Bell-Booth A. Construction of a cyclic roster for locomotive engineers at Tranz rail. Technical report, ES 04, 1996.
[6] Ng A. Construction of a daily schedule of duties for locomotive engineers. Technical report, ES 19, 1996.
[7] Walker CG. A real-time optimization model for the resolution of disruptions to a train schedule. Masters thesis, University of Auckland, 2001.
[8] Szpigel B. Optimal train scheduling on a single track railway. Operations Research 1973; 343-52.
[9] Nachtigall, K., Periodic network optimization with different arc frequencies, Discrete applied mathematics, 69, 1-17, (1996) · Zbl 0856.90118
[10] Odijk, M.A., A constraint generation algorithm for the construction of periodic railway timetables, Transportation research, 30B, 91-107, (1997)
[11] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM journal on discrete mathematics, 2, 4, 550-581, (1989) · Zbl 0676.90030
[12] Bussieck, M.R.; Kreuzer, P.; Zimmermann, U.T., Discrete optimization in public rail transport, Mathematical programming, 79, 415-444, (1997) · Zbl 0887.90055
[13] Stojković, M.; Soumis, F., An optimization model for the simultaneous operational flight and pilot scheduling problem, Management science, 47, 9, 1290-1305, (2001) · Zbl 1232.90293
[14] Cordeau, J.; Stojković, G.; Soumis, F.; Desrosiers, J., Benders decomposition for simultaneous aircraft routing and crew scheduling, Transportation science, 35, 4, 375-388, (2001) · Zbl 1069.90525
[15] Haase, K.; Desaulniers, G.; Desrosiers, J., Simultaneous vehicle and crew scheduling in urban mass transit systems, Transportation science, 35, 3, 286-303, (2001) · Zbl 1069.90528
[16] Klabjan D. Topics in airline crew scheduling and large optimization. PhD thesis, Georgia Institute of Technology, Atlanta, GA, 2000.
[17] Haase K, Friberg C. An exact branch and cut algorithm for the vehicle and crew scheduling problem. Computer-aided transit scheduling. Lecture notes in economics and mathematical systems. 1999. p. 63-80. · Zbl 0935.90006
[18] Patrikalakis I, Xerocostas D. A new decomposition scheme of the urban public transport scheduling problem. Computer-aided transit scheduling. Lecture notes in economics and mathematical systems, vol. 386. 1992. p. 407-25.
[19] Torsini E, Vercellis C. An interactive system for extra-urban vehicle and crew scheduling problems. Computer-aided transit scheduling. Lecture notes in economics and mathematical systems, vol. 308. 1988. p. 41-53.
[20] Gorman, M.F., An application of genetic and tabu searches to the freight railroad operating plan problem, Annals of operations research, 78, 51-69, (1998) · Zbl 0896.90137
[21] Huntley, C.L.; Brown, D.E.; Sappington, D.E.; Markowicz, B.P., Freight routing and scheduling at CSX transportation, Interfaces, 25, 3, 58-71, (1995)
[22] Morlok, E.K.; Peterson, R.B., Final report on a development of a geographic transportation network generation and evaluation model, T transportation research forum, 11, 71-105, (1970)
[23] Ryan DM. A zero-one integer programming package for scheduling. Technical report, Report C. S. S. 85 A. E. R. E. Harwell, Oxfordshire, 1980.
[24] Foster, B.A.; Ryan, D.M., An integer programming approach to the vehicle scheduling problem, Operations research quarterly, 27, 367-384, (1976) · Zbl 0327.90030
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.