Attention, Learn to Solve Routing Problems!

Wouter KoolHerke van HoofMax Welling

article2018ICLR1,740 citations

Proposes an attention-based reinforcement learning architecture with a greedy rollout baseline that solves multiple NP-hard routing problems, including the Traveling Salesman and Vehicle Routing Problems, with near-optimal performance.

Listen

Vehicle routing and related combinatorial optimization problems are critical in modern logistics, supply chain management, and transportation systems, where finding efficient paths directly reduces operational costs and fuel consumption. Solving these problems is computationally difficult, and organizations traditionally rely on hand-crafted rules or specialized solvers that are expensive to engineer and struggle to adapt to new operational constraints. Machine learning has shown promise in learning these problem-solving rules automatically from data, but previous models have suffered from slow training, high computational overhead, and limited performance on larger problem instances.

The article demonstrates an attention-based neural network framework trained via reinforcement learning that automatically learns high-quality heuristics for multiple routing problems without requiring manual algorithm redesign.

To evaluate this framework, the authors conducted extensive computational experiments across several core routing variants: the Traveling Salesman Problem, the Capacitated and Split Delivery Vehicle Routing Problems, the Orienteering Problem, and both deterministic and stochastic versions of the Prize Collecting Traveling Salesman Problem. The system evaluated problem instances ranging from 20 to 100 locations using synthetic datasets standard in operations research. The model processes location features through an attention-based encoder-decoder architecture that remains invariant to input ordering, and it was trained using an efficient reinforcement learning algorithm paired with a deterministic baseline that periodically rolls out the best-performing model found so far.

The evaluation produced several key findings. First, the proposed framework significantly outperformed prior learned methods on the Traveling Salesman Problem, reducing the gap to optimal solutions from around 1.5% down to approximately 0.3% on 20-node instances, while coming within 2.3% of optimal on 100-node instances when sampling multiple candidate solutions. Second, using an identical set of training settings across all problem types, the model delivered competitive results on diverse routing problems, outperforming established construction rules and approaching the quality of highly specialized commercial solvers. Third, the trained system operated at high speed, evaluating 10,000 problem instances in seconds using greedy decision-making and generating 1,280 sampled candidate solutions in under one second per batch on modern hardware. Fourth, the architecture handled real-time uncertainty naturally in stochastic routing tasks, outperforming complex replanning baselines on small instances while requiring a fraction of the computational time.

These findings demonstrate that organizations can reduce the high development costs and engineering timelines required to build custom routing heuristics by leveraging automated, data-driven learning. Because the model executes quickly during operations, it provides significant performance and cost advantages in fast-paced logistics environments requiring real-time dispatching and decision updates under operational uncertainty. The model performs well without problem-specific manual tuning, challenging the traditional assumption that each routing variation requires a bespoke, hand-crafted algorithm.

Organizations evaluating this approach should consider deploying it for real-time routing applications where speed and automated adaptation outweigh the need for mathematically guaranteed optimality. Decision-makers facing larger network sizes should conduct pilot tests or pair the learned neural heuristic with simple local search post-processing to refine route orderings further. Future initiatives should focus on scaling the framework to larger industrial graphs through graph sparsification and incorporating backtracking mechanisms to handle complex operational constraints that cannot be resolved sequentially.

Confidence in these findings is high across the tested benchmarks of up to 100 nodes, where the model demonstrated robust convergence and stability across multiple random initializations. Readers should note that performance gradually degrades when the model is tested on graph sizes significantly different from those seen during training, and the current formulation relies on sequential decision steps with masking, which may require structural adjustments when applied to complex operational constraints.

CIFAR ORTEC University of Amsterdam combinatorial optimization deterministic optimization problems attention mechanism combinatorial optimization vehicle routing

arXiv: 1803.08475 wouterkool/attention-learn-to-route

Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). This work pioneered using policy-gradient reinforcement learning with Pointer Networks to solve combinatorial routing problems like the Travelling Salesman Problem, establishing the foundational framework that the target paper builds upon and improves.
Paper: Pointer networks, Oriol Vinyals et al. (2015). It introduced Pointer Networks, the core sequence-to-sequence attention architecture for selecting variable-length input elements that the target paper explicitly seeks to replace and outperform with an attention model.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). This paper established the paradigm of using graph neural network representations paired with reinforcement learning to learn greedy combinatorial optimization heuristics over graphs.
Paper: Order Matters: Sequence to sequence for sets, Oriol Vinyals et al. (2016). It analyzes the critical role of order and permutation invariance in sequence models processing sets, providing key conceptual foundations for modeling unordered collections of routing nodes.

Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). Provides a comprehensive survey and methodological taxonomy of machine learning techniques for combinatorial optimization, contextualizing end-to-end learned routing heuristics within the broader literature.

