acceptodds
Under review as a conference paper at ICLR 2027

GenRoute: A Minimal Constructive Neural Solver for Multi-Depot Vehicle Routing Variants via Depot-Conditioned Decoding

Abstract

The multi-depot vehicle routing problem asks how vehicles operating from several depots should serve customers at minimum travel cost. Neural methods can construct solutions quickly, but existing approaches handle multiple depots and operational constraints by adding specialized encoders, expert networks, or fine-tuning a separate model for each variant. We show that a substantially simpler design is sufficient. Building on the Attention-Model/POMO line of constructive solvers, our first contribution is that multi-depot structure needs no specialized machinery: it is enough for the decoder's standard context to carry the currently active depot. This induces an implicit sequential decomposition: a shared encoder represents the complete instance, while the decoder constructs one depot-centered part of the solution at a time, jointly deciding customer allocation and routing without explicit clustering. Each encoder layer augments its attention logits with a lightweight learned bias computed from pairwise distances. A three-stage curriculum first trains the core multi-depot problem and then progressively expands the same architecture into a single model covering 16 combinations of open routes, mixed backhauls, route-length limits, and time windows. On held-out evaluations the core model attains a 2.26% gap to reference solutions, while the final generalist reaches a 3.95% mean gap across 16 multi-depot variants and the lowest gap in 9 of 12 depot-count/problem-size settings.

Primary area:
optimization
Keywords:
Neural combinatorial optimization, Multi-depot vehicle routing, operations research

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_EmBgOpenReview ↗
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
  1. The multi-depot setting of VRP is practical and will arouse the interest of some practitioners.
  2. The evaluation of multi-task settings is good.
Critical weaknesses
  1. 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.
  2. The idea of introducing the distance bias has been discussed in prior works. A comprehensive comparison and interpretation would strengthen your contribution.
  3. The presentation and readability are poor. Some paragraphs seem to be AI-generated,e.g., lines 360-364. Table 1 is messy.
  4. Why do we need the three-stage curriculum? What special insights can it bring to the community?
  5. Lines 45-53: Why should multi-depot and cross-problem be introduced simultaneously? These two are orthogonal.
  6. 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

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.

Test (gap, %)GenRoute, learned biasTwin, no biasTwin + DARGenRoute + DAR
N = 100 (1,000 instances)2.261.792.813.37
N = 200 (100 instances)1.741.893.593.71
N = 500 (100 instances)3.354.313.693.45
N = 1,000 (50 instances)3.825.730.130.10

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.

Variant (ref.)MVMoEMTPOMORF-EALFiLMMeDGenRoute submittedGenRoute Joint
MDCVRP (11.89)2.043.389.143.713.353.14 (12.26)
MDOVRP (7.97)5.225.358.375.274.383.79 (8.28)
MDVRPL (11.90)1.953.309.312.713.473.25 (12.28)
MDVRPTW (19.33)13.946.649.436.234.993.75 (20.05)
MDOVRPL (7.97)5.475.728.334.844.373.81 (8.28)
MDOVRPTW (13.00)10.799.336.244.173.372.35 (13.30)
MDVRPLTW (19.35)13.335.949.475.635.053.81 (20.09)
MDOVRPLTW (13.00)10.178.716.243.633.362.33 (13.30)
MDVRPMB (10.68)5.044.8518.984.763.673.43 (11.05)
MDOVRPMB (7.66)10.9510.6811.356.773.412.81 (7.88)
MDVRPMBL (10.71)4.344.1518.563.973.873.56 (11.09)
MDVRPMBTW (19.29)26.5716.3111.0514.344.953.73 (20.00)
MDOVRPMBL (7.66)11.0710.6811.436.903.412.82 (7.88)
MDOVRPMBTW (12.96)21.0316.477.4110.923.292.23 (13.25)
MDVRPMBLTW (19.31)26.0515.9511.0914.034.993.80 (20.04)
MDOVRPMBLTW (12.96)20.2516.017.3210.383.282.23 (13.25)

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.

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

VariantReLD-MTLURSGenRouteGenRoute Joint
MDVRP18.3915.053.323.10
MDOVRP22.3222.014.363.73
MDVRPL18.4815.323.463.21
MDOVRPL22.0522.154.383.74
MDVRPB9.3813.145.17*4.98*
MDOVRPB18.5015.174.47*3.80*
MDVRPBL8.2611.195.14*4.91*
MDOVRPBL18.5014.904.41*3.75*
MDVRPTW30.9037.2620.0919.93
MDOVRPTW33.5526.0519.4619.78
MDVRPLTW31.5638.0419.9019.91
MDOVRPLTW33.2625.5919.3419.73
MDVRPBTW41.2837.7820.30*20.22*
MDOVRPBTW43.3630.3219.35*19.67*
MDVRPBLTW40.5737.7020.05*20.01*
MDOVRPBLTW43.2730.4119.41*19.79*
Mean of 1627.1024.5012.0411.89
Mean, 8 without time windows16.9816.124.343.90
Mean, 8 with time windows37.2232.8919.7419.88
VariantTuneNSearchGenRouteGenRoute Joint
MDVRP11.74411.49511.463
MDVRP, gap to HGS (%)3.523.563.26
MDVRPL11.54011.49611.463
MDOVRP9.2537.9137.862
MDVRPB11.00310.69310.689
MDVRPTW27.31017.69817.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.

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

