Path relinking for the vehicle routing problem. (English) Zbl 1122.90068
Summary: This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aiex, R.M., S. Binato, and M.G.C. Resende. (2003). ”Parallel GRASP with Path-Relinking for Job Shop Scheduling.” Parallel Computing 29(4), 393–430. · doi:10.1016/S0167-8191(03)00014-0 |
| [2] | Aiex, R.M., M.G.C. Resende, P.M. Pardalos, and G. Toraldo. (2005). ”GRASP with Path-Relinking for the Three-Index Assignment Problem,” INFORMS Journal on Computing 17(2), 224–247. · Zbl 1239.90087 · doi:10.1287/ijoc.1030.0059 |
| [3] | Alfa, A.S., S.S. Heragu, and M. Chen. (1991). ”A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problems.” Computers & Industrial Engineering 21(1–4), 635–639. · doi:10.1016/0360-8352(91)90165-3 |
| [4] | Berger, J. and M. Barkaoui. (2003). ”A New Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem.” Journal of the Operational Research Society 54(12), 1254–1262. · Zbl 1181.90032 · doi:10.1057/palgrave.jors.2601635 |
| [5] | Bullnheimer, B., R.F. Hartl, and C. Strauss. (1998). ”Applying the Ant System to the Vehicle Routing Problem.” In S. Voss, S. Martello, I. H. Osman, and C. Roucairol, (eds.), Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization, Boston: Kluwer, pp. 109–120. · Zbl 0970.90019 |
| [6] | Bullnheimer, B., R.F. Hartl, and C. Strauss. (1999). ”An Improved Ant System for the Vehicle Routing Problem.” Annals of Operations Research 89, 319–328. · Zbl 0937.90125 · doi:10.1023/A:1018940026670 |
| [7] | Christofides, N. and S. Eilon. (1969). ”An Algorithm for the Vehicle Dispatching Problem.” Operational Research Quarterly 20(3), 309–318. · doi:10.1057/jors.1969.75 |
| [8] | Christofdes, N., A. Mingozzi, and P. Toth. (1979). ”The Vehicle Routing Problem.” In N. Christofdes, A. Mingozzi, P. Toth, and C. Sandi (eds.) Combinatorial Optimization, Wiley, Chichester, pp. 315–338. |
| [9] | Cordeau, J.-F., M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany. (2005). New Heuristics for the Vehicle Routing Problem. In A. Langevin and D. Riopel, (eds.), Logistics Systems: Design and Optimization. Boston: Kluwer. · Zbl 1130.90416 |
| [10] | Cordeau, J.-F. and G. Laporte. (2004). Tabu Search Heuristics for the Vehicle Routing Problem. In C. Rego and B. Alidaee, (eds.), Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search. Boston: Kluwer, pp. 145–163. · Zbl 1072.90054 |
| [11] | Cordeau, J.-F., G. Laporte, and A. Mercier. (2001). ”A Unifed Tabu Search Heuristic for Vehicle Routing Problems with Time Windows.” Journal of the Operational Research Society 52(8), 928–936. · Zbl 1181.90034 · doi:10.1057/palgrave.jors.2601163 |
| [12] | Dongarra, J.J. (2004). Performance of Various Computers using Standard Linear Equations Software, Technical Report CS-89-85, Computer Science Department, University of Tennessee, Knoxville, TN. |
| [13] | Ergun, Ö., J.B. Orlin, and A. Steele-Feldman. (2003). ”Creating very Large Scale Neighborhoods out of Smaller ones by Compounding Moves: A Study on the Vehicle Routing Problem.” Technical report, Massachusetts Institute of Technology. · Zbl 1122.68593 |
| [14] | Gendreau, M., A. Hertz, and G. Laporte. (1994). ”A Tabu Search Heuristic for the Vehicle Routing Problem.” Management Science 40(10), 1276–1290. · Zbl 0822.90053 · doi:10.1287/mnsc.40.10.1276 |
| [15] | Gendreau, M., G. Laporte, and J.-Y. Potvin. (2002). Metaheuristics for the capacitated VRP, In P. Toth and D. Vigo (eds.), The Vehicle Routing Problem, SIAM Society for Industrial and Applied Mathematics, Philadelphia, pp. 129–154. · Zbl 1076.90545 |
| [16] | Ghamlouche, I., T.G. Crainic, and M. Gendreau. (2004). ”Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design.” Annals of Operations Research 131(1-4), 109–133. · Zbl 1067.90014 · doi:10.1023/B:ANOR.0000039515.90453.1d |
| [17] | Glover, F. (1986). ”Future Paths for Integer Programming and Links to Artificial Intelligence.” Computers & Operations Research13(5), 533–549. · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1 |
| [18] | Glover, F. (1997). ”Tabu Search and Adaptive Memory Programming–Advances, Applications and Challenges.” in R. S. Barr, R. V. Helgason, and J. L. Kennington (eds.), Interfaces in Computer Science and Operations Research. Boston: Kluwer, pp. 1–75. · Zbl 0882.90111 |
| [19] | Glover, F. (1998). ”A Template for Scatter Search and Path Relinking,” in J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer and D. Snyers (eds), ”Artificial Evolution.” Vol. 1363 of Lecture Notes in Computer Science, Springer, Berlin, pp. 13–54. |
| [20] | Glover, F. and M. Laguna. (1993). Tabu search, In C. R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publishing, pp. 70–150. · Zbl 0774.90033 |
| [21] | Glover, F., M. Laguna, and R. Martí. (2000). ”Fundamentals of Scatter Search and Path Relinking.” Control and Cybernetics 39(3), 653–684. · Zbl 0983.90077 |
| [22] | Golden, B. L., E.A. Wasil, J.P. Kelly, and I.-M. Chao. (1998). Metaheuristics in Vehicle Routing, In T. G. Crainic and G. Laporte, eds, Fleet Management and Logistics. Boston: Kluwer, pp. 33-56. · Zbl 0997.90021 |
| [23] | Kawamura, H., M. Yamamoto, T. Mitamura, K. Suzuki, and A. Ohuchi. (1998). ”Cooperative Search on Pheromone Communication for Vehicle Routing problems.” IEEE Transactions on Fundamentals E81-A, 1089–1096. |
| [24] | Laguna, M. and V.A. Armentano. (2005). Lessons from applying and experimenting with scatter search, In C. Rego and B. Alidaee, (eds.), Adaptive Memory and Evolution: Tabu Search and Scatter Search. Kluwer, Norwell, pp. 229–246. · Zbl 1072.90569 |
| [25] | Li, F., B. Golden, and E. Wasil. (2005). ”Very Large-scale Vehicle Routing: New test problems, algorithms, and results.” Computers & Operations Research 32(5), 1165–1179. · Zbl 1075.90013 |
| [26] | Mester, D. and O. Bräysy. (2005). ”Active Guided Evolution Strategies for the Large Scale Vehicle Routing Problems with Time Windows.” Computers & Operations Research 32(6), 1593–1614. · Zbl 1122.90403 · doi:10.1016/j.cor.2003.11.017 |
| [27] | Oliveira, C. A., P.M. Pardalos, and M.G. Resende. (2004). GRASP with path-relinking for the quadratic assignment problem, In C. C. Ribeiro and S. L. Martins (eds.), Efficient and Experimental Algorithms. Vol. 3059 of Lecture Notes in Computer Science,Springer-Verlag, Berlin, pp. 356–368. |
| [28] | Osman, I. H. (1993). ”Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem.” Annals of Operations Research 41(1-4), 421–151. · Zbl 0775.90153 · doi:10.1007/BF02023004 |
| [29] | Prins, C. (2004). ”A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem.” Computers & Operations Research 31(12), 1985–2002. · Zbl 1100.90504 · doi:10.1016/S0305-0548(03)00158-8 |
| [30] | Rego, C. (1998). ”A Subpath Ejection Method for the Vehicle Routing Problem.” Management Science44(10), 1447-1459. · Zbl 0989.90522 · doi:10.1287/mnsc.44.10.1447 |
| [31] | Rego, C. and C. Roucairol. (1996), ”A Parallel Tabu Search Algorithm using Ejection Chains for the Vehicle Routing Problem,” In I. H. Osman and J. P. Kelly (eds), Meta-Heuristics: Theory and Applications, Boston: Kluwer, MA, pp. 661–675. · Zbl 0877.90034 |
| [32] | Reimann, M. (2004). ”Private Communication”. |
| [33] | Reimann, M., K. Doerner, and R.F. Hartl. (2004). ”D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem.” Computers & Operations Research 31(4), 563–591. · Zbl 1061.90024 · doi:10.1016/S0305-0548(03)00014-5 |
| [34] | Resende, M.G.C. and C.C. Ribeiro. (2003). ”A GRASP with Path-relinking for Private Virtual Circuit Routing.” Networks 41(2), 104–114. · Zbl 1028.90502 · doi:10.1002/net.10065 |
| [35] | Rochat, Y. and É.D. Taillard. (1995). ”Probabilistic Diversification and Intensification in Local Search for Vehicle Routing.” Journal of Heuristics 1(1), 147–167. · Zbl 0857.90032 · doi:10.1007/BF02430370 |
| [36] | Souza, M. C., C. Duhamel, and C.C. Ribeiro. (2003). ”A GRASP Heuristic for the Capacitated Minimum Spanning tree Problem using a Memory-Based Local Search Strategy,” In M. G. C. Resende and J. P. Sousa, (eds.), Metaheuristics: Computer Decision-Making. Boston: Kluwer Academic Publishers, pp. 627–658. |
| [37] | Taillard, É.D. (1993). ”Parallel Iterative Search Methods for Vehicle Routing Problems.” Networks 23(8), 661–673. · Zbl 0804.90045 · doi:10.1002/net.3230230804 |
| [38] | Tarantilis, C. D. (2005). ”Solving the Vehicle Routing Problem with Adaptive Memory Programming Methodology.” Computers & Operations Research32(9), 2309–2327. · Zbl 1116.90119 · doi:10.1016/j.cor.2004.03.005 |
| [39] | Toth, P. and D. Vigo. (2003). ”The Granular Tabu Search and its Application to the Vehicle-Routing Problem.” Journal on Computing 15(4), 333–346. · Zbl 1238.90141 |
| [40] | Toth, P. and D. Vigo, (eds.), (2002). The Vehicle Routing Problem, SIAM Society for Industrial and Applied Mathematics, Philadelphia. · Zbl 0979.00026 |
| [41] | Xu, J. and J.P. Kelly. (1996). ”A Network flow-based Tabu Search Heuristic for the Vehicle Routing Problem.” Transportation Science 30(4), 379–393. · Zbl 0879.90086 · doi:10.1287/trsc.30.4.379 |
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.
