Abstract
In this paper we discuss several methods to solve large real-world instances of the vehicle and crew scheduling problem. Although there has been an increased attention to integrated approaches for solving such problems in the literature, currently only small or medium-sized instances can be solved by such approaches. Therefore, large instances should be split into several smaller ones, which can be solved by an integrated approach, or the sequential approach, i.e., first vehicle scheduling and afterwards crew scheduling, is applied.
In this paper we compare both approaches, where we consider different ways of splitting an instance varying from very simple rules to more sophisticated ones. Those ways are extensively tested by computational experiments on real-world data provided by the largest Dutch bus company.
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.
References
De Groot, S. W. (2003). Een geïntegreerde aanpak van voertuig-en personeelsplanning toegepast op grote probleeminstanties, master’s thesis (in Dutch). School of Economics, Erasmus University Rotterdam.
Fores, S., Proll, L., and Wren, A. (2001). Experiences with a flexible driver scheduler. In S. Voß and J. R. Daduna, editors, Computer-Aided Scheduling of Public Transport, pages 137–152. Springer, Berlin.
Freling, R. (1997). Models and Techniques for Integrating Vehicle and Crew Scheduling. Ph.D. thesis, Tinbergen Institute, Erasmus University Rotterdam.
Freling, R., Huisman, D., and Wagelmans, A. P. M. (2003). Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling, 6, 63–85.
Gaffi, A. and Nonato, M. (1999). An integrated approach to extra-urban crew and vehicle scheduling. In N. H. M. Wilson, editor, Computer-Aided Transit Scheduling, pages 103–128. Springer, Berlin.
Haase, K. and Friberg, C. (1999). An exact branch and cut algorithm for the vehicle and crew scheduling problem. In N. H.M. Wilson, editor, Computer-Aided Transit Scheduling, pages 63–80. Springer, Berlin.
Haase, K., Desaulniers, G., and Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35, 286–303.
Haghani, A. and Banihashemi, M. (2002). Heuristic approaches for solving largescale bus transit vehicle scheduling problem with route-time constraints. Transportation Research Part A, 36, 309–333.
Haghani, A., Banihashemi, M., and Chiang, K.-H. (2003). A comparative analysis of bus transit vehicle scheduling models. Transportation Research Part B, 37, 301–322.
Hendrickson, B. and Leland, R. (1993). An improved spectral load balancing method. In R. F. Sincovec, D. E. Keyes, M. R. Leuze, L. R. Petzold, and D. A. Reed, editors, Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, pages 953–961. SIAM.
Huisman, D. (2004). Integrated and Dynamic Vehicle and Crew Scheduling. Ph.D. thesis, Tinbergen Institute, Erasmus University Rotterdam.
Huisman, D., Freling, R., and Wagelmans, A. P. M. (2004). A robust solution approach to the dynamic vehicle scheduling problem. Transportation Science, 38, 447–458.
Huisman, D., Freling, R., and Wagelmans, A. P.M. (2005). Multiple-depot integrated vehicle and crew scheduling. Transportation Science, 39, 491–502.
Kernighan, B. and Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 29, 291–307.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Groot, S.W., 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, vol 600. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73312-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-73312-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73311-9
Online ISBN: 978-3-540-73312-6
eBook Packages: EngineeringEngineering (R0)