Cover for Attention, Learn to Solve Routing Problems!

Abstract

The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.

Topics

combinatorial optimization deterministic optimization problems routing problems value functions vehicle routing vehicle routing problems combinatorial problems routing scheme regularization parameters

Keywords

attention mechanism combinatorial optimization vehicle routing reinforcement learning Prize Collecting TSP Pointer Network Operations Research

1 Introduction
2 Related work
3 Attention model
3.1 Encoder
3.2 Decoder
4 REINFORCE with greedy rollout baseline
5 Experiments
5.1 Problems
5.2 Attention Model vs. Pointer Network and different baselines
6 Discussion
References
A Attention model details
B Travelling Salesman Problem
B.1 Critic architecture
B.2 Instance generation
B.3 Details of baselines
B.4 Comparison to concurrent work
B.5 Extended results
C Vehicle Routing Problem
C.1 Instance generation
C.2 Attention Model for the VRP
C.3 Details of baselines
C.4 Example solutions
D Orienteering Problem
D.1 Instance generation
D.2 Attention Model for the OP
D.3 Details of baselines
D.4 Extended results
E Prize Collecting TSP
E.1 Instance generation
E.2 Attention Model for the PCTSP
E.3 Details of baselines
F Stochastic PCTSP (SPCTSP)
F.1 Attention Model for the SPCTSP
F.2 Rollout baseline in the stochastic setting
F.3 Details of baselines

Knowls

Knowl 1 — REINFORCE with Greedy Rollout Baseline for Combinatorial Optimization
algorithm
The REINFORCE algorithm with a greedy rollout baseline trains an autoregressive policy $\pi \sim p_\theta(\cdot|s)$ parameterized by $\theta$ to minimize an expected combinatorial routing cost $\mathcal{L}(\theta|s) = \mathbb{E}_{p_\theta(\pi|s)}[L(\pi)]$ , where $s$ is a problem instance and $L(\pi)$ denotes the cost of solution $\pi$ .

The policy gradient estimator uses a baseline $b(s) = L(\pi^{BL})$ defined by the deterministic greedy rollout of a frozen copy of the model parameters $\theta^{BL}$ :

$\nabla_\theta \mathcal{L}(\theta|s) = \mathbb{E}_{p_\theta(\pi|s)} \left[ \left( L(\pi) - L(\pi^{BL}) \right) \nabla_\theta \log p_\theta(\pi|s) \right]$

If the sampled solution $\pi$ achieves a lower cost than the deterministic greedy rollout $\pi^{BL}$ , the advantage term $L(\pi) - L(\pi^{BL})$ is negative (for cost minimization), reinforcing the sampled decisions.

The baseline parameters $\theta^{BL}$ remain fixed throughout each training epoch of $T$ steps. At the end of every epoch, greedy rollouts of the current training policy $p_\theta$ and the baseline policy $p_{\theta^{BL}}$ are compared on a separate held-out validation set of 10,000 instances. The baseline parameters are updated to $\theta^{BL} \leftarrow \theta$ if and only if the current model achieves a statistically significant improvement over the baseline according to a one-sided paired $t$ -test at significance level $\alpha = 0.05$ . Whenever the baseline is updated, a fresh set of 10,000 evaluation instances is sampled to prevent overfitting.
Input: Number of epochs $E$ , steps per epoch $T$ , batch size $B$ , significance level $\alpha$
Initialize policy parameters $\theta$ , baseline parameters $\theta^{BL} \leftarrow \theta$
for $\text{epoch} = 1, \dots, E$ do
    for $\text{step} = 1, \dots, T$ do
         $s_i \leftarrow \text{RandomInstance}()$ for all $i \in \{1, \dots, B\}$
         $\pi_i \leftarrow \text{SampleRollout}(s_i, p_\theta)$ for all $i \in \{1, \dots, B\}$
         $\pi_i^{BL} \leftarrow \text{GreedyRollout}(s_i, p_{\theta^{BL}})$ for all $i \in \{1, \dots, B\}$
         $\nabla \mathcal{L} \leftarrow \sum_{i=1}^B (L(\pi_i) - L(\pi_i^{BL})) \nabla_\theta \log p_\theta(\pi_i)$
         $\theta \leftarrow \text{Adam}(\theta, \nabla \mathcal{L})$
    end for
    if $\text{OneSidedPairedTTest}(p_\theta, p_{\theta^{BL}}) < \alpha$ then
         $\theta^{BL} \leftarrow \theta$
    end if
