Application of column generation for railway crew scheduling problems with practical constraints

被引：0

作者：

Nishi T. ^{[1
]}

Muroi Y. ^{[1
]}

Inuiguchi M. ^{[1
]}

Takahashi S. ^{[2
]}

Kataoka K. ^{[2
]}

机构：

[1] Graduate School of Engineering Science, Osaka University, Toyonaka 560-8531, 1-3, Machikaneyama-cho

[2] Advanced Technology R and D Center, Mitsubishi Electric Corporation, Amagasaki 661-8661, 8-1-1, Tsukaguchi-honmachi

来源：

IEEJ Transactions on Electronics, Information and Systems | 2011年 / 131卷 / 06期

关键词：

Column generation; Combinatorial optimization; Dominance relation; Label setting algorithm; Meal break time constraints; Railway crew scheduling;

D O I：

10.1541/ieejeiss.131.1199

中图分类号：

学科分类号：

摘要：

In this paper, we propose a column generation method for the railway crew scheduling problem with a variety of practical constraints such as lower and upper constraints of one continuous traveling, total working time, admissible number of crews, and meal time constraints. The proposed method consists of the two steps. The first step is to derive a lower bound by the column generation and the second step is to generate a feasible solution by a heuristic method. In the proposed method, a label setting algorithm is developed to solve the pricing problem efficiently to reduce computational time. A new dominance condition is developed to eliminate unnecessary states in the label setting algorithm. A heuristic algorithm is also proposed to reduce the generation of the infeasible solutions violating the constraint on the number of the allocated crews. The effectiveness of the proposed method is evaluated by using a real railway data. © 2011 The Institute of Electrical Engineers of Japan.

引用

页码：1199 / 1208

页数：9

共 10 条

[1] Takahashi S., Kataoka K., Kojima T., Asami M., An algorithm for automatically modifying train crew schedule, IEEJ Trans. IA, 128, 11, pp. 1291-1297, (2008)
[2] Lubbecke M.E., Desrosiers J., Selected topics in column generation, Operations Research, 53, 6, pp. 1007-1023, (2005)
[3] Desrochers M., Soumis F., A column generation approach to the urban transit crew scheduling problems, Transportation Science, 23, 1, pp. 1-13, (1989)
[4] Huisman D., A column generation approach for the rail crew re-scheduling problem, European Journal of Operational Research, 180, 1, pp. 163-173, (2007)
[5] Bengtsson L., Galia R., Gustafsson T., Hjorring C., Kohl N., Railway crew pairing optimization, LNCS, 4359, pp. 126-144, (2007)
[6] Caprara A., Fischetti M., Toth P., Vigo D., Guida P.L., Algorithm for railway crew management, Mathematical Programming, 79, pp. 125-141, (1997)
[7] Abbink E., Fischetti M., Kroon L., Timmer G., Vromans M., Reinventing crew scheduling at netherlands railways, Interfaces, 35, 5, pp. 393-401, (2005)
[8] Muroi Y., Nishi T., Inuiguchi M., Improvement of Column Generation Method for Railway Crew Scheduling Problems, IEEJ Trans. EIS, 130, 2, pp. 275-283, (2010)
[9] Desrosiers Jacques, Soumis Francois, Desrochers Martin, Routing with time windows by column generation, Networks, 14, 4, pp. 545-565, (1984)
[10] Desrochers M., Soumis F., A generalized permanent labelling algorithm for the shortest path problem with time wondows, INFOR, 26, 3, pp. 191-212, (1988)

← 1 →