Title :
Capacitated vehicle routing: perturbing the landscape to fool an algorithm
Author :
Morgan, Matthew J W ; Mumford, Christine L.
Author_Institution :
Sch. of Comput. Sci., Cardiff Univ., UK
Abstract :
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.
Keywords :
bin packing; genetic algorithms; heuristic programming; road traffic; travelling salesman problems; CVRP; Clarke-Wright heuristic; capacitated vehicle routing problem; constructive heuristic techniques; customer locations; hybrid genetic algorithm; Buildings; Computer science; Costs; Genetic algorithms; Iterative algorithms; Optimization methods; Routing; Testing; Traveling salesman problems; Vehicles;
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Print_ISBN :
0-7803-9363-5
DOI :
10.1109/CEC.2005.1554977