Skip to Main content Skip to Navigation
Journal articles

Heuristic methods for the sectoring arc routing problem

Abstract : The sectoring arc routing problem (SARP) is introduced to model activities associated with the streets of large urban areas, like municipal waste collection. The aim is to partition the street network into a given number of sectors and to build a set of vehicle trips in each sector, to minimize the total duration of the trips. Two two-phase heuristics and one best insertion method are proposed. In the two-phase methods, phase 1 constructs the sectors using two possible heuristics, while phase 2 solves a mixed capacitated arc routing problem (MCARP) to compute the trips in each sector. The best insertion method determines sectors and trips simultaneously. In addition to solution cost, some evaluation criteria such as imbalance, diameter and dispersion measures are used to compare algorithms. Numerical results on large instances with up to 401 nodes and 1056 links (arcs or edges) are reported and analysed.
Document type :
Journal articles
Complete list of metadatas

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

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Maria Cândida Mourão, Ana Catarina Nunes, Christian Prins. Heuristic methods for the sectoring arc routing problem. European Journal of Operational Research, Elsevier, 2009, 196 (3), pp.856-868. ⟨10.1016/j.ejor.2008.04.025⟩. ⟨hal-02493950⟩

Share

Metrics

Record views

41