PaperlayerView exact revision on arXiv

Source-linked AI summary

Attention, Learn to Solve Routing Problems!

Wouter Kool, Herke van Hoof, Max Welling

arXiv:1803.08475v3stat.MLcs.LG

TL;DR

Learned heuristics for combinatorial optimization need better models and training methods to become practical. This paper combines an attention-based model with REINFORCE and a deterministic greedy-rollout baseline, achieving strong results across routing problems and near-optimal TSP performance up to 100 nodes.

  • Problem

    Existing learned heuristics for combinatorial optimization require better models and training methods to support practical use across routing problems.

  • Method

    The paper uses an attention-based encoder-decoder policy trained with REINFORCE and a deterministic greedy rollout from the best model as its baseline.

  • Results

    The method significantly improves learned TSP heuristics and learns strong heuristics for VRP variants, OP, and stochastic PCTSP, with results close to specialized algorithms.

  • Takeaways & Limitations

    A single model and hyperparameter setting provides a strong starting point for learning sequential-decision heuristics across graph-based combinatorial optimization problems.

  • Takeaways & Limitations

    Scaling to larger instances and handling feasibility constraints beyond simple masking remain important challenges.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Routing problems are difficult combinatorial optimization tasks, motivating learned heuristics that can discover effective policies for instance classes rather than solve every worst-case instance exactly. This paper advances that approach with an attention model and greedy-rollout training across multiple routing problems.

  • Motivation: The Travelling Scientist Problem reduces to the NP-hard Travelling Salesman Problem, but typical instances may have exploitable structure.The motivating example suggests learning algorithms specialized to recurring instance types rather than targeting arbitrary worst-case inputs.
  • Motivation: Combinatorial optimization methods trade guaranteed optimality against computational cost through exact algorithms and heuristics.Heuristics can be interpreted as policies that select decisions from a combinatorially large solution space.
  • Contribution: The authors propose attention-based modeling and REINFORCE training with a deterministic greedy-rollout baseline.They aim to learn strong heuristics across multiple routing problems using one set of hyperparameters, rather than outperform specialized TSP solvers.

2 RELATED WORK

Prior work applied neural networks and reinforcement learning to routing, including pointer-based, graph-based, supervised, and non-autoregressive approaches. The paper distinguishes its attention model and training procedure from these learned heuristics and concurrent attention-based work.

  • Neural approaches: Neural networks have been used for combinatorial optimization since Hopfield-network approaches to small TSP instances.Later work increasingly learned offline across classes of problem instances rather than solving each instance from scratch.
  • Neural approaches: Pointer Networks output permutations for TSP, first with supervised example solutions and later with actor-critic reinforcement learning.The reinforcement-learning approach estimates policy gradients from sampled tour costs.
  • Neural approaches: Graph-based reinforcement learning methods trained node-insertion policies with incremental rewards that effectively encouraged greedy behavior.
  • Neural approaches: A supervised Graph Neural Network directly predicted TSP adjacency matrices, while a Transformer model produced fractional solutions for multiple TSP.The reported non-autoregressive GNN approach had a 2.7% optimality gap for n = 20, worse than the cited autoregressive approaches.
  • Positioning: Compared with concurrent attention-based TSP work, this paper uses a different decoder and improved training algorithm, obtaining stronger results without 2OPT and extending to other problems.

3 ATTENTION MODEL

The Attention Model represents routing instances with an order-invariant attention encoder and an autoregressive decoder that selects feasible nodes sequentially. For TSP, decoder context summarizes the graph and the first and last nodes of the partial tour while masking visited nodes.

  • Model formulation: A problem instance is represented as a graph whose nodes have features, and a solution is a permutation generated by a stochastic policy p(π|s).
  • Decoder: The decoder constructs the tour one node at a time using encoder embeddings, a problem-specific mask, and the previously generated outputs.For TSP, the context includes the graph embedding and embeddings of the first and last nodes; learned placeholders are used at the first step.
  • Encoder: Removing positional encoding makes encoder node embeddings invariant to the input order.
  • Encoder: The encoder embeds all input nodes through sequential attention layers and computes a graph embedding as the mean of the final node embeddings.Each layer combines multi-head attention for node communication with a node-wise feed-forward sublayer.
  • Decoder: At each TSP decoding step, already visited nodes are masked, and final node probabilities are obtained from clipped attention compatibilities followed by a softmax.The decoder computes attention messages only to a special context node for efficiency.

