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

Yining MaZhiguang CaoYeow Meng Chee

article2023NeurIPS129 citations

Presents NeuOpt, a learning-to-search solver that enables flexible neural k-opt operations across both feasible and infeasible solution spaces to outperform state-of-the-art neural and classical heuristics on complex vehicle routing problems.

Listen

Vehicle routing problems are core operational challenges in logistics and transportation, where optimizing delivery routes directly impacts fuel costs, delivery timelines, and fleet utilization. Deep reinforcement learning methods have emerged to automate algorithm design for these problems. However, existing learning-to-search methods have been limited by rigid search neighborhood sizes and a strict reliance on feasibility masking, which restricts exploration solely to valid routes and often traps algorithms in suboptimal solutions.

The article aims to overcome these limitations by developing a learning-to-search framework, Neural k-Opt (NeuOpt), capable of dynamically adjusting edge-exchange moves of any size, combined with a Guided Infeasible Region Exploration (GIRE) strategy that strategically explores both valid and temporarily invalid solution spaces.

To evaluate this approach, the authors tested NeuOpt across synthetic benchmarks (sizes of 20, 50, 100, and 200 nodes) and standard public datasets (TSPLIB and CVRPLIB) on Traveling Salesman and Capacitated Vehicle Routing Problems. The system breaks down complex edge-exchange moves into manageable basis steps decoded by a recurrent dual-stream network. It incorporates violation indicators and exploration statistics into the policy, guides reinforcement learning via reward shaping, and applies dynamic data transformations during inference to avoid local traps.

The findings show that NeuOpt achieves near-optimal performance, reducing optimality gaps on 100-node Traveling Salesman Problems to 0.00% within reasonable runtimes and halving the gaps of previous learning-to-search methods. On the Capacitated Vehicle Routing Problem, it outperforms existing learning-to-search, learning-to-construct, and learning-to-predict baselines, and is the first neural search solver to surpass the strong classical heuristic benchmark, LKH-3. Ablation experiments confirmed that enabling controlled excursions into infeasible regions accelerates discovery of higher-quality feasible solutions, with roughly 80% of successful solution updates preceded by visiting infeasible intermediate routes.

These results demonstrate that artificial intelligence routing models can surpass leading specialized heuristics without requiring expensive per-instance retraining. Bypassing strict feasibility masks reduces computational overhead and enables algorithms to discover structural shortcuts across isolated feasible solution regions, offering organizations better route quality with lower operational runtimes.

For practical adoption, organizations can evaluate NeuOpt on constrained vehicle routing workloads by integrating dynamic data transformations and multi-GPU parallel processing to accelerate deployment. Future development should focus on testing the infeasible exploration framework on broader operational constraints, such as time windows and pickup-and-delivery dependencies, as well as integrating divide-and-conquer strategies for scaling beyond several hundred stops.

Confidence in these findings is high across standard academic benchmarks and problem sizes up to 200 nodes. However, caution is warranted when scaling directly to thousands of stops without problem decomposition, or when applying the solver to complex, multi-constraint distribution systems that differ substantially from the uniform benchmark distributions evaluated in the study.

National University of Singapore Singapore Management University routing problems routing scheme shortest path problem neural combinatorial optimization vehicle routing k-opt heuristics

arXiv: 2310.18264

Paper: Attention, Learn to Solve Routing Problems!, Wouter Kool et al. (2018). It introduces the foundational attention-based reinforcement learning framework for routing problems like TSP and CVRP that modern neural routing solvers build upon and compare against.
Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). It pioneers reinforcement learning policy gradients for combinatorial optimization and routing problems, providing the core learning paradigm adapted by learning-to-search methods.
Paper: Pointer networks, Oriol Vinyals et al. (2015). It introduces Pointer Networks for variable-length combinatorial routing outputs, which underpin modern neural action selection mechanisms.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). It establishes graph neural network embeddings combined with deep reinforcement learning for solving graph-based combinatorial optimization problems.
Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). It provides a comprehensive taxonomy and conceptual framework categorizing machine learning approaches for discrete combinatorial optimization, including search and construction paradigms.
Paper: Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping, Andrew Y. Ng et al. (1999). It formalizes the theoretical foundations of potential-based reward shaping, which directly inspires the reward shaping schemes used in guided infeasible region exploration.
Paper: Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization, Minsu Kim et al. (2022). It demonstrates how exploiting geometric symmetries and data augmentation enhances neural combinatorial optimization solvers for vehicle routing.

Paper: Combinatorial Optimization and Reasoning with Graph Neural Networks, Quentin Cappart et al. (2023). It synthesizes graph neural network reasoning and hybrid search techniques across combinatorial optimization paradigms, offering a broader perspective on the neural search concepts explored in NeuOpt.

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

Abstract

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.

Topics

routing problems routing scheme shortest path problem

Keywords

