DocumentCode :
2731313
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
Volume :
3
fYear :
2005
fDate :
2-5 Sept. 2005
Firstpage :
2271
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Print_ISBN :
0-7803-9363-5
Type :
conf
DOI :
10.1109/CEC.2005.1554977
Filename :
1554977
Link To Document :
بازگشت