A column-and-row generation algorithm for a crew planning problem in railways

The share of crew-related costs is substantial in railways and the fixed crew salaries constitute a significant portion of crew-related costs. Therefore, the number of crew members under long-term contracts is an important decision. Tactical planning is concerned with determining the required crew capacity of a crew region to operate the train schedule under the responsibility of the region. The crew capacity planning problem determines the minimum number of crew members required to cover all duties in a region while each crew member is to be associated with a feasible schedule of duties. This problem can be formulated as a pure set covering problem where a feasible crew schedule corresponds to a column in the formulation. In this study, we consider finding the minimum number of crew members associated with a set of feasible crew schedules that can be connected to other schedules from one period to the other. To formulate this version of the problem, the set covering problem is enriched with additional constraints that represent the connectivity relationship among the schedules. Existence of such constraints (i.e. rows of the formulation) depends on the existence of columns in the formulation. In this respect, a traditional column generation algorithm would not suffice to solve this problem. In order to solve this problem, we develop a column-and-row generation algorithm that simultaneously generates feasible crew schedules and associated connectivity constraints. The pricing subproblem of the column-and-row generation algorithm is formulated as a shortest path problem over a space-time network that represents the crew capacity planning problem. We present the computational study on a real-life data set acquired from Turkish State Railways.