An emission-capacitated vehicle routing model for sustainable urban waste collection using hybrid guided local search

Abstract Urban logistics services, such as municipal solid waste collection, play a crucial role in shaping cities’ sustainability. These services are significant contributors to fuel consumption, operational costs, and greenhouse gas emissions. Traditional vehicle routing models, such as the capacitated vehicle routing problem with time windows, typically focus on minimizing distance or cost, which indirectly impacts emissions. However, these models fail to address the growing need for sustainable and environmentally conscious logistics strategies. This study introduces the emission-capacitated vehicle routing problem with time windows (E-CVRPTW), a novel optimization formulation that explicitly integrates a load-dependent fuel consumption model and an emission objective. The formulation also incorporates fleet-level policy constraints, including a carbon budget and an emission-intensity ceiling, providing a more comprehensive approach to minimizing both operational costs and environmental impacts. To solve the E-CVRPTW, a hybrid guided local search (HGLS) approach is employed with additional embedded features: (i) a novel cheapest insertion first initialization to generate high-quality starting solutions; (ii) adaptive feature penalties to diversify the search, while controlled neighborhood switching between 2-opt and 3-opt moves ensures an optimal balance between intensification and diversification. These features help the proposed algorithm to achieve better optimization solutions. Moreover, a rigorous experimental protocol using the Solomon and Gehring-Homberger benchmark instances demonstrates that HGLS, with additional features, significantly improves fuel consumption and emission reductions compared to baseline heuristics. Furthermore, a real-world case study on municipal waste collection reveals that optimized routing plans reduce fuel consumption and CO2 emissions by 9–11% while lowering total costs by 8–9%. The optimized solutions also meet strict policy targets under constrained conditions, showcasing the potential of E-CVRPTW in real-world applications. A sensitivity analysis explores the trade-offs among fuel prices, carbon prices, and emission weights, providing valuable insights for decision-makers in urban service planning and sustainability-focused policy formulation.