acceptodds
Withdrawn from ICLR 2027

Rethinking Order-First Split-Second for Vehicle Routing Problems in Neural Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Neural combinatorial optimization (NCO) has achieved promising performance in vehicle routing problems (VRPs), but how solution representation affects the learning process remains unclear. Inspired by the classical order-first, split-second strategy, we investigate whether neural routing models can benefit from generat- ing only customer orders while delegating route partitioning to an exact Split de- coder. We conduct a systematic comparison between direct route construction and customer-ordering policies with Split decoding under single-task learning, multi- task learning, and various generalization settings. Experiments are performed on synthetic instances, public benchmarks, larger problem sizes, and unseen combi- nations of routing constraints. The results show that replacing route construction with customer ordering does not provide consistent improvements. Although Split can always obtain the best feasible partition for a given customer order, it cannot modify an inappropriate order or recover information unavailable to the policy. The performance gap becomes more significant when constraints, such as hard time windows, strongly couple customer ordering and route planning. These find- ings indicate that reducing the number of neural decisions alone is insufficient to improve routing performance. Effective neural routing methods require joint consideration of solution representation, available information, and downstream optimization procedures.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Vehicle Routing Problems, Solution Representation, Split Algorithm.

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_QownOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper compares direct route construction with an order-first, split-second scheme in neural VRP solvers, where the policy outputs only a customer order and an exact Split dynamic program partitions it into routes. Across single-task, multi-task, and generalization settings with matched backbones, direct construction is consistently better, especially with hard time windows.

Critical strengths

Broad coverage. The same conclusion is tested across single-task, multi-task, size generalization, and public benchmarks, rather than on one setting.

Critical weaknesses
  1. An order-first policy without meaningful state updates is expected to be worse than direct construction. The comparison is therefore confounded, and the claim that both policies receive the same information holds only nominally.
  2. The conclusion is overgeneralized. The order-first method may be worse only because its design is poor, so the results do not show that OFSS itself is ineffective.
  3. The contribution to current research is limited. Almost no current constructive NCO method uses Split, so a negative result on this representation does not change what the community is doing. As a result, it does not deliver the “rethinking” its title promises.
Questions for authors

I thank the authors for these experiments, and I can feel the effort behind them, but I really doubt the contribution to this community. I would like the authors to provide:

  1. More variants of the order-first policy that are aware of state updates, to show whether the gap remains when the policy has a meaningful capacity and time state.
  2. A direct policy with the capacity and time state removed, to separate the effect of information loss from the effect of delegating partitioning to Split.
  3. An explanation of why HGS achieves notable results with OFSS, and which of those factors are absent in the neural setting.
  4. An analysis of why the learned orders are poor, to show whether the gap comes from the order-first representation itself or from the quality of the learned orders.
  5. Even if it is firmly established that order-first is worse than direct construction, what does this contribute to current NCO research?
Reviewer_fjJXOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper shares negative results of applying the Order-First Split-Second strategy to solve the Vehicle Routing Problem. Motivated by the success of the OFSS strategy in HGS, it designs a neural policy to learn it via REINFORCE. The proposed framework is extensively tested in diverse settings, such as single-task, multi-task, and generalization.

Critical strengths
  1. The motivation is good.
  2. The evaluation is extensive across diverse settings, such as single-task, multi-task, and generalization.
  3. The code is provided for follow-up.
Critical weaknesses
  1. The presentation is poor:
  • inappropriate wording, such as OFSS representation and neural formulation (in line 150).
  • insufficient positioning of the contribution, such as lacking the difference from the most related works applying OFSS and neural construction.
  1. Overclaimed. See example in questions.
  2. Insufficient contributions. Although I appreciate the negative results, I do not see any in-depth insights from the authors' interpretation. This paper focuses too much on performance in different settings, which they consider as ''systematic rethinking''. However, I would more like to see why it doesn't work.
Questions for authors
  1. Why is OFSS considered a ''representation'' throughout the whole paper? I think this term is inappropriate, as OFSS is a decoding paradigm for solving the VRP.
  2. The claim that ''effective neural combinatorial optimization requires joint consideration of solution representation, policy inputs, and downstream optimization procedures" isn't fully verified. Are there any success and failure cases to support this claim? Much better, could the authors provide a successful example that originally failed and achieved success after following the guideline in your claim?
  3. In Lines 141-156, the introduction of the two most related works that have adopted the OFSS is unclear in two aspects: what they actually did and the differences with your work (especially why they work while yours doesn't).
  4. What is special about the neural construction policy of giant tours compared with the canonical autoregressive paradigm? It seems that the giant tour construction is a special case of the canonical construction without returning to the depot.
Reviewer_AxQEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper asks whether the classical Order-First Split-Second (OFSS) scheme can replace joint ordering-and-partitioning in constructive neural VRP solvers. Under matched backbones (AM, POMO) and multi-task models (POMO-MTL, MVMoE/4E), it compares Direct construction against Order–Split on synthetic CVRP/CVRPTW, 16 multi-task variants, larger sizes (200/500/1000), and CVRPLIB X-set/XML100/Solomon. Split variants are uniformly worse on aggregate, with the largest gaps under hard time windows; the authors conclude that delegating partitioning to an exact algorithm does not compensate for lost route-level decision information.

Critical strengths
  1. OFSS is foundational in classical metaheuristics but has rarely been examined inside constructive NCO, and the paper takes up this gap with a reasonably broad program

  2. The implementation checks are rigorous: Split is validated against exhaustive enumeration on small instances, and every saved solution passes an independent verifier covering coverage, capacity, time windows, backhaul transitions, and integer EUC_2D cost, so the reported gaps are not caused by bugs or infeasibility.

  3. Failure reporting is honest: backhaul×hard-time-window variants are excluded from conditional averages rather than averaged over the small feasible subset, and per-instance results together with route visualizations are provided.

Critical weaknesses
  1. Order–Split changes more than the representation: masks are removed, decoder state is not reset at boundaries (Appendix E), service duration drops from multi-task input, and only a backhaul mask survives, so the gap mixes OFSS, lost constraint-awareness, and altered state evolution rather than isolating the representation.

  2. The central lesson is stated at a high level but never operationalized. The paper offers no design principle for choosing Direct vs Order–Split, no hybrid recipe, and no analysis of the positive exceptions it reports that could define conditions under which OFSS remains competitive. The result therefore establishes "what does not work" but gives the NCO community little guidance on what to do next, limiting impact beyond this specific negative finding.

  3. Classical OFSS sits inside a reorder/refinement loop, while this study evaluates one frozen pass with no refinement, so the result speaks to this single-shot policy rather than OFSS broadly; it also gives no rule for choosing Direct vs Order–Split, no hybrid, and ignores exceptions like POMO Solomon-100 (−11.81% distance) or AM-Split using fewer vehicles at n=1000.

  4. One training run per setting, no seed variance or CIs; multi-task results compare against published aggregate means without pairing or common runtime. On Solomon selection is distance-first and non-lexicographic; the size gap is non-monotonic (AM +6.39% → +17.05% → +8.98%) and unexplained; Split's O(n²) cost is omitted.

Questions for authors

See Weaknesses.

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

Related papers

Discussion (0)

Sign in to comment.