4 REINFORCE WITH GREEDY ROLLOUT BASELINE

The training method minimizes expected solution cost with REINFORCE and uses a deterministic greedy rollout from the best frozen model as an instance-dependent baseline. Periodic policy updates stabilize the baseline, while the extra rollout adds limited empirical overhead.

  • REINFORCE: The model is trained by gradient descent on expected tour cost using the REINFORCE gradient estimator with a baseline.
  • Baseline: A good baseline reduces gradient variance and increases learning speed, whereas learned value-function critics can be difficult to make work.
  • Baseline: The rollout baseline uses the cost of a deterministic greedy rollout from the best model so far.
  • Baseline updates: The baseline policy is frozen for each epoch and replaced only when the current policy improves under greedy decoding.
  • Training signal: Sampling solutions better than the greedy rollout reinforces their actions, training the model to improve over its greedy self.
  • Efficiency: 25%: the rollout baseline's empirical computation overhead, despite each additional rollout adding 50% more forward-pass computation.The baseline rollout accounts for 20% of total training time and can be parallelized.

5 EXPERIMENTS

Experiments evaluate the Attention Model across routing problems, decoding strategies, baselines, runtime settings, and training comparisons with Pointer Networks. The model achieves strong results across TSP, VRP, OP, PCTSP, and stochastic PCTSP, while rollout baselines improve training quality and convergence.

  • Experimental setup: The Attention Model is evaluated on TSP, two VRP variants, OP, PCTSP, and stochastic PCTSP using problem sizes n = 20, 50, and 100.Inputs, decoder context, masks, and objectives are adjusted for each problem.
  • Decoding and baselines: At test time, greedy decoding selects the best action at each step, while sampling evaluates 1280 solutions and reports the best.Sampling improves solution quality with increased computation.
  • TSP: For TSP, greedy construction reaches 0.3% above optimal for n = 20, improving over previous learned heuristics from around 1.5%.The model also outperforms EAN, including EAN enhanced with 2OPT local search.
  • Vehicle Routing Problem: The model obtains significantly better greedy VRP results than Nazari et al.’s reinforcement-learning framework and gets closer to LKH3 in most larger cases.The reported runtime is less than 1 second per instance.
  • Orienteering Problem: For OP, sampling 1280 solutions is only 2% worse than the Compass genetic algorithm on the hardest reported prize distribution.The model also outperforms a Python genetic algorithm and the construction phase of a classical heuristic.
  • Prize-collecting variants: For PCTSP, results are within 2% of the C++ ILS algorithm and nearly match OR Tools with 60 seconds of local search in significantly less time.For stochastic PCTSP, the model outperforms all baselines for n = 20 and provides competitive solutions at a fraction of the computational cost.
  • Attention Model versus Pointer Network: The Attention Model outperforms the Pointer Network with every tested baseline, while the rollout baseline improves quality and convergence speed for both models.Compared with rollout, the exponential baseline is around 20% faster per epoch and the critic baseline around 13% slower.

6 DISCUSSION

The work combines an attention-based model with a training method that improves learned heuristics for TSP and supports strong heuristics across multiple routing problems. The authors identify larger instances and complex feasibility constraints as key directions for extending practical scope.

  • The model and training method significantly improve learned heuristics for TSP and produce strong single-construction heuristics for multiple routing problems.
  • The graph-based approach may support learning heuristics for other graph optimization problems whose solutions are sequential decisions.
  • Operational constraints create problem variants lacking good human-designed heuristics, making learned heuristics potentially valuable in practice.
  • Scaling to larger instances remains an important direction, with graph sparsification identified as a first step toward computational efficiency.
  • Many practically important problems have feasibility constraints that simple masking cannot satisfy, motivating combinations of heuristic learning and backtracking.

A ATTENTION MODEL DETAILS

