Column generation with dual inequalities for railway crew scheduling problems

Document Type

Journal Article

Publication Date


Subject Area

organisation - workforce planning, mode - rail, operations - scheduling, place - asia


Combinatorial optimization, Railway crew scheduling, Column generation, Set covering problem, Dual inequality


The railway crew scheduling problem is to determine an optimal crew assignment for the railway timetable data by minimizing the required number of crew members in order to satisfy the set covering constraints. Column generation is one of the optimization methods that can solve the problem efficiently. In order to improve the convergence of column generation, we propose dual inequalities for a Dantzig-Wolfe decomposition of railway crew scheduling problems to reduce the number of replications in the column generation procedure. The dual inequalities are generated from the characteristic of the given railway timetable data. Computational results demonstrate the effectiveness of the proposed method compared with the conventional column generation for an actual railway timetable data.


Permission to publish the abstracts has been given by SpringerLink, copyright remains with them.