end for
During the first epoch ( $E=1$ ), an exponential moving average baseline ( $b(s) \leftarrow \beta b(s) + (1-\beta) L(\pi)$ with decay $\beta = 0.8$ ) can be used as a warmup prior to greedy rollout evaluations. Hyperparameters used: $E = 100$ , $T = 2500$ , $B = 512$ (or $B = 256$ for $n=100$ routing instances), optimizer Adam with fixed learning rate $\eta = 10^{-4}$ (or $\eta = 10^{-3}$ with exponential decay factor $0.96$ per epoch).
Knowl 2 — Attention Model Architecture for Routing Problems
model/method
The Attention Model (AM) is an encoder-decoder architecture designed to parameterize an autoregressive policy $p_\theta(\pi|s) = \prod_{t=1}^n p_\theta(\pi_t|s, \pi_{1:t-1})$ for routing problems on a graph of $n$ nodes.

Encoder: Each node $i \in \{1, \dots, n\}$ with input feature vector $x_i \in \mathbb{R}^{d_x}$ is initially mapped to a $d_h$ -dimensional embedding ( $d_h = 128$ ) via a linear projection:

$h_i^{(0)} = W^x x_i + b^x$

The embeddings are updated across $N = 3$ sequential layers without positional encodings (guaranteeing permutation invariance). Each layer $\ell \in \{1, \dots, N\}$ consists of a Multi-Head Attention (MHA) sublayer and a node-wise Feed-Forward (FF) sublayer with skip-connections and Batch Normalization (BN):

$\hat{h}_i = \text{BN}^\ell \left( h_i^{(\ell-1)} + \text{MHA}^\ell \left( h_1^{(\ell-1)}, \dots, h_n^{(\ell-1)} \right) \right)$

$h_i^{(\ell)} = \text{BN}^\ell \left( \hat{h}_i + \text{FF}^\ell(\hat{h}_i) \right)$

The MHA sublayer uses $M = 8$ heads with key/query/value dimension $d_k = d_v = d_h / M = 16$ . The FF sublayer consists of a single hidden layer with dimension $d_{\text{ff}} = 512$ and ReLU activation: $\text{FF}(\hat{h}_i) = W^{\text{ff}, 1} \text{ReLU}(W^{\text{ff}, 0} \hat{h}_i + b^{\text{ff}, 0}) + b^{\text{ff}, 1}$ . The aggregated graph embedding is computed as the node mean $\bar{h}^{(N)} = \frac{1}{n} \sum_{i=1}^n h_i^{(N)}$ .

Decoder: At decoding timestep $t \in \{1, \dots, n\}$ , a context node embedding $h_{(c)}^{(N)}$ is constructed from $\bar{h}^{(N)}$ and dynamic state features (such as previous and first visited node embeddings). The context node computes an $M$ -head attention query $q_{(c)} = W^Q h_{(c)}^{(N)}$ over keys $k_i = W^K h_i^{(N)}$ and values $v_i = W^V h_i^{(N)}$ from the encoder output to produce an updated context embedding $h_{(c)}^{(N+1)}$ (a single glimpse, computed without BN or FF for speed).

A final single-head attention layer ( $M = 1, d_k = d_h$ ) computes output logits $u_{(c)j}$ for all nodes $j$ , with logits clipped within $[-C, C]$ ( $C = 10$ ) using $\tanh$ before applying an infeasibility mask:

$u_{(c)j} = \begin{cases} C \cdot \tanh\left( \frac{q_{(c)}^T k_j}{\sqrt{d_k}} \right) & \text{if node } j \text{ is feasible at step } t \\ -\infty & \text{otherwise} \end{cases}$

The conditional probability of choosing next node $\pi_t = i$ is computed via softmax:

$p_\theta(\pi_t = i | s, \pi_{1:t-1}) = \frac{e^{u_{(c)i}}}{\sum_j e^{u_{(c)j}}}$
Knowl 3 — Problem-Specific Decoder Context and Dynamic Feasibility Masking
model/method
The Attention Model adapts to different routing problems by tailoring the decoder context embedding $h_{(c)}^{(N)}$ and the dynamic feasibility mask $u_{(c)j} = -\infty$ at step $t$ .

Travelling Salesman Problem (TSP):
- Context embedding ( $[\cdot, \cdot, \cdot]$ denotes horizontal concatenation):
$h_{(c)}^{(N)} = \begin{cases} [\bar{h}^{(N)}, h_{\pi_{t-1}}^{(N)}, h_{\pi_1}^{(N)}] & t > 1 \\ [\bar{h}^{(N)}, v^l, v^f] & t = 1 \end{cases}$

