A variable neighborhood descent algorithm for a real waste collection problem with mobile depots

We consider a waste collection problem encountered in Due Carrare, a town located in Northern Italy. The original feature of the problem consists in the need for arranging appointments between vehicles along their routes so that small vehicles can dump their contents in the large ones and continue their work. This feature identifies the problem as a generalization of the well-known Capacitated Arc Routing Problem (CARP). We propose a local search heuristic obtained from a variable neighborhood procedure suggested by Hertz and Mittaz for the CARP. In the Due Carrare instance, the proposed algorithm decreases the total route duration, apart from the required time for any feasible set of routes, of about 30% with respect to the routes so far adopted.