Independent Crew Scheduling in Public Transport: Implementing a Column Generation Approach

I will present the solution method for independent crew scheduling I implemented for my diploma thesis. Independent crew scheduling is based exclusively on the timetable. Hence, much more possible duties can be taken into account for scheduling than in traditional crew scheduling.

In the presented solution approach, independent crew scheduling is formulated as a set covering problem. In order to solve the LP-relaxation of this problem column generation is used. The master problem in this connection is solved by CPLEX. For the pricing problem a two phase procedure is applied. Integer solutions were found by the branch-and-bound algorithm of CPLEX. The approach was tested on randomly generated data instances. Furthermore, I would like to discuss the use of a branch-and-price framework.