acceptodds
Under review as a conference paper at ICLR 2027

POST-PARTITION BOUNDARY RELAXATION FOR REAL-TIME CLUSTER-FIRST LARGE-SCALE VEHICLE ROUTING

Abstract

Large-scale capacitated vehicle routing problems (CVRPs) can require substantially more computation than strict real-time budgets allow, motivating cluster-first decomposition into smaller routing subproblems. Yet decomposition silently fixes a modeling choice: how strongly the resulting cluster boundaries should be enforced. We introduce Post-Partition Boundary Relaxation (PBR), a learning-free mechanism that selectively relaxes these post-partition commitments. Given a fixed partition, PBR scores each customer by its assignment margin, the gap between its strongest and second-strongest cluster assignment, and uses these solver-free ambiguity scores to identify boundaries for joint reoptimization. Rather than moving individual customers directly, PBR reopens selected neighboring cluster pairs and lets the routing solver determine the resulting reassignment. We evaluate PBR on large-scale CVRP instances under strict real-time deadlines. At nodes, monolithic optimization requires approximately seconds, motivating cluster-first decomposition to substantially reduce routing latency. Across 594 instances, PBR shortens routes on 593, reducing mean and median cost by relative to strict decomposition. Matched random boundary selection is substantially weaker, showing that the improvement is not explained by additional joint reoptimization alone, but by where reoptimization is applied. The benefit, however, depends on the computational regime. It disappears when the residual time budget cannot absorb the larger merged subproblems. These results show that decomposition quality is not determined by the partitioner alone: post-partition commitment is an independent algorithmic design axis, and inexpensive ambiguity signals can identify where that commitment should be relaxed.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Cluster-First-Route-Second, Capacitated Vehicle Routing Problem, Neural Combinatorial Optimization, Large-Scale Real-Time Decision Making

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_w6P9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies cluster-first-route-second (CFRS) decomposition for large CVRPs under tight latency budgets. It proposes Post-Partition Boundary Relaxation (PBR), a learning-free step applied after a fixed partition.

How PBR works:

  • Each customer gets a normalized margin between its distances to the centroid of its assigned cluster and to the second-nearest centroid (Eq. 1). Customers with margin below τ are "ambiguous".
  • Each cluster pair is weighted by the number of ambiguous customers between them (Eq. 2).
  • The deployed selector orders clusters into a chain (a nearest-neighbor tour over per-cluster anchors) and greedily takes non-overlapping consecutive pairs with w > 0.
  • Each selected pair is merged into one sub-CVRP and re-solved with PyVRP; all other clusters are solved independently, as in strict decomposition.

On 594 synthetic uniform instances with N = 10,000 and K = 24, PBR improves over strict decomposition on 593 instances (mean paired improvement 3.29%), while monolithic PyVRP needs about 18 s to reach its first useful checkpoint. Supporting experiments include matched random-boundary and fixed-candidate controls, sweeps over K, τ, partitioner checkpoint and chain anchor, a capacitated k-means portability study at N ≤ 1000, the CVRPLIB X-set under a 0.9 s budget (51 better / 11 worse among 62 solved instances), and a learned merge-value selector that does not improve on the hand-crafted score. The authors conclude that post-partition commitment is an independent algorithmic design axis.

Critical strengths
  1. Simple, cheap, and consistently effective. PBR needs no training and no extra solver calls for selection, and it leaves the partitioner untouched, so it can be added to any CFRS pipeline. With the same partition, solver and per-subproblem budget as strict decomposition, it improves 593 of 594 instances at N = 10,000 (mean 3.29%) and stays positive across K = 26–32, six τ values, six partitioner checkpoints and two partition sources. For anyone running cluster-first pipelines this is an easy, low-risk improvement, and this practical value is the main reason for my positive score.

  2. A useful framing, backed by honest controls. Separating "where to partition" from "how strongly to enforce the partition" is a clean way to think about CFRS pipelines. The paper supports it with a coarser-partition control (strict K = 12) and matched random-boundary and fixed-candidate controls. It also reports its own limits: the learned selector does not help, and the gain is not significant when little time remains. This makes the scope of the method easy to judge and gives later work a clear baseline.

Critical weaknesses

1. It is not yet clear how much of the gain comes from where boundaries are reopened, as opposed to merging clusters at all. This is the paper's main conceptual claim (RQ3 and the abstract), so it deserves a direct test.

What I see:

  • The selector reopens 11.2 of at most 12 pairs on average (l. 270), so about 22 of 24 clusters end up merged. Since 11.2 ≤ 11 + x, at least 20% of instances reopen every possible pair. The deployed rule accepts any chain pair with w > 0 (l. 186–187).
  • The gain is nearly unchanged across a sixfold range of τ (0.09 pp, Supp. Table 1), and across anchor choices that change the selected boundaries "substantially" (at most 0.11 pp, Supp. Sec. 1.5).
  • The random control does favor ambiguity (median percentile rank 30%, p = 8.2×10⁻¹²), but only ranks are reported, so the size of the advantage is unknown.

Suggestions (most can use runs the authors already have):

  • Report how many pairs are reopened at each τ, and what share of ambiguous customers have a negative margin. These customers are ambiguous by construction since τ > 0 (l. 140–142).
  • Add one ablation that pairs consecutive chain clusters while ignoring w (w ≡ 1).
  • Report cost differences, not only ranks, between PBR and the random selections.
  • Report the correlation between w(k,ℓ) and the realized merge value v(k,ℓ), using the labels collected for Sec. 4.4.

