Skip to Main content Skip to Navigation
Book sections

An Effective Memetic Algorithm with Population Management for the Split Delivery Vehicle Routing Problem

Abstract : This paper studies the Split Delivery Vehicle Routing problem (SDVRP), a variant of the VRP in which multiple visits to customers are allowed. This NP-hard problem is solved by a recent metaheuristic called Memetic Algorithm with Population Management or MA|PM (Sörensen, 2003). It consists in a genetic algorithm, combined with a local search procedure for intensification and a distance measure to control population diversity. Special moves dedicated to split deliveries are introduced in the local search. This solution approach is evaluated and compared with the tabu search algorithm of Archetti et al. (2006) and with lower bounds designed by Belenguer et al. (2000). Our method outperforms the tabu search both in solution quality and running time. On a set of 49 instances, it improves the best-known solution 32 times. The savings obtained confirm the interest and the power of the MA|PM.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02490411
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, February 25, 2020 - 10:59:07 AM
Last modification on : Wednesday, February 26, 2020 - 2:02:53 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Mourad Boudia, Christian Prins, Mohamed Reghioui. An Effective Memetic Algorithm with Population Management for the Split Delivery Vehicle Routing Problem. Hybrid Metaheuristics, 4771, Springer Berlin Heidelberg, pp.16-30, 2007, Lecture Notes in Computer Science, ⟨10.1007/978-3-540-75514-2_2⟩. ⟨hal-02490411⟩

Share

Metrics

Record views

36