Capacitated vehicle routing: perturbing the landscape to fool an algorithm

Simple constructive heuristic techniques often product poor solutions when applied to the capacitated vehicle routing problem (CVRP). In this paper, we present a hybrid genetic algorithm that lightly perturbs the customer coordinate sets, and "fools" a simple Clarke and Wright heuristic (CW) into producing much better solutions than is the case when CW is applied to the original customer locations. Furthermore, we demonstrate that the new approach compares favorably with other state-of-the-art methods when tested on a set of instances derived from the literature.