neural combinatorial optimization vehicle routing k-opt heuristics reinforcement learning policy optimization feasible regions active search dynamic programming

1 Introduction
2 Literature review
3 Preliminaries and notations
4 Neural k-opt (NeuOpt)
4.1 Formulations
4.2 Recurrent Dual-Stream (RDS) decoder
4.3 Inference with the dynamic data augmentation (D2A)
5 Guided infeasible region exploration (GIRE)
6 Experiments
6.1 Comparison studies
6.2 Ablation studies
6.3 Generalization and scalability studies
6.4 Hyper-parameter studies
7 Conclusions and limitations
Acknowledgments and Disclosure of Funding
References
A Action factorization examples
B NeuOpt encoder
C Training and inference algorithms
C.1 Training algorithm
C.2 Inference algorithm
D Additional discussions on GIRE scheme
E Additional experimental results
E.1 Details of implementation
E.2 Generalization on real-world datasets
E.3 Results on TSP-200 and CVRP-200
E.4 Inference with multiple GPUs
E.5 Visualization of exploration behaviour
E.6 Used assets and licenses

Knowls

Knowl 1 — Action Factorization for Flexible Neural k-Opt
model/method
Neural $k$ -Opt (NeuOpt) introduces an action factorization method that constructs any sequential $k$ -opt exchange ( $k \ge 2$ ) on a route or tour by composing three primitive basis moves:
1. Starting move ( $S$ -move): Removes an existing edge $e^{\text{out}}(x_a \to x_b)$ from a tour $\tau$ , converting the Hamiltonian cycle into an open Hamiltonian path with endpoints $x_a$ and $x_b$ . The starting node $x_a$ is termed the anchor node. Because $x_b$ is uniquely determined as the successor of $x_a$ in $\tau$ , the move is parameterized solely by $x_a$ , denoted $S(x_a)$ .
  
  Definition (Node rank): For a solution tour $\tau$ and anchor node $x_a$ , the node rank $\Gamma[x_a, x_u]$ (or $\Gamma[a, u]$ ) of node $x_u \in V$ is defined as the minimal number of directed edges in $\tau$ needed to reach $x_u$ starting from $x_a$ .
2. Intermediate move ( $I$ -move): Adds a new edge $e^{\text{in}}(x_u \to x_v)$ , removes an existing edge $e^{\text{out}}(x_v \to x_w)$ , and reverses edge directions between $x_j$ and $x_v$ to transform the open Hamiltonian path into a new valid Hamiltonian path. Letting $x_i, x_j$ be the current endpoints of the Hamiltonian path before the move (with $\Gamma[a, i] < \Gamma[a, j]$ ), the added edge must satisfy two sequential conditions to prevent step conflict: (a) $x_u = x_i$ (the lower-ranked endpoint) and (b) $\Gamma[a, i] < \Gamma[a, j] < \Gamma[a, v]$ . An $I$ -move is uniquely specified by selecting $x_v$ , denoted $I(x_v)$ .
3. Ending move ( $E$ -move): Adds a directed edge connecting the two endpoints of the current Hamiltonian path, completing a new closed Hamiltonian cycle $\tau'$ . It requires no node selection, denoted $E(x_{\text{null}})$ . If the rank condition is relaxed to $\Gamma[a, j] \le \Gamma[a, v]$ , an $E$ -move is equivalent to selecting $x_v = x_j$ , denoted $I'(x_j)$ or $E(x_j)$ .
For a maximum allowed step limit $K \ge 2$ , an action sequence $a = \{ \Phi_1(x_1), \dots, \Phi_K(x_K) \}$ consists of $\Phi_1(x_1) = S(x_1)$ followed by $(K-1)$ general $I$ -moves. The effective $k$ of the executed $k$ -opt corresponds directly to the number of intermediate moves performed before early termination via an $E$ -move or reaching step $K$ .
Knowl 2 — Recurrent Dual-Stream Decoder Architecture
model/method
The Recurrent Dual-Stream (RDS) decoder parameterizes the conditional distribution over basis moves $\pi_\theta(a|s) = \prod_{\kappa=1}^K P^\kappa_\theta(\Phi_\kappa | \Phi_1, \dots, \Phi_{\kappa-1}, s)$ as a sequential node-selection process over $N$ graph nodes.

Given node embeddings $h \in \mathbb{R}^{N \times d}$ from an encoder, the decoder maintains two distinct Gated Recurrent Unit (GRU) streams for contextual representation:
- Move stream ( $\mu$ ): Models global history of past selections by taking the embedding of the previous selected node as input: $o_\mu^\kappa = h_{\kappa-1}$ (with learnable initialization $o_\mu^1 = \hat{o}$ ).
- Edge stream ( $\lambda$ ): Models detailed local edge proposals by taking the embedding of the lower-ranked path endpoint node $x_{i_\kappa}$ (the source of the proposed edge) as input: $o_\lambda^\kappa = h_{i_\kappa}$ (with learnable initialization $o_\lambda^1 = \tilde{o}$ ).
The hidden states evolve via: $q_\mu^\kappa = \text{GRU}(o_\mu^\kappa, q_\mu^{\kappa-1}), \quad q_\lambda^\kappa = \text{GRU}(o_\lambda^\kappa, q_\lambda^{\kappa-1})$ where $q_\mu^0 = q_\lambda^0 = \frac{1}{N} \sum_{i=1}^N h_i$ .

