1 Introduction↩︎

We consider the Capacitated Vehicle Routing Problem (CVRP) with both homogeneous [1] and heterogeneous vehicle fleets [2], [3]. 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 [4], parcel and last-mile delivery [5], humanitarian logistics [6], and urban service operations such as waste collection and street maintenance [7], [8].

The CVRP is NP-hard [9]. Consequently, the literature has developed a broad range of exact algorithms, heuristics, metaheuristics, and decomposition techniques for obtaining high-quality routing solutions [10]–[12]. Among these, decomposition-based approaches have become an important component of modern vehicle-routing heuristics, particularly for large routing instances [13].

One prominent decomposition paradigm is the cluster-first route-second (CFRS) framework [10], [14]. 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 [12], [15]. 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.1 Prior Art↩︎

Early CFRS methods focused primarily on geometric partitioning. Representative examples include the sweep algorithm [10] and centroid-based clustering approaches [16], 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 [17], [18].

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 [14], [19], [20]. More recently, learning-based approaches have used optimization feedback to guide decomposition decisions through reinforcement learning, neural combinatorial optimization, and large language models [21]–[25]. These modern approaches extend the former by exploiting the patterns collected in the historical data by estimating a policy via empirical risk minimization [26].

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 [10], [27]. 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 [15]. These approaches apply global improvement procedures, such as adaptive large neighborhood search [28] 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.

2 Problem 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.

2.1 Capacitated 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). Let \(C\) denote the set of customers, \(M\) the set of vehicles, and \(L=C\cup\{0\}\) the set of all locations including the depot. Each customer \(c\in C\) has demand \(d_c\), each vehicle \(m\in M\) has capacity \(Q_m\), and the travel cost between locations \(i,j\in L\) is given by \(t_{ij}\).

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

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. Let \(x_{ijm}\) be a binary variable indicating whether vehicle \(m\) traverses arc \((i,j)\), let \(z_{cm}\) be a binary variable indicating whether customer \(c\) is assigned to vehicle \(m\), and let \(y_c\) indicate whether customer \(c\) remains unserved. We consider the following objective: \[\min \sum_{m\in M}\sum_{i\in L}\sum_{j\in L} t_{ij}x_{ijm} + \rho\sum_{c\in C}d_cy_c,\] 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 [29]. Each customer must either be visited exactly once or remain unserved, \[\sum_{m\in M}\sum_{j\in L} x_{cjm} + y_c = 1, \qquad \forall c\in C.\]

Flow conservation requires that every vehicle entering a customer location must also depart from that location, \[\sum_{j\in L} x_{ijm} = \sum_{j\in L} x_{jim}, \qquad \forall i\in C,\; m\in M.\]

Vehicle capacities are enforced through \[\sum_{c\in C} d_cz_{cm} \le Q_m, \qquad \forall m\in M.\]

Additional routing constraints, including depot connectivity, subtour elimination, and binary-domain restrictions, follow the standard CVRP formulation and are omitted for brevity.

2.2 Cluster-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.1 Static 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). Let \[\mathcal{P}=\left\{(C_1,M_1),(C_2,M_2),\dots,(C_K,M_K)\right\}\] denote a decomposition of the customer set \(C\) and vehicle fleet \(M\), where each routing subproblem consists of a customer subset \(C_k\subseteq C\) and an associated vehicle subset \(M_k\subseteq M\). The customer and vehicle assignments form disjoint partitions, \[\begin{align} C_i\cap C_j &= \emptyset, & \forall i\neq j,\\ \bigcup_{k=1}^{K}C_k &= C,\\[0.3em] M_i\cap M_j &= \emptyset, & \forall i\neq j,\\ \bigcup_{k=1}^{K}M_k &= M. \end{align}\]

Each partition defines an independent routing subproblem \(X_k=(C_k,M_k)\), which is solved using a routing procedure \[S_k=\sigma(X_k)=\{R_m\}_{m\in M_k},\] where \(S_k\) denotes the incumbent solution associated with subproblem \(X_k\). Note that the routes contained in the set are only for the vehicles of the partition \(k\). The collection of incumbent solutions is given by \(\mathcal{S}=\left\{S_1,\ldots,S_K\right\}\).

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.2 Evolving 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), but it does not directly modify incumbent routes whose assigned customers and vehicles remain unchanged.

