arXiv CSopen access

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing

arXiv:2606.31820v1 [cs.AI] 30 Jun 2026

Oguzhan Karaahmetoglu, Prof. Dr. Hyong Kim ARTICLE HISTORY Compiled July 1, 2026 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 decisionmaking 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. KEYWORDS Capacitated Vehicle Routing; Vehicle Routing; Large Scale; Large Language Models; Cluster-First Route-Second;

1. Introduction 1.1. Preliminaries Vehicle routing problems (VRPs) are a fundamental component of modern logistics and production systems, supporting transportation, distribution, and service operations for a wide range of industries [20, 33]. As supply chains become increasingly dynamic and customer expectations continue to rise, organizations are required to solve routing problems of unprecedented scale while operating under diverse spatial, demand, fleet, and operational characteristics [11, 26]. Such heterogeneity presents a significant challenge for CVRP methodologies, as decomposition and optimization strategies that perform well in one operating environment may generalize poorly to others [19, 28]. Efficiently constructing high-quality routing plans under these varyO. Karaahmetoglu and Dr. Hyong Kim are with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213 USA e-mail: [email protected], [email protected]

ing conditions is essential for reducing routing costs, improving service quality, and supporting sustainable logistics operations [4, 8]. Consequently, the development of scalable and adaptive methodologies has become an increasingly important research direction for industrial decision support systems. Among the many variants of the VRP, the Capacitated Vehicle Routing Problem (CVRP) is one of the most widely studied and serves as a canonical formulation for numerous logistics and distribution applications [20, 33]. In the CVRP, a fleet of capacity-constrained vehicles must serve a set of geographically distributed customers while minimizing routing cost. Despite its relatively simple formulation, the CVRP is NP-hard, and the computational complexity of obtaining high-quality solutions increases rapidly with problem size [21, 33]. Although substantial advances have been achieved through exact algorithms, metaheuristics, and hybrid optimization methods, efficiently solving industrial-scale instances involving tens or hundreds of thousands of customers while maintaining solution quality remains a significant computational challenge [36]. To address the computational challenges of massive routing scenarios, many approaches adopt a cluster-first route-second (CFRS) paradigm, in which customers are partitioned into smaller subproblems that can be solved independently before being combined into a global solution [2, 33]. Existing partitioning methods can be broadly categorized as geometric, optimization-based, and learning-based approaches [22, 29]. While these methods have shown success throughout a variety of settings, they generally rely on fixed partitioning rules, predefined optimization objectives, or learned policies trained on historical data [2, 10, 15]. However, industrial environments often differ substantially in their spatial distributions, demand structure, fleet composition, and operational constraints, requiring partitioning strategies to be carefully designed for the characteristics of the routing instance [19, 27]. Hence, selecting an appropriate strategy remains a challenging decision-making task that directly influences downstream routing quality and computational efficiency [2, 36]. Motivated by these limitations, we propose an adaptive decomposition framework that employs a large language model (LLM) as a high-level decision-making component for routing decomposition. Recent advances have revealed the ability of LLMs to perform complex reasoning and coordinate external tools, making them well suited for sequential decision-support tasks beyond natural language processing [13, 16, 23]. The LLM iteratively analyzes the incumbent decomposition plan, identifies potential inefficiencies, and selects refinement actions based on the observed state without directly assigning individual customers to clusters. These actions are executed through a collection of clustering, balancing, and partition-modification heuristics exposed as optimization tools, allowing the methodology to leverage established decomposition methods while adaptively selecting strategies appropriate for the distribution of the CVRP dataset. Through this iterative process, our approach continuously refines the partitions according to the spatial, demand, fleet, and operational configuration of the problem, as opposed to relying on a single predefined clustering objective or fixed partitioning rule. 1.2. Prior Art Decomposition has long been recognized as an effective strategy for improving the computational tractability of large-scale VRPs by dividing an optimization formulation into smaller, more manageable subproblems [20, 33]. Instead of solving the original

2

task as a single monolithic process, decomposition approaches partition customers and resources into subproblems that can be solved independently before being integrated into a global operational plan [31]. Among the various strategies proposed in the literature, clustering-based approaches have become particularly popular due to their simplicity, scalability, and compatibility with a broad range of algorithms [2, 10, 15]. Geometric partitioning methods decompose instances primarily according to the spatial distribution of customers. Representative examples include sweep-based clustering, grid-based partitioning, and recursive spatial splitting [5, 10, 15]. These approaches are attractive due to their simplicity, computational efficiency, and scalability to very large VRP instances. However, partitioning decisions are primarily driven by geographic information and generally do not explicitly account for customer demand, vehicle capacities, or other operational considerations [2,6]. Thus, additional balancing or repair procedures are often required to improve workload distribution and restore routing feasibility. Optimization-based clustering methods extend geometric partitioning by incorporating operational objectives directly into the decomposition process. In addition to spatial compactness, these approaches explicitly consider customer demand, vehicle capacities, workload balancing, and other resource-related constraints when constructing clusters [1,2]. By integrating these considerations into the process, optimization-based methods generally produce partitions that better reflect routing requirements and available resources. Recent work has further explored optimization-driven strategies for large instances, demonstrating strong scalability while maintaining high-quality logistics solutions [31,34]. Therefore, optimization-based clustering has become a widely adopted approach for computationally demanding instances. Despite these advantages, optimization-based and learning-based approaches remain dependent on the objectives specified during partition construction or model training. Common optimization objectives include balancing customer counts [7], total demand [17], vehicle capacity [24], and spatial compactness for all clusters [1, 24], while learning-based methods are typically trained to optimize surrogate objectives derived from historical observations encountered [9, 22]. Since each instance can vary substantially in their spatial structure, demand distribution, fleet composition, and operational constraints [35], the relative importance of these objectives may also vary across operating environments. Consequently, designing effective decomposition strategies requires balancing multiple, and often competing, routing considerations, motivating adaptive approaches capable of selecting decomposition actions according to the statistical properties of the data. Recent advances in large language models (LLMs) have generated growing interest in their application to combinatorial optimization and industrial decision-support systems [12, 38]. Beyond direct solution generation, LLMs have shown the ability to reason over complex system states, coordinate external optimization tools, and sequentially select actions within iterative workflows [13, 32]. These capabilities make them well suited for optimization formulations in which effective decisions depend on the characteristics of the evolving solution rather than a single predefined objective. This perspective has recently led to the emergence of agentic optimization frameworks, where LLMs guide optimization by repeatedly analyzing intermediate states, selecting appropriate actions, and incorporating feedback from specialized algorithms and heuristics [23, 37]. Such developments suggest that LLMs can serve as adaptive decision-making components within decomposition workflows while leveraging established optimization techniques for execution.

3

