6533b7d1fe1ef96bd125d90a
RESEARCH PRODUCT
Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
Enrique BenaventChristian PrinsNacima LabadiJosé-manuel BelenguerMohamed Reghiouisubject
EngineeringMathematical optimization0211 other engineering and technologiesTransportation02 engineering and technologyUpper and lower boundsCARP0502 economics and businessLocal search (optimization)capacitated arc-routing problemMetaheuristicCivil and Structural Engineering050210 logistics & transportationSDCARP021103 operations researchbusiness.industryNode (networking)05 social sciences[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]split deliverycutting planeevolutionary local searchMemetic algorithmRouting (electronic design automation)businessArc routingCutting-plane methoddescription
International audience; 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-05-01 |