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. In this research work three objectives were 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. One constructive heuristic and two local search heuristics based on hill climbing (HC) and on tabu search (TS) methods, are presented. Experiments with a set of benchmark based instances and with a set of real world based instances are performed. Computational results show that the constructive heuristic is very fast but tends to produce solutions with very high imbalances, namely on the largest size instances. The computational results 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 criterion. The results obtained with TS on the large instances are very promising, namely if compared with the best previous known results, making it worth to consider for other practical applications.

--

Capacitated Arc Routing problems, District Design, Metaheuristics