The attention model interprets attention as weighted message passing over graph nodes. Multi-head attention aggregates different neighbor messages, followed by projected outputs and node-wise feed-forward processing with normalization.

  • Attention computes weighted messages by matching each node’s query with neighboring nodes’ keys and combining their value vectors.
  • Non-adjacent nodes receive no messages because their compatibility is defined as −∞.
  • Multi-head attention: Multi-head attention uses M = 8 heads with dk = dv = dh / M, allowing nodes to receive different message types from different neighbors.
  • Multi-head attention: The head outputs are projected back into a single dh-dimensional vector before forming the final multi-head attention value.
  • Each attention layer combines multi-head message passing with a node-wise feed-forward sublayer, skip connections, and batch normalization.

B.1 CRITIC ARCHITECTURE

The appendix describes heuristic baselines that construct TSP tours sequentially and a critic architecture used for comparison. TSP instances use uniformly sampled node locations in the unit square.

  • Critic architecture: The critic uses three attention layers, averages node embeddings, and processes them with a one-hidden-layer MLP producing a single output.
  • TSP instances contain n node locations sampled uniformly at random in the unit square.
  • All implemented TSP heuristics construct one tour in a single pass by extending a partial solution one node at a time.
  • Nearest neighbor: Nearest neighbor repeatedly adds the node nearest to the partial path’s end node, then connects the final node back to the start.
  • Insertion heuristics: Insertion heuristics add nodes at the tour position minimizing the insertion cost dji + dik − djk.
  • Insertion heuristics: Nearest, farthest, and random insertion differ in whether they select the nearest, farthest, or a random node for insertion.

B.4 COMPARISON TO CONCURRENT WORK

The paper compares its attention model with concurrent Transformer-based work while aligning evaluation conditions through rerunning the concurrent model. It also distinguishes decoder context, baselines, local search, dimensionality, preprocessing, and problem coverage.

  • Decoder context: The concurrent model uses the last K = 3 visited nodes as decoder context, whereas this work uses the last node, the first node, and the graph embedding.
  • Training baseline: The concurrent work uses a critic baseline, while this paper finds a rollout baseline more effective after also experimenting with a Transformer-based critic.
  • Both works use attention-based TSP models, but this paper uses a different decoder and training algorithm and reports results without 2OPT.
  • Local search: Adding 2OPT to the concurrent model improves its best sampled solution, illustrating a hybrid learned-algorithm and local-search approach.
  • Problem coverage: The comparison includes TSP, two VRP variants, the OP with different prize distributions, and stochastic PCTSP.
  • Evaluation: The authors reran the concurrent code under matched greedy-decoding and 1280-solution sampling conditions on a dataset with the same uniform-unit-square generation procedure.

B.5 EXTENDED RESULTS

The extended experiments examine training stability, generalization across problem sizes, and adaptations of the model to vehicle-routing constraints. They also document implementation choices and comparisons with optimization baselines.

  • Training and model choices: A learning rate of 10^-3 works better with decay but can be unstable, whereas 10^-4 is more stable without requiring decay.Without decay, training had not fully converged after 100 epochs in the reported TSP20 and TSP50 experiments.
  • Training and model choices: The final experiments at n = 100 used the smaller learning rate because training was more stable, while larger models sometimes diverged with the larger rate.Most end results were otherwise similar across learning-rate schedules.
  • Training and model choices: N = 3 layers provide a good trade-off between result quality and model runtime, while N = 3 and N = 5 achieve the best performance.The layer-count experiments compare model quality against computational complexity.
  • Generalization: Models generalize to test sizes different from their training sizes, but quality degrades as the size difference increases.Selecting the best trained model for each instance size yields a strong overall algorithm.
  • Vehicle-routing formulation: The VRP formulation adds a depot, node demands, remaining demands, and remaining vehicle capacity while supporting both standard and split-delivery variants.For n = 100, longer VRP outputs require a batch size of 256 to satisfy memory constraints.
  • Vehicle-routing formulation: VRP decoding uses the current location and remaining capacity as context, masks infeasible nodes, and prevents consecutive depot visits.Without split deliveries, nodes are masked when already served or when their demand exceeds remaining capacity.
  • Baselines: The LKH38 baseline is run once with a maximum of 10000 trials because ten runs improve quality only marginally while requiring much more time.This is an explicit runtime–quality choice for the comparison.

