acceptodds
Under review as a conference paper at ICLR 2027

Two-Stage Learned Decomposition for Scalable Routing on Multigraphs

Abstract

Most neural methods for Vehicle Routing Problems (VRPs) are limited to Euclidean settings or simple graphs. In this work, we instead consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs (e.g., distance vs. time). Multigraphs are highly relevant in practice, yet few neural methods are designed for them, and those that do exist face major scalability issues. We address these scalability issues with Node-Edge Policy Factorization (NEPF), which splits the routing policy into a node permutation stage and an edge selection stage. To enable the decomposition, we introduce a pre-encoding edge aggregation scheme and a non-autoregressive architecture for the edge stage, as well as a hierarchical reinforcement learning method to train the stages jointly. Our experiments across six VRP variants demonstrate that NEPF trains and runs up to orders of magnitude faster than prior neural multigraph methods and scales to considerably larger instances, while matching or improving on their solution quality.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Combinatorial Optimization, Reinforcement Learning, Graph-based Machine Learning, Multigraphs, Traveling Salesman Problem, Multi-Objective Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Jr1KOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes NEPF for neural routing on multigraphs: it first generates a node permutation from compressed edge information, then selects one edge per segment with a lightweight network. It matches or improves prior multigraph methods while being much faster and more scalable.

Critical strengths
  1. Faster inference without compromising solution quality: NEPF is one to two orders of magnitude faster than GMS-EB and 2-3x faster than GMS-DH, while matching or improving solution quality.
  2. Broad experimental coverage: it is evaluated on six problem variants, several multigraph distributions, larger instances, real-world road networks, and different backbones.
Critical weaknesses
  1. The core idea, a learned two-stage decomposition, is not shown to be useful. On MOTSP and MOCVRP, edges are chosen greedily, so the good results there only support edge compression and the node policy. For the learned edge stage, the only evidence is one ablation on MOTSPTW against a per-edge greedy baseline that is myopic by construction, with no comparison to the classical dynamic program. Also, all 4 of NEPF’s losses in Table 1 occur on MOTSPTW/MOOP, the problems that use the learned edge stage.
  2. The scalability claim is overstated relative to GMS-DH. The decoder is still O(N³), and memory still grows with M, so invariance to M holds for runtime only. The regime where N and M are both large is never tested, and Appendix B.3 says M is usually small in practice, which is in tension with the Introduction’s motivation.
  3. The cross-backbone results do not support the claim of compatibility with foundation models: quality degrades on RCTSP, only the encoder is swapped in the multi-objective setting, and no pretrained GOAL/URS is used.
Questions for authors
  1. Can the authors compare the learned edge stage with the classical FSASP dynamic program on small instances, and report the optimality gap of the learned selection for a fixed node order, on problems where edge choice matters (MOTSPTW, RCTSP)?
  2. The existing ablation only removes the learned edge stage. Can the authors add a variant without the node-edge split to separate the effect of decomposition from that of compression?
  3. How accurate is the state estimator, and how much would an oracle state improve results on RCTSP, OP and MOOP?
  4. How do solution quality and runtime behave when N and M are both large (for example N=500 with M=20)?
  5. Can the authors show a second problem class beyond routing, such as flexible job-shop scheduling, to support the claim that the factorization is a general principle?
5 comments

We thank Reviewer Jr1K for their specific and very constructive questions. We have answered all five questions and the weaknesses with new experiments, which we detail below. We also updated the original manuscript, with changes in blue. Overall, the manuscript has been significantly strengthened by the new additions in our opinion (especially the pretrained foundation model experiments and the FJSP extension).

Critical Weaknesses:

W1. The core idea, a learned two-stage decomposition, is not shown to be useful. On MOTSP and MOCVRP, edges are chosen greedily [...]. For the learned edge stage, the only evidence is one ablation on MOTSPTW against a per-edge greedy baseline that is myopic by construction, with no comparison to the classical dynamic program. [...]

We thank the reviewer for suggesting further experiments targeting the learned edge stage.

As a clarification first: on the MOTSP and MOCVRP, greedy selection is exact for linearly scalarized edge cost, so the learned edge stage is largely unnecessary. We would argue this shows exactly the usefulness of the decomposition, which exposes the simplicity of the second stage for these two problems. We have moved the edge stage configuration into the main text for further transparency.

