Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic - Archive ouverte HAL Access content directly
Journal Articles Transportation Science Year : 2010

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

(1) , (1) , (2) , (2) , (3)
1
2
3

Abstract

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.
Not file

Dates and versions

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

Identifiers

Cite

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
18 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More