A Two-Stage Clustering and Genetic Algorithm Approach for Courier Delivery Clustering and Route Optimization

Abstract

Efficient delivery area allocation and route planning are essential for improving operational performance in last-mile logistics. However, inappropriate delivery area grouping can lead to longer travel distances and reduced delivery efficiency. This study proposes a two-stage approach for courier delivery optimization consisting of delivery area clustering and route optimization. In the first stage, delivery areas were clustered using Single Linkage and K-Means based on geographical proximity. In the second stage, delivery routes were optimized using a Genetic Algorithm (GA) within the Capacitated Vehicle Routing Problem (CVRP) framework while considering vehicle capacity constraints. The proposed approach was evaluated using delivery demand data from a courier service hub and compared with the existing delivery system. The results indicate that the K-Means clustering approach produced the shortest total travel distance among the evaluated scenarios. Demand analysis showed that the highest weekend demand occurred on Sundays with 199 packages, while the highest weekday demand occurred on Wednesdays with 147 packages. Compared with the existing routing system, the K-Means-based approach reduced total travel distance by 37.6% on Sundays and 5.51% on Wednesdays. These findings demonstrate that the proposed cluster-first, route-second approach can effectively reduce travel distance and improve delivery efficiency in last-mile logistics operations.