Vehicle Routing and Adaptive Iterated Local Search within the HyFlex Hyper-heuristic Framework

摘要

HyFlex (Hyper-heuristic Flexible framework) [15] is a software framework enabling the development of domain independent search heuristics (hyper-heuristics), and testing across multiple problem domains. This framework was used as a base for the first Cross-domain Heuristic Search Challenge, a research competition that attracted significant international attention. In this paper, we present one of the problems that was used as a hidden domain in the competition, namely, the capacitated vehicle routing problem with time windows. The domain 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 adaptive variants of a multiple-neighborhood iterated local search algorithm that operate in a domain independent fashion, and therefore can be considered as hyper-heuristics. Our results confirm 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.