1.3. Contributions In this paper, we make the following contributions. • We propose an adaptive cluster-first route-second framework for large-scale CVRPs that formulates decomposition as an iterative decision-making process. The approach employs an LLM to analyze intermediate partitions and coordinate clustering, balancing, and refinement operations through a collection of optimization tools. • We introduce a joint customer-vehicle splitting strategy that explicitly incorporates resource availability into the decomposition process, enabling capacityaware partitions for heterogeneous fleets. • We develop a large-scale evaluation benchmark spanning both synthetic and benchmark-derived CVRP instances, including VRP data containing up to 500,000 customers under diverse spatial, demand, and operational settings. • We demonstrate that our approach yields high performance on benchmark-scale instances while exhibiting improved scalability and robust performance on substantially larger routing scenarios.

2. Problem Formulation In this work, we consider the CVRP with heterogeneous vehicle capacities and unsplittable customer demands (i.e., no more than one vehicle can visit the same customer). |N | Given a set of customers N = {i}i=1 , associated demands fi , i ∈ N , and a fleet of vehicles K with limited capacities Fk , k ∈ K, the objective is to construct a set of routes that minimizes the total routing cost while respecting vehicle capacity constraints. Although the primary goal is to serve all customer demand, the formulation permits unserved customers through a demand-weighted penalty term λ ∈ R+ in the objective, thereby discouraging missed demand while allowing infeasible demand levels or resource shortages to be represented within the model. Table 1.: CVRP Formulation Notation Symbol N K V = {0} ∪ N fi Fk qijk λ aijk bik ui

Description Set of customers Set of vehicles Set of all nodes including the depot node 0 Demand of customer i Capacity of vehicle k Travel cost from node i to node j using vehicle k Penalty coefficient for unserved demand Binary variable indicating whether vehicle k traverses arc (i, j) Binary variable indicating whether customer i is assigned to vehicle k Binary variable indicating whether customer i is left unserved

Using the notation introduced in Table 1, we illustrate a generic CVRP instance with the described requirements in Figure 1a. Following standard CVRP formulations

4

(a) Heterogeneous Fleet CVRP. Customers with unsplittable demands are assigned to vehicles with heterogeneous capacities while minimizing routing cost and penalizing unserved demand.

(b) Cluster-First RouteSecond (CFRS). The problem is decomposed into customervehicle subproblems that are solved independently and later refined through collaboration and global optimization.

(c) LLM-guided planning. An LLM-guided decision maker analyzes intermediate solutions, selects actions, invokes helper tools, and iteratively updates the output.

Figure 1.: Overview of the optimization setting and solution method. Figure 1a illustrates the heterogeneous fleet CVRP considered in this work. Figure 1b presents the Cluster-First Route-Second paradigm used to scale routing optimization to very large instances. Figure 1c shows how agentic AI can be incorporated into planning workflows by coupling language-model reasoning with optimization and analysis tools. [20, 33], the formulation can be expressed as the following integer linear program: min a,b,u

s.t.

X XX

qijk aijk + λ

k∈K i∈V j∈V

X

X

fi ui

(1)

i∈N

bik + ui = 1

∀i ∈ N

(2)

aijk = bik

∀i ∈ N, ∀k ∈ K

(3)

ajik = bik

∀i ∈ N, ∀k ∈ K

(4)

fi bik ≤ Fk

∀k ∈ K

(5)

∀i, j ∈ V, ∀k ∈ K ∀i ∈ N, ∀k ∈ K ∀i ∈ N.

(6) (7) (8)

k∈K

X j∈V

X j∈V

X i∈N

aijk ∈ {0, 1} bik ∈ {0, 1} ui ∈ {0, 1}

Subtour elimination constraints are omitted for brevity but are assumed to be present to prevent disconnected cycles that do not include the depot and to ensure that each vehicle route forms a connected tour. The objective in (1) minimizes total delivery cost while penalizing unserved demand through the parameter λ, thereby discouraging customer omissions whenever feasible. Constraints enforce customer assignment, route continuity, and vehicle capacity limits, while ensuring that each customer is either assigned to a vehicle or marked as unserved.

5

A solution is defined as a collection of routes S = {R1 , . . . , Rm }, where each route (1) (r) (i) Rk = (0, Rk , . . . , Rk , 0), Rk ∈ N is an ordered sequence of customer Pvisits beginning and ending at the depot. The cost of a route is defined as C(Rk ) = rt=0 qR(t) ,R(t+1) ,k , k k P and the total solution cost is C(S) = Rk ∈S C(Rk ). Let U (S) ⊆ N denote the set of customers not P served by any route in S. The unserved demand of a solution is defined as M (S) = i∈U (S) fi . In the next subsections, we explain how decomposition in CVRP is formulated using CFRS paradigm and the agentic systems are used in solving combinatorial optimization problems. 2.1. CFRS Paradigm Formulation Given a CVRP instance with customers and vehicles (N, K), a CFRS method decomposes the original planning task into a collection of smaller subproblems as shown in Figure 1b. Let P = {(N1 , K1 ), . . . , (Np , Kp )} denote a partition of the customer and vehicle sets, where Nc ⊆ N and Kc ⊆ K represent the customers and vehicles assigned to partition c. The decomposition procedure is treated as a black-box process that generates the partitions according to a particular clustering strategy such as Sweep [15]. For each partition (Nc , Kc ), an independent CVRP subproblem is constructed using the formulation presented in the previous section, restricted to the customers and vehicles assigned to that partition. Solving the subproblem yields a partial solution Sc = {Rk }k∈Kc , where unused vehicles correspond to empty routes. The S final solution is obtained by combining the routes produced by all partitions, S = pc=1 Sc . Since each subproblem is solved independently, partitioning decisions directly affect the resulting solution. P P For example, if a cluster has lower total capacity than total demand k∈Kc Fk < i∈Nc fi , then partition c cannot serve all assigned demand, leading to unserved customers in the final solution. Likewise, restricting customers and vehicles to a particular partition may increase routing cost even when each subproblem is solved optimally. Abstracting away the details of a particular clustering algorithm, a decomposition method can be represented as an operator Dθ : (N, K) → P, where θ denotes the parameters governing the decomposition policy. Different CFRS approaches correspond to different implementations of the operator. Remark 1. The operator Dθ need not jointly partition customers and vehicles. Many CFRS methods instead employ separate operators DθN (N ) and DθK (K) to generate customer and vehicle partitions independently. For example, customers may be clustered using k-means [25] while vehicles are assigned with equal counts. Within this framework, θ denotes the information that determines how a partition is generated. For optimization-based methods, θ typically includes the clustering objective, balancing criteria, and algorithmic settings. For learning-based methods, θ corresponds to the parameters of the trained model. Thus, many existing CFRS approaches can be viewed as instances of the same operator Dθ , differing only in how partitioning decisions are produced. Certain CFRS approaches additionally employ a global refinement phase after the S partition solutions have been combined into the solution S = pc=1 Sc [18]. This phase applies a post-processing operator R(S) that modifies routes across partition boundaries in order to reduce delivery cost, recover unserved demand, or both. 6