New experiments (added to Table 7 and Appendix F.9, Table 28): For the two suggested problems (RCTSP and MOTSPTW) we compare the per-edge greedy approach, NEPF learned edge stage and Gurobi exact edge selection:

SettingNEPF (learned edges)exact edges, NEPF's orderper-edge greedy
MOTSPTW FLEX2 (HV ↑)0.9280.9300.303
MOTSPTW FIX20.9420.9530.195
RCTSP FLEX2 (cost ↓)4.234.214.36
RCTSP FIX211.510.511.0 (95% feasible)

The learned edge stage is close to optimal for these configurations. It is also substantially faster (more than 5x for MOTSPTW) compared to the exact variant. In contrast, the myopic per-edge greedy collapses on MOTSPTW and is infeasible on 5% of RCTSP FIX2 instances. We also tested a more advanced non-myopic heuristic, which does not match the learned stage for the MOTSPTW (beam label setting, see Appendix F.9).

We note that learning the edge stage is what makes joint training practical, since using an exact solver there would slow down training considerably. However, a further benefit of the factorization is modularity. If a fast exact FSASP solver exists, it can replace the learned stage at inference. Without augmentation, NEPF + exact edges reaches 0.953 HV on MOTSPTW FIX2, above the best GMS result (0.951, GMS-DH with augmentation), while remaining 2.7× faster (1.8 vs. 4.9 min).

W2. The scalability claim is overstated relative to GMS-DH. The decoder is still O(N³), and memory still grows with M [...]. The regime where N and M are both large is never tested, and Appendix B.3 says M is usually small in practice [...]

We agree with the reviewer that the manuscript can be made more precise regarding computational scaling. We have revised the wording in the Introduction, Section 5.2 and Appendix C accordingly. Overall though our conclusion still stands: NEPF's runtime is nearly invariant to M, and its dependence on M in memory is confined to the shallow pre-encoding and edge stages (which can be computed in chunks with almost no runtime penalty), whereas GMS carries the O(MN²) representation through the entire encoder.

High M and N: we supplement the results already in the paper (Appendix F.2, MOTSP) by testing N ∈ {200, 500, 1000} × M ∈ {10, 20}, zero-shot with GMS-DH and GMS-EB as baselines. The new results are in Table 19. In summary, NEPF beats GMS-DH in all cells. While it trails GMS-EB in some cells, it runs up to 19 times quicker. GMS-EB also fails to run in 6/12 configurations due to the graph size.

We additionally extend the scalability stress test in Table 20. With M=20, GMS-EB and GMS-DH fail at N>500, while NEPF (with chunked pre-encoding) handles up to N=2000.

We note that extending the main tables to the M=20 and N=500 setting is not feasible, as training GMS for M=5, N=100 is already very time consuming. However, Appendix F.2 + F.3 and Figure 2 now show the dense large N regime.

Finally, we have revised Appendix B.3 somewhat. It now cites the available evidence in literature more precisely: M is moderate (<=5) considering two edge attributes. With more conflicting attributes M will grow, often exponentially, motivating the high M regime. We note also that GMS already struggles computationally for M=5 and high node counts.

(continued in next comment)

W3. The cross-backbone results do not support the claim of compatibility with foundation models: quality degrades on RCTSP, only the encoder is swapped in the multi-objective setting, and no pretrained GOAL/URS is used.

To better illustrate the compatibility with cross-task models, we fine-tuned the pretrained GOAL [1] multi-task checkpoint and the URS [2] unified checkpoint (available online) with NEPF on RCTSP and OP (FLEX2, FIX2). Results have been added to Table 8 and Appendix D.4 (together with experimental setup).

Results for GOAL (see updated manuscript for URS):

GOAL backboneOP FLEX2 ↑OP FIX2 ↑RCTSP FLEX2 ↓RCTSP FIX2 ↓
pretrained, 20 epochs41.534.34.713.9
from scratch, 200 epochs41.632.66.8715.8

Initializing NEPF's node stage from the pretrained GOAL checkpoint improves on training from scratch. The pretrained URS checkpoint also transfers stably. Moreover, when the original tasks are rehearsed during fine-tuning, the models keep their original capabilities, and only degrade very marginally across their rehearsed tasks.

We now consider the results to show much better that NEPF can be applied on top of these foundation models, keeping their cross-task generalization capabilities while extending them to our multigraph problems.

