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

José-Manuel Belenguer (), Enrique Benavent (), Nacima Labadi (), Christian Prins () and Mohamed Reghioui ()
Additional contact information
José-Manuel Belenguer: Departamento d'Estadística i Investigació Operativa, Universitat de València, 46100 Burjassot (València), Spain
Enrique Benavent: Departamento d'Estadística i Investigació Operativa, Universitat de València, 46100 Burjassot (València), Spain
Nacima Labadi: ICD-LOSI (FRE CNRS 2848), Université de Technologie de Troyes, 10010 Troyes, France
Christian Prins: ICD-LOSI (FRE CNRS 2848), Université de Technologie de Troyes, 10010 Troyes, France
Mohamed Reghioui: ENSA de Tétouan, Mhannech II, BP 2121 Tétouan, Morocco

Transportation Science, 2010, vol. 44, issue 2, 206-220

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.

Keywords: capacitated arc-routing problem; split delivery; cutting plane; CARP; SDCARP; evolutionary local search (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0305 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:44:y:2010:i:2:p:206-220

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().