Crew Scheduling Considering both Crew Duty Time Difference and Cost on Urban Rail System

  • Wenliang Zhou Central South University
  • Xia Yang Rensselaer Polytechnic Institute
  • Lianbo Deng Central South University
  • Jin Qin Central South University
Keywords: urban railway, crew schedule, ant colony algorithm, duty time difference,

Abstract

Urban rail crew scheduling problem is to allocate train services to crews based on a given train timetable while satisfying all the operational and contractual requirements. In this paper, we present a new mathematical programming model with the aim of minimizing both the related costs of crew duty and the variance of duty time spreads. In addition to iincorporating the commonly encountered crew scheduling constraints, it also takes into consideration the constraint of arranging crews having a meal in the specific meal period of one day rather than after a minimum continual service time. The proposed model is solved by an ant colony algorithm which is built based on the construction of ant travel network and the design of ant travel path choosing strategy. The performances of the model and the algorithm are evaluated by conducting case study on Changsha urban rail. The results indicate that the proposed method can obtain a satisfactory crew schedule for urban rails with a relatively small computational time.

Author Biographies

Wenliang Zhou, Central South University

Associate professor of central south university.

Rank: 1

Xia Yang, Rensselaer Polytechnic Institute

Dr. of Rensselaer Polytechnic Institute

Rank 2

Lianbo Deng, Central South University

Professor of Cental South Universtiy

Rank 4

Jin Qin, Central South University

Professor of Central South University

Rank 3

References

Fischetti M, Martello S, Toth P. The fixed job schedule problem with working-time constraints. Operations Research. 1989;37(3):395-403. doi.org/10.1287/opre.37.3.395

Morgado EM, Martins JP. Scheduling and managing crew in the Portuguese railways. Expert Systems with Applications. 1992;5(3):301-321. doi:10.1016/0957-4174(92)90014-J

Kroon L, Fischetti M. Crew scheduling for Netherlands railways destination: computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems Berlin: Springer. 2001;505:181-201. doi:10.1007/978-3-642-56423-9-11

Alfieri A, Kroon L, Velde S. Personnel scheduling in a complex logistic system: a railway application case. Journal of Intelligent Manufacturing. 2007;18(2):223-232. doi:10.1007/s10845-007-0017-9

Nishi T, Muroi Y, Inuiguchi M. Column generation with dual inequalities for railway crew scheduling problems. Public transport. 2011;3(1):25-42. doi:10.1007/s12469-011-0037-x

Jütte S, Thonemann UW. Divide-and-price: a decomposition algorithm for solving large railway crew scheduling problems. European Journal of Operational Research. 2012;219(2):214-223. doi:10.1016/j.ejor.2011.12.038

Yan S, Tu YP. A network model for airline cabin crew scheduling. European Journal of Operational Research. 2002;140(3):531-540. doi:10.1016/S0377-2217(01)00215-6

Freling R, Lentink RM, Wagelmans APM. A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. Annals of Operations Research. 2004;127:203-222. doi:10.1023/B:ANOR.0000019090.39650.32

Vaidyanathan B, Jha KC, Ahuja RK. Multi-commodity network flow approach to the railroad crew-scheduling problem. IBM Journal of Research and Development. 2007;51(3,4):325-344. doi:10.1147/rd.513.0325

Jütte S, Thonemann UW. A graph partitioning strategy for solving large-scale crew scheduling problems. OR Spectrum. 2015;37(1):137-170. doi:10.1007/s00291-014-0381-8

Emden-Weinert T, Proksch M. Best practice simulated annealing for the airline crew scheduling problem. Journal of Heuristics. 1999;5(4):419-436. doi:10.1023/A:1009632422509

Dias TG, Sousa JP, Cunha JF. Genetic algorithms for the bus driver scheduling problem: a case study. Journal of the Operational Research Society. 2002;53(3):324-335. doi:10.1057/palgrave/jors/2601312

Elizondo R, Parada V, Pradenas L, Artigues C. An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport. Journal of Heuristics. 2010;16(4):575-591. doi:10.1007/s10732-009-9102-x

Hanafi R, Kozan E. A hybrid constructive heuristic and simulated annealing for railway crew scheduling. Computers & Industrial Engineering. 2014;70:11-19. doi:10.1016/j.cie.2014.01.002

Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions. 1997;1(1):53-66.

Dorigo M, Birattari M. Ant colony optimization. In: Encyclopedia of Machine Learning. Springer US. 2010; p. 36-39. doi:10.1007/978-0-387-30164-8

Published
2016-11-02
How to Cite
1.
Zhou W, Yang X, Deng L, Qin J. Crew Scheduling Considering both Crew Duty Time Difference and Cost on Urban Rail System. PROMET [Internet]. 2016Nov.2 [cited 2019Aug.20];28(5):449-60. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/1842
Section
Articles