A Flexible and Adaptive Hyper-heuristic Approach for (Dynamic) Capacitated Vehicle Routing Problems

• Autorzy: Garrido P. , Castro C.
• Języki publikacji: EN

Abstrakty

EN

We present a self-adaptive hyper-heuristic capable of solving static and dynamic instances of the capacitated vehicle routing problem. The hyper-heuristic manages a generic sequence of constructive and perturbative low-level heuristics, which are gradually applied to construct or improve partial routes. We present some design considerations to allow the collaboration among heuristics, and to find the most promising sequence. The search process is carried out by applying a set of operators which constructs new sequences of heuristics, i.e., solving strategies. We have used a general and low-computational cost parameter control strategy, based on simple reinforcement learning ideas, to assign non-arbitrary reward/penalty values and guide the selection of operators. Our approach has been tested using some standard state-of-the-art benchmarks, which present different topologies and dynamic properties, and we have compared it with previous hyper-heuristics and several well-known methods proposed in the literature. The experimental results have shown that our approach is able to attain quite stable and good quality solutions after solving various problems, and to adapt to dynamic scenarios more naturally than other methods. Particularly, in the dynamic case we have obtained high-quality solutions when compared with other algorithms in the literature. Thus, we conclude that our self-adaptive hyper-heuristic is an interesting approach for solving vehicle routing problems as it has been able (1) to guide the search for appropriate operators, and (2) to adapt itself to particular states of the problem by choosing a suitable combination of heuristics.

Słowa kluczowe

EN

hyper-heuristics; heuristic search; vehicle routing problems; metaheuristics; parameter control; reinforcement learning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 1
• Strony: 29--60
• Opis fizyczny: Bibliogr. 43 poz., tab., wykr.

Twórcy

autor

Garrido P.

autor

Castro C.

• Departamento de Informatica, Universidad Tecnica Federico Santa Marýa, Avenida Espa�na 1680, Casilla 110-V, 2390123 Valparaýso, Chile.,

Bibliografia

