PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt

Yining Ma, Zhiguang Cao, Yeow Meng Chee

arXiv:2310.18264v1cs.LGcs.AI

TL;DR

Existing L2S solvers lag leading L2C and L2P methods, and prior k-opt approaches use small, fixed values of k. NeuOpt combines flexible k-opt search with GIRE for feasible and infeasible exploration, plus D2A at inference. The paper reports superiority over L2C and L2P solvers and LKH-3 on CVRP.

  • Problem

    Existing L2S solvers have limited search efficiency, and prior neural k-opt solvers use small, fixed k values.

    Source: §1 · pp. 1–2

  • Method

    NeuOpt uses a flexible k-opt policy and recurrent dual-stream decoder, with GIRE for constraint-aware feasible and infeasible exploration and D2A at inference.

    Source: §1 · p. 2

  • Results

    NeuOpt surpasses L2C and L2P solvers and LKH-3 on CVRP.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GIRE's exploration of feasibility boundaries can bridge feasible regions and help escape local optima.

    Source: §1 · p. 2

    Some baselines could not be reproduced, and code issues caused reported gaps to be underestimated by roughly 0.02% on TSP-50 and 0.04% on TSP-100.

    Source: §6.1 · p. 8

Abstract

from arXiv · show

In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.

1 Introduction

Although neural solvers have advanced, existing L2S methods remain less efficient than leading L2C and L2P solvers. The paper introduces NeuOpt, GIRE, and D2A to broaden L2S search and reports strong benchmark performance.

1 Introduction

  • NeuOpt factorizes flexible k-opt exchanges into S-, I-, and E-moves, letting the policy choose k and combine coarse- and fine-grained searches.Its recurrent dual-stream decoder models dependencies between removed and added edges.Source: §1 · p. 2
  • GIRE supplements constraint-violation and exploration features and shapes rewards to explore feasible and infeasible regions, including their boundaries.The paper applies GIRE to CVRP and describes it as generic to most VRP constraints.Source: §1 · p. 2
  • NeuOpt surpasses L2C and L2P solvers and the strong LKH-3 solver on CVRP.The paper presents experiments on TSP and CVRP and identifies this CVRP comparison as a contribution.Source: §1 · p. 2
  • D2A augments inference to increase search diversity and help escape local optima.NeuOpt is trained with a reinforcement-learning algorithm from prior work [12].Source: §1 · p. 2

2 Literature review

The review distinguishes neural routing solvers by how they construct, search, or predict solutions, and describes their respective limitations. It also surveys k-opt search and constraint handling.

L2C and L2P solvers

  • L2C builds solutions quickly but can get trapped in local optima, while L2P predicts useful search information but is less general for VRP constraints beyond TSP.L2C methods include Ptr-Net and Attention Model; POMO [4] improved AM with diverse rollouts and data augmentation.Source: §2 · pp. 2–3

k-opt and traditional solvers

  • Unless specified otherwise, k-opt refers to an exchange introducing k entirely new edges; broadly, added edges may coincide with removed ones, so 2-opt may be viewed as degenerated 8-opt.Source: §2 · p. 2

L2S solvers

  • L2S learns to refine solutions directly, but prior methods relied on handcrafted search components or fixed small k and lagged leading L2C solvers.Examples include ruin-and-repair in NLNS, 2-opt methods [9] [16], and a 3-opt extension.Source: §2 · p. 3

L2P solvers

  • L2P methods can scale to larger TSP instances, but are mostly limited to supervised learning and often struggle with VRP constraints.DPDP [42] addressed CVRP with dynamic programming, while latent-space approaches may be time-consuming or ineffective for constraints.Source: §2 · p. 3

Feasibility satisfaction

  • Most neural solvers use masks to filter invalid actions, while prior constraint-awareness approaches overlooked temporary violations used by traditional solvers.The review distinguishes VRP constraint handling from safe RL, which focuses on avoiding risky actions in uncertain environments [47] [48].Source: §2 · p. 3

3 Preliminaries and notations

The section defines routing solutions and describes k-opt as iterative edge exchange. It also outlines sequential exchange and varying k as ways to shape the search neighborhood.

VRP notations

  • A TSP solution is a Hamiltonian cycle; a CVRP solution uses depot-based subtours that visit each customer once without exceeding vehicle capacity.The section defines the problem on a complete directed graph with Euclidean edge weights.Source: §3 · p. 3

Traditional k-opt heuristic

  • A k-opt move exchanges k existing edges for k entirely new edges, while sequential exchange links each removed edge and successive added edges through shared endpoints.The paper's convention excludes added edges that coincide with removed ones when referring to k-opt.Source: §3 · p. 3
  • LK schedules increasing k values to vary search neighborhoods and help escape local optima.The paper's approach draws on this idea to choose k flexibly.Source: §3 · p. 3

