Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 214607, 15 pages
Research Article

Modeling and Algorithms of the Crew Rostering Problem with Given Cycle on High-Speed Railway Lines

School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China

Received 18 June 2012; Revised 6 September 2012; Accepted 7 September 2012

Academic Editor: Wuhong Wang

Copyright © 2012 Zhiqiang Tian and Huimin Niu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper studies the modeling and algorithms of crew roster problem with given cycle on high-speed railway lines. Two feasible compilation strategies for work out the crew rostering plan are discussed, and then an integrated compilation method is proposed in this paper to obtain a plan with relatively higher regularity in execution and lower crew members arranged. The process of plan making is divided into two subproblems which are decomposition of crew legs and adjustment of nonmaximum crew roster scheme. The decomposition subproblem is transformed to finding a Hamilton chain with the best objective function in network which was solved by an improved ant colony algorithm, whereas the adjustment of nonmaximum crew rostering scheme is finally presented as a set covering problem and solved by a two-stage algorithm. The effectiveness of the proposed models and algorithms are testified by a numerical example.