To make this distinction explicit, let \(\mathcal{C}(S_k)=\{c\in C_k : c \text{ is served in } S_k\}\) denote the customers served by incumbent solution \(S_k\), and let \(\mathcal{M}(S_k)=\{m\in M_k : R_m\in S_k\}\) denote the vehicles used in \(S_k\). An incumbent subproblem solution \(S_k^{(t-1)}\) can be preserved at step \(t\) whenever its served customers and used vehicles remain assigned to the same subproblem, \[\mathcal{C}(S_k^{(t-1)}) \subseteq C_k^{(t)} \qquad\text{and}\qquad \mathcal{M}(S_k^{(t-1)}) \subseteq M_k^{(t)}. \label{eqn:evolve}\tag{1}\]

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 \[\mathcal{P}^{(t)}=\left\{(C_1^{(t)},M_1^{(t)}),\dots,(C_K^{(t)},M_K^{(t)})\right\}\] denote the decomposition after optimization step \(t\). Each decomposition induces routing subproblems \[X_k^{(t)}=(C_k^{(t)},M_k^{(t)}), \label{eqn:subproblem95dyn}\tag{2}\] and corresponding incumbent solutions \[S_k^{(t)}=\sigma\!\left(X_k^{(t)},S_k^{(t-1)}\right). \label{eqn:solution95dyn}\tag{3}\]

By a slight abuse of notation, we allow the routing procedure \(\sigma\) to 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 step \(t\) is \[\mathcal{S}^{(t)}=\left\{S_1^{(t)},\dots,S_K^{(t)}\right\},\] and the corresponding global solution is \[S^{(t)}=\bigcup_{k=1}^{K}S_k^{(t)}.\]

The optimization therefore evolves through a sequence of decompositions and incumbent solutions, \[(\mathcal{P}^{(0)},\mathcal{S}^{(0)}) \rightarrow (\mathcal{P}^{(1)},\mathcal{S}^{(1)}) \rightarrow \cdots\rightarrow (\mathcal{P}^{(T)},\mathcal{S}^{(T)}).\]

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.

3 Collaborative Route Construction↩︎

Building upon the evolving CFRS formulation introduced in Section 2, CoRC introduces an intermediate coordination stage into route building, enabling routing subproblems to exchange customers and vehicles while preserving independent optimization.

Figure 2 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.1 Routing State Management by Partition Agents↩︎

As defined in Section 2, each routing subproblem \(X_k^{(t)}\) maintains an incumbent solution \(S_k^{(t)}\), obtained through the routing procedure \(\sigma(\cdot)\) in 3 . 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 may be employed within the framework.

3.1.1 Routing Statistics↩︎

Following each invocation of the routing procedure, every routing agent derives a compact summary of its current routing outcome, \[\Phi_k^{(t)} = f\!\left( X_k^{(t)}, S_k^{(t)} \right),\] where \(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.

Let \(U_k^{(t)}\subseteq C_k^{(t)}\) denote the set of customers that remain unserved after route construction.

The smallest missed customer demand is \[D_k^{\min} = \min_{c\in U_k^{(t)}} d_c,\] 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 \[Q_k^{\mathrm{free}} = \sum_{m\in M_k^{(t)}}Q_m - \sum_{c\in C_k^{(t)}\setminus U_k^{(t)}}d_c,\] which measures the unused carrying capacity available after the incumbent routing solution has been constructed.

The number of unserved customers is \[N_k^{\mathrm{miss}} = |U_k^{(t)}|,\] while the number of vehicles that remain unused is \[N_k^{\mathrm{free}} = |E_k^{(t)}|.\]

Finally, each routing agent records the aggregate customer demand and available vehicle capacity within the routing subproblem, \[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.\]

Collectively, these quantities define the routing statistics vector \[\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).\]

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.2 Collaboration 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.1 Collaboration 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.

\[\begin{align} s(i,j)= \begin{cases} 2, & \begin{aligned}[t] &N_i^{\mathrm{miss}}>0 \\ &{}\land\;D_i^{\min} < Q_j^{\mathrm{free}}, \end{aligned} \\[0.6em] 2, & \begin{align}[t] &N_j^{\mathrm{miss}}>0 \\ &{}\land\;D_j^{\min} < Q_i^{\mathrm{free}} \\ &{}\land\;N_i^{\mathrm{free}}>0, \end{align} \\[0.6em] 1, & \begin{align}[t] &N_i^{\mathrm{miss}}+N_j^{\mathrm{miss}}>0 \\ &{}\land\;D_i^{\mathrm{tot}}+D_j^{\mathrm{tot}} \le Q_i^{\mathrm{tot}}+Q_j^{\mathrm{tot}}, \end{align} \\[0.6em] 0, & \text{otherwise}. \end{cases} \end{align}\]