If ambiguity adds value, these results will make the central claim much stronger. If most of the gain comes from pairing itself, the method is still useful; the paper would then present it as cheap adaptive coarsening rather than ambiguity-driven selection.

2. The real-time evaluation needs a compute-matched comparison and at least one external reference point. PBR is motivated by strict deadlines, but readers cannot yet tell whether the 3.3% is a better use of time than the alternatives.

What I see:

  • For Table 1, the main text gives no deadline, hardware or parallelism. The supplement suggests a 0.9 s budget for this configuration (Supp. Sec. 1.2, Table 4), yet Table 1 reports 1.310 s (strict) and 1.509 s (PBR). PBR's measured wall-clock is 15% higher, so equal per-subproblem allocation (l. 266–268) is not equal total time.
  • The comparators are strict decomposition, cold-start monolithic PyVRP, and a one-pass sweep without local search (24.6× worse than monolithic). The paper therefore does not show where PBR stands against other ways of spending the same time. After PBR the solution is still 9.8% above the monolithic reference.

Suggestions (feasible within the same code base):

  • State the deadline, hardware, thread count, and how MaxRuntime is assigned to a merged pair.
  • Add a strict-decomposition arm that receives PBR's total wall-clock.
  • Add a quality-vs-time curve that includes PyVRP warm-started from the strict-decomposition solution. This uses the same solver and is the most natural competitor for the extra time.
  • Apply PBR on top of one learned CFRS pipeline the paper cites (e.g., GLOP or Hou et al.), or compare at equal time with one fast large-scale heuristic (e.g., FILO2). This would show PBR is a general plug-in, and it would also connect the paper more directly to the ICLR learning-for-optimization audience.

Additional suggestions for the revision (not decisive for my score):

  • Scope of claims. The claim of an "independent design axis" would be better supported by varying partition quality together with PBR. Currently the gain is larger for the weaker k-means partitioner (Supp. Table 3) and for finer partitions, which suggests the two interact. Likewise, the abstract's "the benefit disappears" rests on 22 instances (13/9, p = 0.52); a budget sweep at fixed N = 10,000 would test this directly.
  • Related work. A short related-work section would sharpen the contribution. Decomposition phases in HGS for large instances (Vidal, Crainic, Gendreau & Prins, 2013), the decomposition strategies of Santini et al. (2023), and POPMUSIC (Queiroga, Sadykov & Uchoa, 2021) also relax partition commitment. Stating precisely what PBR adds would help (it works at the boundary level, needs no solver for selection, and runs in one shot).
  • Method description. Present the deployed chain-greedy rule as the method (e.g., in pseudo-code), with Eq. 3 as its idealized form, and state how "spatially adjacent" is determined (l. 147–149).
  • X-set setup. With K = 24 fixed, X-set instances have about 4–42 customers per cluster. Scaling K with N and adding a monolithic row would make this experiment more informative. Using the neural partitioner (0.036 s) could also avoid the 38 deadline failures of k-means.
  • Consistency. The abstract reports a 3.3% median that does not appear in the body, and the K = 26 p-value in Supp. Table 2 should be 5.8×10⁻⁸ for 29/1.
Questions for authors
  1. Budget protocol (clarification). What is the deadline, and on what hardware and how many threads are subproblems solved, sequentially or in parallel? How is MaxRuntime set for a merged pair? What explains the 1.310 s / 1.509 s in Table 1, given the 0.9 s budget in the supplement? And what does strict decomposition achieve when given PBR's total wall-clock?
  2. Where vs. how much (additional analysis). How many pairs are reopened at each τ, and what does pairing consecutive chain clusters with w ignored (w ≡ 1) achieve? What are the cost differences between PBR and the random selections?
  3. Instance parameters (clarification). For the N = 10,000 instances, what are the vehicle capacity, depot location and mean route length, and how many routes do the monolithic, strict and PBR solutions use? If monolithic uses fewer routes than K, part of the gain may come from pooling vehicles across merged clusters, which would be useful to know when interpreting the mechanism.
  4. Selector choice (clarification). Sec. 4.4 reports that exact matching is both better (0.61–0.77%) and faster (4.99 ms vs 12.12 ms) than the greedy traversal. Why is the greedy rule kept, given that the number of pairs could be set to what the greedy rule selects?
  5. Consistency (clarification). Supp. Table 1 reports 28/2 on "the first 30 instances of the main evaluation set", while the main result is 593/1 on 594. Do these come from different budgets or runs?

My weak-accept score assumes that the budget protocol can be clarified and that the w ≡ 1 and equal-wall-clock comparisons (Q1, Q2) support the paper's claims. If the gain largely disappears at equal total time, I would lower my score. If the ambiguity signal clearly beats w ≡ 1 pairing, I would consider raising it.

5 comments
AuthorsOpenReview ↗

Reply to Weakness 1 and Question 2

Thank you for proposing this test. We ran the w ≡ 1 ablation you requested. With the revised selector, choosing which boundaries to reopen outperforms pairing every consecutive chain pair on 625/787 new instances at a 1.5 s deadline, with a median route-length reduction of 0.78%.