Regarding the multi-objective case, the foundation models were not trained there, and the number of applicable literature backbones (for asymmetric multi-objective problems) with verified performance is small, hence we are limited there in the experiments we can perform. We consider encoder-only swapping, and note that it illustrates the principle well.

Questions For Authors:

Q1. Can the authors compare the learned edge stage with the classical FSASP dynamic program on small instances, and report the optimality gap of the learned selection for a fixed node order [...]?

We have added such a direct comparison in Appendix F.9. See our response to W1 above. On the investigated settings, the learned stage matches the exact one well, while remaining substantially faster.

Q2. [...] Can the authors add a variant without the node-edge split to separate the effect of decomposition from that of compression?

We admit that we are somewhat uncertain about what is meant here exactly. Let us know if the below interpretation is not correct, and we will happily extend the experiment.

To answer the question, we trained two additional NEPF variants: NEPF-joint (the same aggregation and node encoder, but an edge head picks the edge immediately after each node, meaning state is exact) and NEPF without aggregation (only pre-encoding aggregation is removed). Together with existing models this gives a full 2×2 table (split × compression). Results for OP (higher-is-better), RCTSP (lower-is-better) and MOTSPTW (higher-is-better):

SplitCompressionOP FLEX2OP FIX2RCTSP FLEX2RCTSP FIX2MOTSPTW FLEX2MOTSPTW FIX2
GMS-EB––44.036.25.4415.00.630.64
NEPF w/o pre-enc. agg.✓–44.635.44.1211.40.9250.942
NEPF-joint–✓44.536.34.2810.50.9270.949
NEPF✓✓44.735.34.2311.50.9280.942

We can draw two conclusions: 1) NEPF compression barely affects solution quality, while it enables significantly improved scaling in memory and runtime; 2) NEPF-joint is often neutral in terms of quality, with some advantage over vanilla NEPF on the FIX distribution. However, our split additionally allows parallel edge sampling per node order, exact or heuristic FSASP solvers at inference (see W1 above), and node-only backbones such as the pretrained GOAL/URS encoders (W3). The split also scales better computationally than the joint variant. We have added this 2×2 table in Appendix F.9.

References:

[1] GOAL: A Generalist Combinatorial Optimization Agent Learner. ICLR, 2025.

[2] URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization. ICML, 2026.

(continued in next comment)

Q3. How accurate is the state estimator, and how much would an oracle state improve results on RCTSP, OP and MOOP?

Following this suggestion, we expanded Appendix D.2 with Table 12, which contains the estimator accuracy and NEPF’s sensitivity to its error. Note that injecting the ground-truth state is not possible, as it both depends on and affects the selected nodes, thereby creating a circular dependency. Instead, to measure how much a perfect state would help, we injected Gaussian noise at 1× and 2× the measured error at inference and re-evaluated.

In short: The estimator is accurate (R² 0.95–0.996), and NEPF is robust to the residual error: doubling it changes the objective minimally. Extrapolating to zero error, an oracle state would therefore add little in these settings. At the same time, Table 11 (already included in the original manuscript) establishes the necessity of this component.

Q4. How do solution quality and runtime behave when N and M are both large (for example N=500 with M=20)?

See our response to W2 above. We have extended Appendix F.2 (quality) and F.3 (memory and runtime) to cover this setting.

Q5. Can the authors show a second problem class beyond routing, such as flexible job-shop scheduling, to support the claim that the factorization is a general principle?

We implemented NEPF for flexible job-shop scheduling (FJSP), presented in new Section 5.4 with details in Appendix F.7. The node stage orders operations, with job precedence enforced by masking. The parallel alternatives are each operation's eligible machines, aggregated with the same Deep Sets pre-encoding. The edge stage assigns a machine to each operation given the order.

Results:

10×5 Obj.GapTime20×10 Obj.GapTimeBrandimarte [3] Obj.GapTime
CP-SAT (60 s limit)96.30.03%(16m)200.33.40%(1.7h)174.11.41%(2.4m)
CP-SAT (1 h limit)96.20.00%(18m)193.70.00%(100h)172.90.41%(2.0h)
MWKR117.422.01%(<1s)220.313.76%(<1s)203.321.79%(<1s)
HGNN [4]111.716.13%(40s)215.811.41%(2.5m)201.028.13%(10s)
HGNN (sampling)105.69.75%(3.1m)214.810.87%(14m)190.919.90%(58s)
NEPF102.96.98%(12s)196.41.37%(45s)197.721.69%(3.1s)

