Applying the attribute based hill climber heuristic to the vehicle routing problem. (English) Zbl 1109.90011
Summary: The attribute based hill climber (ABHC) is a variant of the general tabu-search principle which has shown to be competitive with respect to quality as well as efficiency to other local search heuristics for the two corner stone problems in combinatorial optimization: the travelling salesman problem and the quadratic assignment problem. ABHC is completely parameter-free, and its generic logic depends on the concept of partitioning the solution space based on solution “attributes”, which is the problem-specific choice. In this paper we analyze the effectiveness of this concept and the efficiency of the ABHC heuristic for the general vehicle routing problem.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B40 | Search theory |
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Augerat, P., 1995. Approche polyèdrale du problème de tournées de véhicules. Thesis/PhD, Artemis/IMAG, Institut National Polytechnique de Grenoble-Inpg.; Augerat, P., 1995. Approche polyèdrale du problème de tournées de véhicules. Thesis/PhD, Artemis/IMAG, Institut National Polytechnique de Grenoble-Inpg. |
| [2] | Berger, J.; Barkaoui, M., A new hybrid genetic algorithm for the capacitated vehicle routing problem, Journal of the Operational Research Society, 54, 1254-1262 (2004) · Zbl 1181.90032 |
| [3] | Christofides, N.; Eilon, S., An algorithm for the vehicle dispatching problems, Operational Research Quarterly, 20, 309-318 (1979) |
| [4] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581 (1964) |
| [5] | 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 |
| [6] | 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 (2001) · Zbl 1181.90034 |
| [7] | Cordeau, J.-F.; Gendreau, M.; Laporte, G.; Potvin, J.-Y.; Semet, F., A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53, 512-522 (2002) · Zbl 1099.90506 |
| [8] | Cordeau, J.-F.; Gendreau, M.; Hertz, A.; Laporte, G.; Sormany, J.-S., New heuristics for the vehicle routing problem, (Langevin, A.; Riopel, D., Logistic Systems: Design and Optimization (2005), Springer: Springer New York), 279-297 · Zbl 1130.90416 |
| [9] | De Backer, B.; Furnon, V., Local search in constraint programming: Experiments with tabu search on the vehicle routing problem, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics—Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 63-76 · Zbl 0972.90014 |
| [10] | Ergun, Ö., Orlin, J.B., Steele-Feldmann, A., 2003. 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.; Ergun, Ö., Orlin, J.B., Steele-Feldmann, A., 2003. 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. |
| [11] | Fisher, M. L., Optimal solution of vehicle routing problems using minimum \(k\)-trees, Operations Research, 42, 626-642 (1994) · Zbl 0815.90066 |
| [12] | Glover, F., Tabu search—Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054 |
| [13] | Glover, F., Tabu search—Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084 |
| [14] | Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I.-M., Metaheuristics in vehicle routing, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 33-56 · Zbl 0997.90021 |
| [15] | Kilby, P.; Prosser, P.; Shaw, P., Guided local search for the vehicle routing problem with time windows, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics—Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 473-486 · Zbl 0985.90019 |
| [16] | Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [17] | Laporte, G., 2005. Metaheuristics for the vehicle routing problem. Presentation at Operations Research 2005, Bremen, Germany. Available from: <www.hec.ca/chairedistributique/metaheuristics.pdf; Laporte, G., 2005. Metaheuristics for the vehicle routing problem. Presentation at Operations Research 2005, Bremen, Germany. Available from: <www.hec.ca/chairedistributique/metaheuristics.pdf |
| [18] | Laporte, G.; Osman, I. H., Routing problems: A bibliography, Annals of Operations Research, 61, 227-262 (1995) · Zbl 0839.90032 |
| [19] | Li, F.; Golden, B. L.; Wasil, E. A., Very large-scale vehicle routing: New test problems, algorithms, and results, Computers & Operations Research, 32, 1165-1179 (2004) · Zbl 1075.90013 |
| [20] | Mester, D.; Bräysy, O., Active guided evolution strategies for the large scale vehicle routing problems with time windows, Computers & Operations Research, 32, 1593-1614 (2005) · Zbl 1122.90403 |
| [21] | Mills, P.H., 2002. Extensions to guided local search. Ph.D. thesis, Department of Computer Science, University of Essex.; Mills, P.H., 2002. Extensions to guided local search. Ph.D. thesis, Department of Computer Science, University of Essex. |
| [22] | Potvin, J.-Y.; Rousseau, J.-M., An exchange heuristic for routing problems with time windows, Journal of the Operational Research Society, 46, 1433-1446 (1995) · Zbl 0843.90043 |
| [23] | Potvin, J.-Y.; Kervahut, T.; Garcia, B.-L.; Rousseau, J.-M., The vehicle routing problem with time windows, Part I: Tabu search, INFORMS Journal on Computing, 8, 157-164 (1996) · Zbl 0866.90057 |
| [24] | Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research, 31, 1985-2002 (2004) · Zbl 1100.90504 |
| [25] | Savelsbergh, M. W.P., The vehicle routing problem with time windows: Minimizing route duration, ORSA Journal on Computing, 4, 146-154 (1992) · Zbl 0780.90105 |
| [26] | Schulze, J.; Fahle, T., A parallel algorithm for the vehicle routing problem with time window constraints, Annals of Operations Research, 86, 585-607 (1999) · Zbl 0922.90059 |
| [27] | Tarantitis, C.-D.; Kiranoudis, C. T., Bone route: An adaptive memory-based method for effective fleet management, Annals of Operations Research, 115, 227-241 (2002) · Zbl 1013.90020 |
| [28] | Toth, P.; Vigo, D., The granular tabu search and its application to the vehicle routing problem, INFORMS Journal on Computing, 15, 333-346 (2003) · Zbl 1238.90141 |
| [29] | Voudouris, C., 1997. Guided local search for combinatorial problems. Ph.D. thesis, University of Essex.; Voudouris, C., 1997. Guided local search for combinatorial problems. Ph.D. thesis, University of Essex. · Zbl 0882.90102 |
| [30] | Voudouris, C.; Tsang, E., Guided local search and its application to the traveling salesman problem, European Journal of Operational Research, 113, 469-499 (1999) · Zbl 0937.90094 |
| [31] | Whittley, I. M.; Smith, G. D., The attribute based hill climber, Journal of Mathematical Modelling and Algorithms, 3, 167-178 (2004) · Zbl 1062.90078 |
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.
