This paper addresses a residential waste collection problem, as a real world application of the sectoring arc routing problem. The aim is to assign the street services to the different vehicles, and then to determine the set of trips to be performed by each single vehicle such that all the required streets are serviced within a minimum objective. Three objectives are taken into account: the total traveled time, the workload balance among the sectors, and the connectivity of each sector. The proposed solution methods were designed in order to favor the concentration of each vehicle service area in a geographical region. A constructive heuristic and meta-heuristics are presented. Preliminary computational results with both a set of benchmark and a set of real world based instances are performed. The results show that the constructive heuristic is very fast but tends to produce imbalanced sectors concerning the traveled time. They also highlight the importance of considering the aforementioned criteria simultaneously on the evaluation of the solutions during the search process: if only one criteria is considered then the quality of the solution increases for the criteria that is being considered but decreases, in some cases largely, for the other two criteria.

--

Capacitated Arc Routing problems, Sector Design, Meta-heuristics