Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue Transportation Science Année : 2010

Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic

Résumé

This paper proposes lower and upper bounds for the split-delivery capacitated arc-routing problem (SDCARP), a variant of the capacitated arc-routing problem in which an edge can be serviced by several vehicles. Recent papers on related problems in node routing have shown that this policy can bring significant savings. It is also more realistic in applications such as urban refuse collection, where a vehicle can become full in the middle of a street segment. This work presents the first lower bound for the SDCARP, computed with a cutting plane algorithm and an evolutionary local search reinforced by a multistart procedure and a variable neighborhood descent. Tests on 126 instances show that the new metaheuristic outperforms on average a published memetic algorithm; achieves small deviations to the lower bound; and finds 44 optima, including 10 new ones.
Fichier non déposé

Dates et versions

hal-02507859 , version 1 (13-03-2020)

Identifiants

Citer

Jose-Manuel Belenguer, Enrique Benavent, Nacima Labadie, Christian Prins, Mohamed Reghioui. Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic. Transportation Science, 2010, 44 (2), pp.206-220. ⟨10.1287/trsc.1090.0305⟩. ⟨hal-02507859⟩

Collections

CNRS UTT LOSI
19 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More