Marcelo R. H. Maia, Universidade Federal Fluminense

Abstract

The hybrid genetic search (HGS) metaheuristic has produced outstanding results for several variants of the vehicle routing problem. A recent implementation of HGS specialized to the capacitated vehicle routing problem (CVRP) stands as a state-of-the-art method for this variant. This paper proposes an improved HGS for the CVRP obtained by incorporating a new method for initializing the population to guide the search more efficiently and effectively. The initialization method introduced in this work combines an approach based on frequent patterns extracted from good solutions by a data mining process and a randomized version of the Clarke and Wright savings heuristic. As observed in our experimental comparison with the original algorithm, the proposed method provides significant improvements to the primal integral, a performance measure that rewards a balance of convergence speed and solution quality.

[Challenge Paper]   [Video]