W1, Q2. How much of the gain comes from where boundaries are reopened, rather than from merging at all?

The submitted rule. Your analysis was accurate: the chain traversal reopens 11 or 12 of the 12 possible pairs on 98% of instances, which leaves little room for selection. Against w ≡ 1 it was shorter on 206 and longer on 181 of the 388 instances with fewer than 12 merges, which is not a significant difference. Against random pairings with the same merge count it was shorter on 249/388, by 0.37% in median (post hoc).

The revised selector. After the reviews we adopted the option you raise in Q4: the traversal now sets only the number of merges, and exact minimum-margin matching chooses the pairs. We tested it in a pre-specified experiment on 1,200 new instances, with the same partition, end-to-end deadline, and feasible-initialization safeguard for every rule. The rules can differ only where fewer than 12 pairs are merged: 787 instances at 1.5 s, and 396 of the first 600 at 1.2 s.

Revised selector versus1.5 s1.2 s
Every chain pair merged (w ≡ 1)625/787 wins; median reduction 0.78%321/396; 0.83%
Random pairing, same merge count651/787; 1.00%330/396; 1.02%
Centroid-distance pairing, same merge count441 wins / 328 losses; 0.05%172 / 141; 0.00%

What the controls show.

  • Merging itself has the larger effect. Randomly chosen pairs already improve over strict decomposition by approximately 2–3%.
  • Where boundaries are reopened adds to it: about 1% of route length beyond random pairing, and 0.8% beyond w ≡ 1, at both deadlines.
  • The margin is one effective signal, not the only one. Its advantage over centroid distance is small: significant at 1.5 s (p = 5 × 10⁻⁵) but not at 1.2 s (p = 0.09). Where the two rules select different pairs (post hoc), the margin yields shorter routes in 62% and 60% of cases.

These are distinct comparisons, not an additive decomposition of the total gain.

What we claim. The selector itself is not the paper's main contribution, and the revision does not claim that the margin rule is superior to centroid distance. The contribution is the decision itself: reopening selected boundaries after partitioning and before any route is built. The controls show that this decision benefits from choosing the pairs rather than merging at random or merging every pair, and that an inexpensive geometric signal is enough to do so; the margin is one such signal.

Pairs reopened at each τ. (recall that τ is the threshold that decides which customers count as “ambiguous”). Of 12 possible pairs, the submitted rule reopens 11.3 on average at every τ. The table counts the 600 evaluation instances by number of reopened pairs:

τ10 pairs11 pairs12 pairs
0.0514379207
0.15 (default), 0.2, 0.314374212

The number changes on only 5 of the 600 instances across this range of τ, consistent with a gain that barely varies with τ.

The other analyses you requested.

  • Negative margins. About 18% of customers are closer to another cluster's centroid than to their own, so they are ambiguous at any τ, as you point out. They make up 79% of the ambiguous customers at τ = 0.05, 54% at the default τ = 0.15, and 35% at τ = 0.3.
  • Correlation with merge value (exploratory, Section 4.4 labels). w was not stored with the labels; the closest stored quantity is the pair's share of contested customers. Its within-instance rank correlation with realized merge value is positive in 91% of instances (median 0.29; 0.17 after accounting for merged size). The pair's minimum margin is a stronger predictor: median −0.41 (smaller margins go with larger savings), against −0.25 for centroid distance.

Following your comment, the revision reports these analyses and presents PBR as you suggest: selective coarsening before routing, rather than ambiguity-driven selection.

We address W2 (time budget and external reference points) and the rest of your concerns in separate comments.

AuthorsOpenReview ↗

Reply to Weakness 2 and Question 1

Thank you for pressing on the budget accounting. You were right that equal per-subproblem limits did not give equal total time, so we re-ran the comparison under a common end-to-end deadline. The gain holds at equal total time: at 1.2 and 1.5 s, PBR produces shorter routes than strict decomposition on 578/600 and 582/600 instances, with 2.7% lower mean route length, while returning earlier and with less solver time per subproblem.

W2 (time budget), Q1. What is the budget protocol, and what does strict decomposition achieve with PBR's total wall-clock?

Protocol.

  • Hardware and parallelism. One L40S GPU runs the partitioner. 32 CPU cores solve all subproblems in a single parallel wave, one single-threaded PyVRP process per subproblem.
  • Submission. Each subproblem, merged or unmerged, received the same MaxRuntime: 0.9 s minus the partition time. The 0.9 s was therefore a per-subproblem solver limit, not a deadline. Table 1's 1.310 s and 1.509 s are end-to-end times, which add process start-up and I/O; the solver limit is also not a hard stop.
  • Revision. Both methods face one end-to-end deadline covering partitioning, selection, initialization, start-up, I/O and routing. MaxRuntime is the deadline minus the elapsed pre-solve time and an overhead allowance calibrated on 100 separate instances. Within a run, a merged pair and a single cluster receive the same value.

Results under a common deadline (600 evaluation instances). PBR uses the submitted selector and includes the feasible-initialization safeguard introduced after the reviews (one capacity-feasible starting solution per subproblem). Giving strict decomposition the same safeguard leaves the 1.2 and 1.5 s counts unchanged (578 and 582).

