INTEGRATED VEHICLE ROUTING AND COLLECTION POINT OPTIMIZATION FOR URBAN WASTE MANAGEMENT: A LAGRANGIAN RELAXATION APPROACH WITH WALKING-DISTANCE CONSTRAINTS

Abstract

Thailand’s urban areas face significant waste management challenges due to increasing population density and inefficient collection systems. This results in high operational costs and significant environmental impact. Moreover, traditional waste management methods lack integrated optimizations of collection point placement and vehicle routing, leading to suboptimal resource utilization. This study develops an integrated optimization approach that simultaneously determines optimal collection point locations and vehicle routes while minimizing fuel consumption and ensuring resident accessibility through walking-distance constraints. A vehicle routing problem with generalized clustering and maximum walking distance (VRPGC-MWD) is formulated in this study as a mixed-integer linear programming model that integrates collection point selection with vehicle routing optimization. A Lagrangian relaxation (LR) approach is proposed and tested on instances ranging from 7 to 30 locations, with 2–5 vehicles and 3–8 collection points, to efficiently solve this Non-deterministic Polynomial-time hard problems. The LR approach maintains optimality gaps below 7.73% for small instances. For larger instances where exact methods fail, the LR approach offers efficient solutions with gaps between 8.91% and 13.10%. This research contributes to the first integrated model combining collection point selection with vehicle routing under walking-distance constraints, offering Thai municipalities a practical tool to support waste management.