# Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing Source: [Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing]() Collection index: [llms.txt]() Data updated: 2026-07-02T05:00:13.060Z Authors: Oguzhan Karaahmetoglu, Hyong Kim (1) \_\_INSTITUTION\_2\_\_ Carnegie Mellon University) Published: 2026-06-30T15:31:40.000Z ## Abstract Large-scale capacitated vehicle routing problems (CVRPs) are commonly addressed using cluster-first route-second (CFRS) approaches that split a routing instance into smaller, computationally tractable subproblems. Existing splitting methods typically rely on fixed partitioning rules, predefined optimization objectives, or learned policies, which may perform inconsistently across instances exhibiting different spatial, demand, and operational characteristics. In this work, we propose an adaptive CFRS system that formulates a decomposition procedure as an iterative decision-making process. Motivated by the recent success of large language models (LLMs) in reasoning and tool selection, the system employs an LLM as a high-level decision maker that analyzes the evolving decomposition state and selectively applies further clustering, balancing, and refinement operators. The proposed algorithm jointly partitions customers and vehicles, enabling capacity-aware clustering while adapting partitioning decisions to the characteristics of each problem. We evaluate the approach on synthetic and benchmark-derived CVRP instances containing up to 500,000 customers. Experimental results demonstrate competitive performance on benchmark-scale instances while exhibiting improved scalability and robust routing quality on substantially larger problems. These results highlight the potential of adaptive, LLM-guided decision support as a practical approach for industrial-scale vehicle routing and large-scale logistics planning. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Capacitated Vehicle Routing Problem on AGS Grid + Original 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Original 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 0. - [Capacitated Vehicle Routing Problem on AGS Grid + Scaled 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Scaled 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 0.04. - [Capacitated Vehicle Routing Problem on AGS Overlapping 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Overlapping 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 0. - [Vehicle Routing Problem on AGS benchmark-derived instances concatenated, Overlapping 2-instance (Flanders1, Flanders2)](): Vehicle Routing Problem; AGS benchmark-derived instances concatenated, Overlapping 2-instance (Flanders1, Flanders2); Missed Deliveries (%): 0. - [Capacitated Vehicle Routing Problem on AGS benchmark 10-instance concatenated (Grid + Unified Depot)](): Capacitated Vehicle Routing Problem; AGS benchmark 10-instance concatenated (Grid + Unified Depot); Missed Deliveries: 0. - [Vehicle Routing Problem on AGS Flanders1 & Flanders2, Grid + Original 2-instance concatenated](): Vehicle Routing Problem; AGS Flanders1 & Flanders2, Grid + Original 2-instance concatenated; Missed Deliveries (%): 0. - [Capacitated Vehicle Routing Problem on AGS benchmark-derived instances Grid + Unified Depot](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Unified Depot; Missed Deliveries (%): 0. - [Capacitated Vehicle Routing Problem on AGS Grid + Unified Depot 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Unified Depot 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 0.48. - [Capacitated Vehicle Routing Problem on AGS benchmark-derived instances Grid + Original (10-instance concatenated)](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Original (10-instance concatenated); Time (s): 154.321. - [Capacitated Vehicle Routing Problem on AGS 2-instance concatenated, Grid + Scaled](): Capacitated Vehicle Routing Problem; AGS 2-instance concatenated, Grid + Scaled; Missed Deliveries Rate: 11.19. - [Capacitated Vehicle Routing on 10-instance concatenated AGS (Overlapping) (test)](): Capacitated Vehicle Routing; 10-instance concatenated AGS (Overlapping) (test); Solution Time (s): 233.9. - [Capacitated Vehicle Routing Problem on AGS Grid + Scaled 10-instance Concatenated Set](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Scaled Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1, Antwerp2, Antwerp1, Leuven2, Leuven1 (10-instance concatenated); Time (s): 219.875. - [Capacitated Vehicle Routing Problem on AGS Overlapping](): Capacitated Vehicle Routing Problem; AGS Overlapping; Solution Time (s): 226.63. - [Capacitated Vehicle Routing Problem on AGS benchmark (Grid + Scaled)](): Capacitated Vehicle Routing Problem; AGS benchmark (Grid + Scaled); Total Time (s): 207.984. ## Original sources and implementation [Original paper]() [PDF]()