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.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