where $v^l, v^f \in \mathbb{R}^{d_h}$ are learned placeholder vectors.
- Masking: Visited nodes are masked: $u_{(c)j} = -\infty$ if $j \in \{\pi_1, \dots, \pi_{t-1}\}$ .
Capacitated Vehicle Routing Problem (CVRP):
- Depot is node $0$ . Node demands are normalized $\hat{\delta}_i = \delta_i / D$ . State tracks remaining vehicle capacity $\hat{D}_t$ , where $\hat{D}_1 = 1$ , $\hat{D}_{t+1} = \max(\hat{D}_t - \hat{\delta}_{\pi_t, t}, 0)$ if $\pi_t \neq 0$ , and $\hat{D}_{t+1} = 1$ if $\pi_t = 0$ .
- Context embedding:
$h_{(c)}^{(N)} = \begin{cases} [\bar{h}^{(N)}, h_{\pi_{t-1}}^{(N)}, \hat{D}_t] & t > 1 \\ [\bar{h}^{(N)}, h_0^{(N)}, \hat{D}_t] & t = 1 \end{cases}$
- Masking: Depot $j=0$ is masked if $t=1$ or $\pi_{t-1}=0$ (prevent consecutive depot visits). Customers $j \neq 0$ are masked if already visited (remaining demand $\hat{\delta}_{j,t} = 0$ ) or if $\hat{\delta}_{j,t} > \hat{D}_t$ .
Orienteering Problem (OP):
- State tracks remaining tour length budget $T_t$ , where $T_1 = T$ and $T_{t+1} = T_t - d_{\pi_{t-1}, \pi_t}$ (with $\pi_0 = 0$ ).
- Context embedding:
$h_{(c)}^{(N)} = \begin{cases} [\bar{h}^{(N)}, h_{\pi_{t-1}}^{(N)}, T_t] & t > 1 \\ [\bar{h}^{(N)}, h_0^{(N)}, T_t] & t = 1 \end{cases}$
- Masking: Depot is never masked. Customer $j \neq 0$ is masked if already visited or if returning to depot exceeds remaining length ( $d_{\pi_{t-1}, j} + d_{j, 0} > T_t$ ).
Prize Collecting TSP (PCTSP):
- State tracks remaining prize to collect $P_t$ , where $P_1 = 1$ and $P_{t+1} = \max(0, P_t - \hat{\rho}_{\pi_t})$ .
- Context embedding:
$h_{(c)}^{(N)} = \begin{cases} [\bar{h}^{(N)}, h_{\pi_{t-1}}^{(N)}, P_t] & t > 1 \\ [\bar{h}^{(N)}, h_0^{(N)}, P_t] & t = 1 \end{cases}$
- Masking: Customer $j \neq 0$ is masked if already visited. Depot $j = 0$ is masked if $P_t > 0$ and $t \le n$ .

Knowl 4 — Empirical Benchmark Results across TSP, CVRP, SDVRP, OP, and PCTSP

data/table

The Attention Model (AM) evaluated with greedy decoding (selecting the maximum probability node at each step) and sampling (selecting the best solution among 1280 samples) was tested on 10,000 random instances of size $n \in \{20, 50, 100\}$ for TSP, CVRP, SDVRP, Orienteering Problem (OP, distance prize distribution), Prize Collecting TSP (PCTSP), and Stochastic PCTSP (SPCTSP). Gaps are reported relative to the best available method for each problem.

	$n = 20$			$n = 50$			$n = 100$
