Enhancing Last-Mile Delivery Efficiency in Urban Environments Through Clustering and MILP-Based Route Optimization

Abstract

Last-mile delivery in dense urban areas demands routes that are both time-efficient and operationally realistic. We address this need with a two-stage framework coupling road-network-aware spatial clustering with an exact Mixed-Integer Linear Programming (MILP) solution to the Traveling Salesman Problem (TSP). Delivery points are first grouped via k-means using shortest-path distances on an OpenStreetMap-derived graph; centroids are snapped to valid road nodes, and the cluster count is automatically increased until every stop lies within a user-defined distance threshold. The depot and these centroids form a reduced TSP that is solved optimally. A case study for Al Khobar, Saudi Arabia, condenses 100 synthetic delivery locations into eight clusters and produces an optimal vehicle tour of 26.2 km in roughly one second on commodity hardware. Experiments over 50 random instances and five cluster sizes confirm that the proposed MILP route is consistently shortest, reducing total distance compared to heuristic and metaheuristic methods, while remaining tractable (< 5 s) even at 25 clusters. These results demonstrate that embedding realistic road geometry in the clustering stage enables exact optimization to scale to real-world problem sizes, providing a reproducible blueprint for efficient, high-quality last-mile delivery planning in understudied regions.