Node selection scores from both streams are computed using additive and multiplicative (Hadamard product $\odot$ ) attention: $\mu_\kappa = \tanh \left( (q_\mu^\kappa W_\mu^{\text{Query}} + h W_\mu^{\text{Key}}) + (q_\mu^\kappa W_\mu^{\text{Query}'}) \odot (h W_\mu^{\text{Key}'}) \right) W_\mu^O$ $\lambda_\kappa = \tanh \left( (q_\lambda^\kappa W_\lambda^{\text{Query}} + h W_\lambda^{\text{Key}}) + (q_\lambda^\kappa W_\lambda^{\text{Query}'}) \odot (h W_\lambda^{\text{Key}'}) \right) W_\lambda^O$ where all $W \in \mathbb{R}^{d \times d}$ are learnable weight matrices.

The final categorical probability distribution over nodes $x_\kappa$ is computed by: $P^\kappa_\theta = \text{Softmax}(C \cdot \tanh(\mu_\kappa + \lambda_\kappa))$ with scaling constant $C = 6$ . Candidate nodes violating the sequential condition $\Gamma[a, j_\kappa] \le \Gamma[a, \kappa]$ are assigned $-\infty$ probability logit masks. An $E$ -move is triggered automatically if all nodes are masked or when the endpoint $x_\kappa = x_{j_\kappa}$ is selected.
Knowl 3 — Guided Infeasible Region Exploration Framework
model/method
Guided Infeasible Region Exploration (GIRE) enables neural local search to traverse infeasible solution spaces instead of relying on hard feasibility action masking. For the Capacitated Vehicle Routing Problem (CVRP):
1. Search Space Partition:
  - Feasible space $\mathcal{F}$ : Solutions satisfying both Hamiltonian tour constraints and vehicle capacity constraints $\Delta$ .
  - Infeasible space $\mathcal{U}$ : Solutions satisfying routing constraints but violating capacity constraints.
  - $\epsilon$ -Feasible space $\epsilon\text{-}\mathcal{F} \subseteq \mathcal{U}$ : Solutions whose total capacity violation percentage does not exceed $\epsilon$ , determined by $\epsilon = \zeta \times N_{\text{customer}} \times (\bar{\delta} / \Delta)$ , where $\bar{\delta}$ is the average customer demand and $\zeta = 0.1$ .
