Algorithms for railway crew management.

*(English)*Zbl 0887.90056Summary: Crew management is concerned with building the work schedules of crews needed to cover a planned timetable. This is a well-known problem in operations research and has been historically associated with airlines and mass-transit companies. More recently, railway applications have also come on the scene, especially in Europe. In practice, the overall crew management problem is decomposed into two subproblems, called crew scheduling and crew rostering. In this paper, we give an outline of different ways of modeling the two subproblems and possible solution methods. Two main solution approaches are illustrated for real-world applications. In particular we discuss in some detail the solution techniques currently adopted at the Italian railway company, Ferrovie dello Stato SpA, for solving crew scheduling and rostering problems.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B35 | Deterministic scheduling theory in operations research |

PDF
BibTeX
Cite

\textit{A. Caprara} et al., Math. Program. 79, No. 1--3 (B), 125--141 (1997; Zbl 0887.90056)

Full Text:
DOI

##### References:

[1] | N. Balakrishnan and R.T. Wong, A network model for the rotating workforce scheduling problem,Networks 20 (1990) 25–42. |

[2] | E. Balas and M.C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering,Operations Research 44 (1996) 875–890. · Zbl 0879.90155 |

[3] | E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics and subgradient optimization: A computational study,Mathematical Programming Study 12 (1980) 37–60. · Zbl 0435.90074 |

[4] | C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, Branch-and-price: Column generation for solving huge integer programs, in: J.R. Birge and K.G. Murty, eds.,Mathematical Programming: State of the Art 1994 (The University of Michigan, 1994) 186–207. · Zbl 0979.90092 |

[5] | J.E. Beasley, An algorithm for set covering problems,European Journal of Operational Research 31 (1987) 85–93. · Zbl 0679.90039 |

[6] | J.E. Beasley, A Lagrangian heuristic for set covering problems,Naval Research Logistics 37 (1990) 151–164. · Zbl 0684.90063 |

[7] | J.E. Beasley and P.C. Chu, A genetic algorithm for the set covering problem,European Journal of Operational Research 94 (1996) 392–404. · Zbl 0953.90565 |

[8] | J.E. Beasley and K. Jörnsten, Enhancing an algorithm for set covering problems,European Journal of Operational Research 58 (1992) 293–300. · Zbl 0759.90070 |

[9] | L. Bianco, M. Bielli, A. Mingozzi, S. Ricciardelli and M. Spadoni, A heuristic procedure for the crew rostering problem,European Journal of Operational Research 58 (1992) 272–283. · Zbl 0767.90032 |

[10] | L. Bodin, B. Golden, A. Assad and M. Ball, Routing and scheduling of vehicles and crews: The state of the art,Computer and Operations Research 10 (1983) 63–211. |

[11] | A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Technical Report OR-95-8, DEIS University of Bologna, 1995, extended abstract published in: W.H. Cunningham, S.T. McCormick and M. Queyranne, eds.,Proceedings of the 5th IPCO Conference, Lecture Notes in Computer Science, Vol. 1084 (Springer, Berlin, 1995) 72–84. · Zbl 0976.90086 |

[12] | A. Caprara, M. Fischetti, P. Toth and D. Vigo, Modeling and solving the crew rostering problem, Technical Report OR-95-6, DEIS University of Bologna, 1995; Also in:Operations Research, to appear. · Zbl 0987.90035 |

[13] | P. Carraresi and G. Gallo, Network models for vehicle and crew scheduling,European Journal of Operational Research 16 (1984) 139–151. · Zbl 0537.90053 |

[14] | P. Carraresi and G. Gallo, A multilevel bottleneck assignment approach to the bus drivers’ rostering problem,European Journal of Operational Research 16 (1984) 163–173. · Zbl 0537.90076 |

[15] | S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Technical Report R. 406, IASI-CNR, Rome, 1995; also in:Mathematical Programming, to appear. · Zbl 0919.90085 |

[16] | J.R. Daduna and A. Wren, eds.,Computer-Aided Transit Scheduling, Lecture Notes in Economic and Mathematical Systems, Vol. 308 (Springer, Berlin, 1988). |

[17] | M. Desrochers and J.-M. Rousseau, eds.,Computer-Aided Transit Scheduling, Lecture Notes in Economic and Mathematical Systems, Vol. 386 (Springer, Berlin, 1992). |

[18] | J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis, Time constrained routing and scheduling, in: M.O. Ball et al., eds.,Handbooks in OR & MS, Vol. 8 (Elsevier, Amsterdam, 1995) 35–139. · Zbl 0861.90052 |

[19] | M.L. Fisher, The Lagrangian relaxation method for solving integer programming problems,Management Science 27 (1981) 1–18. · Zbl 0466.90054 |

[20] | M.L. Fisher and P. Kedia, Optimal solutions of set covering/partitioning problems using dual heuristics,Management Science 36 (1990) 674–688. · Zbl 0706.90048 |

[21] | M. Gamache and F. Soumis, A method for optimally solving the rostering problem, Les Cahiers du GERAD G-93-40, Montréal, 1993. |

[22] | M. Gamache, F. Soumis, G. Marquis and J. Desrosiers, A column generation approach for large scale aircrew rostering problems, Cahiers du GERAD G-94-20, Montrèal, 1994. · Zbl 1041.90513 |

[23] | B. Hagberg, An assignment approach to the rostering problem, in: J.-M. Rousseau, ed.,Computer Scheduling of Public Transport, Vol. 2 (North-Holland, Amsterdam, 1985). |

[24] | J.K. Jachnik, Attendance and rostering systems, in: A. Wren, ed.,Computer Scheduling of Public Transport (North-Holland, Amsterdam, 1981). |

[25] | L.W. Jacobs and M.J. Brusco, A local search heuristic for large set-covering problems,Naval Research Logistic 52 (1995) 1129–1140. · Zbl 0839.90085 |

[26] | A.I.Z. Jarrah and J.T. Diamond, The crew bidline generation problem, Technical Report, SABRE Decision Technologies, 1995. |

[27] | L.A.N. Lorena and F.B. Lopes, A surrogate heuristic for set covering problems,European Journal of Operational Research 79 (1994) 138–150. · Zbl 0813.90096 |

[28] | J.-M. Rousseau, ed.,Computer Scheduling of Public Transport, Vol. 2 (North-Holland, Amsterdam, 1985). |

[29] | D.M. Ryan, The solution of massive generalized set partitioning problems in aircrew rostering,Journal of the Operational Research Society 43 (1992) 459–467. |

[30] | J.M. Tien and A. Kamiyama, On manpower scheduling algorithms,SIAM Review 24 (1982) 275–287. · Zbl 0482.90040 |

[31] | D. Wedelin, An algorithm for large scale 0–1 integer programming with application to airline crew scheduling,Annals of Operational Research 57 (1995) 283–301. · Zbl 0831.90087 |

[32] | T.H. Wise, Column generation and polyhedral combinatorics for airline crew scheduling, Ph.D. Thesis, Cornell University, 1995. |

[33] | A. Wren, ed.,Computer Scheduling of Public Transport (North-Holland, Amsterdam, 1981). · Zbl 0474.90033 |

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.