• [1] Bader-El-Den, M., Poli, R.: Generating SAT local-search heuristics using a GP hyper-heuristic framework, 8th International Conference on Artificial Evolution, EA 2007, 4926, Springer, 2008.
• [2] Bai, R., Burke, E., Gendreau, M., Kendall, G., McCollum, B.: Memory length in hyper-heuristics: an empirical study, IEEE Symposium on Computational Intelligence in Scheduling, SCIS '07, IEEE, 2007.
• [3] Bianchi, L.: Notes on dynamic vehicle routing - the state of the art, Technical Report IDSIA-05-01, IDSIA, 2001.
• [4] Burke, E., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: A survey and classification of hyperheuristics, Journal of Heuristics, to appear.
• [5] Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology, Handbook of Metaheuristics, 57, 2003, 457-474.
• [6] Burke, E., Petrovic, S., Qu, R.: Case-based heuristic selection for timetabling problems, Journal of Scheduling, 9(2), 2006, 115-132.
• [7] Burke, E., Silva, J. L., Soubeiga, E.: Multi-objective hyper-heuristic approaches for space allocation and timetabling, Meta-heuristics: Progress as Real Problem Solvers, 32, 2005, 129-158.
• [8] Chakhlevitch, K., Cowling, P.: Hyperheuristics: Recent Developments, in: Adaptive and Multilevel Metaheuristics, vol. 136 of Studies in Computational Intelligence, Springer, 2008, 3-29.
• [9] Christofides, N., Beasley, J.: The period routing problem, Networks, 14(2), 1984, 237-256.
• [10] Cordeau, J., Gendreau, M., Hertz, A., Laporte, G., Sormany, J.: New heuristics for the vehicle routing problem, Logistics Systems: Design and Optimization, 2005, 279-297.
• [11] Dorigo, M., Stützle, T.: Ant Colony Optimization (Bradford Books), The MIT Press, 2004.
• [12] Dowsland, K., Soubeiga, E., Burke, E.: A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation, European Journal of Operational Research, 179(3), 2007, 759-774.
• [13] Fisher, M.: Optimal solution of vehicle routing problems using minimum k-trees, Operations Research, 42(4), 1994, 626-642.
• [14] Fonseca, E., Fuchshuber, R., Santos, L., Plastino, A., Martins, S.: Hybrid DM-GRASP metaheuristic: evaluating mining frequency, 10th International Conference on Parallel Problem Solving From Nature, Dortmund, Germany, 2008.
• [15] Gambardella, L., Taillard, E., Agazzi, G.: MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, New Ideas in Optimization, 1999, 63-76.
• [16] Garrido, P., Castro, C.: Stable solving of CVRPs using hyperheuristics, Genetic and Evolutionary Computation Conference, GECCO '09, ACM, 2009.
• [17] Garrido, P., Castro, C., Monfroy, E.: Towards a flexible and adaptable hyperheuristic approach for VRPs, 2009 International Conference on Artificial Intelligence, IC-AI 2009, CSREA Press, 2009.
• [18] Garrido, P., Riff, M.: Collaboration between hyperheuristics to solve strip-packing problems, 12th International Fuzzy Systems Association World Congress, IFSA 2007, 4529, Springer-Verlag, 2007.
• [19] Gendreau, M., Guertin, F., Potvin, J., S´eguin, R.: Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Transportation Research Part C: Emerging Technologies, 14(3), 2006, 157-174.
• [20] Gendreau, M., Potvin, J.-Y., Bräysy, O., Hasle, G., Løkketangen, A.: Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography, in: The Vehicle Routing Problem: Latest Advances and New Challenges, vol. 43 of Operations Research/Computer Science Interfaces Series, Springer-Verlag, 2008, 143-169.
• [21] Hanshar, F. T., Ombuki-Berman, B. M.: Dynamic vehicle routing using genetic algorithms, Applied Intelligence, 27(1), 2007, 89-99.
• [22] Kendall, G., Hussin, N. M.: An investigation of a tabu search based hyper-heuristic for examination timetabling, Multidisciplinary Scheduling: Theory and Applications, 2005, 309-328.
• [23] Kilby, P., Prosser, P., Shaw, P.: Dynamic VRPs: a study of scenarios, Technical Report APES-06-1998, University of Strathclyde, Glasgow, Scotland, 1998.
• [24] Kinderwater, G., Savelsbergh, M.: Vehicle routing: handling edge exchanges, Local Search in Combinatorial Optimization, 1997, 337-360.
• [25] Krumke, S., Rambau, J., Torres, L.: Real-time dispatching of guided and unguided automobile service units with soft time windows, 10th Annual European Symposium on Algorithms, ESA '02, 2461, Springer, 2002.
• [26] Laporte, G., Gendreau, M., Potvin, J., Semet, F.: Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7, 2000, 285-300.
• [27] Lysgaard, J., Letchford, A., Eglese, R.: A new branch-and-cut algorithm for the capacitated vehicle routing problems, Mathematical Programming, 100(2), 2004, 423-445.
• [28] Mester, D., Bräysy, O.: Active guided evolution strategies for large-scale vehicle routing problems with time windows, Computers and Operations Research, 32(6), 2005, 1593-1614.
• [29] Montemanni, R., Gambardella, L., Rizzoli, A., Donati, A.: A new algorithm for a dynamic vehicle routing problem based on ant colony system, Proceedings of ODYSSEUS 2003, Palermo, Italy, 2003.
• [30] Montemanni, R., Gambardella, L., Rizzoli, A., Donati, A.: Ant colony system for a dynamic vehicle routing problem, Journal of Combinatorial Optimization, 10(4), 2005, 327-343.
• [31] Montero, E., Riff, M.: Calibrating strategies for evolutionary algorithms, IEEE Congress on Evolutionary Computation, CEC 2007, IEEE, 2007.
• [32] Nannen, V., Eiben, A.: Efficient relevance estimation and value calibration of evolutionary algorithm parameters, IEEE Congress on Evolutionary Computation, CEC 2007, IEEE, 2007.
• [33] Özcan, E., Kalender, M., Burke, E.: A greedy gradient-simulated annealing hyperheuristic, 10th International Conference on Parallel Problem Solving From Nature, Dortmund, Germany, 2008.
• [34] Özcan, E., Uyar, S., Burke, E.: A greedy hyper-heuristic in dynamic environments, Genetic and Evolutionary Computation Conference (Conference Companion), GECCO '09, ACM, 2009.
• [35] Pankratz, G.: Dynamic vehicle routing by means of a genetic algorithm, International Journal of Physical Distribution & Logistics Management, 35(5), 2005, 362-383.
• [36] Potvin, J., Xu, Y., Benyahia, I.: Vehicle routing and scheduling with dynamic travel times, Computers and Operations Research, 33(4), 2006, 1129-1137.
• [37] Rego, C.: A subpath ejection chain method for the vehicle routing problem, Management Science, 44(10), 1996, 1447-1459.
• [38] Rochat, Y., Taillard, E.: Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1(1), 1995, 147-167.
• [39] Ross, P., Marin-Blázquez, J. G., Schulenburg, S., Hart, E.: Learning a procedure that can solve hard binpacking problems: a new GA-based approach to hyperheurstics, Genetic and Evolutionary Computation Conference, GECCO '03, ACM, 2003.
• [40] Soubeiga, E.: Development and application of hyperheuristics to personnel scheduling, Ph.D. Thesis, University of Nottingham, United Kingdom, 2003.
• [41] Sutton, R. S., Barto, A. G.: Reinforcement Learning: An Introduction, The MIT Press, 1998.
• [42] Taillard, E.: Parallel iterative search methods for vehicle routing problem, Networks, 23, 1993, 661-673.
• [43] Terashima-Marin, H., Farias-Zarate, C., Ross, P., Valenzuela-Rendon, M.: Comparing two models to generate hyper-heuristics for the 2d-regular bin-packing problem, Genetic and Evolutionary Computation Conference, GECCO '07, ACM, 2007.