A new hybrid genetic algorithm for the capacitated vehicle routing problem. (English) Zbl 1181.90032

Berger, J.; Barkaoui, M.

J. Oper. Res. Soc. 54, No. 12, 1254-1262 (2003).

Summary: Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.

MSC:

90B06	Transportation, logistics and supply chain management
90B10	Deterministic network models in operations research
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

vehicle routing problems; heuristics