Skip to Main content Skip to Navigation
Journal articles

Heuristics for the periodic capacitated arc routing problem

Abstract : The Capacitated Arc Routing Problem (CARP) involves the routing of vehicles to service a set of arcs in a network. This NP-hard problem is extended to a multiperiod horizon, giving a new tactical problem called the Periodic CARP (PCARP). This problem actually occurs in municipal waste collection. Its objective is to assign arcs to periods and to compute the trips in each period, to minimize an overall cost on the horizon. An integer linear program, two insertion heuristics and a two-phase heuristic are developed. These very first algorithms for the PCARP are evaluated on PCARP instances derived from standard CARP benchmarks from literature: the insertion heuristics are very fast but the two-phase method yields better solution costs.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02493970
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, February 28, 2020 - 12:39:55 PM
Last modification on : Saturday, February 29, 2020 - 1:35:33 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Feng Chu, Christian Prins, Nacima Labadie. Heuristics for the periodic capacitated arc routing problem. Journal of Intelligent Manufacturing, Springer Verlag (Germany), 2005, 16 (2), pp.243-251. ⟨10.1007/s10845-004-5892-8⟩. ⟨hal-02493970⟩

Share

Metrics

Record views

43