A Combined Generative and Selective Hyper-heuristic for the Vehicle Routing Problem

Sim, K., Hart, E. (2016). A Combined Generative and Selective Hyper-heuristic for the Vehicle Routing Problem. In: (Ed.) Proceedings go GECCO 2016, , () ( ed.). (pp. ). : . ACM.



Hyper-heuristic methods for solving vehicle routing problems (VRP) have proved promising on a range of data. The vast majority of approaches apply selective hyper- heuristic methods that iteratively choose appropriate heuristics from a fixed set of pre-defined low-level heuristics to either build or perturb a candidate solution. We propose a novel hyper-heuristic called GP-MHH that operates in two stages. The first stage uses a novel Genetic Programming (GP) approach to evolve new high quality constructive heuristics; these can be used with any existing method that relies on a candidate solution(s) as its starting point. In the second stage, a perturbative hyper- heuristic is applied to candidate solutions created from the new heuristics. The new constructive heuristics are shown to outperform existing low-level heuristics. When combined with a na ̈ıve perturbative hyper-heuristic they provide results which are both competitive with known optimal values and outperform a recent method that also designs new heuristics on some standard benchmarks. Finally, we provide results on a set of rich VRPs, showing the generality of the approach.
[Read More]


Emma Hart
Director of CEC
+44 131 455 2783
Kevin Sim
+44 131 455 2497

Areas of Expertise

Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.