- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors propose Assignment-structured Representation and Construction (ARC) for the ATSP. This method builds on Sinkhorn assignment to both provide a structured encoder input and to guide the decoding process. Building on a RADAR base model, the authors show that their method improves cross-size generalization for the ATSP. They also show that the decoding component, referred to as FSP, improves a number of base models without retraining.
Critical strengths
- Combining the classical optimization principle of ATSP assignment relaxation to construct principled encoder features and a decoding mechanism is a nice and sound contribution that seems effective empirically. The fact that the decoding integrates zero-shot with existing backbones and improves their results is also a major advantage.
- Thorough experiments, ablations and generalization studies support the major arguments and claimed advantages of ARC.
Critical weaknesses
- My main criticism is that the empirical study (and to some extent the paper overall) only concerns the ATSP. In general, I believe a narrow problem focus should not be a barrier for acceptance. However, in this case it seems necessary to investigate whether the conclusions hold for more general VRPs. To my understanding, the core assignment operator should transfer rather cleanly to for example the ACVRP and other variants. Some experimental results along these lines and a broader discussion on applicability to other problems would significantly strengthen the paper.
- The presentation is also quite dense in places, especially in sections 2-3. Relying less on technical jargon and introducing the notation more thoroughly would improve the text substantially.
In particular, if the first point above is addressed satisfactorily, I might be compelled to raise my score. The methodological contribution and experimental evidence are sufficient, but the broader impact is somewhat unclear as the paper stands.
Questions for authors
- Are there any major obstacles to generalize ARC to other asymmetric VRPs? Are performance advantages maintained in such cases?
6 comments
Response to W1 and Q1 (continued). Following the average results reported in our previous comment, we provide the detailed gap and runtime results for each of the 16 asymmetric VRP variants below.
| Variant (Gap %/time) | HGS | OR-Tools | RF | RF-NN | RADAR | ARC-base | ARC-I | ARC-T |
|---|---|---|---|---|---|---|---|---|
| ACVRP | —/20.84m | 2.92/20.84m | 3.65/1.40s | 3.45/1.41s | 3.08/2.35s | 2.50/2.54s | 2.29/2.99s | 1.63/2.99s |
| AOVRP | —/20.84m | 1.84/20.84m | 3.39/1.48s | 3.32/1.49s | 2.91/2.43s | 2.47/2.63s | 2.30/3.09s | 1.77/3.10s |
| AVRPB | —/20.84m | 2.61/20.84m | 4.20/1.40s | 4.22/1.40s | 3.48/2.35s | 3.06/2.54s | 2.93/2.99s | 2.11/2.99s |
| AVRPL | —/20.84m | 3.02/20.84m | 3.64/1.42s | 3.55/1.42s | 3.15/2.38s | 2.65/2.57s | 2.41/3.02s | 1.70/3.02s |
| AOVRPB | —/20.84m | 1.43/20.84m | 2.55/1.52s | 2.50/1.52s | 2.01/2.47s | 1.70/2.65s | 1.57/3.14s | 1.16/3.16s |
| AOVRPL | —/20.84m | 1.89/20.84m | 3.43/1.48s | 3.38/1.49s | 2.96/2.43s | 2.41/2.63s | 2.29/3.09s | 1.77/3.11s |
| AVRPBL | —/20.84m | 2.60/20.84m | 4.29/1.44s | 4.24/1.43s | 3.60/2.39s | 3.20/2.58s | 3.01/3.05s | 2.19/3.04s |
| AVRPTW | —/20.82m | 1.09/20.82m | 3.42/1.46s | 3.51/1.47s | 2.68/2.42s | 2.49/2.61s | 2.41/3.08s | 1.85/3.09s |
| AOVRPBL | —/20.84m | 1.46/20.84m | 2.56/1.52s | 2.51/1.52s | 2.01/2.46s | 1.69/2.65s | 1.63/3.13s | 1.16/3.14s |
| AOVRPTW | —/20.84m | 0.62/20.84m | 1.40/1.64s | 1.45/1.66s | 0.91/2.59s | 0.76/2.79s | 0.73/3.33s | 0.43/3.34s |
| AVRPBTW | —/20.84m | 1.00/20.84m | 3.32/1.49s | 3.33/1.49s | 2.58/2.44s | 2.33/2.63s | 2.29/3.11s | 1.80/3.12s |
| AVRPLTW | —/20.84m | 1.09/20.84m | 3.57/1.49s | 3.70/1.50s | 2.86/2.45s | 2.71/2.64s | 2.61/3.12s | 2.08/3.13s |
| AOVRPBTW | —/20.84m | 0.74/20.84m | 1.28/1.70s | 1.31/1.70s | 0.97/2.66s | 0.72/2.83s | 0.67/3.38s | 0.44/3.43s |
| AOVRPLTW | —/20.84m | 0.61/20.84m | 1.43/1.65s | 1.51/1.65s | 0.96/2.62s | 0.80/2.80s | 0.76/3.34s | 0.44/3.35s |
| AVRPBLTW | —/20.84m | 1.03/20.84m | 3.37/1.53s | 3.47/1.54s | 2.71/2.49s | 2.46/2.68s | 2.40/3.17s | 1.92/3.19s |
| AOVRPBLTW | —/20.82m | 0.70/20.82m | 1.25/1.69s | 1.30/1.69s | 0.89/2.63s | 0.69/2.83s | 0.66/3.40s | 0.44/3.39s |
Together, these results show that ARC's benefits extend beyond ATSP to a multi-task setting covering 16 asymmetric VRP variants. They support the broader applicability of assignment structure: adapting the assignment marginals to customer and depot roles preserves its value for neural representations and construction guidance.
W2: The presentation is also quite dense in places, especially in sections 2-3. Relying less on technical jargon and introducing the notation more thoroughly would improve the text substantially.
We apologize for the unclear presentation and thank the reviewer for this helpful feedback. We have provided more detailed explanations in our response to W1 from reviewer mALs. We will incorporate these clarifications into Sections 2 and 3. We will also reduce technical jargon and explain each symbol when it first appears to make the presentation easier to follow.
Thank you for the response, the presentation improvements and the additional experiment.
Could you add the two new tables to the manuscript? Preferably alongside a section detailing the experimental evaluation more carefully.
I would agree that the new results show the broader usefulness of ARC. Hence, if they are added to the manuscript and no additional concerns surface from any reviewer, I will raise my score from 2 to 3.
Thank you for your careful review and constructive suggestions on extending ARC beyond ATSP and improving the clarity of Sections 2–3. In response, we have extended ARC to a multi-task setting covering 16 asymmetric VRP variants and provide the formulation, experimental setup, and results below. We also clarify the notation and streamline the explanations of the method. The corresponding revisions to the main text are highlighted in different colors for ease of reference. We hope these responses and revisions clarify ARC's broader applicability and make the presentation more accessible.
Thank you for this constructive suggestion. We agree that broader VRP experiments would strengthen the evidence for ARC's applicability. We have extended ARC to 16 asymmetric VRP variants, and ARC-T achieves the best solution quality among the evaluated neural methods in all 16.
To extend ARC to VRPs, we adapt the assignment constraints to allow multiple routes to share a depot. Each customer retains unit incoming and outgoing assignment mass. With depot 0 and N customers, we use a continuous assignment matrix P satisfying
P1=P⊤1=(κ,1,…,1)⊤.
The depot mass κ has the capacity-based lower bound
K_{\mathrm{lb}}=\max\left\\{\left\lceil\frac{\sum_i d_i^{\mathrm{delivery}}}{Q}\right\rceil,\left\lceil\frac{\sum_i d_i^{\mathrm{pickup}}}{Q}\right\rceil,1\right\\},
where Q is vehicle capacity. We combine Sinkhorn scaling with bisection over κ∈[Klb,N] to approximately solve the entropy-regularized assignment relaxation and obtain κ and dual potentials ui,vi. The capacity bound reflects aggregate demand; directed costs also affect route organization. Estimating κ lets the depot mass adapt to this cost structure through a scalar search. These potentials provide ARC's node and edge features, and FSP guides route construction. The RouteFinder decoder handles each variant's constraints.
To evaluate this extension, we use the RouteFinder (RF) multi-task framework and follow RADAR's experimental setup for the 16 asymmetric VRP variants. These variants cover capacity, open routes, backhauls, route-length limits, time windows, and their combinations. All neural methods use six encoder layers, following the released implementation, and are trained on all 16 variants. We evaluate 15,998 test instances and measure neural runtimes on an A100 GPU. ARC-base uses the assignment representation without FSP; ARC-I adds FSP at inference; ARC-T uses FSP during training and inference.
ARC-T reduces the average gap relative to HGS from RADAR's 2.3605% to 1.4314%, a 39.4% relative reduction, with average runtime increasing from 2.47s to 3.16s. ARC-base improves on RADAR in every variant, reducing the average gap by 13.5% with 0.19s additional runtime. Adding FSP at inference improves every variant further, and training with FSP gives the strongest neural results throughout.