Refuse collection in large urban areas may by modeled by a Sectoring-Arc Routing Problem (SARP). The SARP groups two families of problems: sectoring (or districting) problems and capacitated arc routing problems (CARP). Therefore, it combines two levels of decisions: i) medium/long term decisions – tactical/strategic level – on which sectors are defined; and ii) short term decisions – operational level – where trips for each sector are built. In the literature, the refuse collection in urban areas is usually modeled by the CARP. However, despite being more difficult to solve than the CARP, the SARP has some advantages: it avoids sub optimization, and some features such as sectors balance, contiguity, and compactness may be better handled. The relevance of these marks is justified by the need of obtaining balanced vehicle crew services with a number of intersections as small as possible. The SARP is defined over a mixed graph with links (arcs and edges) representing the street segments, and some of these links require collection. For each link, a traversal duration is known. Furthermore, for each demand link, collecting quantity and time are also given. The SARP aims to build a given number of similar sectors (sub-graphs) and a set of collecting trips in each sector. The objective is to minimize the total duration of the trips. All of the demand links of a sector are collected by exactly one vehicle. Vehicles are identical and have limited capacity. Each vehicle is assigned to only one sector and 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; Heuristics; Sectoring