Applying Cluster Analysis to the Vehicle Routing Problem

With changes in consumer habits, online shopping has become an integral part of routine life. However, transactions with online or physical shops still need to be completed through the delivery of physical goods to consumers. Planning transportation for physical goods involves the vehicle routing problem (VRP). Minimizing the number of dispatched vehicles, optimizing travel distances, and ensuring on-time deliveries contribute directly to improvements in customer satisfaction, energy use, and carbon emissions. Environmental, social, and governance (ESG) issues are now a global concern, and transportation planning outcomes can affect a company’s ESG performance. Heuristic methods are commonly employed to solve VRPs, and cluster analysis plays a particularly crucial role in this process. In this study, the applicability of three cluster analysis methods—minimum spanning tree (MST), K-means clustering, and density-based spatial clustering of applications with noise (DBSCAN)—for various VRPs was explored. A method for adjusting k-means cluster sizes was developed and verified to outperform MST and DBSCAN, particularly for vehicle fleets with heterogeneous capacities. The developed method achieved distance costs over 15% lower than the other tested algorithms.