Skip to Main content Skip to Navigation
Book sections

A Memetic Algorithm Solving the VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs

Abstract : The VRP (Vehicle Routing Problem) and the CARP (Capacitated Arc Routing Problem) involve the routing of vehicles in an undirected network to service respectively a set of nodes or a set of arcs. Motivated by applications in waste collection, we define a more general model called NEARP (Node, Edge and Arc Routing Problem) for tackling mixed graphs with required nodes, edges and arcs. A memetic algorithm (MA) is developed for the NEARP. An evaluation on standard VRP and CARP benchmarks shows that the MA is competitive with most metaheuristics for these particular cases of the NEARP. We finally propose a set of NEARP instances, together with the solutions costs achieved by the MA, as a challenge for other researchers in vehicle routing.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02477539
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 2:31:49 PM
Last modification on : Friday, February 14, 2020 - 1:36:34 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins, Samir Bouchenoua. A Memetic Algorithm Solving the VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs. Recent Advances in Memetic Algorithms, 166, Springer-Verlag, pp.65-85, 2005, Studies in Fuzziness and Soft Computing, 978-3-540-32363-1. ⟨10.1007/3-540-32363-5_4⟩. ⟨hal-02477539⟩

Share

Metrics

Record views

46