A hybrid population heuristic for the heterogeneous vehicle routing problems

• We designed a population heuristic for the HVRPD and HVRPFD problems.
• The local search moves are applied to a nearest neighborhood with variable size.
• Our heuristic is tested and compared with others on the Taillard (1999) instances.
• We report a new solution to instance 16 over that of Li et al. (2010).
• Give a complete description of solution to instance 20.

The heterogeneous vehicle routing problem (HVRP) plays an important role in supply chain logistics. Two variants of HVRP are treated in this paper: one with fixed and variable costs (HVRPFD), and the other with only variable cost (HVRPD). A hybrid population heuristic that is able to solve both variants is proposed, in which a population of solutions are progressively evolved by crossovers and local searches. Computational results on a set of eight benchmark test problems from literature show that the proposed heuristic produces excellent solutions in short computing times.