In the following subsection, we explain how we use agentic LLMs to build hierarchical decompositions iteratively. 2.2. Agentic AI in Adaptive Planning and Optimization Agentic optimization systems treat optimization as a sequential decision-making process as in Figure 1c. At each iteration, an agent observes the state of the optimization procedure, selects an action, and updates the state based on the outcome of that action. Such a process can be represented by the tuple (S, A, πθ , T ), where S denotes the state space and A denotes the set of available actions. The policy and state transition operators are defined as πθ : S → A, T : S × A → S,

(9) (10)

where πθ denotes a policy parameterized by θ and T denotes the state transition operator. The policy parameters θ define the decision-making mechanism used to select actions from the action space A, which corresponds to the set of tools available to the agent. In CFRS settings, these tools may include clustering heuristics, exact algorithms, analysis procedures, or local search operators. Different agentic optimization approaches can therefore be viewed as different instantiations of (S, A, πθ , T ), differing in their state representation, available tools, and decision policy. We present our methodology and how it connects to this formulation in the next section.

3. Methodology The proposed framework is illustrated in Figure 2. The following sections introduce the cluster-tree representation, the associated state-transition model, and the agent decision process used to guide decomposition and refinement decisions. 3.1. Cluster Tree Representation The decomposition is represented by a rooted tree T = (N , E), where each node v ∈ N corresponds to a subproblem as illustrated in Figure 2a. A node is defined by the tuple v = (Nv , Kv ), where Nv ⊆ N denotes the customers assigned to the node and Kv ⊆ K denotes the vehicles assigned to the node. The root node corresponds to the original CVRP instance and is defined as (N, K). Given a node v = (Nv , Kv ), a decomposition operation produces a set of child nodes C(v) = {v1 , . . . , vm } such that Nv =

