Vehicle Routing Planning Using a Hybrid Approach of Spectral Clustering and Nearest Neighbour Algorithms

บทคัดย่อ

Vehicle routing is a critical problem in logistics and supply chain management, particularly in urban environments where delivery points are spatially complex and demand constraints must be satisfied. This study proposes a hybrid approach combining spectral clustering and the Nearest Neighbour (NN) algorithm to improve routing efficiency. The dataset consists of 51 delivery points located in Bangkok, Thailand, with demand information derived from historical data. Spectral clustering is first applied to group delivery points into four clusters based on spatial proximity, effectively reducing problem complexity, after which the NN algorithm is used to construct delivery routes within each cluster. The results show that the proposed method successfully generates four feasible routes, all of which satisfy the vehicle capacity constraint of 120 units. The total travel distance is reduced from 320 km to 268 km, representing an improvement of approximately 16.25%. This reduction leads to an estimated cost saving of 1,560 THB per trip, or approximately 468,000 THB annually (assuming 300 operating days). Additionally, the approach contributes to environmental sustainability by reducing carbon emissions by approximately 3.28 tons of CO₂ per year. Overall, the proposed hybrid method demonstrates strong potential for improving routing efficiency, reducing operational costs, and supporting sustainable logistics practices, with future work focusing on integrating advanced optimization techniques and real-time data.