PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Improvement Heuristics for Solving Routing Problems

Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Andrew Lim

arXiv:1912.05784v2cs.AIcs.LG

TL;DR

Existing deep-learning routing methods largely construct solutions that remain far from optimality, while hand-crafted improvement rules may limit refinement. The paper learns improvement heuristics with deep reinforcement learning and a self-attention policy for TSP and CVRP, reporting stronger performance than deep-learning and hand-crafted baselines, with further gains from diversification and generalization across settings.

Abstract

from arXiv · show

Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by hand-crafted rules which may limit their performance. In this paper, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention based deep architecture as the policy network to guide the selection of next solution. We apply our method to two important routing problems, i.e. travelling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art deep learning based approaches. The learned policies are more effective than the traditional hand-crafted ones, and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions and even real-world dataset.

I. INTRODUCTION

Deep learning for routing has mainly learned construction heuristics, leaving solution quality below highly optimized solvers. This paper instead learns improvement policies with deep reinforcement learning for TSP and CVRP.

  • Routing problems such as TSP and CVRP are challenging combinatorial optimization problems because of their NP-hardness.Source: §I · p. 1
  • Existing deep-learning methods mainly construct solutions incrementally, but their objective values remain relatively far from highly optimized traditional solvers.Source: §I · p. 1
  • The proposed framework learns improvement heuristics that iteratively refine an initial solution through neighborhood search and pairwise local operators.Source: §I · p. 1
  • A self-attention policy network guides next-solution selection, and the framework is applied to TSP and CVRP using actor-critic training.Source: §I · p. 1
  • The method outperforms existing deep-learning approaches on TSP and CVRP, exceeds hand-crafted policies, benefits from diversification, and generalizes across sizes, initial solutions, and real-world data.Source: §I · pp. 1–2

III. PRELIMINARIES

Routing solutions are tours subject to problem-specific constraints, and improvement heuristics repeatedly apply local operators to reduce tour distance. This paper focuses on pairwise operators and an always-accept improvement scheme.

  • A routing instance is represented as a graph with n nodes, each having features, while a solution is a sequence of nodes forming a tour.Source: §III · p. 2
  • TSP tours visit every node exactly once, whereas CVRP uses depot-centered routes that serve each customer exactly once under capacity constraints.Source: §III · p. 2
  • The objective is to minimize the Euclidean distance f(s) of the tour.Source: §III · p. 2
  • Improvement heuristics start from an initial solution and iteratively replace it with a neighborhood solution produced by a local operator.Source: §III · p. 2
  • Pairwise operators act on two nodes; examples include node swap, 2-opt reversal, and relocation, with larger operators decomposable into multiple 2-opt operations.Source: §III · p. 2
  • Traditional policies require domain knowledge and may stagnate, whereas the proposed simple scheme always accepts the selected solution and stops after a user-specified maximum step T.Source: §III · pp. 2–3

IV. THE METHOD

The method formulates iterative solution improvement as a reinforcement-learning task in which node-pair actions deterministically produce neighboring solutions. A self-attention policy selects pairs, while rewards track incumbent improvements over a continuing run.

  • The framework first formulates improvement heuristics as a reinforcement-learning task and then uses a self-attention policy network.Source: §IV · p. 3
  • The state is the current solution, the action is a selected node pair, and the next state is deterministically generated by a pairwise local operator.Source: A. RL Formulation · p. 3
  • The reward is designed to improve the initial solution as much as possible within the step limit T.Source: A. RL Formulation · p. 3
  • The incumbent is the best solution found so far and is updated only when the new solution has lower objective value.Source: A. RL Formulation · p. 3
  • Rewards are positive only for newly found improvements; with γ = 1, cumulative reward equals improvement from the initial solution to the best final solution.Source: A. RL Formulation · p. 3
  • The stochastic policy repeatedly selects actions until T, and the continuing formulation uses γ < 1 to support user-specified anytime step limits.Source: A. RL Formulation · p. 3
  • The policy network embeds nodes and computes a probability matrix whose entries represent selection probabilities for node pairs.Source: Figure 2 · p. 3

