Simultaneous vehicle and crew scheduling problem: case study Transantiago, Chile
Abstract
In this paper we propose an alternative formulation to solve the simultaneous vehicle and crew scheduling problem. This paper presents a constructive heuristic and a mixed integer linear programming model to address this problem. To substantially reduce solution times, our formulation proposes a way to implicitly construct the optimal set of vehicle schedules. Additionally, the objective function of the model incorporates multiple cost terms that improve the operational quality of the delivered solution. We present the results of the implementation of our methodology for a study case using real instances from one of major private bus operators in Transantiago, Chile. The model results evaluate the trade-off between two extreme solutions from addressed problem: prioritizing minimization of shifts versus prioritizing minimization of vehicle schedules.
References
Ceder A. (2002). Urban Transit Scheduling: Framework, Review and Examples. Journal of Urban Planning and Development, 128, 225-244.
Freling, R.; Huisman, D. & Wagelmans, A. (2003). Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling, 6(1), 63-85.
Gaffi, A. & Nonato, M. (1999). An integrated approach to extra-urban crew and vehicle scheduling. In: Wilson, N. (Ed), Computer-Aided Transit Scheduling. Lecture notes in economics and mathematical systems. Springer Verlag, Berlin, Germany, 471,103-128.
Groot, S. W. & Huisman, D. (2008). Vehicle and crew scheduling: solving large real-world instances with an integrated approach. Lecture Notes in Economics and Mathematical Systems 600, 43-56.
Guihaire, V. & Hao, J.K. (2008). Transit network design and scheduling: a global review. Transportation Research Part A: Policy and Practice, 42(10), 1251-1273.
Haase, K. & Friberg, C. (1999). An exact branch and cut algorithm for the vehicle and crew scheduling problem. In: Wilson, N. (Ed), Computer-Aided Transit Scheduling. Lecture notes in economics and mathematical systems. Springer Verlag, Berlin, Germany, 471, 63-80.
Haase, K.; Desaulniers, G. & Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science 35(3), 286-303.
Huisman, D.; Freling R., & Wagelmans A. P. (2005). Multiple-depot integrated vehicle and crew scheduling. Transportation Science, 39(4), 491-502.
Kliewer, N.; Amberg, B. & Amberg, B. (2012). Multiple depot vehicle and crew scheduling with time windows for scheduled trips. Public Transport, 3, 213-244.
Laurent, B. & Hao, J. K. (2008). Simultaneous vehicle and crew scheduling for extra urban transports. Lecture Notes in Computer Science, 5027, 466-475.
Mesquita, M. & Paias, A. (2008). Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Computers & Operations Research, 35, 1562-1575.
Rodrigues, M. M.; Souza, C. C. & Moura, A. V. (2006). Vehicle and crew scheduling for urban bus lines. European Journal of Operational Research, 170(3), 844-862.
