- 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
-
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.
-
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
- 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?
- 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?
- 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.
- 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?
- 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
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).
| Deadline | PBR returns after | Strict returns after | PBR shorter | Mean route-length difference |
|---|---|---|---|---|
| 0.9 s | 0.71 s | 0.92 s | 227/600 | 0.9% longer |
| 1.2 s | 1.07 s | 1.15 s | 578/600 | 2.7% shorter |
| 1.5 s | 1.13 s | 1.50 s | 582/600 | 2.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 after | PBR (1.13 s) shorter | Mean reduction |
|---|---|---|
| 0.98 s (stopped early) | 593/600 | 3.2% |
| 1.15 s (its 1.2 s runs) | 586/600 | 2.9% |
| 1.50 s (its 1.5 s runs) | 582/600 | 2.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.
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.
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.
What the controls show.
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:
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.
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.