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.

  • Problem

    Deep-learning routing methods mainly learn construction heuristics whose solutions remain far from optimality, while hand-crafted improvement policies may limit iterative refinement.

  • Method

    The paper uses deep reinforcement learning with a self-attention policy network to learn pairwise improvement heuristics for TSP and CVRP.

  • Results

    The method outperforms state-of-the-art deep-learning approaches on TSP and CVRP, surpasses hand-crafted rules, and improves further with diversification.

  • Takeaways & Limitations

    Learned improvement policies generalize to different problem sizes, initial solutions, and real-world datasets, supporting automatic heuristic learning with limited domain knowledge.

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.
  • Existing deep-learning methods mainly construct solutions incrementally, but their objective values remain relatively far from highly optimized traditional solvers.
  • The proposed framework learns improvement heuristics that iteratively refine an initial solution through neighborhood search and pairwise local operators.
  • A self-attention policy network guides next-solution selection, and the framework is applied to TSP and CVRP using actor-critic training.
  • 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.

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.
  • TSP tours visit every node exactly once, whereas CVRP uses depot-centered routes that serve each customer exactly once under capacity constraints.
  • The objective is to minimize the Euclidean distance f(s) of the tour.
  • Improvement heuristics start from an initial solution and iteratively replace it with a neighborhood solution produced by a local operator.
  • Pairwise operators act on two nodes; examples include node swap, 2-opt reversal, and relocation, with larger operators decomposable into multiple 2-opt operations.
  • 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.

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.
  • 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.
  • The reward is designed to improve the initial solution as much as possible within the step limit T.
  • The incumbent is the best solution found so far and is updated only when the new solution has lower objective value.
  • Rewards are positive only for newly found improvements; with γ = 1, cumulative reward equals improvement from the initial solution to the best final solution.
  • The stochastic policy repeatedly selects actions until T, and the continuing formulation uses γ < 1 to support user-specified anytime step limits.
  • The policy network embeds nodes and computes a probability matrix whose entries represent selection probabilities for node pairs.

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.
  • 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.
  • Node Embedding: 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.
  • 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.
  • Node Pair Selection: 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.

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.
  • Training: 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.

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.
  • 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.
  • CVRP: 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.

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.
  • 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.
  • 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.
  • 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.
  • 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.

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.
  • Results: At T=1,000, the method significantly outperforms OR-Tools for both TSP and CVRP across all tested sizes.
  • Results: At T=3,000, the method consistently outperforms AM with N=5,000 on all instance sets.
  • Results: At T=3,000, the method nearly matches Concorde on TSP20 and is on par with NeuRewriter for CVRP.
  • Results: At T=5,000, the method further reduces optimality gaps and reports state-of-the-art results on TSP and CVRP among the compared deep models.

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: The comparison uses first-improvement and best-improvement rules, which select the first or best cost-reducing neighborhood solution.
  • Results: For the same T, the learned policy consistently outperforms both conventional rules on all instance sets.
  • Results: At T=3,000, the learned policy already outperforms both rules at T=5,000 on TSP100, CVRP50, and CVRP100.
  • Interpretation: The advantage of learned policies is more prominent on larger problems, where they provide better guidance than conventional rules.
  • Efficiency: Runtime is not directly comparable because the conventional rules run on CPU, but the neural policy avoids neighborhood traversal when selecting the next solution.

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: Multi-run executes the final policy multiple times, whereas multi-policy applies policies from the last several training epochs.
  • Results: Both diversification strategies consistently improve solution quality as more runs or policies are used.
  • 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.
  • Results: With 8 multi-run solutions, optimality gaps reach 0.11% for TSP50 and 0.09% for CVRP50.
  • Results: With 8 multi-run solutions, optimality gaps narrow to 0.56% for TSP100 and 1.52% for CVRP100.
  • Results: For CVRP100, 16 and 32 multi-run solutions reduce the objective values to 15.840 and 15.809, with gaps of 1.24% and 1.08%.
  • Efficiency: The strategies can be parallelized, so extra runtime is small when sufficient device memory is available.

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.
  • 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.
  • Problem-size generalization: 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.
  • 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.
  • 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.
  • Real-world datasets: 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.

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.
  • Conclusions: 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.
  • 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.
Loading 1912.05784v2…