Method	Obj.	Gap	Time	Obj.	Gap	Time	Obj.	Gap	Time
TSP
Concorde	3.84	0.00%	(1m)	5.70	0.00%	(2m)	7.76	0.00%	(3m)
LKH3	3.84	0.00%	(18s)	5.70	0.00%	(5m)	7.76	0.00%	(21m)
Farthest Insertion	3.93	2.36%	(1s)	6.01	5.53%	(2s)	8.35	7.59%	(7s)
Bello et al. (greedy)	3.89	1.42%	-	5.95	4.46%	-	8.30	6.90%	-
AM (greedy)	3.85	0.34%	(0s)	5.80	1.76%	(2s)	8.12	4.53%	(6s)
Bello et al. (sampling)	-	-	-	5.75	0.95%	-	8.00	3.03%	-
AM (sampling 1280)	3.84	0.08%	(5m)	5.73	0.52%	(24m)	7.94	2.26%	(1h)
CVRP
LKH3	6.14	0.58%	(2h)	10.38	0.00%	(7h)	15.65	0.00%	(13h)
RL (Nazari et al., greedy)	6.59	8.03%	-	11.39	9.78%	-	17.23	10.12%	-
AM (greedy)	6.40	4.97%	(1s)	10.98	5.86%	(3s)	16.80	7.34%	(8s)
RL (Nazari et al., beam 10)	6.40	4.92%	-	11.15	7.46%	16.96	8.39%	-
AM (sampling 1280)	6.25	2.49%	(6m)	10.62	2.40%	(28m)	16.23	3.72%	(2h)
SDVRP
RL (Nazari et al., greedy)	6.51	4.19%	-	11.32	6.88%	-	17.12	5.23%	-
AM (greedy)	6.39	2.34%	(1s)	10.92	3.08%	(4s)	16.83	3.42%	(11s)
AM (sampling 1280)	6.25	0.00%	(9m)	10.59	0.00%	(42m)	16.27	0.00%	(3h)
OP (distance)
Compass (GA)	5.37	0.36%	(2m)	16.17	0.00%	(5m)	33.19	0.00%	(15m)
Tsili (greedy)	4.08	24.25%	(4s)	12.46	22.94%	(4s)	25.69	22.59%	(5s)
AM (greedy)	5.19	3.64%	(0s)	15.64	3.23%	(1s)	31.62	4.75%	(5s)
Tsili (sampling 1280)	5.30	1.62%	(28s)	15.50	4.14%	(2m)	30.52	8.05%	(6m)
AM (sampling 1280)	5.30	1.56%	(4m)	16.07	0.60%	(16m)	32.68	1.55%	(53m)
PCTSP
ILS (C++)	3.16	0.77%	(16m)	4.50	0.36%	(2h)	5.98	0.00%	(12h)
OR Tools (60s)	3.13	0.01%	(5h)	4.48	0.00%	(5h)	6.07	1.56%	(5h)
AM (greedy)	3.18	1.62%	(0s)	4.60	2.66%	(2s)	6.25	4.46%	(5s)
AM (sampling 1280)	3.15	0.45%	(5m)	4.52	0.74%	(19m)	6.08	1.67%	(1h)
SPCTSP
REOPT (half)	3.31	1.38%	(25m)	4.64	0.00%	(3h)	6.16	0.00%	(16h)
AM (greedy)	3.26	0.00%	(0s)	4.65	0.33%	(2s)	6.32	2.69%	(5s)

The Attention Model trained with the greedy rollout baseline consistently outperforms previous learned heuristics (e.g., Bello et al. and Nazari et al.) in both greedy and sampled decoding modes across all problem sizes. For TSP, AM greedy decoding runs in seconds and achieves gaps of 0.34%, 1.76%, and 4.53% for $n=20, 50, 100$ . For OP and PCTSP, AM sampling approaches within 1.5–2.3% of specialized solvers like Compass and ILS at substantially lower computational time.

Knowl 5 — Split Delivery VRP Adaptation with Dynamic Demand Embeddings
model/method
In the Split Delivery Vehicle Routing Problem (SDVRP), customer demands can exceed single-vehicle drops, and customers may be visited multiple times until their full demand is satisfied. The remaining customer demand $\hat{\delta}_{i,t}$ evolves dynamically after each visit $\pi_t = i$ :

$\hat{\delta}_{i,t+1} = \begin{cases} \max(0, \hat{\delta}_{i,t} - \hat{D}_t) & \pi_t = i \\ \hat{\delta}_{i,t} & \pi_t \neq i \end{cases}$

Because remaining demand $\hat{\delta}_{i,t} \in [0, \hat{\delta}_i]$ varies continuously per node over time, it cannot be represented in a single aggregated context node embedding. Instead, the Attention Model dynamically augments the key and value projections in both the decoder attention layer and the final output layer using parameter matrices $W_d^K, W_d^V \in \mathbb{R}^{d_k \times 1}$ :

$k_i = W^K h_i^{(N)} + W_d^K \hat{\delta}_{i,t}$

$v_i = W^V h_i^{(N)} + W_d^V \hat{\delta}_{i,t}$

where $\hat{\delta}_{0,t} = 0$ for the depot node $i = 0$ . The static terms $W^K h_i^{(N)}$ and $W^V h_i^{(N)}$ are computed once during encoding, requiring only the dynamic scalar product with $\hat{\delta}_{i,t}$ to be evaluated at each decoding step $t$ .

In SDVRP masking, customer nodes $j \neq 0$ are masked ( $u_{(c)j} = -\infty$ ) only when their remaining demand is completely fulfilled ( $\hat{\delta}_{j,t} = 0$ ), allowing visits even when $\hat{\delta}_{j,t} > \hat{D}_t$ since deliveries can be partial.
Knowl 6 — Stochastic Prize Collecting TSP Policy and CRN Baseline Training
model/method
In the Stochastic Prize Collecting TSP (SPCTSP), expected node prizes $\hat{\rho}_i = \mathbb{E}[\hat{\rho}_i^*]$ are known upfront, but the true prize collected $\hat{\rho}_i^* \sim \text{Uniform}(0, 2\hat{\rho}_i)$ is revealed only upon visiting node $i$ . The policy constructs a tour sequentially, updating the remaining prize requirement $P_t$ online:

$P_{t+1} = \max(0, P_t - \hat{\rho}_{\pi_t}^*)$

To train the policy using the greedy rollout baseline under stochasticity, Common Random Numbers (CRN) are utilized for variance reduction: the realization of real prizes $\hat{\rho}_i^*$ is sampled at the beginning of each instance and shared identically between the policy's sampled exploration rollout and the baseline's greedy rollout. Consequently, performance differences $L(\pi) - L(\pi^{BL})$ reflect policy decision quality rather than prize sample variation.

Because exact offline planning cannot guarantee constraint satisfaction under uncertain prizes, online adaptivity is required. The learned Attention Model constructs tours node-by-node without replanning, outperforming re-optimization heuristics (e.g., iteratively replanning via C++ ILS after every step or after visiting half the planned tour) on small instances ( $n=20$ ) and matching them on $n=50, 100$ in orders of magnitude less time (e.g., 5 seconds vs. 16 hours for $n=100$ on 10,000 instances).
Knowl 7 — Empirical Ablation: Attention Model vs. Pointer Network and Baseline Types
empirical result
Ablation experiments on TSP with $n = 20$ evaluate the separate contributions of the Attention Model (AM) architecture versus the recurrent Pointer Network (PN), as well as three reinforcement learning baselines: an exponential moving average baseline ( $b(s)$ with decay $\beta = 0.8$ ), a learned parametric Critic network (using 3 attention layers followed by a 2-layer MLP), and the deterministic Greedy Rollout baseline.

Key findings on 10,000 held-out validation instances:
1. Architecture Effect: The Attention Model outperforms the Pointer Network across all baseline configurations (e.g., AM with rollout achieves 0.29–0.34% optimality gap vs. 1.63–2.46% for PN with rollout; AM with critic achieves 0.88–0.97% gap vs. 2.01–3.00% for PN with critic).
2. Baseline Effect: The greedy rollout baseline yields lower optimality gaps and faster convergence than both the critic and exponential baselines for both AM and PN.
3. Computational Efficiency: The exponential baseline runs ~20% faster per epoch than the rollout baseline, while the critic baseline runs ~13% slower per epoch than the rollout baseline. The rollout baseline adds ~25% computation relative to training without a baseline, accounting for ~20% of total training time, and can be parallelized on a secondary GPU without wall-clock overhead.
4. Encoder Depth: Evaluating encoder layers $N \in \{0, 1, 2, 3, 5, 8\}$ reveals that $N = 3$ and $N = 5$ achieve the best performance ( $N=0$ has a 10.5% gap; $N=1$ has a 0.97% gap; $N=3$ has a 0.34% gap; $N=5$ has a 0.25% gap), with $N = 3$ offering the optimal balance between solution quality and training runtime.
Knowl 8 — Synthetic Instance Generation Protocols for Routing Benchmarks
experimental setup
Synthetic benchmark instances for routing problems are generated on the 2D unit square $[0, 1]^2$ for instance sizes $n \in \{20, 50, 100\}$ :
- TSP: $n$ node coordinates $x_i \sim \text{Uniform}([0, 1]^2)$ .
- CVRP & SDVRP: Depot coordinate $x_0 \sim \text{Uniform}([0, 1]^2)$ and $n$ node coordinates $x_i \sim \text{Uniform}([0, 1]^2)$ . Discrete demands $\delta_i \sim \text{DiscreteUniform}(\{1, \dots, 9\})$ normalized by vehicle capacities $D_{20} = 30$ , $D_{50} = 40$ , and $D_{100} = 50$ , yielding normalized demands $\hat{\delta}_i = \delta_i / D_n$ .
- Orienteering Problem (OP): Depot $x_0 \sim \text{Uniform}([0, 1]^2)$ $x_{0} \sim Uniform ([0, 1]^{2})$ , nodes $x_i \sim \text{Uniform}([0, 1]^2)$ $x_{i} \sim Uniform ([0, 1]^{2})$ . Maximum tour length budgets fixed to $T_{20} = 2.0$ $T_{20} = 2.0$ , $T_{50} = 3.0$ $T_{50} = 3.0$ , $T_{100} = 4.0$ $T_{100} = 4.0$ (approximately half the expected TSP tour length). Three prize distributions $\hat{\rho}_i \in (0, 1]$ $\overset{ρ}{^}_{i} \in (0, 1]$ :
  1. Constant: $\hat{\rho}_i = 1.0$ .
  2. Uniform: $\rho_i \sim \text{DiscreteUniform}(\{1, \dots, 100\})$ , $\hat{\rho}_i = \rho_i / 100$ .
  3. Distance: $\rho_i = 1 + \lfloor 99 \cdot (d_{0i} / \max_{j} d_{0j}) \rfloor$ , $\hat{\rho}_i = \rho_i / 100$ , where $d_{0i} = \|x_0 - x_i\|_2$ .
