Abstract
This work introduces a model of the crew scheduling problem for the operation of trains in the mining industry in the North of Chile. The model possesses particular features due to specific regulations with which train operators in mine material transportation are required to comply: every week, a fixed set of trips must be made according to current demand for the transportation of mine products and supplies. In order to balance the loads of the crews in the long term, the proposed model generates an infinite horizon schedule by means of a rotative scheme in which each crew takes the place of the previous one at the beginning of the next week. This gives rise to a medium/large size 0–1 linear optimization problem, whose solution represents the optimal assignment of drivers to trips with the number of working hours per week distributed equally among crews. The model and algorithm have been implemented with a user interface suitable for the remote execution of real instances on a High Performance Computing platform. The transportation company regularly uses this computerized tool for planning crew schedules and generating efficient assignments for emerging and changing operational conditions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abbink E, Wout JV, Huisman D (2007) Solving large scale crew scheduling problems by using iterative partitioning. In: Liebchen C, Ahuja RK, Mesa JA (eds), 7th Workshop on Algorithmic approaches for transportation modeling, optimization, and systems (ATMOS’07), volume 7 of OpenAccess Series in Informatics (OASIcs) (Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik)
Beasley J, Cao B (1996) A tree search algorithm for the crew scheduling problem. Eur J Oper Res 94(3):517–526
Beliën J, Demeulemeester E, Bruecker PD, den Bergh JV, Cardoen B (2013) Integrated staffing and scheduling for an aircraft line maintenance problem. Comput Oper Res 40(4):1023–1033
Desrochers M, Soumis F (1989) A column generation approach to the urban transit crew scheduling problem. Transp Sci 23(1):1–13
Emden-Weinert T, Proksch M (1999) Best practice simulated annealing for the airline crew scheduling problem. J Heuristic 5(4):419–436
Ernst A, Jiang H, Krishnamoorthy M, Nott H, Sier D (2001) An integrated optimization model for train crew management. Ann Oper Res 108(1):211–224
Ernst A, Jiang H, Krishnamoorthy M, Sier D (2004) Staff scheduling and rostering: a review of applications, methods and models. Eur J Oper Res 153(1):3–27
Gamache M, Soumis F, Marquis G, Desrosiers J (1999) A column generation approach for large-scale aircrew rostering problems. Oper Res 47(2):247–263
Jian MS, Chou TY (2010) Multiobjective genetic algorithm to solve the train crew scheduling problem. In: Proceedings of the 10th WSEAS international conference on systems theory and scientific computation, ISTASC’10 (Stevens Point, Wisconsin, USA: World Scientific and Engineering Academy and Society (WSEAS)), pp 100–106
Jütte S, Albers M, Thonemann UW, Hasse K (2011) Optimizing railway crew scheduling at DB Schenker. Interfaces 41(2):109–122
Levine D (1996) Application of a hybrid genetic algorithm to airline crew scheduling. Comput Oper Res 23(6):547–558
Karsu Ö, Morton A (2015) Inequity averse optimization in operational research. Eur J Oper Res 245(2):343–359
Mesquita M, Moz M, Paias A, Pato M (2015) A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern. Eur J Oper Res 245(2):423–437
Nishi T, Sugiyama T, Inuiguchi M (2014) Two-level decomposition algorithm for crew rostering problems with fair working condition. Eur J Oper Res 237(2):465–473 ISSN 0377-2217
Şahin G, Yüceoğlu B (2011) Tactical crew planning in railways. Transp Res Part E: Log Transp Rev 47(6):1221–1243
Sanders P, Takkula T, Wedelin D (1999) High-performance computing and networking. In: 7th International conference, HPCN Europe 1999 Amsterdam, April 12–14, 1999 Proceedings, chapter High performance integer optimization for crew scheduling, Springer, Berlin, pp 1–12
Vaidyanathan B, Jha KC, Ahuja RK (2007) Multicommodity network flow approach to the railroad crew-scheduling problem. IBM J Res Dev 51(3):325–344
Walker CG, Snowdon JN, Ryan DM (2005) Simultaneous disruption recovery of a train timetable and crew roster in real time. Comput Oper Res 32(8):2077–2094
Yunes TH, Moura AV, de Souza CC (2005) Hybrid column generation approaches for urban transit crew management problems. Transp Sci 39(2):273–288
Acknowledgements
The authors thank FCAB-Antofagasta Minerals Co. for support and real data testing and Andrew Hart for his careful reading and criticism that improved the quality of the article. Reviewers are also acknowledged for helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been partially supported by Basal project CMM-University of Chile, and by Fondecyt Grant 1130816.
Rights and permissions
About this article
Cite this article
Amaya, J., Uribe, P. A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy. TOP 26, 383–402 (2018). https://doi.org/10.1007/s11750-018-0479-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-018-0479-2