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.

A graph is balanced when its clique matrix is balanced. Bonomo, Durán, Lin and Szwarcfiter (2006) proved that a graph is balanced if and only if it contains no induced subgraphs known as extended odd suns. However, a characterization of balanced graphs by minimal forbidden induced subgraphs is not known. In this work, we find such a characterization when restricted to the class of claw-free graphs. As a consequence, we prove that there is an O(m2 + n)-time algorithm that, given any graph, either decides that it is balanced or gives a certificate of the fact that it is not claw-free balanced.