×

A general heuristic for vehicle routing problems. (English) Zbl 1144.90318

Summary: We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).All problem variants are transformed into a rich pickup and delivery model and solved using the adaptive large neighborhood search (ALNS) framework presented in Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear]. The ALNS framework is an extension of the large neighborhood search framework by P. Shaw [Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lect. Notes Comput. Sci. 1520, 417–431 (1998)] with an adaptive layer. This layer adaptively chooses among a number of insertion and removal heuristics to intensify and diversify the search. The presented approach has a number of advantages: it provides solutions of very high quality, the algorithm is robust, and to some extent self-calibrating. Moreover, the unified model allows the dispatcher to mix various variants of VRP problems for individual customers or vehicles. As we believe that the ALNS framework can be applied to a large number of tightly constrained optimization problems, a general description of the framework is given, and it is discussed how the various components can be designed in a particular setting.The paper is concluded with a computational study, in which the five different variants of the vehicle routing problem are considered on standard benchmark tests from the literature. The outcome of the tests is promising as the algorithm is able to improve 183 best known solutions out of 486 benchmark tests. The heuristic has also shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in by the authors [Eur. J. Oper. Res. 171, No. 3, 750–775 (2006; Zbl 1116.90019)].

MSC:

90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research

Citations:

Zbl 1116.90019

Software:

