Affiliations: Department of Computer Science, Universidad Técnica Federico Santa María, 2390123 Valparaíso, Chile, pgarrido@inf.utfsm.cl ; ccastro@inf.utfsm.cl
Note: [] Address for correspondence: Departamento de Informática, Universidad Técnica Federico Santa María, Avenida España 1680, Casilla 110-V, 2390123 Valparaíso, Chile. Partially supported by the Chilean National Science and Technology Fund, FONDECYT, under grant No. 1070268.
Abstract: 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.
