The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company regulations. Previous work on CRP addresses mainly urban mass-transit systems, in which the minimum number of crews to perform the duties can easily be determined, and the objective is to evenly distribute the workload among the crews. In typical railway applications, however, the roster construction has to take into account more involved sequencing rules, and the main objective is the minimization of the number of crews needed to perform the duties. In this paper we propose a basic model for CRP, and describe a Lagrangian lower bound based on the solution of an assignment problem on a suitably defined graph. The information obtained through the lower bound computation is used to drive an effective algorithm for finding a tight approximate solution to the problem. Computational results for real-world instances from railway applications involving up to 1,000 duties are presented, showing that the proposed approach yields, within short computing time, lower and upper bound values that are typically very close. The code based on the approach we propose won the FARO competition organized by the Italian railway company, Ferrovie dello Stato SpA, in 1995. © 1998 INFORMS.

Caprara A., Toth P., Vigo D., Fischetti M. (1998). Modeling and solving the crew rostering problem. OPERATIONS RESEARCH, 46(6), 820-830 [10.1287/opre.46.6.820].

Modeling and solving the crew rostering problem

Caprara A.
Membro del Collaboration Group
;
Toth P.
Membro del Collaboration Group
;
Vigo D.
Membro del Collaboration Group
;
1998

Abstract

The Crew Rostering Problem (CRP) aims at determining an optimal sequencing of a given set of duties into rosters satisfying operational constraints deriving from union contract and company regulations. Previous work on CRP addresses mainly urban mass-transit systems, in which the minimum number of crews to perform the duties can easily be determined, and the objective is to evenly distribute the workload among the crews. In typical railway applications, however, the roster construction has to take into account more involved sequencing rules, and the main objective is the minimization of the number of crews needed to perform the duties. In this paper we propose a basic model for CRP, and describe a Lagrangian lower bound based on the solution of an assignment problem on a suitably defined graph. The information obtained through the lower bound computation is used to drive an effective algorithm for finding a tight approximate solution to the problem. Computational results for real-world instances from railway applications involving up to 1,000 duties are presented, showing that the proposed approach yields, within short computing time, lower and upper bound values that are typically very close. The code based on the approach we propose won the FARO competition organized by the Italian railway company, Ferrovie dello Stato SpA, in 1995. © 1998 INFORMS.
1998
Caprara A., Toth P., Vigo D., Fischetti M. (1998). Modeling and solving the crew rostering problem. OPERATIONS RESEARCH, 46(6), 820-830 [10.1287/opre.46.6.820].
Caprara A.; Toth P.; Vigo D.; Fischetti M.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/915178
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 92
  • ???jsp.display-item.citation.isi??? ND
social impact