- Prize Collecting TSP (PCTSP): Depot $x_0 \sim \text{Uniform}([0, 1]^2)$ , nodes $x_i \sim \text{Uniform}([0, 1]^2)$ . Raw prizes $\rho_i \sim \text{Uniform}(0, 1)$ normalized as $\hat{\rho}_i = \rho_i \cdot (4 / n)$ so that expected prize of half the nodes equals the target minimum total prize of $1.0$ . Penalties $\hat{\beta}_i \sim \text{Uniform}(0, 3 K_n / n)$ where $K_{20} = 2, K_{50} = 3, K_{100} = 4$ , balancing penalty cost with tour length.
- Stochastic PCTSP (SPCTSP): Expected prizes $\hat{\rho}_i$ defined as in PCTSP; real observed prizes $\hat{\rho}_i^* \sim \text{Uniform}(0, 2\hat{\rho}_i)$ revealed only upon visiting node $i$ .
Knowl 9 — Cross-Size Generalization Performance of Learned Routing Policies
empirical result
Attention Model policies trained on a fixed problem size $n_{\text{train}} \in \{20, 50, 100\}$ generalize to different test problem sizes $n \in \{5, 10, 15, 20, 25, 30, 40, 50, 60, 75, 100, 125\}$ .

When evaluated via greedy decoding on TSP:
- The model trained on $n=20$ achieves the best performance for sizes $n \in [5, 25]$ .
- The model trained on $n=50$ achieves the best performance for sizes $n \in [30, 60]$ .
- The model trained on $n=100$ achieves the best performance for sizes $n \ge 75$ .
While solution quality relative to exact Gurobi solutions degrades as $|n - n_{\text{train}}|$ grows, selecting the best model checkpoint for each problem size interval yields a composite learned heuristic that strictly outperforms classical construction heuristics (Nearest Neighbor, Random Insertion, Nearest Insertion, and Farthest Insertion) across the entire range $n \in [5, 125]$ .
Knowl 10 — Multi-Head Graph Attention Sublayer Formulation
equation
The Multi-Head Attention (MHA) sublayer maps a sequence of $n$ node embedding vectors $h_1, \dots, h_n \in \mathbb{R}^{d_h}$ into updated message-passed representations. For head $m \in \{1, \dots, M\}$ (with $M = 8$ and $d_k = d_v = d_h / M = 16$ ), query, key, and value vectors are computed via linear projections:

$q_{im} = W_m^Q h_i, \quad k_{jm} = W_m^K h_j, \quad v_{jm} = W_m^V h_j$

where $W_m^Q, W_m^K \in \mathbb{R}^{d_k \times d_h}$ and $W_m^V \in \mathbb{R}^{d_v \times d_h}$ . Compatibility scores $u_{ijm} \in \mathbb{R}$ and attention weights $a_{ijm} \in [0, 1]$ between node $i$ and neighbor $j$ are given by:

$u_{ijm} = \begin{cases} \frac{q_{im}^T k_{jm}}{\sqrt{d_k}} & \text{if node } i \text{ is adjacent to node } j \\ -\infty & \text{otherwise} \end{cases}$

$a_{ijm} = \frac{e^{u_{ijm}}}{\sum_{j'} e^{u_{ij'm}}}$

The aggregated message for head $m$ received by node $i$ is $h_{im}' = \sum_{j=1}^n a_{ijm} v_{jm}$ . The multi-head output is formed by projecting the concatenated head messages using $W_m^O \in \mathbb{R}^{d_h \times d_v}$ :

$\text{MHA}_i(h_1, \dots, h_n) = \sum_{m=1}^M W_m^O h_{im}'$

Coverage note — Auxiliary baseline details (such as external 2OPT local search post-processing scripts, third-party Python genetic algorithm configurations, and PCA coordinate transformations from concurrent work) were omitted as they are standard external tools rather than contributions of the paper.

References