On both synthetic sets, NEPF-FJSP outperforms HGNN [4] (a dedicated neural FJSP solver) with considerable runtime advantage. On Brandimarte instances [3] it lies between the two HGNN variants. On 20×10, it comes within 1.4% of the best CP-SAT solutions found with a one-hour limit per instance.

This supports the factorization as a general principle for problems with a structural decision and parallel local alternatives. Remark that we do not claim state-of-the-art performance here (it is not our goal), as we have not benchmarked against more recent neural baselines. We simply show empirically that the principle is extendable to other problems, with promising and useful results.

We hope these clarifications and additional experiments address the reviewer's concerns and would be grateful if they were reflected in the assessment. We are happy to discuss further or run additional experiments.

References:

[3] Routing and Scheduling in a Flexible Job Shop by Tabu Search. Annals of Operations Research, 1993.

[4] Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning. IEEE Transactions on Industrial Informatics, 2023.

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

This paper proposes the NEPF framework for multi-graph routing problems, which reduces computational and memory overhead caused by multi-graph representations by aggregating parallel edge features before encoding. The framework decomposes route construction into node sequence generation and edge selection given a sequence. The authors evaluate this framework on six routing tasks, demonstrating its advantages in solution quality and computational efficiency compared to existing neural methods. Among them, MOTSP and MOCVRP use greedy edge selection, while the remaining experiments employ a learned edge selection module.

Critical strengths
  • Well organized; the bottleneck, motivation, and module relationships are clearly explained, making the authors’ claims easy to follow.
  • The node-sequence/edge-selection decomposition is structurally motivated, and pre-encoding aggregation directly addresses the cost of increasing parallel edges.
Critical weaknesses
  • The paper evaluates NEPF on six routing tasks, but the neural baseline methods are primarily limited to GMS-EB and GMS-DH, and synthetic instances use the FLEX/FIX distribution proposed in the same work. While this clearly demonstrates improvements over existing multi-graph neural frameworks, it does not establish empirical connections with a broader body of neural routing literature. Variants of NEPF with different backbones help validate framework compatibility, but cannot replace comparisons with independent solving methods.

  • For instance, OP is a native testbed for AM/POMO styles models with a rich pool of neural baselines, yet the single objective OP experiments only compare against GMS. A comparison along either of these directions would be valuable. More importantly, until such comparisons are added, I believe the paper's claims should be scoped to "outperforming GMS in the multi-graph setting" rather than framed as a general improvement over neural multi-objective routing methods.

Questions for authors
  • Can the variant implemented by the author be adjusted to enable a more direct comparison with existing public baselines? And can it report the training budget and time-quality trade-offs under consistent data distributions, preference sets, and evaluation protocols?
5 comments

We thank Reviewer RUFQ for their positive assessment and their concrete suggestions. We address each point individually below. The original manuscript has also been updated, with changes in blue.

Critical Weaknesses:

W1. [...] the neural baseline methods are primarily limited to GMS-EB and GMS-DH [...] it does not establish empirical connections with a broader body of neural routing literature. [...]

Please see our response to W2 below, it answers both weaknesses.

W2. For instance, OP is a native testbed for AM/POMO styles models with a rich pool of neural baselines, yet the single objective OP experiments only compare against GMS. [...] the paper's claims should be scoped to "outperforming GMS in the multi-graph setting" [...]

First, to improve the clarity of the manuscript we have adopted the more careful framing proposed. We now write "best neural multigraph method" throughout (Section 5.1, Table 1 caption, F.1, F.5). Thank you for this suggestion. This was always the interpretation we had in mind.

Second, we want to clarify that the variant of OP we consider is strictly different compared to the standard OP in literature. Our OP is a two-resource multigraph variant (see Appendix E.3), so standard neural baselines (AM/POMO) cannot be applied out-of-the box (see Rydin et al. [2] Appendix B for extended discussion on this). In fact, all our problems are defined on multigraphs, making standard baselines not directly applicable. We have made this clearer in the main text.

Third, to connect to the wider literature better, we add an independent neural baseline: we prune the multigraph to one edge per pair and solve the resulting asymmetric simple graph VRP with MatNet [1]. Essentially, this is a “trick” to make more methods applicable to multigraphs. This baseline is trained with the same budget and curriculum as NEPF and evaluated under the identical protocol of Tables 1–2 (following Rydin et al. [2]).