DeadlinePBR returns afterStrict returns afterPBR shorterMean route-length difference
0.9 s0.71 s0.92 s227/6000.9% longer
1.2 s1.07 s1.15 s578/6002.7% shorter
1.5 s1.13 s1.50 s582/6002.7% shorter

Return times are averages. The deadline is a budget target rather than a hard stop, and route-length statistics include all returned solutions.

Strict decomposition at PBR's wall-clock. PBR's 1.5 s runs return after 1.13 s on average. Three sets of strict-decomposition runs bracket this value:

Strict returns afterPBR (1.13 s) shorterMean reduction
0.98 s (stopped early)593/6003.2%
1.15 s (its 1.2 s runs)586/6002.9%
1.50 s (its 1.5 s runs)582/6002.7%

PBR is shorter whether strict decomposition has less, about equal, or more wall-clock, so the measured gain is not explained by extra time. The first two rows are post hoc comparisons.

With the revised selector (1,200 new instances, same protocol and safeguard), PBR is shorter on 1,190 and 1,185 instances at 1.2 and 1.5 s, by 3.3% and 3.1% in mean.

Measured limits.

  • At 0.9 s, PBR has about 0.08 s of solver time per subproblem and its routes are 0.9% longer in mean. The advantage is supported at the tested 1.2 and 1.5 s deadlines.

These are measured outcomes at matched time; why merging helps is a separate question, which we discuss under Q3.

Following your comment, the revision states the deadline, hardware, parallelism and MaxRuntime rule explicitly, and reports strict decomposition at PBR's wall-clock.

We address the external reference points (warm-started PyVRP, GLOP, FILO2) in the next comment.

AuthorsOpenReview ↗

Reply to W2 (external reference points)

Thank you for proposing these reference points. You suggested a learned pipeline or a fast heuristic; we ran both, and the warm-started PyVRP comparison. PBR works as a plug-in on clusters derived from GLOP: it generates shorter routes than strict decomposition on 559/600 instances, by 3.7% in median. At a 1.5 s deadline it also outperforms the one tested alternative that returns in time, while the tested GLOP, FILO2 and monolithic PyVRP configurations return their first solutions after the deadline.

W2 (external reference points). Where does PBR stand against other ways of spending the same time?

PBR here includes the feasible-initialization safeguard introduced after the reviews. All experiments use 10,000-customer instances.

Plug-in on a learned pipeline (GLOP). We split GLOP's routes into 24 clusters and compared strict decomposition with PBR on them, with the same solver and the same solver limit (0.48 s). PBR is shorter on 559/600 instances, by 3.7% in median. The gain therefore carries over to a partition produced by a different learned pipeline, which supports the plug-in use you describe. Two qualifications:

  • GLOP's partition time is not charged. With its released checkpoint, evaluated outside its training distribution, GLOP took 2.7–4.1 s on these instances, so this tests PBR as a plug-in, not GLOP followed by PBR as a real-time pipeline.
  • On GLOP's own instance distribution, where a cluster holds about seven routes, PBR is not better than strict decomposition (87 shorter, 113 longer of 200). The gain is observed where clusters hold about one vehicle load (see Q3).

Equal time against FILO2. FILO2, with route minimisation off, returned its first solution after 1.85–1.93 s in all 200 timed runs, so it delivered no solution at the 1.2 and 1.5 s deadlines, where PBR does. With more time FILO2 is stronger: its routes at 2 s are shorter than PBR's 1.2 s routes.

Warm-started monolithic PyVRP. We ran single-thread monolithic PyVRP, cold and warm-started from the strict-decomposition solution, with limits from 2 to 20 s on 100 instances. Its first solution arrived after 16 s or more in every run, so its quality-vs-time curve has no point near our deadlines. Warm-starting did not change the result (mean route length 85.2, against 85.1 cold). These solutions are approximately 9% shorter than PBR's, which is the quality available when time is not the constraint.