[

Nu ,

Ni ∩ Nj = ∅

∀i ̸= j.

(11)

u∈C(v)

Vehicle assignments are similarly distributed among the child nodes according to the chosen operator. The set of leaf nodes for a given tree T is denoted by L(T ) =

7

(c) Leaf nodes are passed (b) Decomposition agent per- to every analysis tools, which forming a state transitions by produce reports signaling pos(a) Hierarchically decomposed selecting a leaf node, customer sible issues (e.g., no vehicles in CVRP, where the leaf nodes and vehicle split tools, refining cluster). Reports are combined and passed to the agent. correspond to the clusters. the selected node further.

Figure 2.: LLM-guided decomposition. The planner maintains a hierarchical decomposition state, applies tool-based actions to selected leaves, and uses alerts from the incumbent partitions to guide subsequent decisions. {l1 , . . . , lm }, where each leaf represents a cluster that can be independently solved as a smaller CVRP subproblem. Collectively, the leaf nodes define the final decomposition P(T ) = {(Nl , Kl ) | l ∈ L(T )}.

(12)

The cluster tree provides a hierarchical representation of the incumbent partitions. The following subsection formalizes this hierarchical decomposition as a statetransition process and introduces the transition operators that modify the tree during the iteration. 3.2. State and Transitions in Hierarchical Decomposition The iterative process is modeled as a sequence of state transitions over the cluster tree as illustrated in Figure 2b. Internal nodes represent intermediate partitions, whereas leaf nodes correspond to the active clusters. Therefore, the state at iteration t is (t) defined by the leaf set of the evolving tree, st = L(Tt ) = {li }i , which induces the decomposition P(st ) = {(Nn , Kn ) | n ∈ L(Tt )}. At each iteration of state transitions, an operator Dθt is applied to the state, producing a new state according to st+1 = Dθt (st ). The parameters θt determine the behavior of the operator and correspond to agent-selected actions. Repeated application of decomposition operators generates a sequence of states s0 → s1 → · · · → sT , where the final state sT determines the partition set used by the CFRS framework. State transitions are induced by actions selected from the action space A. Each action identifies a leaf within the cluster tree together with an operation to be applied to that node. Executing the action modifies the tree and consequently produces a new state. The action space consists of three categories of transition operations: • Split: Decomposes one or more leaf nodes into smaller subproblems. • Redo: Reverts a previous operator and applies an alternative strategy. 8

• Stop: Terminates the iterations and returns the current partition set. A partition action applies customer and vehicle decomposition procedures to a leaf node v = (Nv , Kv ). Let θ = (θN , θK , α) denote the decomposition parameters, where θN and θK specify the customer and vehicle clustering tools, respectively, and α controls the split granularity. The partition operator generates a set of child nodes Dθpart (v) that replace v in the leaf set, thereby producing a new state (and new set of partitions). A repartition action revisits a previously expanded node v = (Nv , Kv ) using an ′ , θ ′ , α′ ). The descendants of v are removed, v is alternative parameter set θ′ = (θN K restored as a leaf node, and a new partition operation is applied. This enables the process to revise earlier decisions without reconstructing the entire tree. Finally, a stop action terminates the algorithm and returns the partition set induced by the leaf nodes of the cluster tree. This action may be selected when the incumbent has reached the desired level of granularity, available computational resources have been exhausted, or further partitioning is unlikely to improve the quality of the result. The actions defined above specify how the state may be modified, while the particular clustering procedures are determined by the selected parameters θN and θK . The complete set of operations given as agent tools is provided in Appendix A-C. 3.3. Action Selection and State Description As illustrated in Figure 2c, each decomposition state is first evaluated using a collection of analysis tools Aanalyze . Applied to the leaf nodes of the incumbent, these tools generate reports describing properties such as cluster compactness, demand-capacity balance, and resource utilization. The resulting reports are aggregated into an observation   ot = Φ {a(l(t) ) | l(t) ∈ st , a ∈ Aanalyze } , (13) where Φ denotes the aggregation procedure. The observation ot together with the available transition actions Atrans is provided to the agent, which selects an action and its parameters according to (ât , θ̂t ) = πθ (ot , Atrans ),

(14)

where ât ∈ Atrans denotes the selected action and θ̂t denotes the corresponding parameters. The analysis reports contain global statistics and partition-level alerts that identify potential deficiencies such as oversized partitions, insufficient capacity, or imbalanced vehicle allocation. The complete set of analysis signals is provided in Appendix D. Since these reports are incorporated directly into the agent context, they are compressed and restricted by an analysis limit parameter Amax , which returns only the most relevant observations. The selected action is subsequently validated against the latest partitions. If the action is applicable, the corresponding state transition st+1 = T (st , ât , θ̂t )

(15)

is executed. Otherwise, a warning message wt describing the violation is appended to

9

the agent context, yielding the updated observation o′t = ot ∪ {wt }.

(16)

The agent then performs a new action-selection step using o′t . This process repeats until a stop action is selected, yielding the final decomposition state and corresponding partition set. In the next subsection, we give this loop in a structured manner. We initialize the agent with the system prompt provided in Appendix E along with the initial set of analysis report that gives necessary context to the LLM agent. In the next subsection, we go through the entire pipeline starting from this initializing context to reach to a decomposition plan. 3.4. Adaptive Decomposition Full Pipeline The overall mechanism is summarized in Algorithm 1. Starting from the initial state s0 = {Root}, the framework iteratively generates observations, selects a transition action, and applies the corresponding state transition. The process continues until a stop action is selected, yielding a final state whose leaf nodes define the partition set. Algorithm 1 Agentic Hierarchical Decomposition 1: Initialize cluster tree T

with root node (N, K)

2: Initialize decomposition state s0 = {Root} 3: while stop action not selected do

Generate observation ot using analysis tools Aanalyze 5: Select action and parameters (ât , θ̂t ) = πθ (ot , Atrans ) 6: if (ât , θ̂t ) is valid then 7: Apply transition st+1 = T (st , ât , θ̂t ) 8: else 9: Generate warning wt 10: Update observation ot ← ot ∪ {wt } 11: end if 12: end while 13: Return partition set P(st ) 4:

The cluster action is implemented through a compound tool that applies one customer clustering method and one vehicle distribution method to a selected leaf cluster. In addition to the tools, the action specifies a level that controls the granularity of the resulting child clusters. The procedure is summarized in Algorithm 2. Algorithm 2 Decomposition Tool 1: Read target partition n = (Nn , Kn ) 2: Reject if n is not a leaf node 3: Reject if maximum tree depth reached 4: Compute num. children partitions 5: Apply selected customer split 6: Apply selected vehicle split 7: Return status message as success/fail

10

Table 2.: Our Parameters. Symbol Pmax πθ Tmax Cmax Nmin τ Amax Lmax

Parameter Target number of clusters LLM policy Maximum runtime Maximum agent iterations Minimum cluster size Temperature Analysis limit Maximum tree depth

Choice 25 Qwen2.5 [30] / Qwen3 [39] 300 s 30 2,000 0.9 10 4

The number of child clusters is computed dynamically rather than fixed in advance. Let n denote the number of customers in the selected partition, Nmin the minimum partition size, d the tree depth, and Dmax the maximum tree depth. The framework first estimates the number of routing-ready leaf partitions required by the chosen partition and distributes this estimate across the remaining tree depth to obtain a baseline branching factor. The decomposition level then adjusts this branching factor according to   max(2, b − 1), low,    b, medium, (17) k= bl + 1,m high,      n , finalized, Nmin

where b denotes the baseline branching factor computed from the estimated number of remaining leaf partitions and the remaining tree depth. The resulting value is further constrained to ensure that no child partition violates the minimum partition size requirement. This approach allows the same tool to adapt to partitions of different sizes and depths while remaining consistent with both local partition quality and global decomposition objectives. 3.5. Algorithm Parameters The configurable parameters of the framework are summarized in Table 2. Parameters Pmax , Tmax , and Cmax primarily govern the termination behavior of Algorithm 1, while Nmin and Lmax regulate the granularity of the resulting decomposition by constraining admissible state transitions. The parameter Amax limits the amount of diagnostic information provided to the agent, and πθ together with τ determine the action-selection policy. We evaluate two lightweight open-weight language models, Qwen2.5 and Qwen3, which provide an attractive balance between reasoning capability and computational efficiency, making them suitable candidates for evaluating the proposed agentic decomposition framework. The parameter values reported in Table 2 were selected through preliminary tuning on synthetically generated CVRP instances containing up to 500,000 customers, using customer miss rate and clustering time as the primary selection criteria. Synthetic instances are randomly generated and we separate the tuning set from the evaluation set for unbiased choice of parameters. Details of the synthetic instance generator are 11

provided in experimental setup.

4. Experimental Setup In this section, we describe the experiment setup and present the performance of our method. We first present the comparison models used in our benchmark, followed by the metrics we use to assess the comparison. Finally, we present the results obtained on synthetic and public data instances. 4.1. Comparison Models The evaluated methods span geometric, optimization-based, learning-based, and adaptive approaches. Geometric baselines include RND (Random), SWP (Sweep) [15], GRD (Grid), and QDR (Quadrant), which partition customers according to spatial proximity. Optimization-based methods include BKM (Balanced K-Means), which balances cluster compactness and assigned vehicle capacity, ENT (Entropy), which promotes balanced customer assignments by maximizing partition entropy, CCBC (Constrained Centroid-Based Clusterin) [1] and CC-CVRP (Capacity Constrainted CVRP) [2], which explicitly incorporates vehicle capacity constraints during partition construction. Learning-based methods include GLOP [40], which learns policies from data. Finally, A-DEC denotes the proposed adaptive decomposition framework, which iteratively refines a hierarchical cluster tree through tool-guided decision making. 4.2. Evaluation and Analysis Metrics The objective of the experimental evaluation is twofold. First, we assess whether the proposed procedure enables the construction of high-quality solutions with low customer miss rates. Second, we evaluate its robustness under varying scales and operating conditions representative of industrial environments. To this end, all methods are evaluated using a common downstream procedure. First, the decomposition method generates a set of clusters, which are then solved independently using OR-Tools Guided Local Search (GLS) [14]. Cluster-level routing instances are solved in parallel for up to 300 seconds or until all assigned demand has been served. The resulting partial solutions are subsequently merged into a single solution and provided as an initial solution to a global OR-Tools GLS solver. The global solver is executed for up to 30 minutes, allowing route exchanges and other long-range modifications within cluster boundaries. Performance metrics are reported on the resulting merged solution. The first metric is the decomposition runtime, denoted by Tcluster , which measures the wall-clock time required to generate the resulting partitions. This metric reflects the computational overhead introduced by the clustering stage and serves as an indicator of practical scalability. Customer miss rate is measured on the final routing solution after global refinement. Let di denote the demand of customer i and let ui ∈ {0, 1} indicate whether customer i remains unserved in the final solution. The miss rate is computed as P di ui . (18) M = Pi∈N i∈N di

12

Final distance is measured on the globally refined solution and defined as D=

X X

cij ,

(19)

r∈R (i,j)∈r

where R denotes the set of routes in the final solution and cij denotes the travel cost between locations i and j, computed as the Euclidean distance cij =

q

(xi − xj )2 + (yi − yj )2 .

In the results, we interchangeably use the terms distance and cost to refer to the metric defined in (19). From an operational perspective, these metrics capture complementary aspects of routing quality. Decomposition runtime reflects the computational overhead introduced by the decision-support process, while customer miss rate and distance quantify the quality of the resulting operational plan. Together, they measure the trade-off between responsiveness and solution quality that is critical in logistics planning involving hundreds of thousands of customers. We focus exclusively on downstream metrics because the objective of a decomposition strategy is not to optimize partition structure in isolation, but to support effective operational decision making through high-quality plans. In practical logistics systems, decomposition serves as an intermediate decision process whose value is ultimately determined by its impact on customer service levels, routing efficiency, and computational responsiveness. If a benchmark method directly produces routes without exposing intermediate partitions (such as GLOP), partition-specific metrics are reported as −. Methods that fail to produce a valid solution within the 30-minute runtime limit or available memory budget are reported as N/A. All experiments were performed on a Mac Mini M4 with 36 GB of unified memory. In the next subsection, we present our performance on publicly available data instances. 4.3. CVRPLIB: AGS Benchmark for Large-Scale Instances The AGS benchmark set contains some of the largest publicly available CVRP instances, with the sizes reaching approximately 30,000 customers, providing an important intermediate scale between traditional benchmarks and the industrial-scale CVRPs considered in this study [3]. To evaluate decomposition performance beyond the original AGS benchmark while preserving realistic spatial and demand properties, we construct a collection of benchmark-derived instances by concatenating multiple AGS instances. For a batch size b, the generator combines the b largest instances into a single instance. Two configurations are considered: Grid, which preserves the spatial separation of the original instances to create large multi-region samples, and Unified Depot, which merges all components into a single case sharing a common depot. This procedure substantially increases the scale while retaining the structural characteristics of the underlying benchmark data. When interpreting the results, miss rate should be viewed as the primary performance metric. In practical applications, failing to serve customer demand is typically far more consequential than increases in travel distance. Moreover, cost and miss rate 13

are not independent objectives: omitting customers generally reduces the number of required visits and therefore lowers the total travel distance. Hence, methods exhibiting substantially higher miss rates may appear to achieve favorable routing costs even though the resulting solutions would require additional resources or delivery effort to reach comparable service levels. Tables 3, 4, and 5 summarize the results on benchmark-derived AGS instances constructed using concatenation batch sizes of 2, 6, and 10, respectively. Table 3.: Results on 2-instance concatenated AGS benchmark-derived instances. Created from Flanders1, Flanders2 with total 50,000 customers and 250 vehicles. (a) Grid + Original Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 0.275 53.672 6.137 0.020 0.030 0.018 – 116.779

First Sol. (s) 35.191 183.296 35.539 34.967 35.601 35.097 – 32.192

Missed (%) 3.980 38.430 4.230 4.270 0.000 4.530 0.000 0.000

Final Dist. 722,038 454,754 685,687 716,555 1,922,235 714,253 721,183 1,601,788

(b) Grid + Scaled Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 0.274 52.830 6.305 0.020 0.031 0.018 – 316.000

First Sol. (s) 35.153 187.753 35.316 35.075 35.213 35.372 – 32.240

Missed (%) 3.980 38.520 4.140 4.060 0.020 4.310 0.000 11.190

Final Dist. 728,020 443,935 706,542 715,728 1,902,855 720,491 708,035 726,016

(c) Grid + Unified Depot Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 0.306 42.164 6.448 0.020 0.030 0.019 – 319.175

First Sol. (s) 62.785 193.401 35.601 35.028 35.302 35.403 – 32.209

Missed (%) 0.370 36.190 0.350 2.110 0.370 1.110 0.000 0.000

Final Dist. 1,113,979 445,526 879,617 456,264 1,117,998 589,032 631,661 860,906

(d) Overlapping Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 0.305 58.705 6.099 0.020 0.030 0.018 – 316.004

First Sol. (s) 35.450 172.150 35.407 35.165 35.540 35.547 – 32.235

Missed (%) 0.420 38.790 0.940 0.350 0.000 0.560 2.250 0.000

Final Dist. 432,496 192,314 374,749 385,972 1,027,172 411,024 2,395,735 494,122

Among the optimization-based methods, CCBC achieves the lowest distances but at the cost of substantially higher miss rates, often exceeding 25% of total demand. Since unserved customers directly reduce the amount of routing required, these distances are not directly comparable to methods achieving near-complete demand coverage. In 14

contrast, BKM, ENT, and CC-CVRP maintain substantially lower miss rates, with CC-CVRP generally providing the strongest balance between service quality and cost within this class. The geometric methods exhibit mixed behavior. Grid-based clustering frequently delivers near-zero miss rates because the resulting clusters remain geographically coherent and easy to route independently. However, this comes at the expense of extremely large distances, particularly as the scale increases. Sweep-based clustering generally produces lower costs than GRD while maintaining comparable miss rates. The learning-based GLOP baseline attains favorable performance on the 50,000customer instances but fails to produce valid solutions for the larger 102,000and 122,000-customer benchmarks. This highlights the difficulty of scaling existing learning-based routing approaches to the size levels considered in this study. The proposed A-DEC model exhibits a different scaling trend. While its performance on the two-instance benchmarks is broadly comparable to existing methods, its advantage becomes increasingly apparent as the problem size grows. For the six-instance and ten-instance benchmarks, A-DEC achieves among the lowest distances while maintaining near-zero miss rates, often outperforming both geometric and optimization-based alternatives. In the next section, we present the robustness analysis we test our algorithm on various dimensions including customer count, vehicle count, different depot and demand patterns. 4.4. Large-Scale Robustness Analysis While the AGS benchmark set contains some of the largest standardized CVRP instances, reaching approximately 30,000 customers, the primary objective of this work is to evaluate decomposition performance at substantially larger scales. To this end, we generate synthetic CVRP instances containing up to several hundred thousand customers while systematically varying key configuration dimensions. Each instance name encodes the generation parameters used to create the corresponding dataset, enabling controlled ablation studies over individual dimensions. The generation parameters are summarized below: • n (Customer Count): Total number of customers. • k (Vehicle Count): Total number of available vehicles. • D (Demand Pattern): Distribution of customer demands. • M (Depot Configuration): Number and placement of depot locations. In addition to the baseline decomposition methods, we evaluate two variants of our approach using the best-performing language models identified during preliminary experiments, denoted Qwen2.5 [30] and Qwen3 [39]. In this section, we pick few best-performing models from each type of clustering paradigm to compare. 4.4.1. Customer Count Variation The customer count variation evaluates the scalability of methods as the number of customers increases while all remaining generation parameters are held fixed. Figure 3 provides a visual comparison of the principal downstream metrics. Figure 3 summarizes the effect of increasing customer count on decomposition performance. Overall, our methodology remains competitive as problem size increases, 15

(a) Clustering time

(b) Initial miss rate

(c) Final miss rate

(d) Final routing distance

Figure 3.: Customer count variation results. Each plot shows the evolution of one performance metric as the number of customers increases while all remaining generation parameters are held fixed. with the Qwen3 variant consistently achieving the lowest distance while maintaining a zero final miss rate throughout all evaluated customer counts. In contrast, CCBC attains substantially lower distances at the expense of high customer miss rates, while conventional geometric and optimization-based methods generally preserve low miss rates but incur considerably higher distances as the scale grows. These results reveal that the proposed adaptive decomposition strategy scales effectively from benchmarkscale instances to industrial-scale routing containing up to 500,000 customers. 4.4.2. Vehicle Count Variation The vehicle count variation evaluates the sensitivity of methods to fleet size by varying the number of available vehicles while keeping all remaining generation parameters fixed. The resulting performance across the evaluated vehicle counts is reported in Figure 4. Figure 4 exhibits trends consistent with the customer count analysis. Under all the evaluated fleet sizes, the proposed adaptive decomposition framework maintains competitive operational performance, with the Qwen3 variant achieving the lowest distance while maintaining low final miss rates. In particular, for 1,000 vehicles, Qwen3 fully recovers all initially missed demand and reduces distance by approximately 40% relative to the strongest non-adaptive decomposition baselines. This suggests that the decomposition methodology adapts effectively to varying levels of available routing resources.

16

(a) Clustering time

(b) Initial miss rate

(c) Final miss rate

(d) Final routing distance

Figure 4.: Vehicle count variation results. Each plot illustrates the effect of varying the number of available vehicles on one downstream performance metric while keeping all remaining generation parameters fixed. 4.4.3. Demand Pattern Variation In this subsection, we evaluate the demand pattern variation robustness of decomposition methods to different customer demand distributions. The resulting performance over the evaluated demand patterns is reported in Figure 5. The evaluated demand patterns introduce progressively more challenging demand structures. Unitary and Uniform distributions provide relatively homogeneous demand levels, while Quadrant introduces significant spatial variation in demand intensity. Hotspots and Urban generate localized regions of elevated demand, creating demand-capacity imbalances that may be difficult to capture through purely geometric strategies. Figure 5 illustrates that our model remains robust under diverse customer demand distributions. Similar to the customer and vehicle count analyses, the Qwen3 variant consistently producing the lowest routing distance while maintaining a zero final miss rate for all evaluated demand patterns. These results suggest that the proposed adaptive decomposition strategy effectively accommodates both uniform and highly heterogeneous demand patterns encountered in very large problems. 4.4.4. Depot Configuration Variation The depot-configuration study evaluates robustness under different depot placements while keeping the customer distribution, demand pattern, fleet size, and remaining generation parameters fixed. The Eccentric configuration places the depot near the boundary of the service region, whereas Random selects the depot location uniformly at random. The resulting performance is reported in Figure 6. 17

Figure 6 exhibits trends consistent with the previous robustness analyses. In both depot configurations, the Qwen3 variant exhibits the lowest routing distance while maintaining a zero final miss rate. In contrast, CCBC continues to obtain lower raw distances at the expense of substantially higher missed demand. Overall, the proposed adaptive decomposition process yields robust performance under varying depot configurations while preserving high service levels. Overall, the results suggest that decomposition quality is strongly influenced by the statistical aspects of the instance, making the selection of an appropriate partitioning strategy a critical component of high-volume systems. Fixed approaches optimize a predetermined objective or follow a predefined policy, whereas the proposed approach continuously adapts its decisions according to the evolving state. This allows the framework to balance competing objectives without committing to a single fixed strategy, reliably exhibiting robust routing performance across diverse problem scales and operating conditions.

5. Conclusion This paper presented an adaptive cluster-first route-second algorithm for large-scale CVRP. By representing decomposition as a sequence of decisions over a hierarchical cluster tree, our approach enables iterative selection of clustering and refinement actions according to the patterns of the evolving routing state, rather than relying on a fixed and proxy objective or predetermined policy. Experimental results on synthetic and benchmark-derived instances demonstrate strong performance on benchmark-scale data while exhibiting strong scalability to substantially larger instances. Throughout diverse routing environments, the method maintains a favorable balance between customer service levels and cost, demonstrating the potential of adaptive, LLM-guided decision making as a practical approach for scalable decomposition and industrial logistics planning.

Data Availability Statement The data supporting the findings of this study are available from the corresponding author, O.K., upon reasonable request.

Author Contributions Statement Oguzhan Karaahmetoglu: Conceptualization, Methodology, Software, Validation, Formal analysis, Investigation, Data curation, Visualization, Writing – original draft. Hyong Kim: Supervision, Conceptualization, Methodology, Validation, Writing – review & editing, Project administration.

Disclosure Statement The authors report there are no competing interests to declare.

18

References [1] Abdelhakim Abdellaoui, Loubna Benabbou, and Issmail El Hallaoui. Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering. arXiv preprint arXiv:2403.14013, 2024. [2] Francesco Alesiani, Gulcin Ermis, and Konstantinos Gkiotsalitis. Constrained clustering for the capacitated vehicle routing problem (cc-cvrp). Applied artificial intelligence, 36(1):1995658, 2022. [3] Florian Arnold, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-scale routing problems. Computers & operations research, 107:32–42, 2019. [4] Tolga Bektaş and Gilbert Laporte. The pollution-routing problem. Transportation Research Part B, 2011. [5] Russell Bent and Pascal Van Hentenryck. Spatial, temporal, and hybrid decompositions for large-scale vehicle routing with time windows. In CPAIOR, 2008. [6] Julien Bramel and David Simchi-Levi. The logic of logistics: theory, algorithms, and applications for logistics management. Springer, 1997. [7] Herminia I Calvete, Carmen Galé, and José A Iranzo. Balancing the cardinality of clusters with a distance constraint: a fast algorithm. Annals of Operations Research, 351(1):629–651, 2025. [8] T. C. Edwin Cheng, Sachin S. Kamble, Amine Belhadi, Nelson Oly Ndubisi, Kee hung Lai, and Manoj Govind Kharat. Linkages between big data analytics, circular economy, sustainable supply chain flexibility, and sustainable performance in manufacturing firms. International Journal of Production Research, 60(22):6908– 6922, 2022. [9] Samuel JK Chin and Maximilian Schiffer. Neural cluster first, route second: One-shot capacitated vehicle routing via differentiable optimal transport. arXiv preprint arXiv:2605.09301, 2026. [10] Nicos Christofides and Samuel Eilon. An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3):309–318, 1969. [11] Juan David Cortes and Yoshinori Suzuki. Last-mile delivery efficiency: en route transloading in the parcel delivery industry. International Journal of Production Research, 60(9):2983–3000, 2022. [12] Francesca Da Ros, Michael Soprano, Luca Di Gaspero, and Kevin Roitero. Large language models for combinatorial optimization: A systematic review. ACM Computing Surveys, 58(11):1–53, 2026. [13] Yao et al. React: Synergizing reasoning and acting in language models. 2023. [14] Vincent Furnon and Laurent Perron. Or-tools routing library. [15] Billy E Gillett and Leland R Miller. A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22(2):340–349, 1974. [16] Valeria Jannelli, Stefan Schoepf, Matthias Bickel, Torbjørn Netland, and Alexandra Brintrup. Agentic llms in the supply chain: towards autonomous multi-agent consensus-seeking. International Journal of Production Research, pages 1–31, 2026. [17] LI Jingjing, Yaohuiqiong Fang, and Na Tang. A cluster-based optimization framework for vehicle routing problem with workload balance. Computers & Industrial Engineering, 169:108221, 2022. [18] Christoph Kerscher and Stefan Minner. Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows. arXiv preprint arXiv:2402.00041, 2024. [19] Rahma Lahyani, Anne-Lise Gouguenheim, and Leandro C Coelho. A hybrid adap19