This paper proposes GenRoute, a light-decoder-based constructive solver for multi-depot vehicle routing. It uses active-depot conditioning and a learned distance bias, and trains one model for 16 routing variants through a three-stage curriculum. Experiments report competitive performance across routing variants and depot counts.

Critical strengths

The proposed solver is simple and achieves competitive performance across multiple routing variants and depot counts. The experiments are reasonably extensive and include comparisons on both synthetic instances and established benchmarks.

Critical weaknesses
  1. The architectural novelty needs clearer positioning. Bdeir et al. [1] already extend the Attention Model to MDVRP using the current depot embedding in the decoder context. GenRoute combines route closure and next-depot selection into one action, but the benefit of this difference is unclear.

  2. The curriculum's benefit is not isolated. Successive stages change both the training distribution and the optimization budget, without a matched comparison to joint training on all variants and depot counts. FiLMMeD [2] already studies curriculum versus joint training, making this control particularly relevant.

[1] Bdeir et al. RP-DQN: An Application of Q-Learning to Vehicle Routing Problems. 2021.

[2] Corrêa et al. FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing. 2026.

Questions for authors

See weakness.

1 comment

Thank you for your valuable review. We will address the stated weaknesses.

W1: We agree that Bdeir et al has used the depot embedding in the decoder context and we will cite their work for this. The paper presents this action as part of the construction and attributes no reported gain to it. GenRoute uses a simpler architecture built from established components. GenRoute combines shared attention encoder, learned distance bias, active depot conditioned decoding trained to solve 16 variants of the problem without finetuning or local search and can achieve competent results.

W2: We retrained the model on joint training and found that the curriculum training holds no benefit over the joint training. Infact, the joint training has better performance over the curriculum training. Therefore, we decided to remove the curriculum training from the contributions of this paper and modify the paper accordingly. Below is an updated table.

Variant (ref.)MVMoEMTPOMORF-EALFiLMMeDGR-DM submittedGR-DM joint
MDCVRP (11.89)2.043.389.143.713.353.14 (12.26)
MDOVRP (7.97)5.225.358.375.274.383.79 (8.28)
MDVRPL (11.90)1.953.309.312.713.473.25 (12.28)
MDVRPTW (19.33)13.946.649.436.234.993.75 (20.05)
MDOVRPL (7.97)5.475.728.334.844.373.81 (8.28)
MDOVRPTW (13.00)10.799.336.244.173.372.35 (13.30)
MDVRPLTW (19.35)13.335.949.475.635.053.81 (20.09)
MDOVRPLTW (13.00)10.178.716.243.633.362.33 (13.30)
MDVRPMB (10.68)5.044.8518.984.763.673.43 (11.05)
MDOVRPMB (7.66)10.9510.6811.356.773.412.81 (7.88)
MDVRPMBL (10.71)4.344.1518.563.973.873.56 (11.09)
MDVRPMBTW (19.29)26.5716.3111.0514.344.953.73 (20.00)
MDOVRPMBL (7.66)11.0710.6811.436.903.412.82 (7.88)
MDOVRPMBTW (12.96)21.0316.477.4110.923.292.23 (13.25)
MDVRPMBLTW (19.31)26.0515.9511.0914.034.993.80 (20.04)
MDOVRPMBLTW (12.96)20.2516.017.3210.383.282.23 (13.25)

We hope this addresses your concerns. If anything remains unclear, we are happy to clarify.

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

The paper proposes a neural solver for multi-depot vehicle routing that builds on the Attention Model and POMO. Its main idea is to use the embedding of the currently active depot in the decoder, allowing one policy to assign customers to depots and construct routes simultaneously.

Critical strengths

This paper offers a relatively straightforward alternative to specialized multi-depot encoders, expert networks, and separate customer-assignment modules.

Critical weaknesses

The contribution is weak. The proposed architecture is relatively simple and builds largely on existing methods. Active-depot information has already been incorporated into previous neural routing approaches, and distance-biased attention and curriculum learning are also established techniques. The main contribution appears to be demonstrating that these components can be combined into a simpler, unified constructor for multiple VRP variants. This is potentially valuable, but I think the paper should provide stronger evidence that the proposed architectural choices and training curriculum are responsible for the reported performance improvements. In particular, a comparison with direct joint training across all variants would help clarify the contribution of the three-stage curriculum.

The three-stage curriculum is presented as one of the paper's main contributions. However, the paper does not establish whether this training sequence is actually better than training the same model directly on the mixture of 16 variants and depot counts.

