Article ID: | iaor2014486 |
Volume: | 65 |
Issue: | 5 |
Start Page Number: | 633 |
End Page Number: | 644 |
Publication Date: | May 2014 |
Journal: | Journal of the Operational Research Society |
Authors: | Derigs U, Schfer S |
Keywords: | crew rostering |
Crew scheduling is a highly complex combinatorial problem that has substantial and consequential economic importance in practice. Although the core structure of the problem is the same in many different areas like urban transportation, airlines etc, the specific problem instances show significant differences with respect to constraints stemming from different legal, industry‐wide and firm‐specific regulations. Beasley and Cao (1996) have introduced a generic crew scheduling problem (GCSP) and a basic mathematical program. In this paper, we extend this work by introducing two types of GCSPs that represent important additional features arising in real‐world settings: the possibility of deadheading and the partitioning into duties with long (overnight) breaks in between. We present appropriate models, outline the design of a common branch and price and cut‐solution approach and report computational experience. The aim of this study is to analyse the additional complexity that occurs by introducing these concepts, as well as the reduction in operational cost that can be obtained.