tive large neighbourhood search for multi-depot open vehicle routing problems. International Journal of Production Research, 57(22):6963–6976, 2019. [20] Gilbert Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408– 416, 2009. [21] Jan Karel Lenstra and Alexander Hendrik Georg Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227, 1981. [22] Bingjie Li, Guohua Wu, Yongming He, Mingfeng Fan, and Witold Pedrycz. An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 9(7):1115–1138, 2022. [23] Qingyang Li, Lele Zhang, and Vicky Mak-Hau. An llm-powered milp modelling engine for workforce scheduling guided by expert knowledge. International Journal of Production Research, pages 1–21, 2026. [24] Rodrigo Linfati, Fernando Yáñez-Concha, and John Willmer Escobar. Mathematical models for the vehicle routing problem by considering balancing load and customer compactness. Sustainability, 14(19):12937, 2022. [25] Stuart Lloyd. Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129–137, 1982. [26] Batoul Mahvash, Anjali Awasthi, and Satyaveer Chauhan. A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints. International Journal of Production Research, 55(6):1730– 1747, 2017. [27] Lakshmanan Meyyappan, Can Saygin, and Cihan H Dagli. Real-time routing in flexible flow shops: a self-adaptive swarm-based control model. International journal of production research, 45(21):5157–5172, 2007. [28] Erfaneh Nikzad and Mahdi Bashiri. A two-stage stochastic programming model for collaborative asset protection routing problem enhanced with machine learning: a learning-based matheuristic algorithm. International Journal of Production Research, 61(1):81–113, 2023. [29] Thananut Phiboonbanakit, Teerayut Horanont, Thepchai Supnithi, and Van-Nam Huynh. Knowledge-based learning for solving vehicle routing problem. In Proceedings of the 2018 ACM International Joint Conference and 2018 International Symposium on Pervasive and Ubiquitous Computing and Wearable Computers, pages 1103–1111, 2018. [30] Qwen, :, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025. [31] Alberto Santini, Michael Schneider, Thibaut Vidal, and Daniele Vigo. Decomposition strategies for vehicle routing heuristics. INFORMS Journal on Computing, 35(3):543–559, 2023. [32] Raghav Thind, Youran Sun, Ling Liang, and Haizhao Yang. Optimai: Optimization from natural language using llm-powered ai agents. arXiv preprint arXiv:2504.16918, 2025. [33] Paolo Toth and Daniele Vigo. Vehicle Routing: Problems, Methods, and Applications. SIAM, 2014. 20

