Vehicle routing and adaptive iterated local search within the HyFlex hyper-heuristic framework

Citation

Walker J, Ochoa G, Gendreau M & Burke E (2012) Vehicle routing and adaptive iterated local search within the HyFlex hyper-heuristic framework. In: Hamadi Y & Schoenauer M (eds.) Learning and Intelligent Optimization 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers. Lecture Notes in Computer Science, Vol. 7219. 6th International Conference, LION 6,, Paris, France, 16.01.2012-20.01.2012. Amsterdam: Springer, pp. 265-276. http://link.springer.com/chapter/10.1007/978-3-642-34413-8_19#; https://doi.org/10.1007/978-3-642-34413-8_19

Abstract
HyFlex (Hyper-heuristic Flexible framework) [15] is a soft- ware framework enabling the development of domain independent search heuristics (hyper-heuristics), and testing across multiple problem do- mains. This framework was used as a base for the first Cross-domain Heuristic Search Challenge, a research competition that attracted signif- icant international attention. In this paper, we present one of the prob- lems that was used as a hidden domain in the competition, namely, the capacitated vehicle routing problem with time windows. The do- main implements a data structure and objective function for the vehicle routing problem, as well as many state-of- the-art low-level heuristics (search operators) of several types. The domain is tested using two adap- tive variants of a multiple-neighborhood iterated local search algorithm that operate in a domain independent fashion, and therefore can be con- sidered as hyper-heuristics. Our results con¯rm that adding adaptation mechanisms improve the performance of hyper-heuristics. It is our hope that this new and challenging problem domain can be used to promote research within hyper-heuristics, adaptive operator selection, adaptive multi-meme algorithms and autonomous control for search algorithms

Keywords
combinatorial optimization; hyper-heuristics