Figure 1

  • Figure 1 illustrates an RDS decoder producing a 3-opt exchange on TSP-9 over four steps, with an E-move at the final step.Its upper portion depicts dual-stream attentions and its lower portion shows the resulting solution modification.Source: Figure 1 · p. 4

4 Neural k-opt (NeuOpt)

NeuOpt addresses the challenges of flexible k-opt search with a basis-move factorization and recurrent dual-stream decoder. Dynamic Data Augmentation refreshes instances when search stagnates.

4 Neural k-opt (NeuOpt)

  • NeuOpt targets unified k-opt search for any k ≥2, with action factorization and a customized decoder.The formulation uses starting, intermediate, and ending moves; the number of intermediate moves determines k.Source: §4 · p. 4, §4.1 · p. 4

4.1 Formulations

  • An I-move adds an edge from the lower-ranked path endpoint to a node ranked beyond both endpoints, removes its outgoing edge, and reverses intervening directions.The S-move opens a Hamiltonian cycle into a path, while the E-move reconnects its endpoints into a cycle.Source: §4.1 · pp. 4–5

4.2 Recurrent Dual-Stream (RDS) decoder

  • The RDS decoder uses separate move and edge streams to model past selections and proposed edges, while GRUs sequentially select nodes and infer move types.The move stream takes the last selected node as input; the edge stream takes the source node of the proposed edge.Source: §4.2 · p. 5

4.3 Inference with the dynamic data augmentation (D2A)

  • D2A generates new augmented instances after up to TD2A consecutive steps without a better solution, diversifying inference searches when the solver is trapped in local optima.Earlier augmentation applied optimal-solution-invariant transformations only once at inference start.Source: §4.3 · p. 6

5 Guided infeasible region exploration (GIRE)

GIRE extends CVRP search beyond feasible solutions, supplementing the policy with constraint and exploration features and shaping rewards to regulate exploration. Its design addresses the fragmentation of feasible regions under masking.

5 Guided infeasible region exploration (GIRE)

  • Masking confines search to feasible regions, which may be fragmented into isolated islands; GIRE explores both feasible and infeasible regions.The paper motivates this exploration as a route to shortcuts, boundary searches, and possibly isolated regions.Source: §5 · p. 6, Figure 2 · p. 6
  • GIRE adds violation indicators for infeasible solution portions and exploration statistics based on recent feasibility-transition probabilities.For CVRP, binary node features indicate whether cumulative demand exceeds capacity before or after visiting a node.Source: §5 · p. 6
  • H[P] imposes larger penalties when estimated feasibility-transition probabilities are too high or too low, regulating extreme exploration.The regulation uses an entropy measure over transitions within feasible and infeasible regions.Source: §5 · p. 7, Figure 3 · p. 7
  • Reward shaping also treats an infeasible but ϵ-feasible solution as a potential new best-so-far solution.The ϵ-feasible region consists of solutions whose capacity violation percentage does not exceed ϵ.Source: §5 · pp. 6–7

6 Experiments

Experiments evaluate NeuOpt and NeuOpt-GIRE on TSP and CVRP through benchmark comparisons, ablations, generalization and scalability tests, and hyper-parameter studies. The reported findings include comparisons with neural and traditional solvers, component effects, and performance-cost trade-offs.

6.1 Comparison studies

  • On TSP, NeuOpt surpasses multiple L2P and L2C baselines and halves L2S gaps; on CVRP, NeuOpt-GIRE surpasses strong L2C baselines and LKH-3.The comparisons use TSP and CVRP benchmarks.Source: §6.1 · pp. 7–8, Table 1 · p. 8
  • On CVRP-20, GIRE improves both NeuOpt and DACT-U, reduces mask computation time with marginally larger models, and NeuOpt with K=4 further improves performance at slightly increased runtime.The comparison upgrades DACT to DACT-U with the same embeddings and encoders as NeuOpt.Source: §6.1 · p. 9, Table 2 · p. 9

6.2 Ablation studies

  • Removing GRUs or either RDS stream harms contextual modeling, while D2A consistently improves inference on TSP-100 and CVRP-100.The ablations evaluate the RDS components and D2A separately.Source: §6.2 · p. 9, Table 3 · p. 9, Table 4 · p. 9
  • VI improves GIRE outcomes with or without RS, ES helps only with RS, and complete GIRE is lowest and most stable; learnable S-move and flexible E-move improve search performance.Without E-move, fixed-K search performs worse at larger K.Source: §6.2 · pp. 9–10, Figure 4 · p. 9, Figure 5 · p. 9

6.3 Generalization and scalability studies

  • On TSPLIB and CVRPLIB, NeuOpt achieves lower gaps than DACT and L2C baselines, including AMDKD; when trained directly at size 200, it surpasses LKH-3 on CVRP-200.The size-200 experiment also reports close-to-optimal solutions.Source: Table 7 · p. 10, §6.3 · p. 10, Table 5 · p. 10