3.2.2 Customer Transfer↩︎

A customer transfer is performed when routing subproblem \(i\) contains unserved customers while routing subproblem \(j\) possesses sufficient remaining capacity to accommodate at least the smallest unserved customer demand in \(i\). Formally, if \[N_i^{\mathrm{miss}}>0, \qquad D_i^{\min}<Q_j^{\mathrm{free}},\] CoRC transfers a subset of the unserved customers from \(i\) to \(j\). Let \(\Delta C\subseteq U_i^{(t)}\) denote the transferred customer set. The updated customer assignments become \[C_i^{(t+1)} = C_i^{(t)}\setminus\Delta C, \qquad C_j^{(t+1)} = C_j^{(t)}\cup\Delta C.\]

The affected routing subproblems are subsequently re-optimized according to the evolving decomposition formulation.

3.2.3 Vehicle Transfer↩︎

A vehicle transfer is performed when routing subproblem \(j\) contains unserved customers while routing subproblem \(i\) possesses sufficient remaining capacity together with at least one unused vehicle. Formally, if \[N_j^{\mathrm{miss}}>0, \qquad D_j^{\min}<Q_i^{\mathrm{free}}, \qquad N_i^{\mathrm{free}}>0,\] CoRC transfers one or more unused vehicles from \(i\) to \(j\). Let \(\Delta M\subseteq E_i^{(t)}\) denote the transferred vehicle set. The updated vehicle assignments are \[M_i^{(t+1)} = M_i^{(t)}\setminus\Delta M, \qquad M_j^{(t+1)} = M_j^{(t)}\cup\Delta M.\]

The affected routing subproblems are subsequently re-optimized using the routing procedure \(\sigma(\cdot)\) as in 3 .

3.2.4 Subproblem 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 \[C_{ij}^{(t+1)} = C_i^{(t)}\cup C_j^{(t)}, \qquad M_{ij}^{(t+1)} = M_i^{(t)}\cup M_j^{(t)}.\]

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.3 Asynchronous Agent Decision Cycle↩︎

CoRC is implemented as an asynchronous optimization cycle executed independently by each routing agent as described in Algorithm 3. At optimization step \(t\), agent \(k\) maintains routing subproblem \(X_k^{(t)}=(C_k^{(t)},M_k^{(t)})\) and incumbent solution \(S_k^{(t)}\). Whenever the customer or vehicle assignment of the subproblem changes, the agent invokes the routing operator \(\sigma\) to update its incumbent solution and then recomputes the statistics vector \(\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 [15], 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.

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 \((\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 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.

4 Experiments 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.1 Experiment Setup↩︎

4.1.1 Evaluation 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,

\[\mathrm{MissedDemand}(\%)=100\cdot\frac{\sum_{c\in U} d_c}{\sum_{c\in C} d_c},\] where \(U\) denotes 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.2 Clustering Methods↩︎

To evaluate the proposed collaboration framework under diverse decomposition strategies, we consider four representative clustering methods. Sweep [10] and Grid generate spatially uniformly split rectangular boundaries. CC-CVRP [19] builds routing subproblems using demand and capacity information during decomposition. Finally, Random assigns 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.3 Compared 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 -Ind baselines. 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 [31] in Or-Tools implementation [30].

The fourth category consists of complete routing frameworks that do not explicitly separate decomposition and routing. We consider ScaleNet [32], a learning-based routing framework, and Hybrid Genetic Search (HGS) [33], one of the strongest general-purpose metaheuristics for the CVRP.

4.2 Performance 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 [34] 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 \([2d_{\max},5d_{\max}]\), where \(d_{\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 of \(0.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 ¿tbl:tab:ags95results? and ¿tbl:tab:large95results?, respectively.

Tables ¿tbl:tab:ags95results? and ¿tbl:tab:large95results? 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.3 Sensitivity 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.

4.3.1 Sensitivity 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 the Grid decomposition method. The number of routing subproblems is varied over \(\{9, 49, 100, 484, 961\}\) (all have integer square-roots and are closest to \(\{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 4 (a) 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.2 Robustness 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, where \(1\%\), \(25\%\), \(50\%\), \(75\%\), and \(99\%\) of the routing subproblems are initialized without assigned vehicles. The three routing strategies (Ind, Reopt, and CoRC) 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 4 (b) 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.

5 Conclusion↩︎

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.

6 Code and Data Disclosure↩︎

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

References↩︎