A same-solver alternative that does return in time. We also implemented an L2D-style baseline: it solves each cluster, then uses the remaining time to re-solve pairs of neighboring routes, keeping a pair only if it is shorter (our implementation, with a heuristic in place of L2D's learned selector). At the same end-to-end deadline, PBR with the revised selector is shorter on 275/300 new instances at 1.5 s, by 1.9% in median. Details are in our reply to Reviewer 3yVz.

What the comparisons establish. PBR improves on strict decomposition at the 1.2 and 1.5 s deadlines and on the tested incumbent-based reoptimization at 1.5 s, when the other tested methods have not yet returned a solution. From about 2 s, FILO2 gives better routes. These are measured operating points on our hardware, not a universal crossover.

Following your comment, the revision positions PBR against a learned pipeline (GLOP), an L2D-style reoptimization baseline and a state-of-the-art heuristic (FILO2), and states the deadline range in which the results support it.

We address your additional suggestions and Q3–Q5 in separate comments.

Reviewer_3yVzOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the large-scale capacitated vehicle routing problem (CVRP) under a strict time budget. The method of clustering first and then routing can reduce the computational cost of solving, but the fixed cluster boundaries prevent cross-cluster coordination, resulting in a loss of solution quality. Therefore, the authors propose a learning-free post-processing mechanism, PBR. Based on the given partition, PBR identifies ambiguous customers using the normalized difference between their distances to the assigned cluster centroid and the nearest alternative cluster centroid. It counts ambiguous customers for each cluster pair to obtain its boundary weight, and then uses greedy matching to select a group of non-overlapping adjacent cluster pairs. The selected pairs are merged and handed over to the downstream solver (PyVRP) for joint solution. The remaining clusters are still solved independently. Assignment ambiguity is only used to determine where to restore coordination, and how to redistribute customers is decided by the solver.

The authors evaluated it on synthetic instances and the CVRPLIB X-set. In the main experiment with N=10,000, PBR improved 593 instances compared to strict decomposition, with an average route cost reduction of approximately 3.3% and an average end-to-end running time increase from 1.31 s to 1.51 s. When the number of reopened boundaries is held fixed, selecting boundaries based on assignment ambiguity is significantly better than random selection, indicating that the benefits come from the selection of boundary positions rather than just additional joint optimization. However, when the remaining time budget after partitioning is insufficient to solve the larger merged subproblems, the advantage of PBR disappears.

Critical strengths

Simple and easy to integrate. PBR requires no additional training and can be plugged into existing cluster-based routing pipelines, which reduces the burden of extra training and system modification.

Consistent improvements. PBR achieves fairly consistent improvements over strict decomposition, and the gains persist across the tested parameter and partitioner settings, suggesting that the effect is not limited to a particular configuration.

Critical weaknesses

Firstly, missing baselines. The main comparisons focus on strict decomposition, monolithic PyVRP, a naive sweep heuristic, and internal selection variants. There is no comparison with established large-scale routing frameworks such as GLOP (Ye et al., 2024) and L2D (Li et al., 2021), leaving PBR’s practical competitiveness unclear. In particular, the paper lacks a direct comparison with closely related route-group reoptimization strategies (Li et al., 2021). Boundary-customer local search (Kerscher & Minner, 2025) is also relevant, although its time-window setting would require appropriate adaptation for a fair CVRP comparison. The learned selector in Section 4.4 is inspired by Li et al. but still operates within the cluster-pair framework. While the random-selection controls provide evidence that boundary selection matters, they do not establish the added value of the cluster-pair formulation over existing subproblem reoptimization strategies.

Secondly, unclear time budget. The paper states that strict decomposition and PBR share the same computational budget and later specifies equal per-subproblem time allocations. However, the main experiment reports average end-to-end runtimes of 1.310 s and 1.509 s, respectively, so the comparison does not match total runtime. The paper does not fully explain how the per-subproblem allocations and other computational overheads relate to the overall budget. Without a comparison at equal total runtime, it remains unclear whether PBR’s quality advantage persists under the same overall wall-clock budget.

Thirdly, limited technical novelty. The core mechanism is relatively simple: ambiguous customers are identified by a centroid-distance margin, counted for each cluster pair, and used to greedily merge adjacent clusters. Selectively reoptimizing across decomposition boundaries has been explored in prior work (e.g., Li et al., 2021; Kerscher & Minner, 2025), so the main novelty seems to lie in using boundary-level ambiguity as the selection signal rather than in the reoptimization idea itself. The gains are also somewhat modest. PBR improves over strict decomposition by about 3.3% but remains roughly 10% behind monolithic optimization at N=10,000, and its median gap to the best-known CVRPLIB solutions stays above 10%. It would strengthen the paper to clarify more explicitly what PBR offers beyond existing boundary-reoptimization approaches.

Questions for authors
  1. Choice of baselines. Could the authors explain why representative large-scale routing frameworks such as GLOP (Ye et al., 2024), and in particular route-group reoptimization approaches such as L2D (Li et al., 2021), were not included in the comparison? Is this due to differences in problem setting, budget, or implementation constraints, or were such results obtained but not reported? These methods are closely related to the positioning of this paper and would help clarify the added value of PBR.

  2. Definition of the computational budget. According to Table 1, the mean end-to-end runtimes of strict decomposition and PBR are 1.310 s and 1.509 s, respectively. Could the authors clarify how per-subproblem time is allocated to merged subproblems, and how partitioning, initialization, and other overheads are counted toward the overall budget? Do the authors have results comparing the two methods under the same end-to-end runtime?

  3. Which selector is evaluated in the random-selection controls? Section 2 (p. 4) describes the deployed implementation as a single traversal along the cluster chain that selects a boundary whenever w(k,ℓ)>0w(k,\ell) > 0 and neither endpoint has already been selected. In contrast, Section 4.3 (p. 7) states that PBR ranks the contested boundaries by their ambiguity scores. Could the authors clarify whether different selector variants were used, and which implementation each set of results corresponds to? This determines whether the random-selection controls support the default PBR selector or a different selection rule.

5 comments
AuthorsOpenReview ↗

Reply to Weaknesses 1 and Question 1 (baselines)

Thank you for identifying the missing comparisons. The new experiments show that PBR improves over an effective route-group reoptimization baseline under matched end-to-end deadlines, and establish its practical position relative to the tested GLOP and FILO2 implementations at short budgets.

W1, Q1. How does PBR compare with established large-scale methods?

We conducted these comparisons after the reviews on 10,000-customer instances. The submission compared PBR with the pipeline it modifies and with monolithic solving, and did not run external frameworks; the experiments below add them. PBR here includes the feasible-initialization safeguard introduced after the reviews. The route-group comparison also uses our revised rule for choosing which pairs to merge (see our reply to Q3).

Route-group reoptimization: a direct test of the pre-routing approach. We implemented an L2D-style baseline. It first solves each cluster separately to obtain a complete solution, then uses the remaining time to re-solve pairs of neighboring routes jointly, keeping a re-solved pair only if it is shorter. A simple rule (nearest route centroid) chooses the pairs, in place of L2D’s learned model. Both methods use PyVRP and the same end-to-end deadline. PBR supplies a capacity-feasible initialization to every subproblem. The L2D-style comparator's initial strict-decomposition phase does not use this safeguard; its route-pair reoptimization phase starts from a capacity-feasible construction rather than the incumbent routes, retaining a reoptimized solution only if it improves on the incumbent.

PBR is superior on 275/300 new instances at 1.5 s and 270/300 at 3.0 s, with median route-length reductions of 1.9% and 1.4%, respectively. The baseline itself improves over strict decomposition on 280/300 instances at 1.5 s and all 300 at 3.0 s. Thus, PBR's advantage is measured against a reoptimization procedure that is itself consistently superior to strict decomposition run to the same deadline. The advantage also persists at the longer deadline.

The timing breakdown clarifies how the methods use the budget. At 1.5 s, the baseline has 0.20 s of solver time for incumbent construction and 0.25 s for reoptimization; PBR has a single solve of 0.47 s. At 3.0 s, the baseline's second phase receives 1.19 s. These measurements describe the allocation of routing time; they do not independently isolate the cause of the quality difference.

This comparison supports the practical value of selecting cluster pairs before constructing routes. The baseline uses our heuristic selector rather than L2D’s published learned selector, which would have to be retrained for these instances and adapted to a single reoptimization round. That does not fit the discussion period, so the comparison remains outstanding. The present test is still informative on the question you raised: the baseline already re-solves nearly all routes (on average 12 pairs of about 24), so a learned selector could change which routes are paired, but not the solver time a two-phase design leaves for each solve.

GLOP: measured time to first solution. With its released checkpoint and settings, GLOP returned its first solution in 2.7–4.1 s across all 600 tested instances. None was available within either the 1.2 or 1.5 s deadline. The checkpoint is evaluated outside its training distribution; this finding therefore characterizes the released configuration on our instances, rather than a retrained model.

FILO2: solution availability and subsequent quality. Single-thread FILO2 returned its first solution in 1.85–1.93 s across 200 timed runs. None met the 1.2 or 1.5 s deadlines. With additional time, FILO2 achieves better route quality: its 2 s solutions are shorter than PBR's 1.2 s solutions.

What the comparisons establish. Under the measured short deadlines, PBR provides a practical way to improve cluster-first routing: it outperforms the tested incumbent-based reoptimization alternative, while the tested GLOP and FILO2 implementations do not return their first solutions within 1.2–1.5 s. FILO2's stronger quality with additional time makes the operating trade-off explicit.

Finally, Kerscher & Minner’s method, designed for time windows, was not adapted to this CVRP setting and was not run given the limited discussion time.

Following your comments, we have strengthened the paper’s empirical basis by adding a matched-deadline route-group reoptimization comparison and external timing benchmarks for GLOP and FILO2. These additions clarify both the practical value of PBR’s pre-routing approach and the computational regime in which the measured results support its use.

We will address the remaining concerns about budget accounting, selector attribution, novelty, and presentation in a separate comment.

AuthorsOpenReview ↗

Reply to Weaknesses 2 and Question 2 (time budget)

Thank you for raising the budget question. The new evaluation shows that PBR's improvement persists when all pipeline costs are charged to a common end-to-end budget. At the 1.2 and 1.5 s settings, PBR produces shorter routes on 578/600 and 582/600 instances, respectively, with 2.7% lower mean route length at both settings.

W2, Q2. Does the improvement persist when total runtime is accounted for?

Submitted protocol. Each subproblem, merged or unmerged, received the same solver limit: 0.9 s minus partition time. All subproblems ran in one parallel wave. Start-up and I/O were excluded, and the solver limit was not a hard stop. The submission therefore matched per-subproblem limits rather than total elapsed time, explaining the 1.310 s and 1.509 s runtimes in Table 1.

New end-to-end protocol. We re-ran the comparison with a common deadline covering partitioning, selection, initialization, process start-up, I/O, and routing. Each subproblem's solver limit is the deadline minus elapsed pre-solve time and an overhead allowance calibrated on 100 separate instances. Within a run, merged pairs and single clusters receive the same limit. PBR includes the feasible-initialization safeguard introduced after the reviews.

Requested deadlinePBR shorter than strictMean route-length differencePBR on timeStrict on time
0.9 s227/6000.9% longer586/600258/600
1.2 s578/6002.7% shorter553/600422/600
1.5 s582/6002.7% shorter596/600298/600

Route-quality statistics include all returned solutions, including late ones; deadline compliance is reported separately. The requested deadline is therefore a budget target, not a guaranteed stopping time. On-time counts depend on each method's calibrated overhead allowance; in a later run on 1,200 new instances (run at the 1.2 and 1.5 s deadlines only), both methods were on time in at least 99% of runs.

The improvement does not require PBR to run longer. At the 1.5 s setting, PBR returns after 1.13 s on average, versus 1.50 s for strict decomposition. Strict decomposition receives about twice as much solver time per subproblem, yet PBR produces shorter routes on 582/600 instances. This directly addresses the concern that the quality gain merely reflected PBR's longer measured runtime.

An additional post hoc runtime control from the same evaluation gives a consistent result. Strict decomposition, stopped after 0.98 s on average, has nearly the same solver time per subproblem as PBR (0.50 s versus 0.48 s). PBR produces shorter routes on 593/600 instances, with a 3.3% median reduction.

Measured limits. At 0.9 s, PBR has approximately 0.08 s of solver time per subproblem and produces routes that are 0.9% longer in mean. Its quality advantage is therefore supported at the tested 1.2 and 1.5 s settings.

Following your comment, the revision distinguishes per-subproblem solver limits, requested end-to-end deadlines, and achieved runtimes. The new evidence strengthens the practical result: at the 1.2 and 1.5 s settings PBR returns better solutions, and at 1.5 s it does so with lower average elapsed time.

We will address selector attribution (Q3), novelty, and presentation in a separate comment.

AuthorsOpenReview ↗

Reply to Question 3 (selectors)

Thank you for these questions. We have clarified which selector produced each result and added a direct test of score-based selection: at a fixed merge count, the revised selector improves over random pairing on 651/787 new instances, with a median route-length reduction of 1.00%.

Q3. Which selector did the random-selection controls evaluate?

The submission used two variants:

  • First random control: the deployed chain traversal from Section 2. Its solution cost was ranked among 20 random selections with the same merge count, giving a median percentile rank of 30%.
  • Fixed-candidate control: exact minimum-margin matching. This evaluated score-based selection rather than the deployed traversal.

The fixed-candidate result therefore supports the scored selector, while the first control evaluates the submitted implementation. The revision makes this distinction explicit and maps every result to its selector.

Revised default and new controls. After the reviews, we made minimum-margin matching the default; the traversal now determines only the merge count. We evaluated this default with the initialization safeguard in a pre-specified experiment on 1,200 new instances at a 1.5 s end-to-end deadline. Among the 787 instances where the merge count leaves a choice:

Revised selector versusResult
Random pairing, same merge count651/787 wins; median reduction 1.00%
Unconditional pairing of neighboring clusters625/787 wins; median reduction 0.78%
Centroid-distance pairing, same merge count441 wins / 328 losses; median reduction 0.05%

These controls show that selecting the pairs adds value beyond random or unconditional merging, and both results repeat at 1.2 s (330 and 321 wins of 396). Centroid distance is also competitive, indicating that useful selection need not depend exclusively on the margin. In a post hoc analysis of cases where the margin and centroid rules select different pairs, the margin yields shorter routes in 62% of cases.

For the submitted traversal, a separate post hoc comparison against random pairing at fixed merge count gives 249/388 wins and a median reduction of 0.37%. We report this separately from the new default’s results.

We clarity that the selector itself is not the paper’s main contribution, and we do not claim that the margin rule is superior to centroid distance. The contribution is the decision itself: reopening selected boundaries after partitioning and before any route is built. The controls show that this decision benefits from choosing the pairs rather than merging at random, and that an inexpensive geometric signal is enough to do so; the margin is one such signal.

We address novelty (W3) and presentation in a separate comment.

Reviewer_qLTfOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Post-Partition Boundary Relaxation (PBR) for large-scale CVRP. Starting from a fixed partition, PBR measures assignment ambiguity using distances to cluster centroids, counts ambiguous customers for each cluster pair, and merges non-overlapping pairs for joint optimization. On the main 10,000 customer dataset, PBR improves over strict decomposition on 593 of 594 instances, with an average paired improvement of 3.29%. Further experiments examine different partitioners and parameter settings. The gains are less clear when little routing time remains after partitioning.

Critical strengths

The selection step needs neither training nor an initial routing solution. It can use an existing hard partition without changing or retraining the partitioner, which makes PBR straightforward to add to a cluster-first routing pipeline.

Critical weaknesses
  1. I found the overall idea familiar. Earlier work already selects groups of routes for reoptimization [1, 2], and uses cluster-membership information to guide improvements across boundaries [3]. The contribution therefore rests largely on the margin-based selection rule. The comparisons with strict decomposition and random selection show that PBR can help, but do not show what this rule adds over an inexpensive alternative such as pairing clusters by centroid distance. I learned relatively little about when the margin criterion is useful or why it should be preferred.

  2. It is unclear which selector produced the results in Section 4.3. Section 2 describes a chain traversal that selects eligible pairs whenever w(k,ℓ)>0w(k,\ell)>0. This procedure does not rank positive weights. Section 4.3, however, describes ranking boundaries by their ambiguity scores, including when the candidate set is held fixed. This difference matters because the evidence for score-based selection may concern a different algorithm from the deployed PBR rule.

References [1] Sirui Li, Zhongxia Yan, and Cathy Wu. “Learning to Delegate for Large-scale Vehicle Routing.” Advances in Neural Information Processing Systems, 34, 2021. Paper.

[2] Alberto Santini, Michael Schneider, Thibaut Vidal, and Daniele Vigo. “Decomposition Strategies for Vehicle Routing Heuristics.” INFORMS Journal on Computing, 35(3):543–559, 2023. DOI: 10.1287/ijoc.2023.1288.

[3] Christoph Kerscher and Stefan Minner. “Decompose-route-improve Framework for Solving Large-scale Vehicle Routing Problems with Time Windows.” Transportation Research Part E: Logistics and Transportation Review, 204:104409, 2025. DOI: 10.1016/j.tre.2025.104409.

Questions for authors
  1. Does the margin criterion identify useful merges that a centroid-distance pairing rule would miss? A small comparison on the existing instances, with the same initial partitions, merge count, and routing budget, would answer this. An analysis of the already generated merge-gain data that compares the two signals would also be useful.

  2. Which selector was used in each Section 4.3 experiment, and how does it relate to the w(k,ℓ)>0w(k,\ell)>0 traversal in Section 2? For the exact-matching experiment in Section 4.4, was the prescribed merge count matched to the greedy method on each instance? Please also state how the routing budget was allocated between the methods.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Revision

We thank the reviewers for their careful and constructive reviews. We will upload the revised manuscript as soon as possible. The reviewers' comments have made the paper substantially stronger in its evidence, its scope and its presentation, and we are grateful for them. We hope you will find the revised manuscript worthy of publication at ICLR.

Main revisions.

The feasible-initialization safeguard. Our replies refer to a safeguard introduced after the reviews. While preparing the revision, we examined rare instances, about 1–2% in the new experiments, on which PBR without the safeguard returned an outlier solution (more than 1.5 times as long as strict decomposition's). The cause we identified is the solver's initialization: PyVRP starts each solve from random initial solutions, and a tight solver limit can leave too little time to improve them in a large merged subproblem. The safeguard adds one capacity-feasible solution to the initial population of every subproblem (customers ordered along a space-filling curve and split by capacity). It takes under a millisecond per subproblem, is charged to the deadline, and leaves the selection and merging steps unchanged. Across the 22,200 runs in which PBR used the safeguard, it never returned an outlier solution; its longest solution was 7.7% longer than strict decomposition’s. The safeguard is also not the source of PBR's advantage: when strict decomposition is given the same safeguard, PBR remains superior on the same number of instances (578 and 582 of 600 at 1.2 and 1.5 s).

  • End-to-end evaluation (3yVz, w6P9). Both methods now face one deadline that covers partitioning, selection, initialization, start-up, I/O and routing. Under a common end-to-end deadline, the revised PBR is superior to strict decomposition on 1,190/1,200 new instances at 1.2 s and 1,185/1,200 at 1.5 s, with mean route-length reductions of 3.3% and 3.1%. PBR is also superior on 578 and 582 of the 600 original instances at 1.2 and 1.5 s, while returning earlier on average.
  • Revised selector and selection controls (qLTf, 3yVz, w6P9). Minimum-margin matching now chooses the pairs, and the submitted chain traversal sets only the number of merges. At the same number of merges, it is superior to random pairing on 651/787 instances and to merging every neighboring pair on 625/787. Centroid-distance pairing performs nearly as well.
  • External reference points (3yVz, w6P9). PBR is superior to an L2D-style route-group reoptimization on 275/300 instances at a matched 1.5 s deadline (our implementation with a heuristic selector; the published learned selector remains to be evaluated). The tested GLOP and single-thread FILO2 configurations returned their first solutions after 2.7–4.1 s and 1.85–1.93 s. Applied to clusters derived from GLOP, PBR is superior to strict decomposition on 559/600 instances.
  • Scope. The results support PBR at the tested 1.2 and 1.5 s deadlines and when clusters hold about one vehicle load; the gain grows with finer partitions (median reductions of 4.3% to 8.3% at 26 to 32 clusters, exploratory). At 0.9 s PBR's routes are 0.9% longer, and from about 2 s FILO2 gives better routes. These are measured operating points on our hardware.
  • Rigor. Each new experiment followed a protocol fixed before its runs, and each number reported here was recomputed from the per-run records in a second, independent analysis. Presentation (3yVz, w6P9). The revised manuscript states the boundary-selection rule explicitly, distinguishes the evaluated selector variants, and provides algorithm pseudocode in the supplement. We also clarified the relationship to prior decomposition and route-reoptimization approaches in the Introduction.

Contribution. The paper separates two decisions in cluster-first routing, where to partition and how strongly to enforce the partition, and studies the second: after the partition is fixed and before any route is built, which cluster boundaries should be reopened for joint routing? Intervening before route construction distinguishes PBR from the related methods raised in the reviews. L2D (Li et al.) requires an existing routing solution, from which a learned selector chooses subproblems over multiple rounds, and Kerscher & Minner apply local search between already solved subproblems. PBR lets the solver construct routes jointly across the selected boundaries from the start, with no training, no incumbent solution and no solver calls for selection. Empirically, under matched deadlines PBR is superior to strict decomposition on 1,190/1,200 instances (1.2 s) and to an L2D-style reoptimization on 275/300 (1.5 s). Random merging yields about 2–3% over strict decomposition, and informed pair selection a further 1% over random pairing (distinct comparisons, not additive). Inexpensive geometric signals, the assignment margin or centroid distance, suffice to guide the relaxation.

AuthorsOpenReview ↗

We have uploaded the revised manuscript and supplementary materials

We have uploaded the revised manuscript and supplementary materials. We thank the reviewers and the Area Chair for their constructive feedback and time evaluating our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.