Capacitated arc routing problems are used to manage the activities over the links (arcs and edges) of a graph performed by vehicles with limited capacity. The household refuse collection in urban areas may be modeled by such problems. In particular, we will focus on the mixed capacitated arc routing problem (MCARP) and on the sectoring-arc routing problem (SARP), both defined over a mixed multigraph, since this better holds street map characteristics underlying in household refuse collection applications. The MCARP consists of finding the trips starting and ending at the depot, serving all the required links and satisfying vehicles capacity, at minimum total duration. In the SARP, the subset of required links is partitioned into a fixed number of sectors and, for each sector, a set of MCARP trips, within a given time limit, is achieved. In real world applications, such as the household refuse collection, it is also desirable to ensure the contiguity of the service for each vehicle, thus favoring the concentration of the service of each vehicle in a zone and avoiding vehicles’ intersection while servicing. However, this kind of practical requirement is not usually contemplated in linear programming formulations for capacitated arc routing problems when mixed graphs are considered. Keeping this in mind, we will discuss linear constraints that may be added to force the contiguity of the links served by each vehicle (trip or sector), meaning that the subgraph induced by the links served by each vehicle is connected. Computational results will be reported and analyzed over sets of benchmark problems.

--