A bus driver scheduling problem: A new mathematical model and a GRASP approximate solution. (English) Zbl 1233.90152
Summary: This paper addresses the problem of determining the best scheduling for bus drivers, a 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. (2005).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B06 | Transportation, logistics and supply chain management |
| 90B70 | Theory of organizations, manpower planning in operations research |
References:
| [1] | 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) · Zbl 1012.68795 |
| [2] | 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) · Zbl 1220.90102 · doi:10.1007/s11590-006-0031-4 |
| [3] | 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) · Zbl 0892.90122 · doi:10.1023/A:1009772208981 |
| [4] | 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) · Zbl 0852.90088 |
| [5] | Chambers, J.M., Cleveland, W.S., Kleiner, B., Tukey, P.A.: Graphical Methods for Data Analysis. Chapman & Hall, London (1983) · Zbl 0532.65094 |
| [6] | Cunha, J.F., Sousa, J.P.: The bus stops here–GIST: A decision support system problem. OR/MS Today 27(2), 324–335 (2002) · Zbl 1103.90339 |
| [7] | 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) |
| [8] | Daduna, J.R., Wren, A.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 308. Springer, Heidelberg (1988) · Zbl 0687.90093 |
| [9] | 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) · Zbl 0829.90052 |
| [10] | Desaulniers, G., Hickman, M.D.: Public transit. Technical Report, Les Cahiers du GERAD, G-2003-77 (2003) |
| [11] | Desrochers, M., Rousseau, J.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 386. Springer, Heidelberg (1992) · Zbl 0790.90030 |
| [12] | Desrochers, M., Soumis, F.: A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23(1), 1–13 (1989) · Zbl 0668.90043 · doi:10.1287/trsc.23.1.1 |
| [13] | DEV-C++: http://www.bloodshed.net/dev/index.html (2005) |
| [14] | Dias, T.G., Sousa, J.P., Cunha, J.F.: A genetic algorithm for the bus driver scheduling problem. In: 4th Metaheuristics International Conference (2001) · Zbl 1103.90339 |
| [15] | 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) · Zbl 1103.90339 |
| [16] | Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3 |
| [17] | Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109–133 (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763 |
| [18] | 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) · Zbl 1017.90001 |
| [19] | Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP–Part I: algorithms. Int. Trans. Oper. Res. 16(1), 1–24 (2009a) · Zbl 1153.90553 · doi:10.1111/j.1475-3995.2009.00663.x |
| [20] | Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP–Part II: applications. Int. Trans. Oper. Res. 16(2), 131–172 (2009b) · Zbl 1168.90582 · doi:10.1111/j.1475-3995.2009.00664.x |
| [21] | Festa, P., Pardalos, P., Resende, M., Ribeiro, C.: Randomized heuristics for the max-cut problem. Optim. Methods Softw. 7, 1033–1058 (2002) · Zbl 1032.90073 · doi:10.1080/1055678021000090033 |
| [22] | Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with spread-time constraints. Oper. Res. 35, 849–858 (1987) · Zbl 0638.90055 · doi:10.1287/opre.35.6.849 |
| [23] | Fischetti, M., Martello, S., Toth, P.: The fixed job schedule problem with working-time constraints. Oper. Res. 37, 395–403 (1989) · Zbl 0672.90074 · doi:10.1287/opre.37.3.395 |
| [24] | Fores, S.: Column generation approaches to bus driver scheduling. Ph.D. Thesis, The University of Leeds, School of Computer Studies (1996) |
| [25] | 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) · Zbl 0988.90502 |
| [26] | 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) · Zbl 1139.90364 · doi:10.1057/palgrave.jors.2601271 |
| [27] | GAMS: General Algebraic Modelling System. http://www.gams.com/docs/gams/document.html (2005) |
| [28] | Hart, J., Shogan, A.: Semi-greedy heuristics: an empirical study. Oper. Res. Lett. 6, 107–114 (1987) · Zbl 0615.90082 · doi:10.1016/0167-6377(87)90021-6 |
| [29] | 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) |
| [30] | Huisman, D.: Integrated and dynamic vehicle and crew scheduling. Ph.D. Thesis, Erasmus Universiteit Rotterdam (2004) |
| [31] | Huisman, D., Freling, R., Wagelmans, A.P.M.: Multiple-depot integrated vehicle and crew scheduling. Transp. Sci. 39(4), 491–502 (2005) · doi:10.1287/trsc.1040.0104 |
| [32] | 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) · Zbl 0989.90516 |
| [33] | Löbel, A.: Vehicle scheduling in public transit and Lagrangian pricing. Oper. Res. 44(12), 1637–1649 (1998) · Zbl 0989.90024 |
| [34] | Lourenço, H., Paixão, J., Portugal, P.: Multiobjective metaheuristics for the bus-driver scheduling problem. Transp. Sci. 35, 331–343 (2001) · Zbl 1069.90530 · doi:10.1287/trsc.35.3.331.10147 |
| [35] | Mesquita, M., Paias, A., Respício, A.: Branching approaches for integrated vehicle and crew scheduling. Public Transp. 1, 21–37 (2009) · doi:10.1007/s12469-008-0005-2 |
| [36] | Moz, M., Respício, A., Pato, M.V.: Bi-objective evolutionary heuristics for bus driver rostering. Public Transp. 1, 189–210 (2009) · Zbl 1291.90099 · doi:10.1007/s12469-009-0013-x |
| [37] | Portugal, R., Lourenço, H., Paixão, J.: Driver scheduling problem modelling. Public Transp. 1, 103–120 (2009) · doi:10.1007/s12469-008-0007-0 |
| [38] | Rousseau, J.M.: Computer Scheduling of Public Transport 2. North-Holland, Amsterdam (1985) · Zbl 0569.90014 |
| [39] | 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) |
| [40] | 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) · Zbl 0853.90050 |
| [41] | Shen, Y.: Tabù search for bus and train driver scheduling with time windows. Ph.D. Thesis, The University of Leeds, School of Computing (2001) |
| [42] | 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) |
| [43] | 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) |
| [44] | Voß, S., Daduna, J.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 505. Springer, Heidelberg (2001) · Zbl 0967.00092 |
| [45] | Wilson, N.H.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 471. Springer, Heidelberg (1999) · Zbl 0920.00055 |
| [46] | Wren, A.: Computer Scheduling of Public Transport. North-Holland, Amsterdam (1981) |
| [47] | 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) |
| [48] | 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) · Zbl 0852.90093 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
