Analyzing a Family of Formulations for Cyclic Crew Rostering

Thomas Breugem, Twan Dollevoet and Dennis Huisman ()

No EI2018-35, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. We derive analytical results regarding the relative strength of the dierent formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, which we use to develop an exact Branch-and-Price method, and a heuristic which aims at exploiting the information obtained from the linear relaxation. We conclude by applying our proposed solution method to practical instances from Netherlands Railways. In particular, we show that the computation time depends heavily on the selected formulation, and that the column generation approach outperforms a commercial solver on hard instances.

Keywords: Crew Planning; Roster Sequence; Branch-and-Price; Railway Optimization (search for similar items in EconPapers)
Pages: 27
Date: 2018-09-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/111555/EI2018-35.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:111555

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).