Decision Support for a Waste Collection Service with Time and Shift Constraints

This paper presents a decision support for addressing urban waste collection services that are characterized by the presence of a garage from which all the vehicles start their routes, an intermediate facility where the vehicles unload the waste and a large number of pick up positions. Moreover, in a shift the vehicle can perform several routes subject to time and capacity constraints. Our aim is supporting the decision maker in planning the optimal vehicle routes with the objective of minimizing the length of the travels while collecting all the daily waste. The Waste Collection Vehicle Routing Problem (WCVRP) is modelled as a Mixed Integer Linear Programming problem with shift and time constraints. In order to address the large dimension of the considered city street networks, we propose a heuristic algorithm based on a clustering strategy and a farthest insertion heuristic for the solution of the Traveling Salesman Problem. A set of tests and a case study show the effectiveness of the proposed heuristic algorithm to plan the waste collection in a work day of an Italian city.