3C2 IMPROVEMENT OF CONVERGENCE OF COLUMN GENERATION FOR RAILWAY CREW SCHEDULING PROBLEM

概要

論文の詳細を見る
Railway crew scheduling problem is the problem to determine an optimal assignment of crews to each train to minimize the number of crews satisfying set covering constraints. Column generation is an effective technique for solving the railway crew scheduing problems. The problem is formulated as a huge set covering problem. Column generation requires a lot of replications to derive a lower bound. Moreover, it takes considerable computation time to obtain an upper bound using the conventional method (branch and bound for restricted columns). In this paper, we propose an improvement of column generation for railway crew scheduling problems to reduce computational effort. Dual inequalities for deriving a lower bound and a heuristic to construct a feasible solution are proposed. Computational results show the effectiveness of the proposed method compared with those of the conventional column generation.
2009-07-04