A Memetic Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

The Heterogeneous Fleet Vehicle Routing Problem is a variant of the classical Vehicle Routing Problem in which customers are served by a heterogeneous fleet of vehicles with various capacities, fixed and variable costs. Due to its complexity, no exact algorithm is known for this problem. This paper describes a genetic algorithm hybridized with two known heuristic methods for this problem. Hybrid genetic algorithms are often referred as memetic algorithms. Computational experiments presenting the performance of the proposed algorithm concerning quality of solution and processing time are reported. On a set of benchmark instances, it produces high-quality solutions, including several new best-known solutions.