Column generation with dual inequalities for railway crew scheduling problems
Document Type
Journal Article
Publication Date
2011
Subject Area
organisation - workforce planning, mode - rail, operations - scheduling, place - asia
Keywords
Combinatorial optimization, Railway crew scheduling, Column generation, Set covering problem, Dual inequality
Abstract
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.
Rights
Permission to publish the abstracts has been given by SpringerLink, copyright remains with them.
Recommended Citation
Nishi, T., Muroi, Y., & Inuiguchi, M. (2011). Column generation with dual inequalities for railway crew scheduling problems. Public Transport, Vol. 3, (1), pp. 25-42.
