Skip to Main content Skip to Navigation
Journal articles

Two memetic algorithms for heterogeneous fleet vehicle routing problems

Abstract : The vehicle routing problem (VRP) plays an important role in the distribution step of supply chains. From a depot with identical vehicles of limited capacity, it consists in determining a set of vehicle trips of minimum total length, to satisfy the demands of a set of customers. In general, the number of vehicles used is a decision variable. The heterogeneous fleet VRP (HFVRP or HVRP) is a natural generalization with several vehicle types, each type being defined by a capacity, a fixed cost, a cost per distance unit and a number of vehicles available. The vehicle fleet mix problem (VFMP) is a variant with an unlimited number of vehicles per type. This paper presents two memetic algorithms (genetic algorithms hybridized with a local search) able to solve both the VFMP and the HVRP. They are based on chromosomes encoded as giant tours, without trip delimiters, and on an optimal evaluation procedure which splits these tours into feasible trips and assigns vehicles to them. The second algorithm uses a distance measure in solution space to diversify the search. Numerical tests on standard VFMP and HFVRP instances show that the two methods, especially the one with distance measure, compete with published metaheuristics and improve several best-known solutions.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02525203
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, March 30, 2020 - 6:15:11 PM
Last modification on : Tuesday, March 31, 2020 - 2:01:05 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins. Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, Elsevier, 2009, 22 (6), pp.916-928. ⟨10.1016/j.engappai.2008.10.006⟩. ⟨hal-02525203⟩

Share

Metrics

Record views

19