Delivery routes optimized using mathematical models such as TSP and VRP may appear counterintuitive to users. Upon reviewing the results, users often wonder why the route seems indirect or why nearby stops are not served first. These concerns usually originate from two main reasons.
One contributing factor is the discrepancy between human intuition and the objective functions used in optimization models. Humans tend to interpret “reasonable” routes as those that appear spatially continuous and regionally consistent. Optimization models for vehicle routing, however, focus on minimizing global cost, and therefore may produce solutions that include route crossings or backtracking if such configurations yield better overall performance.
The second factor is that TSP and VRP are inherently NP-hard problems. As the problem scale increases, both computational complexity and solution time grow rapidly. Under practical constraints on computation time, it is often difficult to guarantee that the resulting solution is globally optimal.
Moreover, real-world routing optimization problems typically require the incorporation of additional practical constraints, such as driver working hours, service times at delivery locations, and heterogeneous vehicle types and capacities. These factors further complicate the problem, making it challenging even for human planners to manually construct routes that can be considered “reasonable.”
For computational systems, identifying a solution that remains practically feasible under strict real-world constraints and within limited computation time is likewise a challenging task.Therefore, in many practical scenarios, solutions that appear visually counterintuitive may in fact be the only ones capable of satisfying all imposed constraints simultaneous
To better align the final results with human interpretability, pre-clustering delivery targets represents one of the most intuitive approaches.
When confronted with a large number of delivery locations, humans are often unable to plan one or multiple “ideal” delivery routes in a single step, let alone simultaneously account for various real-world constraints. Consequently, a common strategy is to first partition delivery locations into several groups based on factors such as geographic proximity, distance, or familiarity, and then address each group separately.
Clustering effectively reduces the scale of the problem, making routes more visually and cognitively comprehensible, while also facilitating workload distribution and the delineation of responsibility zones. In other words, the value of clustering does not primarily lie in shortening routes or reducing travel time, but in transforming a complex problem into one that is interpretable. For instance, in real-world delivery operations, frontline personnel often encounter unexpected situations, such as a delivery location being temporarily closed. In such cases, clustering ensures spatial concentration of delivery points, allowing drivers to first address nearby locations before returning to complete tasks that could not be carried out immediately, thereby enhancing operational flexibility.
However, even after clustering, time window constraints at delivery locations may still result in solutions that are, to some extent, “imperfect.” For example, breakfast shops typically require deliveries early in the morning, whereas vendors at evening markets restock in the late afternoon. Even if these locations are geographically close, it may still be challenging to include them in the same delivery route.