We have added these results in a new Appendix F.8, with a short overview in Section 5.1. To briefly summarize them, the pre-pruning baseline underperforms NEPF in seven of the eight multi-objective settings, while being 3–8x slower. Moreover, no pruning rule performs well in all single-objective cases (although the best rule is slightly better than NEPF on FIX2 RCTSP and OP). The pruning trick does technically extend some existing methods to multigraphs, but it comes with considerable downsides compared to our multigraph-native method.

Questions For Authors:

  • Can the variant implemented by the author be adjusted to enable a more direct comparison with existing public baselines? And can it report the training budget and time-quality trade-offs under consistent data distributions, preference sets, and evaluation protocols?

All neural models use the same hardware (one A40), batch size, instance generator and curriculum, and are evaluated on the same test instances with the same 101 preferences, ×8 augmentation and half precision. This setup follows the only directly applicable prior work [2] as closely as possible, and is mostly consistent with the standard protocol in the field (e.g., from AM/POMO or PMOCO [3] in the multi-objective setting).

Regarding training budget, we agree that we can be more transparent. We have therefore extended Table 5 to all six problems (N=100), by creating Table 10 in Appendix D.1. NEPF is significantly cheaper per epoch than GMS across all problems. Consequently, NEPF is consistently trained at a lower budget than the baselines.

On inference time-quality trade off: this is reported in Tables 1 and 2 (against the applicable neural baselines), as well as Figure 3 in the Appendix (against classical methods).

Lastly, as noted above we have added an additional baseline using the MatNet architecture together with rule-based pre-pruning (to make the architecture applicable on multigraph problems). This is implemented with the consistent benchmark suite described above.

We hope this addresses the reviewer’s questions and are happy to discuss further. We are particularly open to adjusting our evaluation protocol further, based on concrete suggestions, to be more consistent with literature.

References:

[1] Matrix Encoding Networks for Neural Combinatorial Optimization. NeurIPS, 2021.

[2] Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs. ICLR, 2026.

[3] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization. ICLR, 2022.

Thank you for the additional experiments and clarifications. However, my main concern remains unresolved, and the response further reinforces my doubts about the framework's broader generality.

The authors emphasize that all six tasks are multigraph variants where established neural baselines are not directly applicable. This further highlights my concern that the evaluation is restricted to settings with limited independent competition. Although the new MatNet baseline is a useful addition, its reliance on pre-pruning introduces information loss and does not provide a sufficiently direct comparison.

I acknowledge the reported cross-distribution results within multigraph settings. Nevertheless, I still believe that additional experiments on established routing benchmarks (e.g., standard TSP/CVRP), or stronger adaptations of existing neural baselines, are necessary to establish the broader competitiveness and applicability of NEPF.

We thank the reviewer for engaging with our response.

We would first like to clarify the scope of our contribution. First, our goal is neural routing on multigraphs, not improving on standard simple-graph benchmarks (e.g., Euclidean TSP). Second, that few strong neural baselines exist for multigraphs is not a limitation of our evaluation, but what makes this setting an open problem.

Within this scope, we address the two remaining points:

Established simple graph routing benchmarks. On a simple graph (M = 1), NEPF's pre-encoding aggregation and edge stage become trivial, so NEPF with a given node backbone reduces to that backbone (e.g., MatNet [1], GREAT [2] or GOAL [3]). Competitiveness on standard TSP/CVRP is therefore inherited from the backbone. NEPF adds multigraph capability on top, which is what our experiments in Section 5.3 show. Adding simple graph results would largely restate the results from the respective papers [1-3].

Additionally, the new experiments with pre-trained cross-problem models (GOAL and URS) in response to reviewer Jr1K (see Table 8, 14 and 15), show that NEPF extends these with little loss in original task performance. In other words, NEPF does not trade off performance on the established benchmarks: it retains the quality of these foundation models on standard routing problems and extends them to multigraphs, which none of them can handle natively.

Stronger adaptations of existing neural baselines. In total, we have 7 neural baselines. Beyond pre-pruning, the manuscript already contains four adaptations of established neural routing architectures to multigraphs: NEPF with MatNet, ICAM, GOAL and URS backbones (Table 8), in addition to GMS-EB and GMS-DH. All these 6 methods keep the full multigraph information, so they avoid the information loss from pre-pruning. NEPF with its vanilla backbone remains the strongest, and against all baselines it is the best in most settings and the most scalable.