CVRPSP; BoneRoute; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cordeau, J.-F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 105-119 (1997) · Zbl 0885.90037
[2] Cordeau, J.-F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936 (2000) · Zbl 1181.90034
[3] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear.; Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear. · Zbl 1116.90019
[4] Ropke S, Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 2004, to appear.; Ropke S, Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 2004, to appear. · Zbl 1116.90019
[5] Sigurd, M.; Pisinger, D.; Sig, M., The pickup and delivery problem with time windows and precedences, Transportation Science, 38, 197-209 (2004)
[6] Cordeau, J.-F.; Desaulniers, G.; Desrosiers, J.; Solomon, M. M.; Soumis, F., Vrp with time windows, (Toth, P.; Vigo, D., The vehicle routing problem, SIAM monographs on discrete mathematics and applications, vol. 9 (2002), SIAM: SIAM Philadelphia), 157-193, [chapter 7] · Zbl 1076.90543
[7] Bräysy O, Gendreau M. Vehicle routing problem with time windows, part II: metaheuristics. Transportation Science 2005;39:119-39.; Bräysy O, Gendreau M. Vehicle routing problem with time windows, part II: metaheuristics. Transportation Science 2005;39:119-39.
[8] Mester D, Bräysy O. Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers and Operations Research 2005;32:1593-614.; Mester D, Bräysy O. Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers and Operations Research 2005;32:1593-614. · Zbl 1122.90403
[9] Bent R, Hentenryck PV. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science 2004; 38: 515-30.; Bent R, Hentenryck PV. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science 2004; 38: 515-30.
[10] Homberger J, Gehring H.A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research 2005;162:220-238.; Homberger J, Gehring H.A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research 2005;162:220-238. · Zbl 1132.90378
[11] Kallehauge B, Larsen J, Madsen OBG. Lagrangean duality applied on vehicle routing with time windows—experimental results. Technical Report IMM-REP-2000-8, Informatics and Mathematical Modelling, Technical University of Denmark, DTU Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby;2001.; Kallehauge B, Larsen J, Madsen OBG. Lagrangean duality applied on vehicle routing with time windows—experimental results. Technical Report IMM-REP-2000-8, Informatics and Mathematical Modelling, Technical University of Denmark, DTU Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby;2001.
[12] Irnich S, Villeneuve D. The shortest path problem with resource constraints and \(kk \geqs; 3\); Irnich S, Villeneuve D. The shortest path problem with resource constraints and \(kk \geqs; 3\) · Zbl 1241.90161
[13] Chabrier A. Vehicle routing problem with elementary shortest path based column generation. Working Paper, ILOG, Madrid, 2003.; Chabrier A. Vehicle routing problem with elementary shortest path based column generation. Working Paper, ILOG, Madrid, 2003. · Zbl 1086.90048
[14] Laporte, G.; Semet, F., Classical heuristics for the capacitated vrp, (Toth, P.; Vigo, D., The vehicle routing problem, SIAM monographs on discrete mathematics and applications, vol. 9 (2002), SIAM: SIAM Philadelphia), 109-128, [chapter 5] · Zbl 1076.90549
[15] Gendreau, M.; Laporte, G.; Potvin, J.-Y., Metaheuristics for the capacitated vrp, (Toth, P.; Vigo, D., The vehicle routing problem, SIAM monographs on discrete mathematics and applications, vol. 9 (2002), SIAM: SIAM Philadelphia), 129-154, [chapter 6] · Zbl 1076.90545
[16] Cordeau J-F, Gendreau M, Hertz A, Laporte G, Sormany J-S. New heuristics for the vehicle routing problem. Technical Report G-2004-33, GERAD, Montreal, Canada; 2004.; Cordeau J-F, Gendreau M, Hertz A, Laporte G, Sormany J-S. New heuristics for the vehicle routing problem. Technical Report G-2004-33, GERAD, Montreal, Canada; 2004. · Zbl 1130.90416
[17] Taillard, E., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-673 (1993) · Zbl 0804.90045
[18] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I.-M., Metaheuristics in vehicle routing, (Crainic, T.; Laporte, G., Fleet management and logistics (1998), Kluwer: Kluwer Boston, MA), 33-56 · Zbl 0997.90021
[19] Li F, Golden B, Wasil E. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers and Operations Research 2005;32:1165-179.; Li F, Golden B, Wasil E. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers and Operations Research 2005;32:1165-179. · Zbl 1075.90013
[20] Lysgaard, J.; Letchford, A. N.; Eglese, R. W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, Series A, 100, 423-445 (2004) · Zbl 1073.90068
[21] Fukasawa R, Lysgaard J, de Aragão MP, Reis M, Uchoa E, Werneck RF. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In: Proceedings of IPCO X. New York: Columbia University; 2004.; Fukasawa R, Lysgaard J, de Aragão MP, Reis M, Uchoa E, Werneck RF. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In: Proceedings of IPCO X. New York: Columbia University; 2004. · Zbl 1092.90540
[22] Sariklis, D.; Powell, S., A heuristic method for the open vehicle routing problem, Journal of the Operational Research Society, 51, 564-573 (2000) · Zbl 1055.90530
[23] Fu Z, Eglese RW, Li L. A tabu search heuristic for the open vehicle routing problem. Technical Report 2003/042, Lancaster University Management School, Lancaster, United Kingdom; 2003.; Fu Z, Eglese RW, Li L. A tabu search heuristic for the open vehicle routing problem. Technical Report 2003/042, Lancaster University Management School, Lancaster, United Kingdom; 2003.
[24] Brandão, J., A tabu search algorithm for the open vehicle routing problem, European Journal of Operational Research, 157, 3, 552-564 (2004) · Zbl 1068.90026
[25] Renaud, J.; Laporte, G.; Boctor, F. F., A tabu search heuristic for the multi-depot vehicle routing problem, Computers and Operations Research, 23, 3, 229-235 (1996) · Zbl 0855.90055
[26] Chao, I.; Golden, B. L.; Wasil, E., A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions, American Journal of Mathematics and Management Science, 13, 371-406 (1993) · Zbl 0808.90061
[27] Nag, B.; Golden, B. L.; Assad, A., Vehicle routing with site dependencies, (Golden, B.; Assad, A., Vehicle routing: methods and studies (1988), Elsevier: Elsevier Amsterdam), 149-159
[28] Chao, I.-M.; Golden, B.; Wasil, E., A computational study of a new heuristic for the site-dependent vehicle routing problem, INFOR, 37, 3, 319-336 (1999) · Zbl 07677596
[29] Cordeau, J.-F.; Laporte, G., A tabu search algorithm for the site dependent vehicle routing problem with time windows, INFOR, 39, 292-298 (2001) · Zbl 07677737
[30] Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen K, Mäkelä M, Toivanen J, editors. Proceedings of EUROGEN99—Short course on evolutionary algorithms in engineering and computer science, University of Jyväskylä, 1999. p. 57-64.; Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen K, Mäkelä M, Toivanen J, editors. Proceedings of EUROGEN99—Short course on evolutionary algorithms in engineering and computer science, University of Jyväskylä, 1999. p. 57-64.
[31] Desaulniers, G.; Desrosiers, J.; Erdmann, A.; Solomon, M. M.; Soumis, F., Vrp with pickup and a delivery, (Toth, P.; Vigo, D., The vehicle routing problem, SIAM monographs on discrete mathematics and applications, vol. 9 (2002), SIAM: SIAM Philadelphia), 225-242, [chapter 9] · Zbl 1076.90544
[32] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lecture notes in computer science, vol. 1520, 1998. p. 417-31.; Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lecture notes in computer science, vol. 1520, 1998. p. 417-31.
[33] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics, 159, 2, 139-171 (2000) · Zbl 0997.90105
[34] Dees, W. A.; Karger, P. G., Automated rip-up and reroute techniques, (Proceedings of the 19th conference on design automation (1982), IEEE Press: IEEE Press New York), 432-439
[35] Ahuja, R. K.; Ergun, Ö.; Orlin, J. B.; Punnen, A. P., A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics, 123, 72-102 (2002) · Zbl 1014.68052
[36] Hansen, P.; Mladenovic, N., An introduction to variable neighborhood search, (Vess, S.; etal., Metaheuristics, advances and trends in local search paradigms for optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 433-458 · Zbl 0985.90095
[37] Pisinger D. Upper bounds and exact algorithms for \(p\); Pisinger D. Upper bounds and exact algorithms for \(p\) · Zbl 1092.90027
[38] Potvin, J.-Y.; Rousseau, J.-M., A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European Journal of Operational Research, 66, 331-340 (1993) · Zbl 0775.90154
[39] Trick, M. A., A linear relaxation heuristic for the generalized assignment problem, Naval Research Logistics, 39, 137-152 (1992) · Zbl 0758.90047
[40] Pisinger D, Ropke S. A general heuristic for vehicle routing problems. Technical Report 05/01, DIKU, University of Copenhagen; 2005.; Pisinger D, Ropke S. A general heuristic for vehicle routing problems. Technical Report 05/01, DIKU, University of Copenhagen; 2005. · Zbl 1144.90318
[41] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 2, 254-265 (1987) · Zbl 0625.90047
[42] Berger, J.; Barkaoui, M.; Bräysy, O., A route hybrid genetic approach for the vehicle routing problem with time windows, INFOR, 41, 2 (2003) · Zbl 07682301
[43] Bräysy, O., A reactive variable neighborhood search for the vehicle-routing problem with time windows, INFORMS Journal on Computing, 15, 4, 347-368 (2003) · Zbl 1238.90136
[44] Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, Yagiura M. Effective local search algorithms for routing and scheduling problems with general time window constraints. Transportation Science 2005;39:206-32.; Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, Yagiura M. Effective local search algorithms for routing and scheduling problems with general time window constraints. Transportation Science 2005;39:206-32.
[45] Larsen J. Parallelization of the vehicle routing problem with time windows. PhD thesis, Department of Mathematical Modelling, Technical University of Denmark; 1999. IMM-PHD-1999-62.; Larsen J. Parallelization of the vehicle routing problem with time windows. PhD thesis, Department of Mathematical Modelling, Technical University of Denmark; 1999. IMM-PHD-1999-62.
[46] Cook W, Rich JL. A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Technical Report TR99-04, Department of Computational and Applied Mathematics, Rice University, 1999.; Cook W, Rich JL. A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Technical Report TR99-04, Department of Computational and Applied Mathematics, Rice University, 1999.
[47] Danna E, Pape CL. Accelerating branch-and-price with local search: a case study on the vehicle routing problem with time windows. Technical Report 03-006, ILOG, ILOG S.A, 9, rue de Verdun, F-94253 Gentilly Cédex; September 2003.; Danna E, Pape CL. Accelerating branch-and-price with local search: a case study on the vehicle routing problem with time windows. Technical Report 03-006, ILOG, ILOG S.A, 9, rue de Verdun, F-94253 Gentilly Cédex; September 2003.
[48] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014
[49] Kohl, N.; Desrosiers, J.; Madsen, O. B.G.; Solomon, M. M.; Soumis, F., 2-path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 1, 101-116 (1999) · Zbl 1004.90015
[50] Gehring, H.; Homberger, J., A parallel two-phase metaheuristic for routing problems with time windows, Asia-Pacific Journal of Operational Research, 18, 35-47 (2001)
[51] Bouthillier AL, Crainic TG. A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers and Operations Research 2005;32:1685-708.; Bouthillier AL, Crainic TG. A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. Computers and Operations Research 2005;32:1685-708. · Zbl 1074.90006
[52] Bräysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research 2004;159:586-605.; Bräysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research 2004;159:586-605. · Zbl 1065.90013
[53] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial optimization (1979), Wiley: Wiley New York), 315-338, [chapter 11]
[54] Toth, P.; Vigo, D., The granular tabu search and its application to the vehicle-routing problem, INFORMS Journal on Computing, 15, 4, 333-346 (2003) · Zbl 1238.90141
[55] Ergun O, Orlin JB, Steele-Feldman A. Creating very large scale neighborhoods out of smaller ones by compounding moves: a study on the vehicle routing problem. Working Paper, Massachusetts Institute of Technology; 2003.; Ergun O, Orlin JB, Steele-Feldman A. Creating very large scale neighborhoods out of smaller ones by compounding moves: a study on the vehicle routing problem. Working Paper, Massachusetts Institute of Technology; 2003.
[56] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and Operations Research, 31, 1985-2002 (2004) · Zbl 1100.90504
[57] Tarantilis, C.; Kiranoudis, C., Boneroute: an adaptive memory-based method for effective fleet management, Annals of Operations Research, 115, 227-241 (2002) · Zbl 1013.90020
[58] Berger, J.; Barkaoui, M., A new hybrid genetic algorithm for the capacitated vehicle routing problem, Journal of the Operational Research Society, 54, 1254-1262 (2003) · Zbl 1181.90032
[59] Reimann, M.; Doerner, K.; Hartl, R., D-ants: savings based ants divide and conquer the vrp, Computers and Operations Research, 31, 563-591 (2004) · Zbl 1061.90024
[60] Lambert, D.; Cooper, M., Issues in supply chain management, Marketing Management, 29, 65-83 (2000)
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.