Abstract
In this paper we describe the use of a set covering model with additional constraints for scheduling train drivers and conductors for the Dutch railway operator NS Reizigers. The schedules were generated according to new rules originating from the project “Destination: Customer” (“Bestemming: Klant” in Dutch). This project is carried out by NS Reizigers in order to increase the quality and the punctuality of its train services. With respect to the scheduling of drivers and conductors, this project involves the generation of efficient and acceptable duties with a high robustness against the transfer of delays of trains. A key issue for the acceptability of the duties is the included amount of variation per duty. The applied set covering model is solved by dynamic column generation techniques, Lagrangean relaxation and powerful heuristics. The model and the solution techniques are part of TURNI, a commercial software package which is currently used by NS Reizigers for carrying out several analyses concerning the required capacities of the depots. The latter are strongly influenced by the “Destination: Customer” rules. We applied TURNI to crew scheduling instances of different sizes. These instances were all based on the 1999/2000 timetable of NS Reizigers.1
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Bibliography
Balas, E. and M.C. Carrera (1990). A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research 44, 25–42.
Balas, E. and A. Ho (1980). Set covering algorithms using cutting planes, heuristics and subgradient optimization: A computational study. Mathematical Programming Study 12, 37–60.
Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance (1994). Branch-and-price: Column generation for solving huge integer programs. In J.R. Birge and K.G. Murty (Eds.), Mathematical Programming: State of the Art 1994, University of Michigan, 186–207.
Beasley, J.E. (1990). A Lagrangian heuristic for set covering problems. Naval Research Logistics 31, 151–164.
Caprara, A., M. Fischetti, P.L. Guida, P. Toth, and D. Vigo (1999a). Solution of large scale railway crew planning problems: The Italian experience. In N.H.M. Wilson (Ed.), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 471, Springer, Berlin, 1–18.
Caprara, A., M. Fischetti, and P. Toth (1999b). A heuristic method for the set covering problem. Operations Research 47, 730–743.
Caprara, A., M. Fischetti, P. Toth, D. Vigo, and P.L. Guida (1997). Algorithms for railway crew management. Mathematical Programming 79, 125–141.
Desrosiers, J., Y. Dumas, M.M. Solomon, and F. Soumis (1995). Time constrained routing and scheduling. In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science, 8, Elsevier, Amsterdam, 35–139.
Freling, R. (1997). Models and techniques for integrating vehicle and crew scheduling. Ph.D. thesis, Erasmus University, Rotterdam, The Netherlands.
Hoffman, K.L. and M.W. Padberg (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science 39, 657–682.
Kroon, L.G. and M. Fischetti (2000). Scheduling drivers and guards: The Dutch Noord-Oost case. In R.H. Sprague (Ed.), Proceedings of the 34th HICSS Conference, IEEE, Piscataway.
Kwan, A.S.K., R.S.K. Kwan, M.E. Parker, and A. Wren (1999). Producing train driver schedules under different operating strategies. In N.H.M. Wilson (Ed.), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 471, Springer, Berlin, 129–154.
Wedelin, D. (1995). An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. Annals of Operations Research 57, 283–301.
Wren, A. and N.D. Gualda (1999). Integrated scheduling of buses and drivers. In N.H.M. Wilson (Ed.), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 471, Springer, Berlin, 155–176.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kroon, L., Fischetti, M. (2001). Crew Scheduling for Netherlands Railways “Destination: Customer”. In: Voß, S., Daduna, J.R. (eds) Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, vol 505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-56423-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-56423-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42243-3
Online ISBN: 978-3-642-56423-9
eBook Packages: Springer Book Archive