Memetic Algorithms for Vehicle Routing Problems

A memetic algorithm (MA) is obtained by hybridizing a genetic algorithm with a local search procedure. The talk presents the general structure of an MA and shows how the components were designed in the case of two efficient MAs for the Vehicle Routing Problem (VRP) and the Capacitated Arc Routing Problem (CARP): chromosome encoding, evaluation, crossover and local search. The flexilibility of the tour splitting procedure used for chromosome evaluation is illustrated on a more complicated problem, the Heterogeneous Fleet VRP (HVRP). To conclude, more evolved MAs with a population management system based on distance measures (MA|PM) are described.