Abstract
This paper addresses the problem of determining the best scheduling for Bus Drivers, a \(\mathcal{NP}\)-hard problem consisting of finding the minimum number of drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and regulations that must be enforced such as spreadover and working time. This problem is known in literature as Crew Scheduling Problem and, in particular in public transportation, it is designated as Bus Driver Scheduling Problem. We propose a new mathematical formulation of a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. Unfortunately, this model can only be usefully applied to small or medium size problem instances. For large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results are reported for a set of real-word problems and comparison is made with an exact method. Moreover, we report a comparison of the computational results obtained with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci. 39(4):491–502, 2005).
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in GRASP: An experimental investigation. J. Heuristics 8, 200–212 (2000)
Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTTplots: a Perl program to create time-to-target plots. Optim. Lett. 1, 355–366 (2007)
Argüello, M., Bard, J., Yu, G.: A GRASP for aircraft routing in responce to groundings and delays. J. Combin. Optim. 1, 211–228 (1997)
Carraresi, P., Nonato, M., Girardi, L.: Network models, Lagrangian relaxation and subgradients bundle approach in crew scheduling problems. In: Daduna, J.R., Branco, I., Paixão, J.R. (eds.) Computer-Aided Transit Scheduling, Lisbon, pp. 187–212. Springer, Berlin (1993)
Chambers, J.M., Cleveland, W.S., Kleiner, B., Tukey, P.A.: Graphical Methods for Data Analysis. Chapman & Hall, London (1983)
Cunha, J.F., Sousa, J.P.: The bus stops here—GIST: A decision support system problem. OR/MS Today 27(2), 324–335 (2002)
Curtis, S.D., Smith, B.M., Wren, A.: Forming bus driver schedules using constraint programming. Technical Report, University of Leeds, School of Computer Studies, Report 99.05 (1999)
Daduna, J.R., Wren, A.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 308. Springer, Heidelberg (1988)
Daduna, J.R., Branco, I., Paixão, J.M.P.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430. Springer, Heidelberg (1995)
Desaulniers, G., Hickman, M.D.: Public transit. Technical Report, Les Cahiers du GERAD, G-2003-77 (2003)
Desrochers, M., Rousseau, J.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 386. Springer, Heidelberg (1992)
Desrochers, M., Soumis, F.: A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23(1), 1–13 (1989)
DEV-C++: http://www.bloodshed.net/dev/index.html (2005)
Dias, T.G., Sousa, J.P., Cunha, J.F.: A genetic algorithm for the bus driver scheduling problem. In: 4th Metaheuristics International Conference (2001)
Dias, T.G., Sousa, J.P., Cunha, J.F.: A multiobjective genetic algorithm for the bus driver scheduling problem. In: The 6th Metaheuristics International Conference (2005)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109–133 (1995)
Festa, P., Resende, M.G.C.: GRASP: An annotated bibliography. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 325–367. Kluwer Academic, Dordrecht (2002)
Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP—Part I: algorithms. Int. Trans. Oper. Res. 16(1), 1–24 (2009a)
Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP—Part II: applications. Int. Trans. Oper. Res. 16(2), 131–172 (2009b)
Festa, P., Pardalos, P., Resende, M., Ribeiro, C.: Randomized heuristics for the max-cut problem. Optim. Methods Softw. 7, 1033–1058 (2002)
Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with spread-time constraints. Oper. Res. 35, 849–858 (1987)
Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with working-time constraints. Oper. Res. 37, 395–403 (1989)
Fores, S.: Column generation approaches to bus driver scheduling. Ph.D. Thesis, The University of Leeds, School of Computer Studies (1996)
Fores, S., Proll, L., Wren, A.: Experiences with a flexible driver scheduler. In: Voß, S., Daduna, J.R. (eds.) Computer-Aided Scheduling of Public Transport, pp. 137–152. Springer, Berlin (2001)
Fores, S., Proll, L., Wren, A.: TRACS II: a hybrid IP/heuristic driver scheduling system for public transport. J. Oper. Res. Soc. 53, 1093–1100 (2002)
GAMS: General Algebraic Modelling System. http://www.gams.com/docs/gams/document.html (2005)
Hart, J., Shogan, A.: Semi-greedy heuristics: an empirical study. Oper. Res. Lett. 6, 107–114 (1987)
Hartley, T.: A glossary of terms in bus and crew scheduling. In: Wren, A. (ed.) Computer Scheduling of Public Transport, pp. 353–359. North-Holland, Amsterdam (1981)
Huisman, D.: Integrated and dynamic vehicle and crew scheduling. Ph.D. Thesis, Erasmus Universiteit Rotterdam (2004)
Huisman, D., Freling, R., Wagelmans, A.P.M.: Multiple-depot integrated vehicle and crew scheduling. Transp. Sci. 39(4), 491–502 (2005)
Kroon, L., Fischetti, M.: Crew scheduling for Netherlands railways destination: customer. In: Voß, S., Daduna, J.R. (eds.) Computer-Aided Scheduling of Public Transport, pp. 181–201. Springer, Berlin (2001)
Löbel, A.: Vehicle scheduling in public transit and Lagrangian pricing. Oper. Res. 44(12), 1637–1649 (1998)
Lourenço, H., Paixão, J., Portugal, P.: Multiobjective metaheuristics for the bus-driver scheduling problem. Transp. Sci. 35, 331–343 (2001)
Mesquita, M., Paias, A., Respício, A.: Branching approaches for integrated vehicle and crew scheduling. Public Transp. 1, 21–37 (2009)
Moz, M., Respício, A., Pato, M.V.: Bi-objective evolutionary heuristics for bus driver rostering. Public Transp. 1, 189–210 (2009)
Portugal, R., Lourenço, H., Paixão, J.: Driver scheduling problem modelling. Public Transp. 1, 103–120 (2009)
Rousseau, J.M.: Computer Scheduling of Public Transport 2. North-Holland, Amsterdam (1985)
Rousseau, J.M., Blais, J.Y.: Hastus: An interactive system for buses and crew scheduling. In: Rousseau, J.M. (ed.) Computer Scheduling of Public Transport 2, pp. 45–60. North-Holland, Amsterdam (1985)
Rousseau, J.M., Desrosiers, J.: Results obtained with crew-opt: a column generation method for transit crew scheduling. In: Daduna, J.R., Branco, I., Paixão, J.R. (eds.) Computer-Aided Transit Scheduling, Lisbon, pp. 349–358. Springer, Berlin (1993)
Shen, Y.: Tabù search for bus and train driver scheduling with time windows. Ph.D. Thesis, The University of Leeds, School of Computing (2001)
Sosnewska, D.: Optimization of a simplified fleet assignment problem with metaheuristics: simulated annealing and GRASP. In: Pardalos, P.M. (ed.) Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, pp. 477–488. Kluwer Academic, Dordrecht (2000)
Souza, M., Maculan, N., Ochi, L.: A GRASP-tabù search algorithm for school timetabling problems. In: Resende, M., Sousa, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 659–672. Kluwer Academic, Dordrecht (2003)
Voß, S., Daduna, J.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 505. Springer, Heidelberg (2001)
Wilson, N.H.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 471. Springer, Heidelberg (1999)
Wren, A.: Computer Scheduling of Public Transport. North-Holland, Amsterdam (1981)
Wren, A.: Scheduling vehicles and their drivers-forty years’ experience. Technical Report, University of Leeds, School of Computing Research Report Series, Report 2004.03 (2004)
Wren, A., Rousseau, J.M.: Bus driver scheduling problem—an overview. In: Daduna, J., Branco, I., Paixão, J. (eds.) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430, pp. 173–187. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
De Leone, R., Festa, P. & Marchitto, E. A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution. J Heuristics 17, 441–466 (2011). https://doi.org/10.1007/s10732-010-9141-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-010-9141-3