Martin Simensen, SINTEF

Abstract

In this paper we propose a hybrid metaheuristic for the Capacitated Vehicle Routing Problem (CVRP) called Hybrid Genetic Search with Ruin-and-Recreate (HGSRR). The CVRP is a problem that has been subject to intense research efforts for more than sixty years. Yet, significant algorithmic improvements are still being made. The most competitive heuristic solution algorithms of today utilize, and often combine, strategies and elements from evolutionary algorithms, local search, and ruin-and-recreate based large neighborhood search. The proposed method HGSRR is no exception, as it is based on the hybrid genetic search algorithm proposed by [8], although it differs by applying the ruin-and-recreate based large neighborhood search from [1] to extend the education phase of the genetic algorithm.

[Challenge Paper]   [Video]