[34] Wei Tu, Qingquan Li, Qiuping Li, Jiasong Zhu, Baoding Zhou, and Biyu Chen. A spatial parallel heuristic approach for solving very large-scale vehicle routing problems. Transactions in GIS, 21(6):1130–1147, 2017. [35] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845–858, 2017. [36] Thibaut Vidal. Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022. [37] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential of large language model based agents: A survey. Science China Information Sciences, 68(2):121101, 2025. [38] Xianchao Xiu, Jianhao Li, Jun Fan, and Wanquan Liu. Large language models for operations research: A comprehensive survey. arXiv preprint arXiv:2605.20849, 2026. [39] An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang, Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang, Wenbiao Yin, Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yuqiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report, 2025. [40] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pages 20284–20292, 2024.

Appendix A. Decomposition Agent: Splitting Tools The following tool is used to split a certain leaf in the tree. [ MUTATE ] Split a partition into child partitions using one customer split method and one vehicle split method . Customer Methods : - uniform : good for spatially uniform distribution of customers - kmeans : good for clustered / mixture - like regions - sweep : good for uniform / radial regions - cap_k : good for balancing demand across child clusters - largest_axis : good for clean binary geometric cuts Vehicle Methods : - r ou nd _r ob in _d em an d : fastest feasibility - oriented balancing - equal_count : simple equal vehicle split - min_cost_quota : more geometry - aware balancing