We remark that the information loss of pre-pruning is not an artifact of our baseline. Rather, it is the reason why simple-graph methods do not transfer natively to multigraphs, as the MOTSP/MOTSPTW/MOCVRP results show (Table 26). More sophisticated adaptations of literature baselines fall outside the scope of this work, since such adaptations would require significant changes, in essence producing new methods entirely.

We agree that the claims should be scoped accordingly, and as stated in our previous response we now write "best neural multigraph method" throughout. We hope this clarifies that NEPF is both complementary to and compatible with the established neural routing literature.

[1] Matrix Encoding Networks for Neural Combinatorial Optimization. NeurIPS, 2021.

[2] A GREAT Architecture for Edge-Based Graph Problems Like TSP. arXiv, 2025.

[3] GOAL: A Generalist Combinatorial Optimization Agent Learner. ICLR, 2025.

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

This paper presents Node-Edge Policy Factorization (NEPF), a neural method for vehicle routing on multigraphs, where parallel edges encode distinct travel options between node pairs. NEPF factorizes the routing policy into a node permutation stage and an edge-selection stage (the Fixed Sequence Arc Selection Problem), using a pre-encoding Deep Sets aggregation of parallel edges and a non-autoregressive BiLSTM edge decoder, with both stages trained jointly via hierarchical reinforcement learning. Experiments across six single- and multi-objective VRPs show NEPF matches or improves solution quality over prior multigraph neural methods (GMS-EB/DH) while reducing training and inference time by up to orders of magnitude and handling larger instances.

Critical strengths

The paper's primary strength is its demonstrated efficiency gain with maintained solution quality: by confining the dense multigraph representation to a shallow pre/post-processing stage, NEPF trains up to 20× faster and runs 1–2 orders of magnitude faster than GMS-EB while matching or exceeding its hypervolume across 16 benchmark configurations, and it handles instances roughly 2.5× larger on identical hardware (Table 14). This is consequential because prior neural multigraph methods were demonstrably impractical beyond small N, so the work removes a real blocker rather than merely incrementing accuracy. A second strength is the careful empirical grounding: six problem variants, multiple backbones, ablations, and real-world instances give unusual coverage for this subfield, making the central claims testable rather than asserted.

Critical weaknesses

The practical significance of the studied problem setting appears limited. Multigraph VRPs occupy a narrow niche: while the paper motivates them via road networks with alternative paths, the underlying multigraph abstraction assumes precomputed, independent, non-dominated paths between node pairs—an assumption the authors themselves acknowledge discards shared road structure, congestion, and time-dependent effects, which are the very phenomena that make real-world routing difficult. Moreover, the paper is a continuation of generalization research restricted to the cost-matrix dimension: it does not address the arguably more pressing bottlenecks in neural routing, namely cross-distribution generalization over demand structures, constraint types, and their combinations, or the covariate shift between synthetic and real instances. As such, the contribution, while technically competent, advances a specific representational axis (multigraphs) rather than the generalization capabilities that currently limit the practical adoption of neural combinatorial optimization.

Questions for authors

All main results train on N=100 synthetic FLEX/FIX instances, with realistic (F.5) and real-world (F.6) results reported either zero-shot or with size-specific retraining. Since the motivation is practical road networks, how sensitive is NEPF's zero-shot performance to the training distribution (e.g., would training on the F.5 instances change conclusions), and does the pre-encoding aggregation transfer better or worse than the baselines across these shifts?

5 comments

We thank Reviewer w4oc for their effort so far in the review process, and for acknowledging the efficiency gains and empirical coverage in our work. We address the weaknesses and questions individually below. The manuscript has also been updated, with changes in blue.

Critical Weaknesses:

W1. The practical significance of the studied problem setting appears limited. [...] the underlying multigraph abstraction assumes precomputed, independent, non-dominated paths between node pairs—an assumption [that] discards shared road structure, congestion, and time-dependent effects [...]

As discussed in B.3, the multigraph abstraction assumes precomputed, independent paths. However, these assumptions are less restrictive than those of the simple-graph representation that essentially all neural routing methods use. A simple graph is the special case M=1 and discards more of the road network's original structure. We would thus argue that our method covers even more realistic instances than most existing work.