2. Feature Supplement:
  - Violation Indicator (VI) features: Two binary node features appended to raw node features indicating whether cumulative sub-tour demand exceeds vehicle capacity $\Delta$ before or after visiting node $x_i$ , increasing the raw feature dimension $d_h$ from 6 to 8.
  - Exploration Statistics (ES) features ( $J_t$ ): A 9-dimensional vector computed from the most recent $T_{\text{his}} = 25$ transition records $H_t = \{(\tau_{t'} \to \tau_{t'+1})\}_{t'=t-T_{\text{his}}}^{t-1}$ , comprising eight empirical transition probabilities ( $P(\tau \in \mathcal{F}, \tau' \in \mathcal{U})$ , $P(\tau \in \mathcal{U}, \tau' \in \mathcal{F})$ , $P(\tau \in \mathcal{F}, \tau' \in \mathcal{F})$ , $P(\tau \in \mathcal{U}, \tau' \in \mathcal{U})$ , $P(\tau' \in \mathcal{F} | \tau \in \mathcal{U})$ , $P(\tau' \in \mathcal{U} | \tau \in \mathcal{F})$ , $P(\tau' \in \mathcal{F} | \tau \in \mathcal{F})$ , $P(\tau' \in \mathcal{U} | \tau \in \mathcal{U})$ ) plus a binary indicator of the current solution's feasibility $\mathbb{I}(\tau_t \in \mathcal{F})$ .
3. Hypernetwork Parameter Conditioning: Two hypernetworks $\text{MLP}_\mu$ and $\text{MLP}_\lambda$ with architecture $(9 \times 8 \times d)$ take $J_t$ as input to dynamically generate the output projection weights $W_\mu^O, W_\lambda^O \in \mathbb{R}^{d \times 1}$ of the decoder, sharing the first hidden layer to reduce parameters.
Knowl 4 — GIRE Reward Shaping and Entropy Regulation
equation
In Guided Infeasible Region Exploration (GIRE), the reinforcement learning training reward $r_t^{\text{GIRE}}$ at search step $t$ is formulated as: $r_t^{\text{GIRE}} = r_t + \alpha \cdot r_t^{\text{reg}} + \beta \cdot r_t^{\text{bonus}}$ where:
- $r_t = f(\tau_t^{\text{bsf}}) - \min(f(\tau_{t+1}), f(\tau_t^{\text{bsf}}))$ is the standard improvement reward for objective tour cost $f(\cdot)$ relative to the best-so-far feasible solution $\tau_t^{\text{bsf}}$ .
- $\alpha = 0.05$ and $\beta = 0.05$ are reward-shaping hyperparameter weights.
- $r_t^{\text{bonus}} = f(\tau_t^{\text{bsf-wrt-}\epsilon}) - \min(f(\tau_{t+1}), f(\tau_t^{\text{bsf-wrt-}\epsilon}))$ rewards objective reductions on infeasible solutions that remain within the $\epsilon$ -feasible boundary $\epsilon\text{-}\mathcal{F}$ , where $\tau_t^{\text{bsf-wrt-}\epsilon}$ tracks the best-so-far $\epsilon$ -feasible cost.
- $r_t^{\text{reg}}$ penalizes extreme exploration behaviors (staying exclusively in $\mathcal{F}$ or exclusively in $\mathcal{U}$ ) using an entropy measure $H[\cdot]$ over estimated conditional self-transition probabilities $P_t(\mathcal{U}|\mathcal{U}) = P(\tau' \in \mathcal{U} | \tau \in \mathcal{U})$ and $P_t(\mathcal{F}|\mathcal{F}) = P(\tau' \in \mathcal{F} | \tau \in \mathcal{F})$ : $r_t^{\text{reg}} = -\mathbb{E}[r_t] \times \left( H[P_t(\mathcal{U}|\mathcal{U})] + H[P_t(\mathcal{F}|\mathcal{F})] \right)$ $H[P] = \text{Clip}\left( 1 - c_1 \log_2 \left[ c_2 \pi e P(1-P) \right], 0, 1 \right)$ with constants $c_1 = 0.5$ and $c_2 = 2.5$ , and running expectation $\mathbb{E}[r_t]$ estimated during training.
Knowl 5 — Dynamic Data Augmentation (D2A) Inference Algorithm
algorithm
Dynamic Data Augmentation (D2A) enhances search diversity during inference by monitoring whether parallel searches on augmented instances have stalled in local optima, triggering new randomized geometric augmentations when a stall threshold is exceeded.
Input: Problem instance $G$ , policy network $\pi_\theta$ , inference step budget $T$ , number of parallel augmentations $D2A$ , stall limit $T_{D2A}$
Output: Best solution found across all augmented instances
for $i = 1$ to $D2A$ do
     $G_i \leftarrow \text{Augmentation}(G)$
    Initialize random solution $\tau_{i,0}$ ; set best-so-far $\tau_i^{\text{bsf}} \leftarrow \tau_{i,0}$
    Set stall counter $T_i^{\text{stall}} \leftarrow 0$
end for
for $t = 1$ to $T$ do
    for $i = 1$ to $D2A$ in parallel do
        Sample basis moves from $\pi_\theta(\cdot | G_i, \tau_{i,t-1})$ to obtain new solution $\tau_{i,t}$
        if $f(\tau_{i,t}) < f(\tau_i^{\text{bsf}})$ then
             $\tau_i^{\text{bsf}} \leftarrow \tau_{i,t}$
             $T_i^{\text{stall}} \leftarrow 0$
        else
             $T_i^{\text{stall}} \leftarrow T_i^{\text{stall}} + 1$
        end if
        if $T_i^{\text{stall}} \ge T_{D2A}$ then
             $G_i \leftarrow \text{Augmentation}(G)$
             $T_i^{\text{stall}} \leftarrow 0$
        end if
    end for
end for
return $\arg\min_{\tau \in \{\tau_i^{\text{bsf}}\}} f(\tau)$
The Augmentation subroutine applies a random composition of four invariant transformations on coordinates: flip-x-y ( $(x', y') = (y, x)$ ), 1-x ( $(x', y') = (1-x, y)$ ), 1-y ( $(x', y') = (x, 1-y)$ ), and rotation by $\theta \in \{0, \pi/2, \pi, 3\pi/2\}$ . In standard evaluations, $T_{D2A} = 10$ .
Knowl 6 — PPO Training with Multi-Critic Architecture for GIRE
algorithm
NeuOpt-GIRE is trained with an $n$ -step Proximal Policy Optimization (PPO) algorithm coupled with a curriculum learning (CL) schedule and three separate value critics to independently approximate the value functions of the decomposed reward terms.
Input: Policy $\pi_\theta$ , critics $\{v_\phi^{\text{origin}}, v_\phi^{\text{reg}}, v_\phi^{\text{bonus}}\}$ , clipping threshold $\vartheta=0.1$ , learning rates $\eta_\theta=8\times 10^{-5}, \eta_\phi=2\times 10^{-5}$ , decay $\varsigma=0.985$ , inner loops $\Omega=3$ , rollout steps $n$ , training steps $T_{\text{train}}$ , epochs $E=200$ , batches per epoch $B=20$ , CL scalar $\xi$
for $\text{epoch} = 1$ to $E$ do
    for $\text{batch} = 1$ to $B$ do
        Sample batch $D = \{G_i\}$ with initial solutions $\{\tau_i\}$
        CL: Warm up $\{\tau_i\}$ by executing current $\pi_\theta$ for $T = \lfloor \text{epoch}/\xi \rfloor$ steps
         $t \leftarrow 0$
        while $t < T_{\text{train}}$ do
            Collect trajectory $\{(s_{t'}, a_{t'}, r_{t'}^{\text{origin}}, r_{t'}^{\text{reg}}, r_{t'}^{\text{bonus}})\}_{t'=t}^{t+n-1}$ using $\pi_\theta$
             $t \leftarrow t + n; \; \pi_{\text{old}} \leftarrow \pi_\theta; \; v_{\text{old}} \leftarrow v_\phi$
            for $j = 1$ to $\Omega$ do
                Compute discounted returns $\hat{R}^{\text{type}}_{t'}$ and advantages $\hat{A}^{\text{type}}_{t'} = \hat{R}^{\text{type}}_{t'} - v_\phi^{\text{type}}(s_{t'})$ for $\text{type} \in \{\text{origin}, \text{reg}, \text{bonus}\}$
                 $\hat{A}_{t'} \leftarrow \hat{A}^{\text{origin}}_{t'} + \hat{A}^{\text{reg}}_{t'} + \hat{A}^{\text{bonus}}_{t'}$
                Compute policy loss $L_\theta^{\text{GIRE}}$ :
                 $L_\theta^{\text{GIRE}} = \frac{1}{n|D|} \sum_{D} \sum_{t'=t-n}^{t-1} \min \left( \frac{\pi_\theta(a_{t'}|s_{t'})}{\pi_{\text{old}}(a_{t'}|s_{t'})} \hat{A}_{t'}, \text{Clip}\left(\frac{\pi_\theta(a_{t'}|s_{t'})}{\pi_{\text{old}}(a_{t'}|s_{t'})}, 1-\vartheta, 1+\vartheta\right) \hat{A}_{t'} \right)$
                Compute critic loss $L_\phi^{\text{GIRE}}$ summing clipped MSE losses across all three critics
                Update parameters: $\theta \leftarrow \theta + \eta_\theta \nabla L_\theta^{\text{GIRE}}$ ; $\phi \leftarrow \phi - \eta_\phi \nabla L_\phi^{\text{GIRE}}$
            end for
        end while
    end for
     $\eta_\theta \leftarrow \varsigma \eta_\theta; \; \eta_\phi \leftarrow \varsigma \eta_\phi$
end for
Each critic shares node representation features $\hat{y}_i = \hat{h}_i W^{\text{Local}} + \text{mean}(\{\hat{h}_i\}) W^{\text{Global}}$ and uses a 4-layer MLP conditioned on respective auxiliary features: $v_\phi^{\text{origin}}$ takes $f(\tau_t^{\text{bsf}})$ , $v_\phi^{\text{reg}}$ takes $f(\tau_t^{\text{bsf}})$ and $J_t$ , and $v_\phi^{\text{bonus}}$ takes $f(\tau_t^{\text{bsf-wrt-}\epsilon})$ .

Knowl 7 — NeuOpt Benchmark Performance on Traveling Salesman Problem

data/table

NeuOpt was evaluated against exact solvers (Concorde), classical heuristics (LKH-2), learning-to-predict (L2P), learning-to-construct (L2C), and learning-to-search (L2S) solvers across 10,000 instances of TSP-20, TSP-50, and TSP-100 uniformly distributed in $[0,1]^2$ . Optimality gaps are computed relative to Concorde.

Method	$N = 20$			$N = 50$			$N = 100$
	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time
Concorde	3.827	-	2m	5.696	-	9m	7.765	-	43m
LKH-2	3.827	0.00%	6m	5.696	0.00%	1.3h	7.765	0.00%	5.7h
DIFUSCO ( $T=50, S=16$ )	-	-	-	5.696	0.01%	5.8h	7.766	0.02%	21.7h
POMO ( $A=8, T=200$ )	3.827	0.00%	13m	5.696	0.00%	1.1h	7.770	0.07%	5.6h
POMO+EAS+SGBS (long)	-	-	-	-	-	-	7.767	0.03%	1.1d
DACT (2-opt, $A=4, T=10k$ )	3.827	0.00%	1.5h	5.696	0.00%	4.1h	7.772	0.10%	13.5h
NeuOpt ( $D2A=1, T=1k$ )	3.827	0.00%	2m	5.697	0.02%	6m	7.790	0.33%	17m
NeuOpt ( $D2A=1, T=5k$ )	3.827	0.00%	12m	5.696	0.00%	32m	7.768	0.05%	1.4h
NeuOpt ( $D2A=1, T=10k$ )	3.827	0.00%	23m	5.696	0.00%	1.1h	7.766	0.02%	2.8h
NeuOpt ( $D2A=5, T=1k$ )	3.827	0.00%	12m	5.696	0.00%	32m	7.767	0.04%	1.4h
NeuOpt ( $D2A=5, T=3k$ )	3.827	0.00%	35m	5.696	0.00%	1.6h	7.765	0.01%	4.2h
NeuOpt ( $D2A=5, T=5k$ )	3.827	0.00%	1h	5.696	0.00%	2.7h	7.765	0.00%	7h

NeuOpt ( $D2A=5, T=5k$ ) achieves a 0.00% optimality gap across all tested TSP sizes, matching exact Concorde performance. It outperforms existing neural 2-opt/3-opt L2S solvers (DACT, Costa et al., Sui et al.) in both solution quality and runtime, and beats advanced L2C methods (POMO+EAS+SGBS) while requiring less compute time.

Knowl 8 — NeuOpt-GIRE Benchmark Performance on Capacitated Vehicle Routing Problem

data/table

NeuOpt equipped with GIRE was evaluated on 10,000 CVRP instances each for $N=20, 50, 100$ against classical heuristics (HGS, LKH-3), L2C, and L2S solvers. Capacities $\Delta$ are 30 ( $N=20$ ), 40 ( $N=50$ ), and 50 ( $N=100$ ), with demands sampled from $\{1, \dots, 9\}$ . Optimality gaps are measured relative to the state-of-the-art heuristic Hybrid Genetic Search (HGS).

Method	$N = 20$			$N = 50$			$N = 100$
	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time
HGS	6.130	-	10.7h	10.366	-	1.2d	15.563	-	2.5d
LKH-3	6.135	0.08%	17.9h	10.375	0.09%	2.8d	15.647	0.54%	5.7d
POMO ( $A=8, T=200$ )	6.136	0.09%	11m	10.397	0.30%	1.4h	15.672	0.70%	7.2h
POMO+EAS ( $A=8, T=200$ )	6.132	0.04%	38m	10.379	0.13%	3.1h	15.610	0.30%	16h
POMO+EAS+SGBS (long)	-	-	-	-	-	-	15.579	0.10%	4.1d
NLNS ( $T=5k$ )	6.175	0.73%	48m	10.506	1.35%	1.4h	15.915	2.26%	2.4h
DACT (2-opt, $A=6, T=10k$ )	6.130	0.01%	4h	10.383	0.16%	16h	15.736	1.11%	1.7d
NeuOpt-GIRE ( $D2A=1, T=1k$ )	6.132	0.03%	4m	10.430	0.61%	12m	15.865	1.94%	28m
NeuOpt-GIRE ( $D2A=1, T=5k$ )	6.130	0.00%	20m	10.382	0.16%	59m	15.698	0.87%	2.3h
NeuOpt-GIRE ( $D2A=1, T=10k$ )	6.130	0.00%	41m	10.375	0.08%	2h	15.656	0.60%	4.6h
NeuOpt-GIRE ( $D2A=5, T=6k$ )	6.130	0.00%	2.1h	10.369	0.03%	5.9h	15.610	0.30%	13.8h
NeuOpt-GIRE ( $D2A=5, T=20k$ )	6.130	0.00%	6.8h	10.367	0.01%	19.7h	15.586	0.15%	1.9d
NeuOpt-GIRE ( $D2A=5, T=40k$ )	6.130	0.00%	13.7h	10.367	0.01%	1.6d	15.579	0.10%	3.8d

NeuOpt-GIRE is the first learning-to-search (L2S) solver to surpass the strong LKH-3 heuristic on CVRP-100 (0.10% vs 0.54% gap), reducing the gap of prior masking-based L2S solvers (such as DACT's 1.11%) by an order of magnitude.

Knowl 9 — Ablation Analysis of Decoder, Moves, and GIRE Components
empirical result
Systematic ablation experiments demonstrate the contribution of individual architecture and training components in NeuOpt and GIRE:
1. RDS Decoder Components (evaluated on TSP-100 and CVRP-20, $T=1k$ ):
  - Removing GRUs degraded TSP-100 tour length from 7.798 to 7.804 (CVRP-20 from 6.163 to 6.165).
  - Removing the move stream $\mu$ degraded TSP-100 to 7.806 (CVRP-20 to 6.165).
  - Removing the edge stream $\lambda$ degraded TSP-100 to 7.799 (CVRP-20 to 6.164). The full RDS decoder achieved the best score (7.798 on TSP-100, 6.163 on CVRP-20).
2. Basis Moves ( $S$ -move and $E$ -move):
  - Replacing the learnable $S$ -move with random selection of anchor node $x_a$ produced severe performance degradation during training (converging to objective values above 8.00 vs. $\approx 7.75$ on TSP-100).
  - Disabling the $E$ -move (forcing a fixed $K$ -opt) degraded performance as $K$ increased (e.g., gap worsened from $K=4$ to $K=6$ ). In contrast, with flexible $E$ -moves, NeuOpt performance monotonically improved with larger $K$ ( $K=2$ : 0.30% gap; $K=4$ : 0.05% gap; $K=6$ : 0.00% gap on TSP-100).
3. GIRE Design Modules on CVRP-20:
  - Evaluating 8 combinations of Violation Indicators (VI), Exploration Statistics (ES), and Reward Shaping (RS) showed that VI consistently improves performance across settings. ES provides improvements specifically when combined with RS. The full GIRE combination (VI + ES + RS) achieved the lowest objective value with the lowest training variance.
Knowl 10 — Limitations of NeuOpt and GIRE
limitation
The authors identify four main limitations of NeuOpt and GIRE:
1. Scalability on Large-Scale TSP: While exhibiting superior scaling compared to prior L2S solvers, NeuOpt's inference efficiency lags behind specialized learning-to-predict (L2P) heatmap/diffusion solvers (e.g., Att-GCN+MCTS, DIMES) on very large TSP graphs ( $N \gg 1000$ ).
2. Implementation Overhead: The policy currently relies on standard PyTorch routines without custom-engineered CUDA kernels, leading to slower per-step execution compared to highly optimized C++/CUDA implementations.
3. Post-Hoc Optimization: NeuOpt does not integrate instance-specific active search techniques (such as Efficient Active Search, EAS) or beam-search boosters at inference time, which have proven effective for L2C solvers.
4. Constraint Diversity: GIRE was empirically evaluated primarily on vehicle capacity constraints in CVRP, and extending it to complex time windows, precedence, or non-linear constraints requires further empirical validation.

Coverage note — None was omitted; all primary contributions, mathematical formulations, algorithms, ablation findings, and experimental tables from the main text and appendices are represented.

References

1.Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM press, 2014.
2.Cong Zhang, Yaoxin Wu, Yining Ma, Wen Song, Zhang Le, Zhiguang Cao, and Jie Zhang. A review on learning to solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufacturing, 5(1):e12072, 2023.
3.Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
4.Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21188–21198, 2020.
5.André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
6.Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI Conference on Artificial Intelligence, 2021.
7.Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, volume 35, pages 25531– 25546, 2022.
8.André Hottung and Kevin Tierney. Neural large neighborhood search for routing problems. Artificial Intelligence, page 103786, 2022.
9.Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages 11096–11107, 2021.
10.Qingfu Zhang Xi Lin, Zhiyuan Yang. Pareto set learning for neural multi-objective combinatorial optimization. In International Conference on Learning Representations, 2022.
11.Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, pages 31226–31238, 2022.
12.Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In International Joint Conference on Artificial Intelligence, pages 4776–4784, 2022.
13.Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages 1936–1949, 2022.
14.Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arxiv preprint arxiv:1906.01227, ArXiV, 2019.
15.Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. arxiv preprint arxiv:2302.08224, ArXiV, 2023.
16.Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 465–480, 2020.
17.Jingyan Sui, Shizhe Ding, Ruizhi Liu, Liming Xu, and Dongbo Bu. Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, volume 157, pages 1301–1316, 2021.
18.Zbigniew Michalewicz et al. Do not kill unfeasible individuals. In Proceedings of the Fourth Intelligent Information Systems Workshop, pages 110–123, 1995.
19.Fred Glover and Jin-Kao Hao. The case for strategic oscillation. Annals of Operations Research, 183: 163–173, 2011.
20.Keld Helsgaun. LKH-3 (3.0.7), 2017. URL http://webhotel4.ruc.dk/~keld/research/LKH-3/.
21.Thibaut Vidal. Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
22.Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pages 2692–2700, 2015.
23.Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Machine Learning (Workshop), 2017.
24.Mohammadreza Nazari, Afshin Oroojlooy, Martin Takác, and Lawrence V Snyder. Reinforcement learning ˇ for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pages 9861–9871, 2018.
25.Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pages 6351–6361, 2017.
26.Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In International Conference on Machine Learning and Applications (ICMLA), pages 19–24, 2020.
27.Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 17(7):4861–4871, 2020.
28.Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In AAAI Conference on Artificial Intelligence, pages 12042–12049, 2021.
29.Yunqiu Xu, Meng Fang, Ling Chen, Gangyan Xu, Yali Du, and Chengqi Zhang. Reinforcement learning with multiple relational attention for solving vehicle routing problems. IEEE Transactions on Cybernetics, 52(10):11107 – 11120, 2022.
30.Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 23(3):2306–2315, 2022.
31.Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 52(12):13572–13585, 2022.
32.Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In AAAI Conference on Artificial Intelligence, 2023.
33.Minsu Kim, Jinkyoo Park, and Joungho kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pages 10418–10430, 2021.
34.Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages 8760–8772, 2022.
35.Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281–6292, 2019.
36.Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
37.Minjun Kim, Junyoung Park, and Jinkyoo Park. Learning to CROSS exchange to solve min-max vehicle routing problems. In International Conference on Learning Representations, 2023.
38.Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, pages 2033–2062, 2020.
39.Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33(9):5057–5069, 2021.
40.Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learning Representations, volume 35, 2022.
41.Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256–2265, 2015.
42.Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 190–213, 2022.
43.André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
44.Jiuxia Zhao, Minjia Mao, Xi Zhao, and Jianhua Zou. A hybrid of deep reinforcement learning and local search for the vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems, 22(11): 7208–7218, 2021.
45.Renchi Zhang, Runsheng Yu, and Wei Xia. Constraint-aware policy optimization to solve the vehicle routing problem with time windows. Information Technology and Control, 51(1):126–138, 2022.
46.Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. Online 3d bin packing with constrained deep reinforcement learning. In AAAI Conference on Artificial Intelligence, pages 741–749, 2021.
47.Ashish K Jayant and Shalabh Bhatnagar. Model-based safe deep reinforcement learning via a constrained proximal policy optimization algorithm. Advances in Neural Information Processing Systems, 35:24432– 24445, 2022.
48.Linrui Zhang, Li Shen, Long Yang, Shixiang Chen, Xueqian Wang, Bo Yuan, and Dacheng Tao. Penalized proximal policy optimization for safe reinforcement learning. In International Joint Conference on Artificial Intelligence, pages 3744–3750, 2022.
49.Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498–516, 1973.
50.Keld Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European journal of operational research, 126(1):106–130, 2000.
51.Keld Helsgaun. LKH-2 (2.0.9), 2018. URL http://webhotel4.ruc.dk/~keld/research/LKH/.
52.Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder–decoder for statistical machine translation. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724–1734, 2014.
53.David Ha, Andrew M. Dai, and Quoc V. Le. Hypernetworks. In International Conference on Learning Representations, 2017.
54.David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. Concorde TSP Solver, 2020. URL http://www.math.uwaterloo.ca/tsp/concorde/.
55.Gerhard Reinelt. TSPLIB-A traveling salesman problem library. ORSA journal on computing, 3(4): 376–384, 1991.
56.Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845–858, 2017.
57.Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
58.Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to solve large-scale tsp instances. In International Conference on Artificial Intelligence and Statistics, pages 1219–1231, 2023.
59.Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian. H-TSP: Hierarchically solving the large-scale travelling salesman problem. In AAAI Conference on Artificial Intelligence, 2023.
60.Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198–26211, 2021.
61.Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, volume 35, pages 14501–14515, 2022.
62.Sebastian Jaszczur, Aakanksha Chowdhery, Afroz Mohiuddin, LUKASZ KAISER, Wojciech Gajewski, Henryk Michalewski, and Jonni Kanerva. Sparse is enough in scaling transformers. In Advances in Neural Information Processing Systems, volume 34, pages 9895–9907, 2021.
63.Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning, 2023.

Citation

MLA

Ma, Y., et al. “Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt”. Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 49555–78, https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf.

APA

Ma, Y., Cao, Z., & Chee, Y. M. (2023). Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt. Advances in Neural Information Processing Systems, 36, 49555–49578. https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf

Chicago

Ma, Y., Z. Cao, and Y. M. Chee. 2023. “Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt”. Advances in Neural Information Processing Systems 36: 49555–78. https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf.

Harvard

Ma, Y., Cao, Z. and Chee, Y.M. (2023) “Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 49555–49578. Available at: https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf.

Vancouver

1. Ma Y, Cao Z, Chee YM (2023) Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 49555–49578

BibTeX

@inproceedings{ma2023learning,
  title = {Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt},
  author = {Ma, Yining and Cao, Zhiguang and Chee, Yeow Meng},
  year = {2023},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {36},
  pages = {49555-49578},
  url = {https://proceedings.neurips.cc/paper_files/paper/2023/file/9bae70d354793a95fa18751888cea07d-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Action Factorization for Flexible Neural k-Opt

Knowl 2 — Recurrent Dual-Stream Decoder Architecture

Knowl 3 — Guided Infeasible Region Exploration Framework

Knowl 4 — GIRE Reward Shaping and Entropy Regulation

Knowl 5 — Dynamic Data Augmentation (D2A) Inference Algorithm

Knowl 6 — PPO Training with Multi-Critic Architecture for GIRE