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

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.


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