C.4 EXAMPLE SOLUTIONS

The example solutions illustrate the heuristic learned for CVRP and the instance-generation choices used for the Orienteering Problem. The CVRP routes are generally structured but can contain locally suboptimal stop orders.

  • CVRP examples: Greedy CVRP solutions with n = 100 generally construct routes from below the depot toward the top, packing most routes densely.The final route often serves remaining nearby customers, and the farthest-from-depot node commonly appears in the route interior.
  • OP formulation: In the OP, each node has a prize, visiting nodes is optional, and the objective is to maximize collected prize under a maximum route length.A selected depot ends the route, while masking prevents infeasible visits.
  • OP instance generation: OP instances use uniformly sampled depot and node locations, with constant, discretized-uniform, or distance-proportional prize distributions.Distance-proportional prizes are challenging because the largest prizes lie farthest from the depot.
  • OP instance generation: The maximum route lengths T_20 = 2, T_50 = 3, and T_100 = 4 are chosen to make roughly half the nodes visitable on average.Fixed limits allow some instances to permit more or fewer visits than the average target.

D.2 ATTENTION MODEL FOR THE OP

The OP adaptation supplies prizes and remaining route length to the Attention Model while masking nodes that are already visited or cannot fit within the remaining distance. It is compared with several classical baselines.

  • Encoder and context: The OP encoder uses a separate depot embedding and provides each regular node’s normalized prize as an input feature.The depot and regular-node embeddings use different parameterizations.
  • Length constraint: The remaining route length is updated by subtracting the distance traveled from the previous node to the selected node.The initial remaining length is T, and the starting location is the depot.
  • Encoder and context: The decoder context consists of the current location and remaining maximum route length, with no initial placeholders because routes start and end at the depot.Collected prizes need not be included in the context for remaining decisions.
  • Masking: OP masking forbids regular nodes that were already visited or cannot be reached and returned to the depot within the remaining length.The depot itself is never masked.
  • Baselines: The learned construction is compared with Compass, OR Tools, and the Tsiligirides heuristic, whose randomized construction has the same structure but manually engineered node probabilities.OR Tools is modified to use Euclidean distance, one vehicle, optional-node penalties, and a maximum-distance constraint.

D.4 EXTENDED RESULTS

The extended results describe OP and PCTSP instance construction, model adaptations, stochastic planning, and baseline procedures. They emphasize balanced prize–penalty settings and a trade-off between adaptivity and computation time.

  • OP results: Constant and uniform prize OP instances produce results similar to distance-based prizes, while Gurobi confirms they are easier by calculation time.These findings are reported in Table 3.
  • PCTSP formulation: PCTSP minimizes tour length plus penalties for unvisited nodes while requiring collection of at least a normalized total prize of 1.This reverses the OP’s maximize-prize-under-length formulation.
  • Instance generation: PCTSP prize and penalty distributions are designed so approximately half the nodes are visited and neither quantity dominates node selection.Penalty magnitudes are chosen to contribute an objective term roughly comparable to tour length.
  • PCTSP model: The PCTSP model tracks remaining prize, ends only after the prize constraint is satisfied, and masks regular nodes only after they are visited.The decoder context uses the current location and remaining prize; collected prizes are represented implicitly by that remaining amount.
  • Stochastic PCTSP: For stochastic PCTSP, the model is retrained using hidden sampled prizes, and greedy and sampled rollouts share the same realizations to reduce variance.The shared realizations implement a common-random-numbers-style variance-reduction approach.
  • Stochastic PCTSP: Exact offline tour construction is impossible for stochastic PCTSP because any tour can be infeasible with nonzero probability and optimal online decisions involve infinitely many scenarios.A baseline instead replans using expected prizes after observing realized prizes.
  • Stochastic PCTSP: Visiting half of the planned tour before replanning yields O(log n) iterations and trades adaptivity against computation time.This schedule becomes more adaptive as the solution approaches the minimum-prize requirement.
Loading 1803.08475v3…