B. Policy Network

The policy network combines position-aware node embeddings with self-attention and pairwise compatibility scoring to produce probabilities for selecting node pairs for local operations.

Architecture

  • The network has node-embedding and node-pair-selection components, with each probability-matrix element representing a node-pair selection probability.Node features are projected into embeddings, then processed to support local-operation selection.Source: B. Policy Network · p. 3

Node Embedding

  • Sinusoidal positional encodings are added because node positions in the solution sequence matter.The paper reports that relative positional encoding performed worse than the sinusoidal alternative.Source: B. Policy Network · pp. 3–4
  • Three self-attention blocks successively refine the position-aware embeddings using message passing, fully connected layers, skip connections, and batch normalization.Each block uses self-attention followed by a fully connected layer, with residual processing after both layers.Source: B. Policy Network · p. 4

Node Pair Selection

  • Node-pair scores are computed through multiplicative compatibility between query and key representations.The compatibility matrix reflects scores for picking each node pair.Source: B. Policy Network · p. 4
  • A masked softmax converts pair scores into probabilities, excludes identical-node pairs, and samples rather than greedily selecting the highest-probability pair.The compatibility values are bounded by tanh with C = 10 before masking and sampling.Source: B. Policy Network · p. 4

C. Training Algorithm

The improvement policy is trained as a continuing reinforcement-learning task with an actor-critic method, using a critic to estimate cumulative rewards and bootstrap value estimates.

Training

  • The policy network is trained with an actor-critic algorithm using Adam, building on REINFORCE with a trainable bootstrapped critic.The critic estimates cumulative reward at each state, while n-step returns balance reward-propagation efficiency and bias-variance trade-offs.Source: C. Training Algorithm · p. 4
  • Because the task has no terminal state, the algorithm bootstraps the value from the time-limit state.This supports learning a policy for the continuing task.Source: C. Training Algorithm · p. 4

D. Deployment

The method is specialized for TSP and CVRP while retaining the shared improvement framework, with problem-specific node features and feasibility or reversal masks.

TSP

  • For TSP, node features contain coordinates, and the previously selected pair is masked to prevent reversing the prior local operation.The remaining components of the approach are kept unchanged.Source: D. Deployment · p. 4

CVRP

  • For CVRP, node features include neighboring coordinates, the node coordinate, and demand to represent local structure.The feature vector is seven-dimensional and combines the immediate left and right neighbors with demand.Source: D. Deployment · p. 5
  • For CVRP, infeasible node pairs and the pair selected at the previous step are masked before selection.This preserves feasibility and avoids immediately repeating the prior operation.Source: D. Deployment · p. 5

V. EXPERIMENTAL RESULTS

Experiments use Euclidean TSP and CVRP instances with 20, 50, and 100 nodes, generated from uniformly sampled coordinates and demands, with problem-specific training settings.

Datasets

  • 20, 50, and 100 nodes are used for both Euclidean TSP and CVRP experiments.The corresponding problem variants are named TSP20, TSP50, TSP100, CVRP20, CVRP50, and CVRP100.Source: §V · p. 5

TSP

  • TSP instances are generated on the fly from uniformly sampled unit-square coordinates and trained from random initial solutions.The training step limit is T=200, with γ = 0.99 and a four-step return.Source: §V · p. 5

CVRP

  • CVRP instances use uniformly sampled customer demands with capacities 30, 40, and 50 for 20, 50, and 100 nodes.Initial solutions are created with a nearest insertion heuristic and augmented with dummy depots.Source: §V · p. 5

Training Setup

  • 200 epochs are trained for all problems, with an initial learning rate of 10^-4 decayed by 0.99 per epoch.Training is performed on a single Tesla V100 GPU, with epoch times varying by problem and size.Source: §V · p. 5

Operators

  • 2-opt, node swap, and relocation are tested as pairwise operators, with 2-opt producing the best results.Unless otherwise stated, experiments apply 2-opt.Source: §V · p. 5

A. Comparison with State-of-the-art Methods

