Column generation with a resource constrained shortest path algorithm applied to train crew scheduling

This thesis deals with a large real world application of the crew scheduling problem. We formulate this problem as a set covering problem with additional constraints. The columns of the formulation correspond to shifts that are in accordance with the labour rules. The crew scheduling problem is proven to be NP-complete, and complete enumeration of all shifts is computationally intractable for most real-life applications. Column generation techniques are often used in literature to solve (integer) linear programs that are too large to consider all variables explicitly. In this thesis, we investigate the applicability of column generation to crew scheduling. The restricted master problem is the LP relaxation of the original program. Promising columns are generated inside the pricing problem. The pricing problem is formulated as a resource constrained shortest path algorithm. Performance improvements are obtained if we solve the pricing problem over different parts of the network. The independent pricing subproblems can be solved in parallel. The column generation technique provides good quality solutions within reasonable computation time for problem instances with up to 1500 tasks.