Abstract
Given a set of timetabled tasks, the multi-depot vehicle scheduling problem consists of determining least-cost schedules for vehicles assigned to several depots such that each task is accomplished exactly once by a vehicle. In this paper, we propose to compare the performance of five different heuristics for this well-known problem, namely, a truncated branch-and-cut method, a Lagrangian heuristic, a truncated column generation method, a large neighborhood search heuristic using truncated column generation for neighborhood evaluation, and a tabu search heuristic. The first three methods are adaptations of existing methods, while the last two are new in the context of this problem. Computational results on randomly generated instances show that the column generation heuristic performs the best when enough computational time is available and stability is required, while the large neighborhood search method is the best alternative when looking for good quality solutions in relatively fast computational times.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network flows: theory, algorithms, and applications. Englewood Cliffs: Prentice Hall.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316–329.
Bertossi, A. A., Carraresi, P., & Gallo, G. (1987). On some matching problems arising in vehicle scheduling models. Networks, 17, 271–281.
Bodin, L., Golden, B., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers and Operations Research, 10, 63–211.
Carpaneto, G., Dell’Amico, M., Fischetti, M., & Toth, P. (1989). A branch and bound algorithm for the multiple vehicle scheduling problem. Networks, 19, 531–548.
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8, 101–111.
Dell’Amico, M., Fischetti, M., & Toth, P. (1993). Heuristic algorithms for the multiple depot vehicle scheduling problem. Management Science, 39, 115–125.
Desaulniers, G., & Hickman, M. (2007). Public transit. In G. Laporte & C. Barnhart (Eds.), Handbooks in operations research and management science: Vol. 14. Transportation (pp. 69–127). Amsterdam: Elsevier Science.
Desaulniers, G., Desrosiers, J., Ioachim, I., Solomon, M. M., & Soumis, F. (1998a). A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In T. G. Crainic & G. Laporte (Eds.), Fleet management and logistics (pp. 57–93). Norwell: Kluwer.
Desaulniers, G., Lavigne, J., & Soumis, F. (1998b). Multi-depot vehicle scheduling problems with time windows and waiting costs. European Journal of Operational Research, 111, 479–494.
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Time constrained routing and scheduling. In M. O. Ball, T. L. Magnanti, C. L. Monma, & G. L. Nemhauser (Eds.), Handbooks in operations research and management science: Vol. 8. Network routing (pp. 35–139). Amsterdam: Elsevier Science.
Forbes, M. A., Holt, J. N., & Watts, A. M. (1994). An exact algorithm for multiple depot bus scheduling. European Journal of Operational Research, 72, 115–124.
Freling, R., Wagelmans, A. P. M., & Paixão, J. M. P. (2001). Models and algorithms for single-depot vehicle scheduling. Transportation Science, 35, 165–180.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40, 1276–1290.
Geoffrion, A. (1974). Lagrangian relaxations for integer programming. Mathematical Programming Study, 2, 82–114.
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9, 849–859.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533–549.
Glover, F., & Laguna, M. (1997). Tabu search. Boston: Kluwer Academic.
Hadjar, A., Marcotte, O., & Soumis, F. (2006). A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Operations Research, 54, 130–149.
Huisman, D., Freling, R., & Wagelmans, A. P. M. (2005). Multiple-depot integrated vehicle and crew scheduling. Transportation Science, 39, 491–502.
Kliewer, N., Mellouli, T., & Suhl, L. (2006). A time–space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research, 175, 1616–1627.
Kokott, A., & Löbel, A. (1996). Lagrangean relaxations and subgradient methods for multiple-depot vehicle scheduling problems (ZIB-Report 96-22). Konrad-Zuse-Zentrum für Informationstecnik, Berlin.
Lamatsch, A. (1992). An approach to vehicle scheduling with depot capacity constraints. In M. Desrochers & J.-M. Rousseau (Eds.), Lecture notes in economics and mathematical systems: Vol. 386. Computer-aided transit scheduling (pp. 181–195). Berlin: Springer.
Löbel, A. (1997). Optimal vehicle scheduling in public transit. PhD thesis, Technische Universität Berlin, Germany.
Löbel, A. (1998). Vehicle scheduling in public transit and Lagrangian pricing. Management Science, 44, 1637–1649.
Odoni, A. R., Rousseau, J.-M., & Wilson, N. H. M. (1994). Models in urban and air transportation. In S. M. Pollock, M. H. Rothkopf, & A. Barnett (Eds.), Handbooks in operations research and management science: Vol. 6. Operations research and the public sector (pp. 107–150). Amsterdam: North-Holland.
Mesquita, M., & Paixão, J. (1992). Multiple depot vehicle scheduling problem: a new heuristic based on quasi-assignment algorithms. In M. Desrochers & J.-M. Rousseau (Eds.), Lecture notes in economics and mathematical systems: Vol. 386. Computer-aided transit scheduling (pp. 167–180). Berlin: Springer.
Ribeiro, C., & Soumis, F. (1994). A column generation approach to the multiple depot vehicle scheduling problem. Operations Research, 42, 41–52.
Ropke, S., & Pisinger, D. (2004). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40, 455–472.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher & J.-F. Puget (Eds.), Lecture notes in computer science. Principles and practice of constraint programming, CP98 (pp. 417–431). New-York: Springer.
Taillard, E. D. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23, 661–673.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pepin, AS., Desaulniers, G., Hertz, A. et al. A comparison of five heuristics for the multiple depot vehicle scheduling problem. J Sched 12, 17–30 (2009). https://doi.org/10.1007/s10951-008-0072-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-008-0072-x