Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates

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.