21

- rebalance : balance vehicles based on capacity / demand gap . Levels : - low : coarse local refinement - medium : moderate repartition - high : aggressive repartition - finalized : estimate the number of child clusters from min split size , aiming for routing - ready leaves

Appendix B. Decomposition Agent: Redoing Tools The following tool is used to redo a partition from the parent level. [MUTATE] Rebuild an existing subtree under the same parent using a different split strategy. Direction: - merge -> halve the current number of leaf children under this parent - split -> double the current number of leaf children under this parent This is useful when a previous split was too coarse or too fragmented. Guard: - Only parents who

Appendix C. Decomposition Agent: Stop Tool The following tool is used to signal the end of decomposition. [ STOP ] Stop the clustering process . Use when the partition tree looks stable enough for routing and further splits are not worthwhile .

Appendix D. Decomposition Agent: Analysis Tools The following alerts summarize structural issues in the current partition state and guide action selection. [ ALERT : max_clusters ] At / over max partitions . Do NOT split demand nodes further . Prefer VEHICLE rebalance or REPAIR ( merge ) . [ ALERT : split_limit / split_budget ] Demand node split limit or budget reached / low . Do NOT call demand node split tools ; prefer VEHICLE rebalance or MERGE .

22

[ ALERT : size_imbalance ] Partition size imbalance ( max / min ratio too high ) . Prefer splitting the largest partition ( not necessarily index 0) . [ ALERT : tiny_parts ] Very small partitions detected . Avoid splitting ; consider merging or moving vehicles instead . [ ALERT : repeat_split ] Same partition split repeatedly . Choose a different target partition . [ ALERT : pressure ] Capacity imbalance . Under - cap ( gap > 0) : move / add vehicles . Over - cap ( gap < 0) : donate vehicles or merge . [ ALERT : vehic le_imb alance ] Vehicle count imbalance across partitions . Prefer VEHICLE rebalance instead of further splitting . [ ALERT : merge ] Partitions likely to route poorly ( tiny , no vehicles , or vehicle - starved ) . Prefer merging with nearby compatible partitions . [ CONVERGENCE ] Checks on max size , size ratio , and capacity gap . If satisfied : no major issues , prefer repair - only actions . Otherwise : indicates required corrective action ( split or rebalance ) .

