Clustering Approaches in Vehicle Routing Problems: A Comparative Study on Real-World Scenarios
The Vehicle Routing Problem (VRP) is among the most complex optimization problems. Practical solutions require addressing real-world constraints such as time windows, vehicle capacities, delivery restrictions, driver working hours, and heterogeneous vehicle fleets. Solutions are often implemented in two stages: the first involves clustering customers, while the second focuses on incremental routing of these clusters to reduce complexity and improve solution control and explainability. However, the second stage heavily depends on the quality of the first, and clustering methods vary depending on client requirements. This paper explores various clustering methods and their impact on the final routing results, with a focus on real-world examples. The study includes diverse client scenarios, ranging from small-scale distribution systems with a limited number of customers to large-scale operations managing more than thousand of deliveries daily, covering both small and large orders. From fixed clustering and geographic partitioning to dynamic clustering algorithms and hybrid approaches, the advantages and limitations of each method are analyzed. The findings aim to provide actionable insights into selecting clustering methods that align with specific use cases, ensuring enhanced efficiency and adaptability in practical applications.