Robust Optimization Model for Green Capacitated Vehicle Routing Problem with Hamiltonian Circuit using the Nearest Neighbor Algorithm

Abstract

The rapid urban expansion of Medan City has intensified the complexity of municipal waste transportation, where limited fleet capacity, congested road segments, and long travel distances to the Terjun disposal site result in high operational costs and excessive carbon monoxide (CO) emissions. In addition, daily fluctuations in waste volume introduce uncertainty that disrupts routing efficiency and increases the risk of vehicle overload. This study proposes a Robust Optimization based Green Capacitated Vehicle Routing Problem model to minimize transportation cost and CO emissions while maintaining route feasibility under demand uncertainty. The model incorporates a Hamiltonian circuit structure to ensure closed-loop routing and applies the Nearest Neighbor Algorithm (NNA) as a constructive heuristic for generating initial solutions. Compared to commonly used methods such as the Clarke–Wright Savings algorithm, NNA provides faster computational performance, simpler implementation, and more stable feasible routes when integrated with robust capacity constraints. Using real CO emission data from major arterials in Medan, the model was evaluated across multiple uncertainty levels (Γ = 0–6). The results show that the robust model reduces overload risk by up to 12%, lowers total emission cost by approximately 5% relative to the deterministic solution, and produces more environmentally efficient routing decisions even when route distance increases slightly. From an analytical perspective, the RO Green-CVRP framework enables evaluation from operational, environmental, and robustness performance dimensions. This research contributes theoretically to green robust optimization and practically supports the development of adaptive, low-emission waste transportation strategies aligned with Medan’s sustainable urban development goals.