Abstract
Last-mile delivery companies can face demand surges where large-volume order requests exceed daily courier capacity. In such cases fast and robust feasibility-first planning becomes more practical and valuable than building optimal routes. This paper proposes a hierarchical, computationally feasible decomposition pipeline that produces shift-feasible clusters under a strict shift-duration limit using travel-time-based duration estimates. While decomposition methods for large-scale VRPs are well established, they typically remain oriented toward route-construction quality within a single operational day or toward balancing customer counts, demand, or Euclidean territory partitions. In contrast, the proposed method targets a different decision problem: rapid feasibility-first strategic capacity planning for one-time extreme demand surges, where the primary requirement is to estimate, within seconds, a conservative upper bound on the number of courier shifts under a strict shift-duration limit. When end-to-end latency is evaluated from raw geographic points, including distance-matrix preparation for monolithic baselines, the proposed pipeline becomes 187 to 1315 times faster than matrix-based monolithic optimization on the common benchmark sizes. Methodologically, the contribution lies in combining (i) topology-preserving spatial linearization with a Hilbert Space-Filling Curve, (ii) adaptive greedy microclustering driven by empirical travel-time quantiles, and (iii) lexicographic dynamic-programming merge that minimizes the number of shifts first and total travel time second. This yields a planning-oriented decomposition mechanism that is distinct from classical route-quality-centered hierarchical VRP approaches.