Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates. (January 2019)

• Record Type: Journal Article
• Authors: Hoffmann, Kirsten; Buscher, Udo
• Is Part Of: Computers & industrial engineering. Volume 127(2019)
• Page Start: 1143
• Page End: 1152
• Publication Date: 2019-01
• Subjects: Railway crew scheduling -- Attendance rates -- Arc flow formulation -- Valid inequalities; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.05.031
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We propose an arc flow model dealing with various practical requirements. We define several problem specific valid inequalities. For small instances (50–100 trips) solution times can be reduced by up to 94.79%. For real-world instances the root relaxation can be increased by up to 3.02%. Abstract: Crew scheduling in regional rail transport consists of generating crew duties for train operators and conductors. We focus on the latter, because in the last few years we can observe the development that just a certain percentage of trains has to be attended. The goal is to minimize crew costs while satisfying operating conditions and legal requirements. Due to the size of real-world instances these problems are typically solved with column generation techniques based on path flow models. In contrast, we present an arc flow model for the railway crew scheduling problem with attendance rates to solve small-sized instances optimally, improve solutions of real-world instances and provide good lower bounds for them. Valid inequalities offer the possibility to fasten the solution process and improve the bound of the linear relaxation of the integer problem. We define various valid inequalities and perform computational tests to estimate the influence of different valid inequalities on computation times and bounds of the linear relaxation.