Genetic local search with distance preserving recombination operator for a vehicle routing problem

The paper describes a systematic adaptation of the genetic local search algorithm to a real life vehicle routing problem. The proposition is motivated by successful implementations of genetic local search-based heuristics for a number of combinatorial optimization problems. The key element of the proposed approach is the use of global convexity tests. The tests allow finding the types of solution features that are essential for solution quality. The results of the tests are used to construct an appropriate distance preserving recombination operator. Results of computational experiments demonstrating the efficiency of the proposed approach are reported. (C) 2003 Elsevier B.V. All rights reserved.