A Density-Based Clustering Method and Beam Search for a Capacitated Vehicle Routing Problem with Time Windows

Abstract. This study introduces a multi-stage strategy for addressing the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) in the context of Iran’s national postal system. The proposed method integrates a density-based spatiotemporal clustering technique with a heuristic optimization process to enhance the efficiency of large-scale logistics management. To reduce computational complexity, the MDST-DBSCAN algorithm is utilized to cluster provincial postal centers based on operational and spatial characteristics. Integrating operational and spatial features of problem in clustering process, brings the CVRPTW closer to real-world. Once clustering is complete, a beam search heuristic is applied to create feasible delivery routes within each cluster. The beam search algorithm identifies optimal routes by searching multiple route in parallel. These routes are then fine-tuned using a 2-opt local search technique. Overall, the framework effectively simplifies the complexity of route planning and aligns with real-world postal logistics needs, achieving notable improvements in both route length reduction and fleet usage.