Graph partitioning-based matheuristic for residential waste collection problem with visual attractiveness and turn penalty

The residential waste collection problem is a variant of the arc routing problem in which vehicles collect household waste along streets and transport it to landfills. In practice, drivers and planners prefer routes that are easy to follow, clearly separated, and visually coherent, whereas cost-minimizing solutions often yield unintuitive routes. To bridge this, the concept of visual attractiveness (VA) has been studied to evaluate how compact, non-overlapping, and connected routing solutions are. This study extends VA by introducing the arc overlapping index (AOI), which quantifies residents’ dissatisfaction from repeated vehicle visits. We propose a mixed integer linear programming model that jointly minimizes AOI and turn-penalty-aware route costs, accounting for the turning delays of heavy garbage trucks often ignored in previous studies. To efficiently generate visually attractive solutions that capture the separability of road networks (e.g., bridges and tunnels), we develop a graph partitioning-based matheuristic. Graph partitioning divides a network into balanced subgraphs while minimizing edge cuts but has rarely been applied to routing problems, which typically assume complete graphs. Our approach leverages both graph-structural and spatial information to produce compact, non-overlapping, and capacity-feasible clusters, whose routes are then optimized using the proposed mathematical model. Computational experiments on 31 road-network clustering instances with up to 2400 nodes and 3000 edges show that our method is 120-times faster than baseline algorithms for capacitated clustering on average, while yielding higher connectivity and less overlap. On 100 routing instances, our method achieves a 6.0 % route-cost reduction and outperforms previous approaches across all VA metrics.