The method is evaluated against exact, heuristic, metaheuristic, and deep-learning baselines on TSP and CVRP. With larger step limits, it narrows optimality gaps and achieves strong comparisons with deep-learning baselines, while remaining distinct from highly optimized traditional solvers.

Baselines

  • The evaluation compares the method with Concorde, LKH3, OR-Tools, AM, and NeuRewriter on TSP and CVRP.The tests use common random instances for most methods, while NeuRewriter results are reported from its original paper.Source: A. Comparison with State-of-the-art… · p. 5

Results

B. Comparison with Conventional Policies

The learned policy is compared with first-improvement and best-improvement rules under the same test conditions. It consistently performs better, with a larger advantage on harder and larger instances.

Policies

Results

Interpretation

Efficiency

C. Enhancement by Diversifying

Two diversification strategies improve the learned policy by exploring multiple solutions: multi-run repeats the final policy, while multi-policy uses policies from recent training epochs. More runs or policies consistently improve solution quality.

Strategies

Results

Comparison

  • With the same number of runs or policies, multi-run outperforms multi-policy across all problems.The authors attribute this to small differences among late-training policies and the absence of diversity-oriented training.Source: C. Enhancement by Diversifying · p. 7

Results

Efficiency

D. Generalization Analysis

The learned policies generalize across initial solutions, problem sizes, and real-world routing datasets, while 2-opt visualizations illustrate effective iterative improvements.

Initial-solution generalization

  • For TSP100 and CVRP100, policies generalized to unseen initial-solution types with nearly identical objective values.TSP achieved 7.874 versus 7.871, while CVRP achieved 16.029 versus 16.025 across the tested initializations.Source: D. Generalization Analysis · p. 7

Problem-size generalization

  • Nearest-insertion initialization enabled relatively good TSP generalization across sizes, whereas random initialization produced weaker cross-size results.Using the TSP50 policy on TSP100 improved the objective from 37.41 to 15.30, but the final result was not very good with random initialization.Source: D. Generalization Analysis · pp. 7–8
  • CVRP policies generalized well across different sizes and outperformed OR-Tools on all tested sizes when trained on CVRP50 and CVRP100.They also outperformed prior reported results, including 18.62 versus 18.86 and 16.53 versus 17.33 on CVRP100.Source: D. Generalization Analysis · p. 8

Policy behavior

  • A 2-opt visualization shows four successive operations reducing a TSP100 objective from 10.93 to 10.70, while motivating extensions to multiple operators.The visualized states depict newly added links after deleted links, illustrating how learned policies guide local operations.Source: E. Visualization · p. 8

Real-world datasets

  • On TSPlib, the TSP100 policy outperformed AM with 1,280 and 5,000 samples on 27 of 36 instances, although all learning methods remained inferior to OR-Tools overall.Average optimality gaps were 11.50%, 18.42%, and 23.61% for instances with 0–100, 101–200, and 201–300 nodes.Source: F. Test on Real-World Dataset · pp. 8–9
  • On CVRPlib, the CVRP100 policy achieved an average optimality gap more than two times smaller than AM and performed better on 13 of 22 instances.Average gaps were 12.36% for 101–150 nodes and 16.27% for 151–200 nodes.Source: F. Test on Real-World Dataset · p. 9

VI. CONCLUSIONS AND FUTURE WORK

The paper presents deep reinforcement learning for automatically learning improvement heuristics with a self-attention architecture. Results on TSP and CVRP show strong performance and generalization, while future work targets more complex operator-selection policies.

Conclusions

  • The framework automatically learns improvement heuristics for routing problems through deep reinforcement learning and self-attention-based policy networks.The architecture supports learning with pairwise local operators.Source: §VI · p. 9
  • On TSP and CVRP, the method outperformed state-of-the-art deep models and further narrowed the gap to highly optimized solvers.The learned policies also generalized across initial solutions, problem sizes, and real-world datasets.Source: §VI · p. 9

Future work

  • Future work includes learning both the local operator and next solution, using multi-head self-attention or hierarchical reinforcement learning.The framework is also intended to learn better solution-picking policies beyond the simple search scheme used here.Source: §VI · p. 9

Related papers

Loading 1912.05784v2…