Multigraphs are an established model in Operations Research: since Garaix et al. (2010) [1], we can identify ten papers [1-10] published in top OR venues (TRB, TRE, EJOR, C&OR) with jointly over 600 unique citing publications. Ben Ticha et al. [4] also reports substantial cost reductions from jointly choosing paths and visit order (up to 10.5% in realistic instances), while reporting significant solution time increases (highlighting the need for learned heuristics). We understand why the setting may appear niche from a neural routing perspective, but the OR literature treats it as an established problem class with demonstrated practical value.

Our results on real San Francisco road networks (F.6) and realistic Pareto-path instances (F.5) also show that the setting arises from real data, not only from synthetic generators.

Finally, in response to Reviewer Jr1K, we added empirical results on a scheduling problem (see new Section 5.4), which show that our approach is promising and useful for other combinatorial optimization tasks.

References:

[1] Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operational Research, 2010.

[2] Pricing routines for vehicle routing with time windows on road networks. Computers & Operations Research, 2014.

[3] A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E, 2016.

[4] Empirical analysis for the VRPTW with a multigraph representation for the road network. Computers & Operations Research, 2017.

[5] Vehicle routing problems with road-network information: State of the art. Networks, 2018.

[6] Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows. Computers & Operations Research, 2019.

[7] Multi-objective periodic cash transportation problem with path dissimilarity and arrival time variation. Expert Systems with Applications, 2021.

[8] Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B, 2017.

[9] The vehicle routing problem with arrival time diversification on a multigraph. European Journal of Operational Research, 2020.

[10] A column generation approach for an emission-oriented vehicle routing problem on a multigraph. European Journal of Operational Research, 2021.

(continued in next comment)

W2. [...] it does not address the arguably more pressing bottlenecks in neural routing, namely cross-distribution generalization [...] the contribution, while technically competent, advances a specific representational axis (multigraphs) [...]

Thank you for acknowledging our work as technically competent. We agree that cross-distribution and cross-problem generalization are important open problems, but they are orthogonal to our contribution, which targets the representational and computational cost of multigraphs.

These directions are also complementary, since model-agnostic approaches to cross-distribution generalization, such as meta-learning [11], knowledge distillation [12], or distributionally robust optimization [13] can in principle be directly integrated with NEPF. We have added this perspective to the Conclusion. Additionally, in response to reviewer Jr1K, we applied NEPF together with pre-trained cross-task models (GOAL [14] and URS [15], see Table 8), addressing the cross-problem generalization direction further.

We also believe that the field of Neural Combinatorial Optimization (NCO) is held back by an over-fixation on synthetic benchmarks (e.g., the Euclidean TSP) and solving larger and larger instances, as much as a lack of cross-distribution generalization. The field should move towards more complex problems without near-optimal baselines, e.g., multigraph VRPs.

Questions For Authors:

Q1. [...] how sensitive is NEPF’s zero-shot performance to the training distribution (e.g., would training on the F.5 instances change conclusions), and does the pre-encoding aggregation transfer better or worse than the baselines across these shifts?

Thank you for the suggestion regarding F.5. We agree that training on these instances would present a cleaner picture, since we could then separate OOD generalization capability from in-distribution performance across the realistic instances. To remove the distribution shift, we retrained NEPF, GMS-DH and GMS-EB on each of the realistic distributions (NC, WC, SC) with the main protocol and re-ran F.5 in-distribution. These results have been added to Table 22 alongside the existing zero-shot results. From the now available comparison, NEPF is the strongest in 5/6 settings zero-shot. Trained in-distribution, it is the best or tied best in 5/6 settings. This highlights both OOD advantages and real-world applicability of our method. In short, training on realistic distributions did not change the conclusions in the original submission.

We also remark that Appendix F.6 was already trained in-distribution, providing a clear picture not confused by generalization capabilities. There NEPF shows the strongest performance overall.

To answer the cross-distribution generalization question further, we additionally evaluated NC/WC/SC checkpoints for NEPF, GMS-DH and GMS-EB on each distribution, creating a 3x3 generalization matrix (see Table 23). NEPF degrades least of the three methods in four of six transfers, with only minor differences in the remaining two cases.

We hope these additions clarify the contribution and its scope, and that the new experiments provide a clearer picture on real-world applicability and out-of-distribution generalization. We are happy to discuss further or run additional experiments.

References:

[11] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML, 2023.