6.4 Hyper-parameter studies

  • On TSP-100, varying K trades better performance for higher inference and training costs, while moderate α and β values yield more effective reward shaping on CVRP-20.The α and β study varies one weight while fixing the other, including values of 0.01 and 0.1.Source: §6.4 · p. 10, Table 8 · p. 10, Figure 6 · p. 10

7 Conclusions and limitations

NeuOpt combines flexible k-opt exchanges with a recurrent dual-stream decoder, while GIRE explores feasible and infeasible regions and D2A diversifies inference searches. The paper notes that NeuOpt remains less scalable than some L2P solvers on larger TSPs.

7 Conclusions and limitations

  • NeuOpt’s scalability exceeds existing L2S solvers but remains behind some L2P solvers on larger TSPs.The authors identify divide-and-conquer, heatmaps, more scalable encoders, and optimized CUDA code as possible future directions.Source: §7 · p. 10

A Action factorization examples

B NeuOpt encoder

  • The encoder separately embeds instance and tour-position features, refines them through three stacked encoders, and sends unified embeddings to the RDS decoder.For CVRP, node features include coordinates and demand-related quantities; when GIRE is used, they also include violation indicators.Source: B NeuOpt encoder · pp. 15–16

C Training and inference algorithms

NeuOpt training adapts n-step PPO with curriculum learning, while GIRE uses separate critics for its reward-shaping terms. At inference, D2A refreshes augmentations when search stalls, supporting more diverse searches.

C.1 Training algorithm

  • NeuOpt is trained with n-step PPO and curriculum learning; GIRE adds separate critics to estimate its reward-shaping terms.The GIRE training updates compute separate returns and advantages for the original reward and replace the PPO loss equations accordingly.Source: §C.1 · p. 16

C.2 Inference algorithm

  • Earlier inference augmentation was fixed after its one-time application at the start of the search.The invariant transformations preserve the identical optimal solution while producing instances the trained model can solve differently.Source: §C.2 · p. 17, Table 9 · p. 17
  • D2A generates new augmented instances when a search makes no improvement for the configured consecutive-step limit.Each augmented instance has its own stall counter, and the inference loops over augmented instances can run in parallel.Source: §C.2 · p. 17

D Additional discussions on GIRE scheme

The GIRE discussion examines reward shaping, feasibility thresholds, entropy-penalty settings, and possible adaptation to other constraints. It reports that reward shaping moderates search behavior and improves training outcomes.

D Additional discussions on GIRE scheme

  • GIRE’s separate critics share upgraded policy embeddings but use distinct additional features for their value estimates.The critics are implemented as four-layer MLPs; the regularization, bonus, and violation-region critics use different extra inputs.Source: D Additional discussions on GIRE scheme · pp. 17–18
  • D2A runs multiple augmented instances, replacing an instance when its stall counter reaches the configured limit.Each instance starts with a random solution, is searched independently, and receives a new augmentation after the stall threshold.Source: D Additional discussions on GIRE scheme · p. 18
  • With reward shaping, GIRE has more stable training, lower variance, and lower objective values; without it, runs can favor feasible regions and become trapped.The paper links very low P(U|U), below 0.1 in the worst case, to extreme search behavior and failed convergence to lower objective values.Source: D Additional discussions on GIRE scheme · pp. 18–19, Figure 8 · p. 19
  • The ϵ threshold is set as ζ × N_customer × (δ̄/∆), with ζ = 0.1, representing a violation equivalent to a fraction of customers each having average demand.Figure 9 examines the impact of varying ζ.Source: D Additional discussions on GIRE scheme · p. 19, Figure 9 · p. 19
  • The authors set c1 = 0.5 and c2 = 2.5 to penalize feasibility-transition probabilities outside [0.25, 0.75], and report that these parameters may not affect training stability.The parameters shape the entropy penalty range; Figure 10 illustrates pattern changes and Figure 11 investigates training stability.Source: Figure 10 · p. 19, D Additional discussions on GIRE scheme · p. 19, Figure 11 · p. 20
  • GIRE’s feature supplement can use binary indicators for constraint violations, while its exploration-statistics features and reward shaping can be retained for other constraints.The authors suggest defining ϵ-feasible regions by a fraction of violating nodes, with ζ = 0.1.Source: D Additional discussions on GIRE scheme · p. 20

E.1 Details of implementation

The implementation details specify training settings, benchmark generation, and baseline configurations. The authors also note that some baseline comparisons rely on reported rather than reproduced results, and that a distance-metric mismatch may affect certain reported gaps.

