The Sectoring-Arc Routing Problem (SARP) models activities associated with the streets of large urban areas, such as waste collection. The SARP is defined over a mixed graph with demand arcs and edges representing the streets that must be collected. The SARP aims to build a given number of similar sectors (sub-graphs) and a set of collecting trips in each sector, such that the total duration of the trips is minimized. Vehicles are identical and have limited capacity and each sector is collected by one vehicle that performs one or more trips with total duration no more than a limited working time. Linear mixed integer programming formulations and algorithms are presented for the SARP. Computational results are reported for a set of benchmark problems.

--

Routing, Sectoring, Algorithms