An Evolutionary Algorithm with Distance Measure for the Split Delivery Capacitated Arc Routing Problem

Nacima Labadie (1) , Christian Prins (1) , Mohamed Reghioui (1)

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

This chapter deals with the Split Delivery Capacitated Arc Routing Problem or SDCARP. Contrary to the classical Capacitated Arc Routing Problem or CARP, an edge may be serviced by more than one vehicle. An integer linear program, an insertion heuristic and a memetic algorithm with population management are proposed for this problem seldom studied. The algorithm calls an effective local search procedure, which contains new moves able to split demands. Compared to one of the best metaheuristics for the CARP, we show that splitting demands can bring important savings and reduce significantly the number of required vehicles.

Mots clés: Capacitated Arc Routing Problem; Split Delivery; Memetic Algorithm; Population Management; Distance Measure

Domaines: Recherche opérationnelle [math.OC]

Nacima Labadie, Christian Prins, Mohamed Reghioui. An Evolutionary Algorithm with Distance Measure for the Split Delivery Capacitated Arc Routing Problem. Recent Advances in Evolutionary Computation for Combinatorial Optimization, 153, pp.275-294, 2008, Studies in Computational Intelligence, 978-3-540-70807-0. ⟨10.1007/978-3-540-70807-0_17⟩. ⟨hal-02490519⟩