E.1 Details of implementation

  • Training uses 200 epochs and 20 batches per epoch, with batch sizes of 512 for TSP and 600 for CVRP; CVRP training takes about 4–8 days depending on size and GPU count.Other settings include d = 128, PPO clip threshold 0.1, and reward discount factor 0.999.Source: §E.1 · p. 20
  • Training and test coordinates are sampled uniformly in the unit square; CVRP demands come from {1, 2, ..., 9}, with capacity set by instance size.The implementation duplicates depots for GPU parallelization, using 10, 20, and 20 dummy depots for sizes 20, 50, and 100.Source: §E.1 · p. 20
  • Some TSP baseline gaps may be underestimated by about 0.02% at size 50 and 0.04% at size 100 because optimal solutions were computed with GEO rather than EUC distances.The authors note that this mismatch can make the GEO-optimal tours non-optimal under the Euclidean objectives used by neural solvers.Source: §E.1 · p. 20
  • L2C baselines use configurations including 200 samplings and eight augmentations for Sym-NCO and POMO, with EAS and SGBS settings varying by benchmark.Pointformer is run with 200 samplings and eight augmentations; POMO+EAS uses 200 iterations, and POMO+EAS+SGBS uses separate short and long round counts.Source: §E.1 · p. 21
  • The L2S and L2P baselines use varied search budgets and inference procedures, including 2-opt, 3-opt, ruin-and-repair, heatmaps, and diffusion.Some results are taken directly from prior reports when code was unavailable, incompatible, or too costly to reproduce.Source: §E.1 · p. 21

E.2 Generalization on real-world datasets

NeuOpt was evaluated on real-world TSPLIB and CVRPLIB instances that differ from its training distributions. It achieved lower average gaps than the reported baselines, though the authors note that L2S generalization still has room to improve.

E.2 Generalization on real-world datasets

  • The evaluation tested models trained on TSP100 and CVRP100 against real-world instances with up to 200 nodes and differing sizes and node distributions.Comparisons included DACT and generalization-enhanced L2C baselines; post-hoc per-instance boosters such as EAS were excluded to focus on the deep models.Source: §E.2 · pp. 21–22
  • On TSPLIB, NeuOpt achieved lower average gaps than DACT at 10k solutions and could surpass DACT at 40k solutions when exploring 25k solutions.It also yielded lower gaps than AM-mix, POMO-mix, and AMDKD (POMO).Source: Table 10 · p. 22, §E.2 · p. 22
  • On CVRPLIB, NeuOpt delivered the lowest average gaps among the compared baselines.The authors note that L2S solvers, including NeuOpt, still have room to improve generalization.Source: §E.2 · p. 22

E.3 Results on TSP-200 and CVRP-200

NeuOpt was tested at size 200 and with multi-GPU inference. The models found close-to-optimal solutions, while the authors report shorter practical runtimes when multiple GPUs are used.

E.3 Results on TSP-200 and CVRP-200

  • For size 200, the experiments used ξ = 0.125 for both problems, with CVRP capacity ∆ = 70 and 30 dummy depots; other hyperparameters were unchanged.The models were compared with traditional heuristics.Source: §E.3 · p. 22
  • NeuOpt consistently found close-to-optimal TSP-200 and CVRP-200 solutions, even outperforming LKH3 on CVRP-200.The authors cite prohibited longer training times as a reason existing L2S solvers may be inefficient to train at size 200, underscoring NeuOpt’s better scalability.Source: §E.3 · p. 22, Table 12 · p. 23

E.4 Inference with multiple GPUs

  • Multiple GPUs can substantially shorten inference runtimes for solving 10,000 instances compared with the single-GPU timing reported in Table 1.Table 13 reports inference times for different GPU counts.Source: §E.4 · p. 23, Table 13 · p. 23

E.5 Visualization of exploration behaviour

NeuOpt-GIRE’s search trajectories show exploration of both infeasible and feasible regions. The authors also report that infeasible solutions commonly precede new best-so-far feasible solutions.

E.5 Visualization of exploration behaviour

  • On five random CVRP-20 instances, NeuOpt-GIRE tended to explore infeasible regions early, correct violations, and then alternate between infeasible and feasible searches.The authors suggest infeasible exploration may foster shortcut discovery, promising boundary searches, and identification of isolated feasible regions.Source: §E.5 · pp. 23–24, Figure 12 · p. 24
  • Around 80% of new best-so-far feasible solutions were preceded by at least one infeasible solution among the last five visited solutions.Figure 13 visualizes the estimated distribution as step size T increases.Source: Figure 13 · p. 24, §E.5 · p. 24

E.6 Used assets and licenses

  • The listed assets are open-source for academic research use, and the code and pretrained models are available on GitHub under the MIT License.Table 14 lists the pretrained models, code, and datasets.Source: §E.6 · p. 24, Table 14 · p. 24

Related papers

Loading 2310.18264v1…