[12] Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation. NeurIPS, 2022.

[13] Learning to Solve Routing Problems via Distributionally Robust Optimization. AAAI, 2022.

[14] GOAL: A Generalist Combinatorial Optimization Agent Learner. ICLR, 2025.

[15] URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization. ICML, 2026.

Thank you but all cited papers are different community/field (i.e. OR and Transportation) where their focuses are mainly about exact methods.

Comments on the paper

4 comments

Dear Reviewers,

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

Best, AC

Dear Reviewers,

Before the end of the rebuttal period, we want to summarize the changes we have implemented in response to the raised concerns. All changes are marked in blue in the revised manuscript.

  • Learned edge stage (Jr1K): comparison against an exact FSASP solver on NEPF's node orders, per-edge greedy and a non-myopic beam label-setting heuristic (Table 28). The learned stage is close to optimal in most settings, and an exact solver can be plugged in at inference if available.
  • Node–edge split vs. compression (Jr1K): a 2×2 ablation with a joint edge head and a variant without pre-encoding aggregation (Table 29). Also a quantitative analysis of the state estimator (Table 12).
  • Scalability (Jr1K): zero-shot quality up to N = 1000 with M = 20 parallel edges and an extended memory/runtime stress test up to N = 2000 (Tables 19–20).
  • Foundation models (Jr1K, w4oc): NEPF on top of the pretrained GOAL and URS models. These become extended to multigraph routing, while retaining their original-task performance under rehearsal (Tables 8, 14–15).
  • Beyond routing (Jr1K, w4oc): NEPF applied to flexible job-shop scheduling, outperforming the dedicated neural solver HGNN on both synthetic benchmarks (Section 5.4).
  • Additional baseline and scoping (RUFQ): a pre-pruning + MatNet baseline (Tables 26–27), which NEPF outperforms in seven of eight multi-objective settings at 3–8× lower runtime, and consistent scoping to "best neural multigraph method".
  • Training budget (RUFQ): training time per epoch for all six problems and all methods (Table 10).
  • Realistic instances and OOD generalization (w4oc): all neural methods retrained on the realistic distributions, and a 3×3 cross-distribution transfer matrix (Tables 22–23). Also a literature overview supporting the practical relevance of multigraph routing.

We thank all of you for your continued effort in the review process. If you have any doubts or questions remaining, we will do our best to address them within the remaining time.

Best regards, The authors

Dear Reviewers,

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

Best, AC

AuthorsOpenReview ↗

Final note to the AC

Dear Area Chair,

We would like to briefly summarize the discussion phase.

  • Reviewer Jr1K raised their score (2 to 3) after our new experiments, which they confirmed addressed most of their concerns. We have also adopted their one remaining suggestion in the main text (Section 5.5).
  • Reviewer RUFQ (score 3) has confirmed that they have no further questions after our clarifications.
  • Reviewer w4oc (score 2) responded briefly, maintaining their rating without specifying which concerns remain. We have asked them to clarify.
    • They explicitly acknowledge the efficiency gains, the broad empirical coverage and the technical competence of the work.
    • Their main concerns: i) the practical significance of the problem setting, i.e., multigraph routing; ii) they view cross-distribution generalization as a more pressing problem in the field.
    • We addressed i) by pointing out the prominence of this problem in operations research, by clarifying that multigraph routing generalizes Euclidean and asymmetric routing (which most neural methods target), and by demonstrating usefulness on other problems (flexible job-shop scheduling).
    • We addressed ii) by clarifying that our work is orthogonal and complementary to this direction. We also ran new experiments that explicitly investigate OOD generalization and performance on realistic instances compared to baselines. NEPF is the strongest method in most of these settings.

In response to all reviewers, the revised manuscript adds (with changes in blue):

  • a comparison with exact edge selection (Jr1K, W1/Q1);
  • a 2×2 ablation of the node–edge split (Jr1K, Q2);
  • experiments with large N and M (Jr1K, W2/Q4);
  • integration with pretrained foundation models (Jr1K, W3);
  • an extension to flexible job-shop scheduling (Jr1K, Q5);
  • an additional pre-pruning baseline (RUFQ, W2/Q1);
  • OOD generalization experiments and further experiments on realistic instances (w4oc, W2/Q1).

Thank you for potentially taking these points into account in your recommendation, and for handling our submission.

Best regards, The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.