Simulation and graph based optimization of urban waste transportation networks with CO₂ emission assessment: evidence from Ampenan district

Abstract

The increasing population in Ampenan District in Lombok Island has contributed to a continuous rise in municipal solid waste generation, requiring a more efficient waste transportation route planning system. Inefficient routing may increase travel distance, fuel consumption, operational costs, collection delays, and carbon emissions. This study applies Prim’s algorithm as a minimum spanning tree approach to determine minimum-distance waste transportation networks and estimate the related CO₂ emissions in Ampenan District. Waste collection points and transportation paths were modeled as a weighted undirected graph, where vertices represent collection points and edges represent road distances between points. The waste transportation system involved four garbage trucks operating in four route groups. For each group, the total route distance was optimized using Prim’s algorithm. The results show that the minimum route distance obtained for Group 1 was 3.279 km, Group 2 was 5.05 km, Group 3 was 6.45 km, and Group 4 was 3.20 km, resulting in a total optimized route length of 17.979 km. Based on an estimated diesel consumption rate of 0.143 L/km and an emission factor of 2.68 kg CO₂/L, the optimized routes require approximately 2.57 liters of diesel and generate around 6.89 kg CO₂ per operation. These findings indicate that Prim’s algorithm can support the design of more efficient waste transportation networks by minimizing travel distance, fuel consumption, and associated emissions. This study contributes to urban waste management planning by providing a graph-based optimization model that can assist local governments in improving transportation efficiency and supporting more sustainable municipal waste services.