An Evolutionary Hyper-Heuristic Approach to the Large Scale Vehicle Routing Problem

The Large Scale Vehicle Routing Problem (LSVRP) is a classical combinatorial optimisation problem that serves several customers on a graph using a set of vehicles. Due to the NP-hardness and large problem size, LSVRP cannot be efficiently solved by exact approaches. Heuristic methods such as the Iterative Local Search or the Hybrid Genetic Algorithm still struggle for finding effective solutions for large scale instances. For these methods to deal with the large search space, pruning techniques are applied in order to limit the number of explored solutions. However, effective pruning is a hard task, requiring domain knowledge to craft good ways of limiting the search space without losing the ability to find better solutions. Hyper-heuristics are types of methods that aim to reduce domain knowledge on the creation of heuristics, and in this work, we also apply them for effective heuristic pruning. Our Evolutionary Hyper-Heuristic (EHH) automatically evolves limits to the solution search space together with the heuristic utilised to build and improve solutions for the LSVRP. We utilise a Guided Local Search (GLS) as the base algorithm in which our EHH searches for the best heuristic configuration. Our results show that the EHH can find better solutions for most LSVRP test instances when compared to the manually designed pruning of the GLS.