- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper targets the multi-depot vehicle routing problem (MDVRP). It first argues that a single stream of encoder-decoder flow can handle the multi-depot setting well without needing multiple streams, as in prior work. It further enhances the network by integrating the distance bias using a separate per-head offset in the encoder. The policy is trained with a three-stage curriculum: MDCVRP, 16 variants with open route, backhaul, duration limit, and time window constraints, and varying numbers of depots. The proposed method is evaluated on the corresponding 16 variants, all under the multi-depot setting.
Critical strengths
- The multi-depot setting of VRP is practical and will arouse the interest of some practitioners.
- The evaluation of multi-task settings is good.
Critical weaknesses
- What is the necessity of using a single stream for multi-depot VRPs, compared with the existing multi-stream approaches? Any specific advantages of this design? I would like to see a deeper understanding of the model capacity, learnability, and generalizability.
- The idea of introducing the distance bias has been discussed in prior works. A comprehensive comparison and interpretation would strengthen your contribution.
- The presentation and readability are poor. Some paragraphs seem to be AI-generated,e.g., lines 360-364. Table 1 is messy.
- Why do we need the three-stage curriculum? What special insights can it bring to the community?
- Lines 45-53: Why should multi-depot and cross-problem be introduced simultaneously? These two are orthogonal.
- Some recent multi-task baselines are not compared in the experiments.
Questions for authors
Please refer to the weaknesses.
The code cannot be viewed at the time of review.
4 comments
W6: We are happy to compare the model to other baselines below is additional comparison to ReLD-MTL, URS and TuneNSearch:
Gap to PyVRP (%), URS’s released sets, N = 100, 3 depots, 1,000 instances per variant
| Variant | ReLD-MTL | URS | GenRoute | GenRoute Joint |
|---|---|---|---|---|
| MDVRP | 18.39 | 15.05 | 3.32 | 3.10 |
| MDOVRP | 22.32 | 22.01 | 4.36 | 3.73 |
| MDVRPL | 18.48 | 15.32 | 3.46 | 3.21 |
| MDOVRPL | 22.05 | 22.15 | 4.38 | 3.74 |
| MDVRPB | 9.38 | 13.14 | 5.17* | 4.98* |
| MDOVRPB | 18.50 | 15.17 | 4.47* | 3.80* |
| MDVRPBL | 8.26 | 11.19 | 5.14* | 4.91* |
| MDOVRPBL | 18.50 | 14.90 | 4.41* | 3.75* |
| MDVRPTW | 30.90 | 37.26 | 20.09 | 19.93 |
| MDOVRPTW | 33.55 | 26.05 | 19.46 | 19.78 |
| MDVRPLTW | 31.56 | 38.04 | 19.90 | 19.91 |
| MDOVRPLTW | 33.26 | 25.59 | 19.34 | 19.73 |
| MDVRPBTW | 41.28 | 37.78 | 20.30* | 20.22* |
| MDOVRPBTW | 43.36 | 30.32 | 19.35* | 19.67* |
| MDVRPBLTW | 40.57 | 37.70 | 20.05* | 20.01* |
| MDOVRPBLTW | 43.27 | 30.41 | 19.41* | 19.79* |
| Mean of 16 | 27.10 | 24.50 | 12.04 | 11.89 |
| Mean, 8 without time windows | 16.98 | 16.12 | 4.34 | 3.90 |
| Mean, 8 with time windows | 37.22 | 32.89 | 19.74 | 19.88 |
| Variant | TuneNSearch | GenRoute | GenRoute Joint |
|---|---|---|---|
| MDVRP | 11.744 | 11.495 | 11.463 |
| MDVRP, gap to HGS (%) | 3.52 | 3.56 | 3.26 |
| MDVRPL | 11.540 | 11.496 | 11.463 |
| MDOVRP | 9.253 | 7.913 | 7.862 |
| MDVRPB | 11.003 | 10.693 | 10.689 |
| MDVRPTW | 27.310 | 17.698 | 17.675 |
It is worth noting that ReLD and URS are trained on single depot variants of the problem.
Q: the code can be found in this link: https://anonymous.4open.science/r/genroute-anon-4895/README.md
Thanks for the rebuttal! I suggest the authors include more baseline results in the revised manuscript.
Regarding W4, I expect a more in-depth understanding of why DAR works better on N=1000 and why your four-component one works better on smaller scales, rather than just listing the results.
My other concerns remain. I am still concerned about how much this work benefits the community and the presentation. Overall, I am inclined to a rejection.
Thank you for your reply,
DAR adds the bias at the selection stage while our distance bias is trained with the model. Consequently, in the case of our model that is trained at N=100 the contribution of local selection decreases at higher number of nodes N=1000.
Our claim is that a simpler design is sufficient. One single-stream model solves the 16 multi-depot variants without the extra streams and components of the compared models. This gives the community a small model that is easy to extend and to compare against.
Thank you for your comments. With regards to the weaknesses of this work we hope that this comment will address them and the subsequent revisions on the paper.
W1: We claim that a simpler design is sufficient and can outperform multi-stream models that have an extra components specifically added to solve the multivariant of the problem. The architecture of the model and the training procedure enabled the model to generalize to different variants of problems.
W2: We agree that the introduction of distance bias has been used before. However, we use a Graphormer-style distance bias with four distance features: the distance itself, its square, its logarithm, and its reciprocal. The expirements shows that the learned bias affects the score at the in distribution instances compared to the same model with no bias. It has better performance over the no bias on out of distribution and the direct distance bias used in DAR [1] is only good for N = 1000 instances and when DAR distance is combined with GenRoute trained on graphormer style distance bias it improves the score of the 1000 number of nodes.
D = 3. The shown gap is to HGS with a 2 s limit, which is a weak reference at N = 1,000.
[1] Wang, Yang, et al. "Distance-aware attention reshaping: Enhance generalization of neural solver for large-scale vehicle routing problems." arXiv preprint arXiv:2401.06979 (2024).
W3: We will make sure that we go through the paper to improve the clarity and presentation of this work.
W4: We agree with your comment and removed the three stage curriculum from the contributions of this work. After retraining the model on random instances we found that this type of training has better performance than the staged training. The three stage training was the steps that we followed to train the model. Starting from a model that solves the general problem then trained to cover other variants.
W5: We agree with this comment and we will alter this paragraph. We introduced them simultaneously to make sure that we do not leave the MDVRP papers uncovered.