Crew Scheduling Considering both Crew Duty Time Difference and Cost on Urban Rail System
AbstractUrban 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.
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
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).