Abstract
Railway crew scheduling deals with generating driver duties for a given train timetable such that all work regulations are met and the resulting schedule has minimal cost. Typical problem instances in the freight railway industry require the generation of duties for thousands of drivers operating tens of thousands of trains per week. Due to short runtime requirements, common solution approaches decompose the optimization problem into smaller subproblems that are solved separately. Several studies have shown that the way of decomposing the problem significantly affects the solution quality. An overall best decomposition strategy for a freight railway crew scheduling problem, though, is not known. In this paper, we present general considerations on when to assign two scheduled train movements to separate subproblems (and when to rather assign them to the same subproblem) and deduct a graph partitioning based decomposition algorithm with several variations. Using a set of real-world problem instances from a major European railway freight carrier, we evaluate our strategy and benchmark the performance of the decomposition algorithm both against a common non-decomposition algorithm and a lower bound on the optimal solution schedule. The test runs show that our decomposition algorithm is capable of producing high-quality solution schedules while significantly cutting runtimes compared to the non-decomposition solution algorithm. We are following a ”greenfield” approach, where no information on previous schedules is needed. Hence, our approach is applicable to any railway crew scheduling setting, including network enlargement, integration of new customers, etc.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abbink E, van’t Wout J, Huisman D (2007) Solving large scale crew scheduling problems by using iterative partitioning. In: Proceedings of the seventh workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS), pp 96–106
Albers M (2008) Freight railway crew scheduling. Phd thesis, University of Cologne, Germany
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316–329
Barnhart C, Cohn AM, Johnson EL, 0Klabjan D, Nemhauser GL, Vance PH (2003) Airline crew scheduling. In: Hall RW (ed) Handbook of transportation science, chap 14, 2nd edn. Springer, New York, pp 517–560
Borndörfer R, Grötschel M, Löbel A (2001) Scheduling duties by adaptive column generation. Tech. Rep. 01–02, Konrad-Zuse-Zentrum für Informationstechnik, Berlin
Borndörfer R, Löbel A, Weider S (2002) Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr. Tech. Rep. 02–10, Konrad-Zuse-Zentrum für Informationstechnik, Berlin
Caprara A, Fischetti M, Toth P (1999) A heuristic method for the set covering problem. Oper Res 47(5):730–743
Caprara A, Kroon L, Monaci M, Peeters M, Toth P (2007) Passenger railway optimization. In: Barnhart C, Laporte G (eds) Handbooks in operations research and management science, transportation, chap 3, vol. 14. Elsevier B.V., Amsterdam, pp 129–187
Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–404
Crainic TG (2003) Long Haul Freight transportation. In: Hall RW (ed) Handbook of transportation science, chap 13, 2nd edn. Springer, New York, pp 451–516
De Groot SW, Huisman D (2008) Vehicle and crew scheduling: solving large real-world instances with an integrated approach. In: Hickman M, Mirchandani P, Voß S (eds) Computer-aided systems in public transport, lecture notes in economics and mathematical systems. Springer, Berlin, pp 43–56
Desrosiers J, Lübbecke ME (2005) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation, chap 1. Springer, New York, pp 1–32
Ernst AT, 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
Fores S, Proll L, Wren A (2001) Experiences with a flexible driver scheduler. In: Voß S, Daduna J (eds) Computer-aided scheduling of public transport. Springer, Berlin, pp 137–152
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
Garey M, Johnson D, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theor Comput Sci 1:237–267
Gopalakrishnan B, Johnson EL (2005) Airline crew scheduling: state-of-the-art. Ann Oper Res 140(1):305–337
Grönkvist M (2005) The tail assignment problem. Phd thesis, Chalmers University of Technology and Göteborg University, Sweden
Haase K, Desaulniers G, Desrosiers J (2001) Simultaneous vehicle and crew scheduling in urban mass transit systems. Transp Sci 35(3):286–303
Huisman D (2004) Integrated and dynamic vehicle and crew scheduling. Phd thesis, Erasmus University of Rotterdam, The Netherlands
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation, chap 2. Springer, New York, pp 33–65
Jütte S, Thonemann UW (2012) Divide-and-price : a decomposition algorithm for solving large railway crew scheduling problems. Eur J Oper Res 219(2):214–223
Jütte S, Albers M, Thonemann UW, Haase K (2011) Optimizing railway crew scheduling at DB Schenker. Interfaces 41(2):109–122
Karypis G, Kumar V (1998a) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359–392
Karypis G, Kumar V (1998b) Multilevel k-way partitioning scheme for irregular graphs. J Parallel Distrib Comput 48:96–129
Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49(2):291–307
Lübbecke ME (2005) Dual variable based fathoming in dynamic programs for column generation. Eur J Oper Res 162(1):122–125
Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007–1023
Michaelis M, Schöbel A (2009) Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented heuristic. Publ Transp 1(3):211–232
Simon HD, Teng SH (1997) How good is recursive bisection? SIAM J Sci Comput 18(5):1436–1445
Smith BM, Wren A (1988) A bus crew scheduling system using a set covering formulation. Transp Res 22A(2):97–108
Steinzen I, Suhl L, Kliewer N (2009) Branching strategies to improve regularity of crew schedules in ex-urban public transit. OR Spectrum 31(4):727–743
Vaidyanathan B, Jha KC, Ahuja RK (2007) Multicommodity network flow approach to the railroad crew-scheduling problem. IBM J Res Dev 51(3–4):325–344
Van den Bergh J, Beliën J, De Bruecker P, Demeulemeester E, De Boeck L (2013) Personnel scheduling: a literature review. Eur J Oper Res 226(3):367–385
Vanderbeck F (2000) On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper Res 48(1):111–128
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jütte, S., Thonemann, U.W. A graph partitioning strategy for solving large-scale crew scheduling problems. OR Spectrum 37, 137–170 (2015). https://doi.org/10.1007/s00291-014-0381-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-014-0381-8