Robust Feasible Route Construction through Collaborative Partition Optimization

# 1 Introduction
Source: [https://arxiv.org/html/2607.03694](https://arxiv.org/html/2607.03694)
\\OneAndAHalfSpacedXII\\EquationsNumberedThrough\\TheoremsNumberedThrough\\ECRepeatTheorems\\MANUSCRIPTNO

\\RUNAUTHOR

Karaahmetoglu and Kim

\\RUNTITLE

Collaborative Partition Optimization

\\TITLE

Robust Feasible Route Construction through Collaborative Partition Optimization

\\ARTICLEAUTHORS\\AUTHOR

Oguzhan Karaahmetoglu\\AFFDepartment of Electrical and Computer Engineering, Carnegie Mellon University,\\EMAILokaraahm@cmu\.edu

\\AUTHOR

Hyong Kim\\AFFDepartment of Electrical and Computer Engineering, Carnegie Mellon University,\\EMAILkim@ece\.cmu\.edu

\\ABSTRACT

Large\-scale Capacitated Vehicle Routing Problems \(CVRPs\) are commonly solved by partitioning customers into smaller routing problems that can be optimized independently\. While this substantially reduces computational complexity, independently constructed routing solutions may leave some customer demand unserved even when sufficient resources exist elsewhere in the fleet\. We present Collaborative Routing Constructors \(CoRC\), a routing framework that enables independently solved subproblems to exchange customers and vehicles during optimization rather than relying solely on a fixed partition or a subsequent global re\-optimization stage\. Computational experiments on AGS benchmark instances and synthetic instances containing up to 200,000 customers compare CoRC against independent routing, post\-routing global re\-optimization, and state\-of\-the\-art, end\-to\-end routing frameworks\. Across all evaluated partitioning strategies, CoRC consistently constructs feasible routing solutions where competing partition\-based methods do not\. Furthermore, it remains effective on problem instances for which the evaluated end\-to\-end routing frameworks did not produce solutions under the same computational budget\. These results demonstrate that collaboration between routing subproblems provides a robust and scalable approach for feasible large\-scale route construction\.

\\KEYWORDS

Vehicle routing, Capacitated vehicle routing problem, Large\-scale optimization, Optimization

We consider the Capacitated Vehicle Routing Problem \(CVRP\) with both homogeneous\(Dantzig and Ramser[1959](https://arxiv.org/html/2607.03694#bib.bib53)\)and heterogeneous vehicle fleets\(Goldenet al\.[1984](https://arxiv.org/html/2607.03694#bib.bib54), Toth and Vigo[2014](https://arxiv.org/html/2607.03694#bib.bib1)\)\. Given a set of customers with known demands and a fleet of capacitated vehicles, the objective is to build sequence of customer visits that serve every customer while minimizing the total routing cost without violating vehicle\-capacity constraints\. The CVRP is one of the fundamental optimization problems in transportation and logistics, with applications including freight distribution\(Crainic and Laporte[1997](https://arxiv.org/html/2607.03694#bib.bib50)\), parcel and last\-mile delivery\(Boysenet al\.[2020](https://arxiv.org/html/2607.03694#bib.bib51)\), humanitarian logistics\(Campbellet al\.[2008](https://arxiv.org/html/2607.03694#bib.bib52)\), and urban service operations such as waste collection and street maintenance\(Yamínet al\.[2024](https://arxiv.org/html/2607.03694#bib.bib47), Anily and Federgruen[1993](https://arxiv.org/html/2607.03694#bib.bib49)\)\.

The CVRP is NP\-hard\(Lenstra and Rinnooy Kan[1981](https://arxiv.org/html/2607.03694#bib.bib8)\)\. Consequently, the literature has developed a broad range of exact algorithms, heuristics, metaheuristics, and decomposition techniques for obtaining high\-quality routing solutions\(Gillett and Miller[1974](https://arxiv.org/html/2607.03694#bib.bib14), Clarke and Wright[1964](https://arxiv.org/html/2607.03694#bib.bib59), Pisinger and Ropke[2018](https://arxiv.org/html/2607.03694#bib.bib58)\)\. Among these, decomposition\-based approaches have become an important component of modern vehicle\-routing heuristics, particularly for large routing instances\(Santiniet al\.[2023](https://arxiv.org/html/2607.03694#bib.bib17)\)\.

One prominent decomposition paradigm is the cluster\-first route\-second \(CFRS\) framework\(Gillett and Miller[1974](https://arxiv.org/html/2607.03694#bib.bib14), Jingjinget al\.[2022](https://arxiv.org/html/2607.03694#bib.bib23)\)\. In this framework, the original routing instance is partitioned into multiple routing subproblems, where each subproblem consists of a subset of customers together with an assigned subset of vehicles\. Each subproblem therefore defines a smaller CVRP that can subsequently be routed independently\. Thus, a routing algorithm is applied to each subproblem to construct local vehicle routes\(Kerscher and Minner[2024](https://arxiv.org/html/2607.03694#bib.bib32), Pisinger and Ropke[2018](https://arxiv.org/html/2607.03694#bib.bib58)\)\. Finally, the routes obtained from all subproblems are then merged to produce a solution for the original large\-scale instance\. This separation between partitioning and routing naturally raises the question of how routing should be performed after the decomposition has been obtained\. To this end, we discuss the proposed methods for this paradigm in the next subsection\.

### 1\.1Prior Art

Early CFRS methods focused primarily on geometric partitioning\. Representative examples include the sweep algorithm\(Gillett and Miller[1974](https://arxiv.org/html/2607.03694#bib.bib14)\)and centroid\-based clustering approaches\(Abdellaouiet al\.[2024](https://arxiv.org/html/2607.03694#bib.bib20)\), which partition customers according to their spatial locations before building routes independently within each partition\. Numerous subsequent methods have continued to build upon geometric partitioning principles while proposing alternative clustering procedures\(Cakiret al\.[2015](https://arxiv.org/html/2607.03694#bib.bib55), Gaonet al\.[2025](https://arxiv.org/html/2607.03694#bib.bib57)\)\.

Subsequent work incorporated additional operational information into the partitioning stage\. Rather than relying exclusively on customer locations, these methods also consider quantities such as customer demand, vehicle capacities, or routing\-related workload measures when constructing partitions\(Alesianiet al\.[2022](https://arxiv.org/html/2607.03694#bib.bib10), Linfatiet al\.[2022](https://arxiv.org/html/2607.03694#bib.bib24), Jingjinget al\.[2022](https://arxiv.org/html/2607.03694#bib.bib23)\)\. More recently, learning\-based approaches have used optimization feedback to guide decomposition decisions through reinforcement learning, neural combinatorial optimization, and large language models\(Liet al\.[2022](https://arxiv.org/html/2607.03694#bib.bib11), Chin and Schiffer[2026](https://arxiv.org/html/2607.03694#bib.bib25), Da Roset al\.[2026](https://arxiv.org/html/2607.03694#bib.bib27), Xiuet al\.[2026](https://arxiv.org/html/2607.03694#bib.bib28), Thindet al\.[2025](https://arxiv.org/html/2607.03694#bib.bib29)\)\. These modern approaches extend the former by exploiting the patterns collected in the historical data by estimating a policy via empirical risk minimization\(Vapnik[1991](https://arxiv.org/html/2607.03694#bib.bib60)\)\.

After the decomposition has been constructed, the most common routing strategy is to solve each routing subproblem independently before combining the resulting routes into a complete solution\(Gillett and Miller[1974](https://arxiv.org/html/2607.03694#bib.bib14), Battarraet al\.[2014](https://arxiv.org/html/2607.03694#bib.bib43)\)\. Under this strategy, each cluster is processed via a routing solver using only the customers and vehicles assigned to its own subproblem\.

Another line of studies perform an additional optimization stage after the independently produced routes have been merged\(Kerscher and Minner[2024](https://arxiv.org/html/2607.03694#bib.bib32)\)\. These approaches apply global improvement procedures, such as adaptive large neighborhood search\(Ropke and Pisinger[2006](https://arxiv.org/html/2607.03694#bib.bib62)\)or decompose\-route\-improve strategies, to refine the combined routing solution\. By optimizing the merged routing plan together with the combined customer and vehicle assignments, these methods provide an additional opportunity to improve the solution obtained from independent route construction\. This aims to reduce routing cost or incorporate customers that remained unserved after the independent routing stage\.

Existing routing paradigms either preserve the initial decomposition throughout route construction or introduce coordination only through a subsequent global re\-optimization stage\. However, route construction itself generates optimization information that is unavailable during the initial decomposition, including unserved demand, unused vehicles, and remaining vehicle capacity\. These quantities characterize the current routing state of each subproblem and may indicate opportunities to revise customer and vehicle assignments before the routing process is complete\.

Motivated by this observation, we investigate an alternative organization of the routing stage\. Rather than restricting coordination to the initial decomposition or postponing it until a subsequent global optimization stage, we introduce an intermediate collaboration stage during route construction\. In this scheme, routing subproblems exchange summaries of their local routing outcomes, enabling customer transfers, vehicle transfers, and partition merges before the final solution is assembled\. Because the collaboration mechanism operates on an existing initial decomposition, it is complementary to geometric, operational, and learning\-based partitioning methods\.

## 2Problem Definition

Our method builds upon the classical CVRP and its decomposition under a cluster\-first route\-second framework\. Accordingly, we first formulate the underlying routing problem, then define the corresponding decomposition, and finally introduce a dynamic extension that allows routing subproblems to interact during routing\.

![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/coorp.drawio.png)\(a\)Capacitated Vehicle Routing Problem formulation\.
![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/coorp-cfrs.drawio.png)\(b\)Static Cluster\-First Route\-Second \(CFRS\) formulation\.
![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/coorp-cfrs_dynamic.drawio.png)\(c\)Evolving CFRS formulation with incumbent solutions\.

Figure 1:Mathematical progression of the presented formulation\. \(a\) CVRP formulation defining routes and routing solutions\. \(b\) Conventional CFRS formulation, where a fixed decomposition𝒫\\mathcal\{P\}induces independent routing subproblems whose incumbent solutions𝒮\\mathcal\{S\}are combined into a global solution\. \(c\) Evolving CFRS formulation, where the decomposition and incumbent solutions evolve over optimization steps through redistribution operations while preserving unaffected incumbent routes\.### 2\.1Capacitated Vehicle Routing with Unsplittable Demands

In this section, we introduce the formulation and the notation used throughout the paper along with the CVRP objective and constraints\. A simple case is illustrated in Figure[1\(a\)](https://arxiv.org/html/2607.03694#S2.F1.sf1)\. LetCCdenote the set of customers,MMthe set of vehicles, andL=C∪\{0\}L=C\\cup\\\{0\\\}the set of all locations including the depot\. Each customerc∈Cc\\in Chas demanddcd\_\{c\}, each vehiclem∈Mm\\in Mhas capacityQmQ\_\{m\}, and the travel cost between locationsi,j∈Li,j\\in Lis given byti​jt\_\{ij\}\.

###### Definition 2\.1\(Route\)

A route for vehiclem∈Mm\\in Mis an ordered sequence of locationsRm=\(0,vm\(1\),…,vm\(lm\),0\),R\_\{m\}=\(0,v\_\{m\}^\{\(1\)\},\\ldots,v\_\{m\}^\{\(l\_\{m\}\)\},0\),wherelml\_\{m\}is the route length of vehiclemmandvi∈Cv\_\{i\}\\in Care distinct customers visited by vehiclemm, the route begins and ends at the depot, and the total demand served along the route does not exceed the vehicle capacity,∑c∈Rmdc≤Qm\\sum\_\{c\\in R\_\{m\}\}d\_\{c\}\\leq Q\_\{m\}\.

###### Definition 2\.2\(Routing Solution\)

A routing solution is a collection of routesS=\{Rm\}m∈MS=\\\{R\_\{m\}\\\}\_\{m\\in M\}, containing at most one route for each vehicle in the fleet\.

Throughout this paper, we distinguish several types of routing solutions\.

###### Definition 2\.3\(Solution Terminology\)

LetSSdenote a routing solution\.

- •A*feasible solution*satisfies all routing constraints of the optimization model but may leave some customer demand unserved\.
- •A*full solution*is a feasible solution in which every customer is served\.

To accommodate routing instances in which the available vehicle resources are insufficient to serve all customer demand, or intermediate optimization stages in which a complete solution has not yet been constructed, we permit customers to remain temporarily unserved\. Letxi​j​mx\_\{ijm\}be a binary variable indicating whether vehiclemmtraverses arc\(i,j\)\(i,j\), letzc​mz\_\{cm\}be a binary variable indicating whether customerccis assigned to vehiclemm, and letycy\_\{c\}indicate whether customerccremains unserved\. We consider the following objective:

min​∑m∈M∑i∈L∑j∈Lti​j​xi​j​m\+ρ​∑c∈Cdc​yc,\\min\\sum\_\{m\\in M\}\\sum\_\{i\\in L\}\\sum\_\{j\\in L\}t\_\{ij\}x\_\{ijm\}\+\\rho\\sum\_\{c\\in C\}d\_\{c\}y\_\{c\},\(1\)whereρ∈ℝ\+\\rho\\in\\mathbb\{R\}^\{\+\}is a penalty coefficient associated with unserved demand\. The objective minimizes total travel cost while penalizing customer demand that is not served\.

The routing solution is subject to standard assignment, flow\-conservation, and vehicle\-capacity constraints\(Laporte[2009](https://arxiv.org/html/2607.03694#bib.bib7)\)\. Each customer must either be visited exactly once or remain unserved,

∑m∈M∑j∈Lxc​j​m\+yc=1,∀c∈C\.\\sum\_\{m\\in M\}\\sum\_\{j\\in L\}x\_\{cjm\}\+y\_\{c\}=1,\\qquad\\forall c\\in C\.\(2\)
Flow conservation requires that every vehicle entering a customer location must also depart from that location,

∑j∈Lxi​j​m=∑j∈Lxj​i​m,∀i∈C,m∈M\.\\sum\_\{j\\in L\}x\_\{ijm\}=\\sum\_\{j\\in L\}x\_\{jim\},\\qquad\\forall i\\in C,\\;m\\in M\.\(3\)
Vehicle capacities are enforced through

∑c∈Cdc​zc​m≤Qm,∀m∈M\.\\sum\_\{c\\in C\}d\_\{c\}z\_\{cm\}\\leq Q\_\{m\},\\qquad\\forall m\\in M\.\(4\)
Additional routing constraints, including depot connectivity, subtour elimination, and binary\-domain restrictions, follow the standard CVRP formulation and are omitted for brevity\.

### 2\.2Cluster\-First Route\-Second Formulation

We next formalize the cluster\-first route\-second \(CFRS\) framework used throughout this paper\. We begin with the conventional static formulation, in which the decomposition remains fixed during route construction\. We then extend this formulation by allowing customer and vehicle assignments to evolve over successive optimization rounds, providing the mathematical basis for the collaborative routing method developed in the following sections\.

#### 2\.2\.1Static Formulation

A cluster\-first route\-second \(CFRS\) decomposition partitions a CVRP instance into a collection of smaller routing subproblems as shown in Figure[1\(b\)](https://arxiv.org/html/2607.03694#S2.F1.sf2)\. Let

𝒫=\{\(C1,M1\),\(C2,M2\),…,\(CK,MK\)\}\\mathcal\{P\}=\\left\\\{\(C\_\{1\},M\_\{1\}\),\(C\_\{2\},M\_\{2\}\),\\dots,\(C\_\{K\},M\_\{K\}\)\\right\\\}\(5\)denote a decomposition of the customer setCCand vehicle fleetMM, where each routing subproblem consists of a customer subsetCk⊆CC\_\{k\}\\subseteq Cand an associated vehicle subsetMk⊆MM\_\{k\}\\subseteq M\. The customer and vehicle assignments form disjoint partitions,

Ci∩Cj\\displaystyle C\_\{i\}\\cap C\_\{j\}=∅,\\displaystyle=\\emptyset,∀i≠j,\\displaystyle\\forall i\\neq j,\(6\)⋃k=1KCk\\displaystyle\\bigcup\_\{k=1\}^\{K\}C\_\{k\}=C,\\displaystyle=C,\(7\)Mi∩Mj\\displaystyle M\_\{i\}\\cap M\_\{j\}=∅,\\displaystyle=\\emptyset,∀i≠j,\\displaystyle\\forall i\\neq j,\(8\)⋃k=1KMk\\displaystyle\\bigcup\_\{k=1\}^\{K\}M\_\{k\}=M\.\\displaystyle=M\.\(9\)
Each partition defines an independent routing subproblemXk=\(Ck,Mk\)X\_\{k\}=\(C\_\{k\},M\_\{k\}\), which is solved using a routing procedure

Sk=σ​\(Xk\)=\{Rm\}m∈Mk,S\_\{k\}=\\sigma\(X\_\{k\}\)=\\\{R\_\{m\}\\\}\_\{m\\in M\_\{k\}\},\(10\)whereSkS\_\{k\}denotes the incumbent solution associated with subproblemXkX\_\{k\}\. Note that the routes contained in the set are only for the vehicles of the partitionkk\. The collection of incumbent solutions is given by𝒮=\{S1,…,SK\}\\mathcal\{S\}=\\left\\\{S\_\{1\},\\ldots,S\_\{K\}\\right\\\}\.

###### Definition 2\.4\(Subproblem Solution\)

The incumbent solutionSk∈𝒮S\_\{k\}\\in\\mathcal\{S\}associated with routing subproblemXkX\_\{k\}is referred to as a*subproblem solution*\.

###### Definition 2\.5\(Global Solution\)

The*global solution*is obtained by combining the incumbent solutions of all routing subproblems,

S=⋃k=1KSk\.S=\\bigcup\_\{k=1\}^\{K\}S\_\{k\}\.\(11\)

In the conventional CFRS framework, the decomposition𝒫\\mathcal\{P\}remains fixed throughout route construction\. Therefore, each incumbent solution is computed using only the customers and vehicles assigned to its corresponding routing subproblem\.

#### 2\.2\.2Evolving Formulation

We extend the static formulation by allowing the decomposition to evolve over a sequence of optimization steps\. In this paper, an evolution step refers to a redistribution of customers or vehicles across routing subproblems\. The redistribution changes the subproblem definitions as shown in Figure[1\(c\)](https://arxiv.org/html/2607.03694#S2.F1.sf3), but it does not directly modify incumbent routes whose assigned customers and vehicles remain unchanged\.

To make this distinction explicit, let𝒞​\(Sk\)=\{c∈Ck:c​is served in​Sk\}\\mathcal\{C\}\(S\_\{k\}\)=\\\{c\\in C\_\{k\}:c\\text\{ is served in \}S\_\{k\}\\\}denote the customers served by incumbent solutionSkS\_\{k\}, and letℳ​\(Sk\)=\{m∈Mk:Rm∈Sk\}\\mathcal\{M\}\(S\_\{k\}\)=\\\{m\\in M\_\{k\}:R\_\{m\}\\in S\_\{k\}\\\}denote the vehicles used inSkS\_\{k\}\. An incumbent subproblem solutionSk\(t−1\)S\_\{k\}^\{\(t\-1\)\}can be preserved at stepttwhenever its served customers and used vehicles remain assigned to the same subproblem,

𝒞​\(Sk\(t−1\)\)⊆Ck\(t\)andℳ​\(Sk\(t−1\)\)⊆Mk\(t\)\.\\mathcal\{C\}\(S\_\{k\}^\{\(t\-1\)\}\)\\subseteq C\_\{k\}^\{\(t\)\}\\qquad\\text\{and\}\\qquad\\mathcal\{M\}\(S\_\{k\}^\{\(t\-1\)\}\)\\subseteq M\_\{k\}^\{\(t\)\}\.\(12\)
Equivalently, an incumbent route is affected only if at least one of its served customers or its associated vehicle is redistributed to another subproblem\.

Let

𝒫\(t\)=\{\(C1\(t\),M1\(t\)\),…,\(CK\(t\),MK\(t\)\)\}\\mathcal\{P\}^\{\(t\)\}=\\left\\\{\(C\_\{1\}^\{\(t\)\},M\_\{1\}^\{\(t\)\}\),\\dots,\(C\_\{K\}^\{\(t\)\},M\_\{K\}^\{\(t\)\}\)\\right\\\}\(13\)denote the decomposition after optimization steptt\. Each decomposition induces routing subproblems

Xk\(t\)=\(Ck\(t\),Mk\(t\)\),X\_\{k\}^\{\(t\)\}=\(C\_\{k\}^\{\(t\)\},M\_\{k\}^\{\(t\)\}\),\(14\)and corresponding incumbent solutions

Sk\(t\)=σ​\(Xk\(t\),Sk\(t−1\)\)\.S\_\{k\}^\{\(t\)\}=\\sigma\\\!\\left\(X\_\{k\}^\{\(t\)\},S\_\{k\}^\{\(t\-1\)\}\\right\)\.\(15\)
By a slight abuse of notation, we allow the routing procedureσ\\sigmato accept the previous incumbent solution as an additional argument\. This indicates that previously computed routing information may be used when constructing the updated incumbent solution\.

The collection of incumbent solutions after optimization stepttis

𝒮\(t\)=\{S1\(t\),…,SK\(t\)\},\\mathcal\{S\}^\{\(t\)\}=\\left\\\{S\_\{1\}^\{\(t\)\},\\dots,S\_\{K\}^\{\(t\)\}\\right\\\},\(16\)and the corresponding global solution is

S\(t\)=⋃k=1KSk\(t\)\.S^\{\(t\)\}=\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\(t\)\}\.\(17\)
The optimization therefore evolves through a sequence of decompositions and incumbent solutions,

\(𝒫\(0\),𝒮\(0\)\)→\(𝒫\(1\),𝒮\(1\)\)→⋯→\(𝒫\(T\),𝒮\(T\)\)\.\(\\mathcal\{P\}^\{\(0\)\},\\mathcal\{S\}^\{\(0\)\}\)\\rightarrow\(\\mathcal\{P\}^\{\(1\)\},\\mathcal\{S\}^\{\(1\)\}\)\\rightarrow\\cdots\\rightarrow\(\\mathcal\{P\}^\{\(T\)\},\\mathcal\{S\}^\{\(T\)\}\)\.\(18\)
At each optimization step, subproblems whose assigned customers or vehicles change may require re\-optimization, while incumbent routes whose customers and vehicles remain assigned to the same subproblem can be preserved\.

The formulation presented here establishes the mathematical framework for the proposed routing methodology\. The following section describes the collaboration operations and optimization procedure that evolve the decomposition and incumbent solutions during the routing process\.

## 3Collaborative Route Construction

Building upon the evolving CFRS formulation introduced in Section[2](https://arxiv.org/html/2607.03694#S2), CoRC introduces an intermediate coordination stage into route building, enabling routing subproblems to exchange customers and vehicles while preserving independent optimization\.

![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/collaborataive.drawio.png)Figure 2:Overview of the collaborative route\-construction framework\. Independent routing agents solve decomposed subproblems, compute and advertise local solution statistics \(such as ”Capacity deficit”\), exchange resources when shortages and surpluses are detected, and iteratively rebuild routes until a globally feasible solution is obtained\.Figure[2](https://arxiv.org/html/2607.03694#S3.F2)illustrates the overall organization of our method\. Starting from an initial decomposition, routing agents repeatedly \(i\) update incumbent routing solutions, \(ii\) derive and exchange routing statistics, and \(iii\) perform collaboration operations before the affected routing subproblems are re\-optimized\. The remainder of this section describes these three components in detail\.

### 3\.1Routing State Management by Partition Agents

As defined in Section[2](https://arxiv.org/html/2607.03694#S2), each routing subproblemXk\(t\)X\_\{k\}^\{\(t\)\}maintains an incumbent solutionSk\(t\)S\_\{k\}^\{\(t\)\}, obtained through the routing procedureσ​\(⋅\)\\sigma\(\\cdot\)in \([15](https://arxiv.org/html/2607.03694#S2.E15)\)\. The formulation permitsσ​\(⋅\)\\sigma\(\\cdot\)to exploit the incumbent solution from the previous optimization step but otherwise remains agnostic to the underlying CVRP solver\. Thus, any routing algorithm compatible with the formulation of Section[2](https://arxiv.org/html/2607.03694#S2)may be employed within the framework\.

#### 3\.1\.1Routing Statistics

Following each invocation of the routing procedure, every routing agent derives a compact summary of its current routing outcome,

Φk\(t\)=f​\(Xk\(t\),Sk\(t\)\),\\Phi\_\{k\}^\{\(t\)\}=f\\\!\\left\(X\_\{k\}^\{\(t\)\},S\_\{k\}^\{\(t\)\}\\right\),\(19\)wheref​\(⋅\)f\(\\cdot\)denotes the statistics extraction procedure\. The resulting statistics summarize the routing resources currently required by the routing subproblem together with the resources that remain available for collaboration\.

LetUk\(t\)⊆Ck\(t\)U\_\{k\}^\{\(t\)\}\\subseteq C\_\{k\}^\{\(t\)\}denote the set of customers that remain unserved after route construction\.

The smallest missed customer demand is

Dkmin=minc∈Uk\(t\)⁡dc,D\_\{k\}^\{\\min\}=\\min\_\{c\\in U\_\{k\}^\{\(t\)\}\}d\_\{c\},\(20\)representing the smallest customer demand that remains unserved\. This quantity is used to determine whether another routing subproblem possesses sufficient remaining capacity to accommodate at least one missed customer\.

The remaining vehicle capacity is

Qkfree=∑m∈Mk\(t\)Qm−∑c∈Ck\(t\)∖Uk\(t\)dc,Q\_\{k\}^\{\\mathrm\{free\}\}=\\sum\_\{m\\in M\_\{k\}^\{\(t\)\}\}Q\_\{m\}\-\\sum\_\{c\\in C\_\{k\}^\{\(t\)\}\\setminus U\_\{k\}^\{\(t\)\}\}d\_\{c\},\(21\)which measures the unused carrying capacity available after the incumbent routing solution has been constructed\.

The number of unserved customers is

Nkmiss=\|Uk\(t\)\|,N\_\{k\}^\{\\mathrm\{miss\}\}=\|U\_\{k\}^\{\(t\)\}\|,\(22\)while the number of vehicles that remain unused is

Nkfree=\|Ek\(t\)\|\.N\_\{k\}^\{\\mathrm\{free\}\}=\|E\_\{k\}^\{\(t\)\}\|\.\(23\)
Finally, each routing agent records the aggregate customer demand and available vehicle capacity within the routing subproblem,

Dktot=∑c∈Ck\(t\)dc,Qktot=∑m∈Mk\(t\)Qm\.D\_\{k\}^\{\\mathrm\{tot\}\}=\\sum\_\{c\\in C\_\{k\}^\{\(t\)\}\}d\_\{c\},\\qquad Q\_\{k\}^\{\\mathrm\{tot\}\}=\\sum\_\{m\\in M\_\{k\}^\{\(t\)\}\}Q\_\{m\}\.\(24\)
Collectively, these quantities define the routing statistics vector

Φk\(t\)=\(Dkmin,Qkfree,Nkmiss,Nkfree,Dktot,Qktot\)\.\\Phi\_\{k\}^\{\(t\)\}=\\left\(D\_\{k\}^\{\\min\},Q\_\{k\}^\{\\mathrm\{free\}\},N\_\{k\}^\{\\mathrm\{miss\}\},N\_\{k\}^\{\\mathrm\{free\}\},D\_\{k\}^\{\\mathrm\{tot\}\},Q\_\{k\}^\{\\mathrm\{tot\}\}\\right\)\.\(25\)
The routing statistics provide a compact summary of the current optimization state and are exchanged between routing subproblems during collaboration, avoiding the need to communicate complete routing solutions\.

### 3\.2Collaboration Operations

The routing statistics determine whether the current decomposition should be revised during route building\. Specifically, routing subproblems evaluate the advertised statistics of other subproblems to identify opportunities for collaboration before selecting one of the decomposition update operations introduced below\.

#### 3\.2\.1Collaboration Selection

Each routing subproblem evaluates the advertised routing statistics and assigns a collaboration priority to every candidate subproblem\. The framework is independent of the particular priority policy; in this work, we employ the following heuristic to rank candidate collaborations before selecting one of the collaboration operations introduced below\.

s​\(i,j\)=\{2,Nimiss\>0∧Dimin<Qjfree,2,Njmiss\>0∧Djmin<Qifree∧Nifree\>0,1,Nimiss\+Njmiss\>0∧Ditot\+Djtot≤Qitot\+Qjtot,0,otherwise\.\\displaystyle s\(i,j\)=\(26\)

#### 3\.2\.2Customer Transfer

A customer transfer is performed when routing subproblemiicontains unserved customers while routing subproblemjjpossesses sufficient remaining capacity to accommodate at least the smallest unserved customer demand inii\. Formally, if

Nimiss\>0,Dimin<Qjfree,N\_\{i\}^\{\\mathrm\{miss\}\}\>0,\\qquad D\_\{i\}^\{\\min\}<Q\_\{j\}^\{\\mathrm\{free\}\},\(27\)CoRC transfers a subset of the unserved customers fromiitojj\. LetΔ​C⊆Ui\(t\)\\Delta C\\subseteq U\_\{i\}^\{\(t\)\}denote the transferred customer set\. The updated customer assignments become

Ci\(t\+1\)=Ci\(t\)∖Δ​C,Cj\(t\+1\)=Cj\(t\)∪Δ​C\.C\_\{i\}^\{\(t\+1\)\}=C\_\{i\}^\{\(t\)\}\\setminus\\Delta C,\\qquad C\_\{j\}^\{\(t\+1\)\}=C\_\{j\}^\{\(t\)\}\\cup\\Delta C\.\(28\)
The affected routing subproblems are subsequently re\-optimized according to the evolving decomposition formulation\.

#### 3\.2\.3Vehicle Transfer

A vehicle transfer is performed when routing subproblemjjcontains unserved customers while routing subproblemiipossesses sufficient remaining capacity together with at least one unused vehicle\. Formally, if

Njmiss\>0,Djmin<Qifree,Nifree\>0,N\_\{j\}^\{\\mathrm\{miss\}\}\>0,\\qquad D\_\{j\}^\{\\min\}<Q\_\{i\}^\{\\mathrm\{free\}\},\\qquad N\_\{i\}^\{\\mathrm\{free\}\}\>0,\(29\)CoRC transfers one or more unused vehicles fromiitojj\. LetΔ​M⊆Ei\(t\)\\Delta M\\subseteq E\_\{i\}^\{\(t\)\}denote the transferred vehicle set\. The updated vehicle assignments are

Mi\(t\+1\)=Mi\(t\)∖Δ​M,Mj\(t\+1\)=Mj\(t\)∪Δ​M\.M\_\{i\}^\{\(t\+1\)\}=M\_\{i\}^\{\(t\)\}\\setminus\\Delta M,\\qquad M\_\{j\}^\{\(t\+1\)\}=M\_\{j\}^\{\(t\)\}\\cup\\Delta M\.\(30\)
The affected routing subproblems are subsequently re\-optimized using the routing procedureσ​\(⋅\)\\sigma\(\\cdot\)as in \([15](https://arxiv.org/html/2607.03694#S2.E15)\)\.

#### 3\.2\.4Subproblem Merge

When neither customer nor vehicle transfers satisfy the collaboration conditions, the two routing subproblems are merged into a single routing problem\. The merged routing subproblem is defined as

Ci​j\(t\+1\)=Ci\(t\)∪Cj\(t\),Mi​j\(t\+1\)=Mi\(t\)∪Mj\(t\)\.C\_\{ij\}^\{\(t\+1\)\}=C\_\{i\}^\{\(t\)\}\\cup C\_\{j\}^\{\(t\)\},\\qquad M\_\{ij\}^\{\(t\+1\)\}=M\_\{i\}^\{\(t\)\}\\cup M\_\{j\}^\{\(t\)\}\.\(31\)
The merged routing subproblem is subsequently re\-optimized, while all unaffected routing subproblems retain their incumbent solutions\.

Accepted proposals update the affected routing subproblems, after which the corresponding incumbent solutions and routing statistics are recomputed according to the evolving decomposition formulation\.

### 3\.3Asynchronous Agent Decision Cycle

CoRC is implemented as an asynchronous optimization cycle executed independently by each routing agent as described in Algorithm[1](https://arxiv.org/html/2607.03694#alg1)\. At optimization steptt, agentkkmaintains routing subproblemXk\(t\)=\(Ck\(t\),Mk\(t\)\)X\_\{k\}^\{\(t\)\}=\(C\_\{k\}^\{\(t\)\},M\_\{k\}^\{\(t\)\}\)and incumbent solutionSk\(t\)S\_\{k\}^\{\(t\)\}\. Whenever the customer or vehicle assignment of the subproblem changes, the agent invokes the routing operatorσ\\sigmato update its incumbent solution and then recomputes the statistics vectorΦk\(t\)\\Phi\_\{k\}^\{\(t\)\}\. These statistics are advertised to the other agents and are also used to evaluate received advertisements\.

The asynchronous structure allows that agents do not wait for a global synchronization round before acting\. Instead, each agent alternates between local route construction, advertisement publication, advertisement reading, and proposal validation\. Sleep parameters are included to avoid continuous polling and to control the frequency of communication and proposal processing\. These parameters, together with the choice of routing operatorσ\\sigma, are reported in the computational settings\.

An agent remains active until either the global time budget is exhausted or all of its customers and vehicles have been transferred to another routing subproblem\. In the latter case, the agent reaches an absorbing state and no longer participates in the optimization process\. Hence, successive merge operations produce progressively larger routing subproblems that accumulate customers, vehicles, and incumbent routing information over time\. Rather than performing a single global re\-optimization after all independent routing has been completed, as in decomposition\-based approaches such as\(Kerscher and Minner[2024](https://arxiv.org/html/2607.03694#bib.bib32)\), CoRC incrementally increases the optimization scope through localized merge operations\. This allows larger routing subproblems to emerge only where collaboration indicates additional joint optimization may be beneficial, while unaffected routing subproblems continue to evolve independently\.

Algorithm 1Asynchronous CoRC Optimization Cycle for Agentkk1:Initial subproblem

Xk\(0\)=\(Ck\(0\),Mk\(0\)\)X\_\{k\}^\{\(0\)\}=\(C\_\{k\}^\{\(0\)\},M\_\{k\}^\{\(0\)\}\), initial incumbent

Sk\(−1\)S\_\{k\}^\{\(\-1\)\}, routing operator

σ\\sigma, end time

TT, advertisement wait time

τadv\\tau\_\{\\mathrm\{adv\}\}, proposal wait time

τprop\\tau\_\{\\mathrm\{prop\}\}
2:

t←0t\\leftarrow 0
3:whilecurrent time

<T<Tdo

4:ifstate has changed, i\.e\.,

Xk\(t\)≠Xk\(t−1\)X\_\{k\}^\{\(t\)\}\\neq X\_\{k\}^\{\(t\-1\)\}then

5:Invoke routing operator,

Sk\(t\)←σ​\(Xk\(t\),Sk\(t−1\)\)S\_\{k\}^\{\(t\)\}\\leftarrow\\sigma\\\!\\left\(X\_\{k\}^\{\(t\)\},S\_\{k\}^\{\(t\-1\)\}\\right\)
6:Recompute statistics,

Φk\(t\)←f​\(Xk\(t\),Sk\(t\)\)\\Phi\_\{k\}^\{\(t\)\}\\leftarrow f\\\!\\left\(X\_\{k\}^\{\(t\)\},S\_\{k\}^\{\(t\)\}\\right\)
7:else

8:Retain

Sk\(t\)←Sk\(t−1\)S\_\{k\}^\{\(t\)\}\\leftarrow S\_\{k\}^\{\(t\-1\)\}
9:Retain

Φk\(t\)←Φk\(t−1\)\\Phi\_\{k\}^\{\(t\)\}\\leftarrow\\Phi\_\{k\}^\{\(t\-1\)\}
10:endif

11:Publish advertisement

Φk\(t\)\\Phi\_\{k\}^\{\(t\)\}to other agents

12:Sleep for

τadv\\tau\_\{\\mathrm\{adv\}\}duration

13:Read advertisements from other agents

\{Φℓ\(tℓ\):ℓ≠k\}\\\{\\Phi\_\{\\ell\}^\{\(t\_\{\\ell\}\)\}:\\ell\\neq k\\\}
14:Find the highest candidate,

j⋆←arg⁡maxj≠k⁡s​\(k,j\)j^\{\\star\}\\leftarrow\\arg\\max\_\{j\\neq k\}s\(k,j\)
15:if

s​\(k,j⋆\)\>0s\(k,j^\{\\star\}\)\>0then

16:Generate proposal

a∈\{CustomerTransfer,VehicleTransfer,Merge\}a\\in\\\{\\textsc\{CustomerTransfer\},\\textsc\{VehicleTransfer\},\\textsc\{Merge\}\\\}
17:Sleep for

τprop\\tau\_\{\\mathrm\{prop\}\}duration

18:if

aais valid under current advertisementsthen

19:Apply

aato update affected subproblems

20:

Xk\(t\+1\)←\(Ck\(t\+1\),Mk\(t\+1\)\)X\_\{k\}^\{\(t\+1\)\}\\leftarrow\(C\_\{k\}^\{\(t\+1\)\},M\_\{k\}^\{\(t\+1\)\}\)
21:endif

22:endif

23:ifno customers and no vehicles in the partitionthen

24:break

25:endif

26:

t←t\+1t\\leftarrow t\+1
27:endwhile

28:return

Sk\(t\)S\_\{k\}^\{\(t\)\}

The proposed framework exposes a small number of configurable parameters that determine the behavior of the optimization cycle\. These include the routing operatorσ\\sigma, the advertisement and proposal waiting times\(τadv,τprop\)\(\\tau\_\{\\mathrm\{adv\}\},\\tau\_\{\\mathrm\{prop\}\}\), and the overall optimization time budget\. The waiting times regulate the frequency of inter\-agent communication and proposal evaluation, balancing communication overhead against responsiveness in the asynchronous optimization process\. Table[1](https://arxiv.org/html/2607.03694#S3.T1)summarizes the parameter values used throughout the computational experiments\. Unless stated otherwise, these values were selected empirically based on preliminary tuning and were held fixed across all benchmark instances\.

Table 1:CoRC parameters used in the computational experiments\.

## 4Experiments and Evaluation

This section describes the computational study conducted to evaluate the CoRC framework\. We first introduce the experimental methodology, including the evaluation metrics and comparison methods, and then present a sequence of experiments designed to assess the effectiveness, scalability, and robustness of the collaboration mechanism\.

### 4\.1Experiment Setup

#### 4\.1\.1Evaluation Metrics

We evaluate our study using three performance measures\. The primary metric is the*time to full solution*, defined as the elapsed time required to construct a feasible solution in which all customer demand is served\. For instances where multiple methods reach a full solution, we additionally report the corresponding routing distance\. When a method does not produce a full solution within the prescribed time limit, its progress is quantified using the percentage of customer demand that remains unserved,

MissedDemand\(%\)=100⋅∑c∈Udc∑c∈Cdc,\\mathrm\{MissedDemand\}\(\\%\)=100\\cdot\\frac\{\\sum\_\{c\\in U\}d\_\{c\}\}\{\\sum\_\{c\\in C\}d\_\{c\}\},\(32\)whereUUdenotes the set of unserved customers\. These metrics jointly evaluate solution quality, convergence speed, and progress toward complete feasibility\.

For methods that could not complete due to computational resource limitations \(e\.g\., memory exhaustion\) are reported as N/A, whereas methods that completed execution but failed to construct a full solution within the prescribed time budget are reported as INF in the results tables\.

#### 4\.1\.2Clustering Methods

To evaluate the proposed collaboration framework under diverse decomposition strategies, we consider four representative clustering methods\.Sweep\(Gillett and Miller[1974](https://arxiv.org/html/2607.03694#bib.bib14)\)andGridgenerate spatially uniformly split rectangular boundaries\.CC\-CVRP\(Alesianiet al\.[2022](https://arxiv.org/html/2607.03694#bib.bib10)\)builds routing subproblems using demand and capacity information during decomposition\. Finally,Randomassigns customers to routing subproblems without considering either spatial or operational structure, providing a challenging reference decomposition\.

Unless the clustering algorithm outlines the vehicle distribution mechanism explicitly, we distribute the vehicles in a balanced manner so that clusters with higher total demand receive higher total vehicle capacity, proportionally\.

These methods span a broad spectrum of decomposition characteristics, allowing the collaboration mechanism to be evaluated independently of any particular clustering strategy\.

#### 4\.1\.3Compared Methods

The evaluated methods are grouped into four categories\.

The first category consists of independent optimization frameworks, denoted by the suffix\-Ind\. For each clustering method, routing subproblems are solved independently using the common routing operatorσ\\sigma, after which the resulting routes are combined to form the final routing solution\.

The second category consists of global re\-optimization baseline, denoted by the suffix\-Reopt\. This method first solves the decomposed routing subproblems independently, as in the\-Indbaselines\. The only difference is that the independent solvers are terminated when the routing solver determines no more customers can be served, or half of the total allotted time is reached\. The combined solution is then used as the initial solution for a global optimization step, which is run for the remaining time budget of 6 hours\.

The third category applies the CoRC framework to the same decompositions\. Since the independent, global re\-optimization, and CoRC variants share identical decompositions and routing operators, these comparisons isolate the effect of when coordination is introduced during the routing process\. We label these runs with the suffix\-CoRC\. All methods under independent, re\-optimization, and the CoRC use Guided Local Search\(Voudouris and Tsang[1999](https://arxiv.org/html/2607.03694#bib.bib61)\)in Or\-Tools implementation\(Didieret al\.[2023](https://arxiv.org/html/2607.03694#bib.bib35)\)\.

The fourth category consists of complete routing frameworks that do not explicitly separate decomposition and routing\. We considerScaleNet\(Liuet al\.[2026](https://arxiv.org/html/2607.03694#bib.bib42)\), a learning\-based routing framework, andHybrid Genetic Search \(HGS\)\(Vidal[2022](https://arxiv.org/html/2607.03694#bib.bib9)\), one of the strongest general\-purpose metaheuristics for the CVRP\.

### 4\.2Performance on Benchmark and Large\-Scale Instances

Our first computational study evaluates the overall routing performance of the CoRC framework across both established benchmark instances and large\-scale synthetic instances\. The objective is to compare CoRC against independent routing, post\-routing global re\-optimization, and complete routing frameworks under a common experimental setting while assessing its behavior across a broad range of problem sizes\.

The study consists of two datasets\. The first is the AGS benchmark suite\(Arnoldet al\.[2019](https://arxiv.org/html/2607.03694#bib.bib33)\)comprising the Ghent1 \(10K\), Brussels1 \(15K\), Flanders1 \(20K\), and Flanders2 \(30K\) instances\. The second consists of synthetic instances containing 100,000 and 200,000 customers\. Customer locations are sampled uniformly over the service region\. Vehicle capacities are drawn uniformly from the interval\[2​dmax,5​dmax\]\[2d\_\{\\max\},5d\_\{\\max\}\], wheredmaxd\_\{\\max\}denotes the maximum customer demand\. The fleet size is fixed to 400 vehicles for both synthetic instances, and the generated capacities are normalized to obtain an overall capacity utilization of0\.950\.95\.

The computational budget is set to one hour for the AGS benchmark instances and six hours for the large\-scale synthetic instances, due to the significant difference in problem sizes\. Results for the AGS and synthetic datasets are reported in Tables[2](https://arxiv.org/html/2607.03694#S4.T2)and[3](https://arxiv.org/html/2607.03694#S4.T3), respectively\.

Table 2:Comparison of decomposition\-based and complete methods on the AGS benchmark instances\. Runs that did not obtain a full solution within the 6\-hour limit are denoted “INF” and experiments failing due to excessive memory are ”N/A”\.\(a\)Ghent1 \(10K\)
\(b\)Instance: Brussels1 \(15K\)
\(c\)Instance: Flanders1 \(20K\)
\(d\)Instance: Flanders2 \(30K\)

Table 3:Comparison of decomposition\-based and complete routing methods on large synthetic instances\. Runs that did not obtain a full solution within the 6\-hour limit are denoted “INF” and experiments failing due to excessive memory are ”N/A”\.\(a\)Gen100K
\(b\)Gen200K

Tables[2](https://arxiv.org/html/2607.03694#S4.T2)and[3](https://arxiv.org/html/2607.03694#S4.T3)demonstrate that CoRC is the only decomposition\-based routing framework that consistently constructs full solutions across all AGS benchmark instances and both synthetic large\-scale instances\. In contrast, neither Independent routing nor post\-routing global re\-optimization reaches a full solution under any decomposition\. Although the global re\-optimization stage generally reduces the amount of unserved demand relative to Independent routing, substantial portions of customer demand remain unserved, particularly on the synthetic instances\. These results indicate that introducing coordination during route construction is considerably more effective at recovering feasibility than postponing coordination until a subsequent global optimization stage\.

The routing distances further demonstrate that CoRC complements rather than replaces the underlying decomposition strategy\. While collaboration consistently restores feasibility, the resulting routing distances continue to reflect the quality of the initial partitioning\. In particular, Random decomposition produces substantially longer routes despite reaching full solutions, whereas Grid and CC\-CVRP generally yield shorter routes\. This behavior suggests that decomposition quality primarily determines route efficiency, while the proposed collaboration mechanism improves the ability to yield complete solutions across diverse decomposition strategies\.

On the AGS benchmark instances, the complete routing frameworks ScaleNet and HGS generally produce shorter routing distances than the decomposition\-based methods, as expected from optimizing the original routing problem directly\. However, neither framework successfully produced routing solutions for the 100K or 200K synthetic instances within the available computational resources, whereas CoRC continued to obtain full routing solutions across all evaluated decompositions\. These results suggest that collaborative partition optimization provides a practical complement to decomposition\-based routing, extending its applicability to substantially larger problem instances while preserving the flexibility of the underlying decomposition strategy\.

### 4\.3Sensitivity and Robustness Analysis

The previous experiments demonstrated the overall effectiveness of CoRC, but they did not isolate the impact of the initial decomposition method\. In this section, we evaluate the robustness of the framework under increasingly challenging partitioning conditions\. To provide a controlled setting, all experiments use grid partitioning, which does not exploit spatial or demand information and therefore represents one of the least balanced clustering strategies, offering a challenging benchmark for collaboration\.

![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/missed_demand_F-n200000-k400-De-Cr-Msl-U95.png)\(a\)Influence of routing subproblem granularity on solution quality\.
![Refer to caption](https://arxiv.org/html/2607.03694v1/figures/missed_demand_starvation_F-n200000-k400-De-Cm-Msl-U95-S123.png)\(b\)Impact of increasing vehicle starvation on the missed demand of frameworks\. The dashed reference line denotes the starvation level \(y=xy=x\)\.

Figure 3:Sensitivity of the three routing strategies to decomposition granularity and vehicle imbalance\.#### 4\.3\.1Sensitivity to Decomposition Granularity

In this experiment, we investigate the sensitivity of the collaboration method to the granularity of the decomposition itself\. Specifically, we study how the number of routing subproblems influences the behavior of independent routing, global re\-optimization, and CoRC\.

The experiment is conducted on the Gen200K synthetic instance using theGriddecomposition method\. The number of routing subproblems is varied over\{9,49,100,484,961\}\\\{9,49,100,484,961\\\}\(all have integer square\-roots and are closest to\{10,50,100,500,1000\}\\\{10,50,100,500,1000\\\}, respectively\) while all remaining experimental settings, including the routing operatorσ\\sigma, remain unchanged\. For each decomposition, we evaluate the three routing strategies introduced previously: independent routing \(\-Ind\), global re\-optimization \(\-Reopt\), and the CoRC\.

Unlike the benchmark and scalability studies, complete routing frameworks are not included in this experiment because the objective is to isolate the effect of decomposition granularity within decomposition\-based routing methods\.

Figure[3\(a\)](https://arxiv.org/html/2607.03694#S4.F3.sf1)evaluates the sensitivity of the routing strategies to the number of routing subproblems\. As the number of clusters increases, the missed demand decreases for all methods, indicating that finer decompositions produce routing subproblems that are easier to solve independently\. At very coarse decompositions \(9 and 49 clusters\), both Independent and Reopt fail to yield feasible solutions, leaving more than half of the demand unserved\. In contrast, CoRC consistently recovers a feasible solution with zero missed demand, demonstrating that collaboration can effectively compensate for challenging initial decompositions\.

The advantage of collaboration gradually diminishes as the decomposition becomes finer\. At 484 and 961 clusters, Independent and Reopt also achieve low missed demand, leaving little opportunity for collaborative repair\. This behavior indicates that CoRC primarily improves robustness rather than benefiting from any particular decomposition granularity\. While the independent approaches rely on carefully selecting an appropriate number of routing subproblems, CoRC maintains high solution quality across a broad range of cluster counts, substantially reducing the sensitivity of the overall framework to decomposition design\.

#### 4\.3\.2Robustness to Resource\-Imbalanced Decompositions

Here, we investigate how the collaboration model behaves under increasingly imbalanced customer and vehicle assignments\. The objective is to evaluate the ability of the routing strategies to adapt when the initial decomposition intentionally creates routing subproblems with highly uneven resource availability\.

The experiment is conducted on the Gen200K synthetic instance \(200K customers\) using the Grid decomposition with 100 routing subproblems\. Starting from a balanced decomposition, an increasing fraction of routing subproblems is selected to receive no vehicles, while their vehicles are redistributed among the remaining subproblems, preserving the overall fleet capacity\. Five imbalance scenarios are considered, where1%1\\%,25%25\\%,50%50\\%,75%75\\%, and99%99\\%of the routing subproblems are initialized without assigned vehicles\. The three routing strategies \(Ind,Reopt, andCoRC\) are then evaluated under identical routing and optimization settings\.

This experiment isolates the effect of resource imbalance while keeping the decomposition method, routing operator, and overall fleet resources fixed\. Consequently, differences in performance can be attributed to the ability of each routing strategy to adapt to increasingly uneven customer and vehicle assignments\.

Figure[3\(b\)](https://arxiv.org/html/2607.03694#S4.F3.sf2)evaluates the robustness of the routing strategies under progressively increasing levels of vehicle starvation\. Independent routing exhibits an almost linear increase in missed demand, closely tracking the imposed starvation level, indicating that isolated partitions have little ability to compensate for missing fleet resources\. Re\-optimization provides partial improvements at moderate starvation levels but displays a non\-monotonic trend, with its best performance occurring under intermediate starvation\. This behavior suggests that re\-optimization is challenged at both extremes: when starvation is low, the independently produced cluster solutions are already of high quality, making the time spent on global re\-optimization less effective than further local optimization; conversely, under severe starvation, the partition\-level infeasibility becomes too substantial to repair within the remaining time budget\.

In contrast, CoRC maintains complete feasibility for starvation levels up to 75% by proactively redistributing vehicles and customers between partitions before routing\. Even under the extreme 99% starvation scenario, CoRC serves approximately two\-thirds of the total demand, substantially outperforming both independent routing and re\-optimization\. These results demonstrate that collaboration not only improves routing performance but also makes partition\-based routing considerably more robust to severe resource imbalance\.

## 5Conclusion

We presented Collaborative Routing Constructors \(CoRC\), a collaborative routing framework that introduces an intermediate coordination stage into cluster\-first route\-second solution methods for the CVRP\. By allowing routing subproblems to exchange customers and vehicles during route construction, CoRC complements existing decomposition strategies without modifying the underlying routing solver\. Computational experiments on AGS benchmark instances and synthetic instances containing up to 200,000 customers showed that CoRC consistently constructs full routing solutions where independent routing and post\-routing global re\-optimization do not, while remaining effective at scales where the evaluated complete routing frameworks did not produce solutions under the same computational budget\. These findings demonstrate that collaborative partition optimization provides a robust approach to feasible large\-scale routing and motivate further research into optimization frameworks that dynamically adapt decompositions during route construction\.

## 6Code and Data Disclosure

The code and data to support the numerical experiments in this paper can be requested from the corresponding author\.

## References

- Towards a connection between the capacitated vehicle routing problem and the constrained centroid\-based clustering\.arXiv preprint arXiv:2403\.14013\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p1.1)\.
- F\. Alesiani, G\. Ermis, and K\. Gkiotsalitis \(2022\)Constrained clustering for the capacitated vehicle routing problem \(cc\-cvrp\)\.Applied artificial intelligence36\(1\),pp\. 1995658\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1),[§4\.1\.2](https://arxiv.org/html/2607.03694#S4.SS1.SSS2.p1.1)\.
- S\. Anily and A\. Federgruen \(1993\)Two\-echelon distribution systems with vehicle routing costs and central inventories\.Operations Research41\(1\),pp\. 37–47\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- F\. Arnold, M\. Gendreau, and K\. Sörensen \(2019\)Efficiently solving very large\-scale routing problems\.Computers & operations research107,pp\. 32–42\.Cited by:[§4\.2](https://arxiv.org/html/2607.03694#S4.SS2.p2.3)\.
- M\. Battarra, G\. Erdoğan, and D\. Vigo \(2014\)Exact algorithms for the clustered vehicle routing problem\.Operations Research62\(1\),pp\. 58–71\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p3.1)\.
- N\. Boysen, S\. Fedtke, and S\. Schwerdfeger \(2020\)Last\-mile delivery concepts: a survey from an operational research perspective\.OR spectrum43\(1\),pp\. 1–58\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- F\. Cakir, W\. N\. Street, and B\. W\. Thomas \(2015\)Revisiting cluster first, route second for the vehicle routing problem\.no\. August\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p1.1)\.
- A\. M\. Campbell, D\. Vandenbussche, and W\. Hermann \(2008\)Routing for relief efforts\.Transportation science42\(2\),pp\. 127–145\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- S\. J\. Chin and M\. Schiffer \(2026\)Neural cluster first, route second: one\-shot capacitated vehicle routing via differentiable optimal transport\.arXiv preprint arXiv:2605\.09301\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- G\. Clarke and J\. W\. Wright \(1964\)Scheduling of vehicles from a central depot to a number of delivery points\.Operations research12\(4\),pp\. 568–581\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p2.1)\.
- T\. G\. Crainic and G\. Laporte \(1997\)Planning models for freight transportation\.European journal of operational research97\(3\),pp\. 409–438\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- F\. Da Ros, M\. Soprano, L\. Di Gaspero, and K\. Roitero \(2026\)Large language models for combinatorial optimization: a systematic review\.ACM Computing Surveys58\(11\),pp\. 1–53\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- G\. B\. Dantzig and J\. H\. Ramser \(1959\)The truck dispatching problem\.Management science6\(1\),pp\. 80–91\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- F\. Didier, L\. Perron, S\. Mohajeri, S\. A\. Gay, T\. Cuvelier, and V\. Furnon \(2023\)OR\-tools’ vehicle routing solver: a generic constraint\-programming solver with heuristic search for routing problems\.Cited by:[Table 1](https://arxiv.org/html/2607.03694#S3.T1.1.1.3),[§4\.1\.3](https://arxiv.org/html/2607.03694#S4.SS1.SSS3.p4.1)\.
- T\. Gaon, Y\. Gabay, and M\. Weiss Cohen \(2025\)Optimizing electric vehicle routing efficiency using k\-means clustering and genetic algorithms\.Future Internet17\(3\),pp\. 97\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p1.1)\.
- B\. E\. Gillett and L\. R\. Miller \(1974\)A heuristic algorithm for the vehicle\-dispatch problem\.Operations research22\(2\),pp\. 340–349\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p1.1),[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p3.1),[§1](https://arxiv.org/html/2607.03694#S1.p2.1),[§1](https://arxiv.org/html/2607.03694#S1.p3.1),[§4\.1\.2](https://arxiv.org/html/2607.03694#S4.SS1.SSS2.p1.1)\.
- B\. Golden, A\. Assad, L\. Levy, and F\. Gheysens \(1984\)The fleet size and mix vehicle routing problem\.Computers & Operations Research11\(1\),pp\. 49–66\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- L\. Jingjing, Y\. Fang, and N\. Tang \(2022\)A cluster\-based optimization framework for vehicle routing problem with workload balance\.Computers & Industrial Engineering169,pp\. 108221\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1),[§1](https://arxiv.org/html/2607.03694#S1.p3.1)\.
- C\. Kerscher and S\. Minner \(2024\)Spatial\-temporal\-demand clustering for solving large\-scale vehicle routing problems with time windows\.arXiv preprint arXiv:2402\.00041\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p4.1),[§1](https://arxiv.org/html/2607.03694#S1.p3.1),[§3\.3](https://arxiv.org/html/2607.03694#S3.SS3.p3.1)\.
- G\. Laporte \(2009\)Fifty years of vehicle routing\.Transportation Science43\(4\),pp\. 408–416\.Cited by:[§2\.1](https://arxiv.org/html/2607.03694#S2.SS1.p4.1)\.
- J\. K\. Lenstra and A\. H\. G\. Rinnooy Kan \(1981\)Complexity of vehicle routing and scheduling problems\.Networks11\(2\),pp\. 221–227\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p2.1)\.
- B\. Li, G\. Wu, Y\. He, M\. Fan, and W\. Pedrycz \(2022\)An overview and experimental study of learning\-based optimization algorithms for the vehicle routing problem\.IEEE/CAA Journal of Automatica Sinica9\(7\),pp\. 1115–1138\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- R\. Linfati, F\. Yáñez\-Concha, and J\. W\. Escobar \(2022\)Mathematical models for the vehicle routing problem by considering balancing load and customer compactness\.Sustainability14\(19\),pp\. 12937\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- S\. Liu, Z\. Cao, N\. Yin, and Y\. Ong \(2026\)Scale\-net: a hierarchical u\-net framework for cross\-scale generalization in multi\-task vehicle routing\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 14295–14303\.Cited by:[§4\.1\.3](https://arxiv.org/html/2607.03694#S4.SS1.SSS3.p5.1)\.
- D\. Pisinger and S\. Ropke \(2018\)Large neighborhood search\.InHandbook of metaheuristics,pp\. 99–127\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p2.1),[§1](https://arxiv.org/html/2607.03694#S1.p3.1)\.
- S\. Ropke and D\. Pisinger \(2006\)An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows\.Transportation Science40\(4\),pp\. 455–472\.External Links:[Document](https://dx.doi.org/10.1287/trsc.1050.0135)Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p4.1)\.
- A\. Santini, M\. Schneider, T\. Vidal, and D\. Vigo \(2023\)Decomposition strategies for vehicle routing heuristics\.INFORMS Journal on Computing35\(3\),pp\. 543–559\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p2.1)\.
- R\. Thind, Y\. Sun, L\. Liang, and H\. Yang \(2025\)Optimai: optimization from natural language using llm\-powered ai agents\.arXiv preprint arXiv:2504\.16918\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- P\. Toth and D\. Vigo \(2014\)Vehicle routing: problems, methods, and applications\.SIAM\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.
- V\. Vapnik \(1991\)Principles of risk minimization for learning theory\.Advances in neural information processing systems4\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- T\. Vidal \(2022\)Hybrid genetic search for the cvrp: open\-source implementation and swap\* neighborhood\.Computers & Operations Research140,pp\. 105643\.Cited by:[§4\.1\.3](https://arxiv.org/html/2607.03694#S4.SS1.SSS3.p5.1)\.
- C\. Voudouris and E\. Tsang \(1999\)Guided local search and its application to the traveling salesman problem\.European journal of operational research113\(2\),pp\. 469–499\.Cited by:[§4\.1\.3](https://arxiv.org/html/2607.03694#S4.SS1.SSS3.p4.1)\.
- X\. Xiu, J\. Li, J\. Fan, and W\. Liu \(2026\)Large language models for operations research: a comprehensive survey\.arXiv preprint arXiv:2605\.20849\.Cited by:[§1\.1](https://arxiv.org/html/2607.03694#S1.SS1.p2.1)\.
- D\. Yamín, A\. L\. Medaglia, and A\. P\. Akkinepally \(2024\)Reliable routing strategies on urban transportation networks\.Transportation Science58\(2\),pp\. 377–393\.Cited by:[§1](https://arxiv.org/html/2607.03694#S1.p1.1)\.