A solution approach to districting modification and route optimization in waste collection

Abstract

The efficient design of waste collection systems is a key challenge for municipalities, both from economic and operational standpoints. This paper addresses the problem of simultaneously modifying an existing districting and optimizing collection routes in urban waste management systems. The routing component is modeled as a Mixed General Routing Problem with Turn Penalties, where each truck must cover all corners and specific block sides within its assigned zone while minimizing both distance and turns. We propose a novel methodology that integrates districting and routing optimization through an iterative process based on Variable Neighbourhood Search. Unlike traditional approaches that build new districtings from scratch, our method improves the current districting to ease practical implementation. Additionally, we introduce a new algorithm to find minimum-cost paths under turn penalties and traffic restrictions.The proposed strategy was applied to the real-world case study of Quilmes, a city in the Buenos Aires metropolitan area. The results show a 10.93% reduction in total daily travel distance achieved through route optimization within the existing zones, and up to a 57% decrease in workload imbalance due to districting modifications. These improvements lead to better working conditions, reduced fuel consumption, and increased operational efficiency. The methodology is applicable to waste collection in cities where districts can be defined as sets of blocks, and where route planning must consider turn costs and traffic constraints. We have delivered the results of this work to the authorities of the Municipality of Quilmes for field implementation.