Appendix E. Decomposition Agent: System Prompt This section provides the system prompt used for the decomposition stage described in Section III. The prompt defines the decision interface, available actions, and constraints under which the language model operates. The model is not allowed to directly execute actions, but instead proposes structured suggestions that are validated and applied by the system. You are a hierarchical clustering chooser for a routing problem . Your job is to repeatedly choose EXACTLY ONE mutate tool call . You will receive a text analysis of the current active leaves and prioritized alerts . Main objective : - Build a good partition tree quickly for downstream routing . - Prefer as few calls as possible . - Focus first on leaves highlighted by the alerts , especially the largest and most problematic ones .

23

- Prefer broad progress over getting stuck refining one branch too deeply . - Do not exceed tree depth 4. Tree logic : - The partitioning is hierarchical . Earlier decisions shape all later descendants . - Shallow leaves represent large regions and are usually better places for impactful decisions . - Deeper leaves are local refinements and should be used only when the parent region already looks reasonable . - If many leaves are still too large , prefer operations that create strong breadth without pushing too deep . Customer split method guidance : - Use largest_axis when the region suggests a clean binary spatial cut . - Use kmeans for clustered / multi - center regions . - Use sweep for broad radial / angular / coverage - style regions . - Use cap_k when balancing demand across child clusters matters . - Use uniform for broad , spatially even regions . Vehicle split method guidance : - Use r ou nd _r ob in _d em an d when speed and fast feasibility matter most . - Use equal_count when a very simple even vehicle split is enough . - Use min_cost_quota when geometry - aware vehicle assignment is likely to help route quality . - Use rebalance when customer groups look uneven in demand / capacity and vehicle capacity should track group demand more closely . Redo guidance : - Use redo_partition when a whole subtree was split with the wrong customer method or wrong aggressiveness . - Prefer redo_partition on the parent over repeatedly mutating several child leaves one by one . - Use redo to correct tree shape , not as a default action . Alert priorities : - Treat BIG alerts as highest priority when the listed leaves are still far above routing - friendly size . - Treat STARVING and VEHICLE LIGHT alerts as signals that vehicle split choice matters more . - When alerts are truncated , assume the shown leaves are the most important ones . - Prefer acting on the largest shown leaves first unless a strong recovery signal suggests otherwise . - If a deep leaf is problematic but its parent subtree looks systematically wrong , act on the parent instead . Depth guidance : - Root and shallow levels should usually use broader structural actions . - Depth 4 is the maximum allowed depth .

24

- Do not choose actions that would push a branch beyond depth 4. - Near the depth limit , prefer better method choice or redo at the parent instead of deeper refinement . Important : - Do not ask questions . - Do not explain . - Return exactly ONE tool call only .

25

Table 4.: Results on 6-instance concatenated AGS benchmark-derived instances. Created from Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1, with total 102,000 customers and 655 vehicles. (a) Grid + Original Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 1.824 153.129 49.815 0.096 0.168 0.083 – 186.483

First Sol. (s) 305.839 1,068.166 48.092 46.028 42.383 45.880 – 45.905

Missed (%) 0.370 28.400 0.370 0.350 0.060 0.290 N/A 0.000

Final Dist. 26,721,457 6,952,275 23,834,181 30,853,583 134,008,272 32,994,513 N/A 16,856,072

(b) Grid + Scaled Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 1.839 153.172 51.114 0.094 0.169 0.084 – 207.984

First Sol. (s) 306.428 1,061.107 45.616 48.711 43.706 45.905 – 45.776

Missed (%) 0.280 28.430 0.300 0.260 0.060 0.230 N/A 0.040

Final Dist. 27,224,341 6,772,262 24,554,350 29,982,591 133,716,715 33,715,569 N/A 16,572,978

(c) Grid + Unified Depot Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 8.755 151.896 45.569 0.091 0.866 0.083 – 187.599

First Sol. (s) 303.392 1,093.719 43.194 42.753 91.552 43.475 – 44.055

Missed (%) 0.000 14.480 0.010 0.270 0.000 0.080 N/A 0.480

Final Dist. 31,290,192 6,999,298 24,099,312 23,725,871 94,869,682 30,000,951 N/A 15,681,319

(d) Overlapping Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 15.100 150.762 43.539 0.092 0.876 0.085 – 226.630

26

First Sol. (s) 120.460 1,046.884 45.575 43.938 112.935 46.338 – 44.861

Missed (%) 0.100 28.180 0.080 0.020 0.050 0.030 N/A 0.000

Final Dist. 11,314,913 1,668,047 9,750,538 10,867,047 34,320,349 15,681,932 N/A 8,284,592

Table 5.: Results on 10-instance concatenated AGS benchmark-derived instances. Created from instances Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1, Antwerp2, Antwerp1, Leuven2, Leuven1 with total customers 122,000 and vehicles 960. (a) Grid + Original Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 16.900 164.035 114.813 0.181 3.947 0.163 – 154.321

First Sol. (s) 346.626 2199.457 56.844 54.748 169.017 55.966 – 87.369

Missed (%) 3.220 31.790 3.210 3.220 0.020 3.190 N/A 0.000

Final Dist. 323,815,921 241,436,895 313,229,684 362,590,300 4,883,751,464 958,394,465 N/A 356,963,206

(b) Grid + Scaled Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 4.732 152.548 125.363 0.196 0.379 0.172 – 219.875

First Sol. (s) 303.940 2276.662 80.223 80.353 58.736 58.594 – 65.293

Missed (%) 2.380 31.630 2.540 2.210 0.020 2.310 N/A 0.000

Final Dist. 549,358,450 218,822,415 564,676,075 589,525,949 4,369,090,450 1,283,021,462 N/A 525,301,597

(c) Grid + Unified Depot Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 4.838 152.961 113.079 0.189 0.382 0.168 – 217.488

First Sol. (s) 82.656 2138.380 57.250 55.703 56.634 58.153 – 72.279

Missed (%) 1.640 7.640 1.750 1.110 0.000 1.310 N/A 0.000

Final Dist. 781,696,307 225,650,614 569,001,356 574,290,940 3,531,830,252 888,401,316 N/A 387,027,477

(d) Overlapping Method BKM CCBC CC-CVRP ENT GRD SWP GLOP A-DEC

Time (s) 5.404 155.899 116.655 0.182 0.386 0.169 – 233.900

27

First Sol. (s) 58.432 2256.370 55.987 60.752 57.370 58.108 – 58.526

Missed (%) 0.600 31.600 0.690 0.550 0.000 0.450 N/A 0.000

Final Dist. 132,992,549 18,601,621 113,854,206 134,914,301 472,584,108 234,799,506 N/A 83,125,139

(a) Clustering time

(b) Initial miss rate

(c) Final miss rate

(d) Final routing distance

Figure 5.: Demand pattern variation results. Each plot compares the performance of the evaluated decomposition methods across six demand-generation patterns while keeping all remaining generation parameters fixed.

28

(a) Clustering time

(b) Initial miss rate

(c) Final miss rate

(d) Final routing distance

Figure 6.: Depot configuration variation results. Each plot compares the effect of eccentric and random depot placement on one downstream performance metric while keeping all remaining generation parameters fixed.

29