I have a concern about the feasibility mask described in Appendix B.3. The authors use separate counters for cumulative deliveries and pickups, but I am not sure these conditions guarantee that the actual vehicle load stays within capacity when deliveries and pickups are interleaved. Could the authors clarify whether their formulation enforces the actual vehicle load at every step or uses a relaxed capacity definition?

Questions for authors
  1. Is active-depot conditioning really responsible for the improvement?
  2. Does the distance bias consistently improve generalization?
  3. Is the curriculum responsible for successful generalist training?
1 comment
AuthorsOpenReview ↗

Reply to Reviewer NGMr

Thank you for your valuable comments. We appreciate your points and will edit the document accordingly.

W1: With regards to the weaknesses of this work we narrowed the contribution and removed the curriculum training from the list of contributions. The curriculum training was what we followed as a staged training while developing the work. An updated tables will be provided with the newer version of this paper and this comment as well.

W2: The feasibility mask check was a relaxed one. Our choice of this mask was performed so that our model agrees with the mask used in RouteFinder’s mixed-backhaul branch and the mixed-backhaul branch of FiLMMeD’s adapted CaDA environment. Considering that this mask can be physically violated we replaced it with an additional check that tracks the running load itself.

VariantSubmitted maskExact checkChangeFiLMMeD
MDVRPB11.43511.656+1.94%11.558
MDOVRPB8.0398.128+1.11%8.387
MDVRPBL11.33111.554+1.97%11.451
MDOVRPBL8.0878.199+1.38%8.416
MDVRPBTW21.28621.2860.00%22.630
MDOVRPBTW13.80813.8080.00%14.728
MDVRPBLTW20.95920.9590.00%22.394
MDOVRPBLTW13.61013.6100.00%14.566

Q1: Yes, we retrained the depot blind model and the experiments show that the active model is better.

Active DepotDepot BlindDifference
2.26%2.58%0.3

Q2: Yes the distance bias improves generalization for out of distribution instances. Meaning that by training the model on D = 3 and N = 100 MDVRP instances and evaluating both versions with distance bias and without distance bias we go the below results as shown in table A3 in the appendix:

CustomersWith distance biasWithout distance bias
N = 2001.74%1.89%
N = 5003.35%4.31%
N = 10003.82%5.73%

Q3: Thank you for this beneficial insight. We agree with what is stated in this question and the relevant weakness. We retrained the model on random instances selection and it shows that the curriculum is not responsible for this. Hence, removed the curriculum training from the contributions of this paper. In fact by training the model on uniform mixture of instances it achieved a better results:

Variant (ref.)MVMoEMTPOMORF-EALFiLMMeDGR-DM submittedGR-DM joint
MDCVRP (11.89)2.043.389.143.713.353.14 (12.26)
MDOVRP (7.97)5.225.358.375.274.383.79 (8.28)
MDVRPL (11.90)1.953.309.312.713.473.25 (12.28)
MDVRPTW (19.33)13.946.649.436.234.993.75 (20.05)
MDOVRPL (7.97)5.475.728.334.844.373.81 (8.28)
MDOVRPTW (13.00)10.799.336.244.173.372.35 (13.30)
MDVRPLTW (19.35)13.335.949.475.635.053.81 (20.09)
MDOVRPLTW (13.00)10.178.716.243.633.362.33 (13.30)
MDVRPMB (10.68)5.044.8518.984.763.673.43 (11.05)
MDOVRPMB (7.66)10.9510.6811.356.773.412.81 (7.88)
MDVRPMBL (10.71)4.344.1518.563.973.873.56 (11.09)
MDVRPMBTW (19.29)26.5716.3111.0514.344.953.73 (20.00)
MDOVRPMBL (7.66)11.0710.6811.436.903.412.82 (7.88)
MDOVRPMBTW (12.96)21.0316.477.4110.923.292.23 (13.25)
MDVRPMBLTW (19.31)26.0515.9511.0914.034.993.80 (20.04)
MDOVRPMBLTW (12.96)20.2516.017.3210.383.282.23 (13.25)

Single Depot Results:

VariantGR-DM submittedGR-DM jointFiLMMeDMoS-CMoS-RRF-TERF-MoEMVMoERF-POMOMTPOMO
CVRP1.751.483.741.321.141.461.591.661.791.95
OVRP5.084.399.433.683.514.074.264.654.684.99
VRPL2.361.984.391.651.511.811.932.122.162.44
VRPTW4.443.355.592.392.853.193.533.813.593.89
OVRPL5.114.409.163.673.494.074.274.734.685.04
OVRPTW3.452.435.411.732.112.372.722.892.752.92
VRPLTW5.013.986.322.853.343.633.954.313.994.41
OVRPLTW3.472.435.391.742.112.372.712.912.752.92
Mean3.833.066.182.382.512.873.123.393.303.57

We hope this addresses your concerns, and we would be grateful if you would consider updating your score. If anything remains unclear, we are happy to clarify.

Comments on the paper

2 comments

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.