The refuse collection is a real problem that municipalities are faced with. In large urban areas it may be modeled by a sectoring-arc routing problem (SARP). The SARP aims to build a given number of similar sectors (sub-graphs) and a set of collecting trips within each sector, so as to minimize the total duration of the trips. A fleet of identical vehicles with limited capacity is considered. Moreover, each sector must be collected by exactly one vehicle that performs one or more trips whose total duration cannot exceed a limited working time. In order to suitably model the household refuse collection in large cities, for the SARP: i) a mixed multigraph is defined, in which demand links (arcs and edges) represent the streets segments that must be serviced; ii) only a subset of the links requires to be serviced, i.e., have an associated demand; iii) like the non-demand links, the demand links may be traversed whenever needed; iv) different times are considered for link traversals with and without service. Despite being illustrated for refuse collection, the SARP is also adequate for any application involving the partition of the street segments of a town into sectors and the definition of the vehicle trips within each sector. The SARP combines sectoring (districting) problems with capacitated arc routing problems (CARP). Thus, the SARP comprises two levels of decisions: i) medium/long term decisions, fitting into the tactical/strategic level, and related with the definition of the sectors; and ii) short term decisions, within the operational level, and concerned with the definition of the trips per sector. In the literature, the CARP is commonly considered to model the household refuse collection in urban areas. However, despite being more difficult to solve than the CARP, the SARP has some advantages: while avoids sub optimization, also allows handling some features such as sectors balance, contiguity, and compactness. In fact, these are relevant issues in real based studies, since balanced vehicle crew services with a reduced number of intersections are desirable. We propose heuristic methods for the household refuse collection in large urban areas. Namely, a local search heuristic that takes into account the balancing, the compactness and the contiguity of the sectors is presented. Computational results are reported and analyzed for a set of benchmark problems.

--

combinatorial optimization, routing, sectoring, local search