1.David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006. URL http://www.math.uwaterloo.ca/tsp/concorde/m.
2.Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
3.Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. A medium-scale distributed system for computer science research: Infrastructure for the long term. Computer, (5):54–63, 2016.
4.Egon Balas. The prize collecting traveling salesman problem. Networks, 19(6):621–636, 1989.
5.Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.
6.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 30, pp. 6348–6358, 2017.
7.Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 170–181. Springer, 2018.
8.Alina Ene, Viswanath Nagarajan, and Rishi Saket. Approximation algorithms for stochastic k-TSP. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018.
9.Matteo Fischetti, Juan Jose Salazar Gonzalez, and Paolo Toth. Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, 10(2):133–148, 1998.
10.Michael R Garey and David S Johnson. Computers and intractability: A guide to the theory of np-completeness (series of books in the mathematical sciences), ed. Computers and Intractability, pp. 340, 1979.
11.Paul Glasserman and David D Yao. Some guidelines and guarantees for common random numbers. Management Science, 38(6):884–908, 1992.
12.Bruce L Golden, Larry Levy, and Rakesh Vohra. The orienteering problem. Naval Research Logistics (NRL), 34(3):307–318, 1987.
13.Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2018. URL http://www.gurobi.com.
14.Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
15.Keld Helsgaun. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems: Technical report. 2017.
16.Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. In NIPS Deep Learning and Representation Learning Workshop, 2015. URL http://arxiv.org/abs/1503.02531.
17.John J Hopfield and David W Tank. “Neural” computation of decisions in optimization problems. Biological cybernetics, 52(3):141–152, 1985.
18.Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448–456, 2015.
19.Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. arXiv preprint arXiv:1803.09621, 2018.
20.Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
21.Gorka Kobeaga, María Merino, and Jose A Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42–59, 2018.
22.Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436, 2015.
23.Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
24.MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9860–9870, 2018.
25.Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms for quadratic assignment with graph neural networks. arXiv preprint arXiv:1706.07450, 2017.
26.Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. 2017.
27.Steven J Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel. Self-critical sequence training for image captioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7008–7024, 2017.
28.Daniel J Rosenkrantz, Richard E Stearns, and Philip M Lewis. An analysis of several heuristics for the traveling salesman problem. In Fundamental Problems in Computing, pp. 45–69. Springer, 2009.
29.David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017.
30.Kate A Smith. Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS Journal on Computing, 11(1):15–34, 1999.
31.Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
32.Theodore Tsiligirides. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9):797–809, 1984.
33.Pieter Vansteenwegen, Wouter Souffriau, and Dirk Van Oudheusden. The orienteering problem: A survey. European Journal of Operational Research, 209(1):1–10, 2011.
34.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998–6008, 2017.
35.Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
36.Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692–2700, 2015.
37.Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In International Conference on Learning Representations, 2016.
38.Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229–256, 1992.
39.David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67–82, 1997.

Citation

MLA

Kool, W., et al. “Attention, Learn to Solve Routing Problems!”. arXiv, 2018, http://arxiv.org/abs/1803.08475v3.

APA

Kool, W., Hoof, H. van ., & Welling, M. (2018). Attention, Learn to Solve Routing Problems!. arXiv. http://arxiv.org/abs/1803.08475v3

Chicago

Kool, W., H. van . Hoof, and M. Welling. 2018. “Attention, Learn to Solve Routing Problems!”. arXiv. http://arxiv.org/abs/1803.08475v3.

Harvard

Kool, W., Hoof, H. van . and Welling, M. (2018) “Attention, Learn to Solve Routing Problems!”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1803.08475v3.

Vancouver

1. Kool W, Hoof H van, Welling M (2018) Attention, Learn to Solve Routing Problems!. arXiv

BibTeX

@article{kool2018attention,
  title = {Attention, Learn to Solve Routing Problems!},
  author = {Kool, Wouter and Hoof, Herke van and Welling, Max},
  year = {2018},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1803.08475v3},
  eprint = {1803.08475}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

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

Open PDF

License: Authors

Attention, Learn to Solve Routing Problems!

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — REINFORCE with Greedy Rollout Baseline for Combinatorial Optimization

Knowl 2 — Attention Model Architecture for Routing Problems

Knowl 3 — Problem-Specific Decoder Context and Dynamic Feasibility Masking

Knowl 4 — Empirical Benchmark Results across TSP, CVRP, SDVRP, OP, and PCTSP

Knowl 5 — Split Delivery VRP Adaptation with Dynamic Demand Embeddings

Knowl 6 — Stochastic Prize Collecting TSP Policy and CRN Baseline Training

Knowl 7 — Empirical Ablation: Attention Model vs. Pointer Network and Baseline Types

Knowl 8 — Synthetic Instance Generation Protocols for Routing Benchmarks

Knowl 9 — Cross-Size Generalization Performance of Learned Routing Policies

Knowl 10 — Multi-Head Graph Attention Sublayer Formulation

References

Citation

BibTeX

Source Code

Access the Paper