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

Christian Prins (1) , Samir Bouchenoua (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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.

Mots clés: memetic algorithm; vehicle routing; general routing problem

Domaines: Recherche opérationnelle [math.OC]; Algorithme et structure de données [cs.DS]

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⟩