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 metadata

https://hal-utt.archives-ouvertes.fr/hal-02525203
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Monday, March 30, 2020 - 6:15:11 PM
Last modification on : Friday, August 27, 2021 - 3:14:08 PM

Identifiers

Collections

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

26