Graph Neural Network Guided Local Search for the Traveling Salesperson Problem

Approach

• The hybrid GNN-and-GLS approach converges to optimal solutions faster than three recent learning-based TSP approaches.The paper focuses on approximately solving the Euclidean TSP.Source: §1 · p. 1
• GLS uses global edge regret to distinguish costly inclusions from less costly ones, seeking high-quality solutions quickly rather than requiring optimality.The approach approximates regret with a learned representation.Source: §1 · pp. 1–2

Results

• Mean optimality gap falls from 0.268% to 0.009% on 50-node sets and from 1.534% to 0.705% on 100-node sets.When generalizing from 20-node instances to the 100-node set, the gap falls from 18.845% to 2.622%.Source: §1 · p. 2

Operations-research solvers

• Concorde guarantees solution optimality, while LKH-2 and LKH-3 are effective approximate solvers; these specialized solvers can solve challenging TSPs in seconds.Concorde uses cutting planes and branch-and-cut; LKH solvers use the κ-opt heuristic.Source: §2 · p. 2

General routing frameworks

• Practical routing constraints motivate general, fast frameworks; KGLS applies GLS to CVRP using three engineered features.KGLS finds solutions almost as good as state-of-the-art metaheuristics in a fraction of the time.Source: §2 · p. 2

Learning-based approaches

• Learning-based optimization can exploit related problem distributions, and the paper organizes TSP learning approaches into three categories.The categories distinguish ML producing solutions, providing information to an OR algorithm, or making decisions within one.Source: §2 · p. 2

ML provides a solution

• Direct-output methods construct tours from problem definitions, including PtrNet, policy-gradient active search, and Transformer-based approaches.PtrNet outputs a node permutation; Kool et al. (2018) use a Transformer architecture.Source: §2 · p. 2
• Other learning methods predict edge heatmaps and then reconstruct tours, using beam search, dynamic programming, or Monte Carlo tree search.These approaches include Joshi et al. (2019), Kool et al. (2021), and Fu et al. (2021).Source: §2 · pp. 2–3

ML provides information to an OR algorithm

• This paper uses ML to inform an OR algorithm by approximating regret and guiding GLS, a use of predictions to guide a metaheuristic that the authors identify as novel.Prior edge-prediction work cited here constructs tours using heuristics.Source: §2 · p. 3

ML makes decisions within an OR algorithm

• Embedded-learning approaches repeatedly use a model for lower-level decisions inside a master optimization procedure, including insertion and 2-opt methods.Examples include a GNN with a DQN and learned policies for applying 2-opt operations.Source: §2 · p. 3

Traveling Salesperson Problem

• A Euclidean TSP is a complete, undirected, weighted graph whose edge weights are distances; a tour is a Hamiltonian cycle, and an optimal tour has minimum weight.The approach focuses on Euclidean TSP but may apply to other routing problems such as CVRP.Source: §3 · p. 3

Regret

• Regret measures the future cost of an action that also gives an immediate reward, and is commonly computed over a fixed horizon.The passage notes that globally computing regret across all possible insertion sequences is not computationally feasible.Source: §3 · p. 3

Local Search

• Local search starts from an initial solution and moves to lower-cost neighboring solutions until none is better under the objective function.A neighborhood comprises solutions reachable by applying an operator.Source: §3 · p. 3

Guided Local Search

• GLS augments the objective with penalties on unfavorable solution aspects; in TSP, those aspects are edges, and utility determines which receive penalties.Higher-cost aspects have greater utility, while aspects with more existing penalties have lower utility.Source: §3 · pp. 3–4
• GLS alternates objective-guided optimization with augmented-objective perturbation, restricting perturbation moves to those that remove a penalized edge.Perturbation continues until K improving operations have been applied, helping the search escape a local minimum.Source: §3 · p. 4

4 METHOD

• The GNN-guided GLS combines learned edge-regret predictions with the original problem graph to steer local search toward high-quality solutions.The model processes the problem graph's line graph, while GLS uses the predictions alongside the original graph.Source: §4 · p. 4, Figure 1 · p. 4

4.1 GLOBAL REGRET

• Global regret measures the cost of requiring an edge in a solution relative to a globally optimal solution; optimal-solution edges have zero regret.With perfect regret information, greedily selecting the lowest-regret decisions could construct an optimal solution.Source: §4.1 · p. 5

4.2 REGRET APPROXIMATION MODEL

• The regret approximation model uses a GNN on the problem graph’s line graph, representing original edges as nodes and predicting regret from edge-focused features.Its architecture has an embedding layer, multiple message-passing layers, and an output layer; the line-graph representation permits a model without node features.Source: §4.2 · pp. 5–6

4.3 REGRET-GUIDED LOCAL SEARCH

• GLS alternates local optimization with perturbation, penalizing high-regret edges to escape local minima; its search uses relocate and 2-opt operators.It starts from a nearest-neighbor tour built by repeatedly selecting the lowest-regret edge to an unvisited node, then applies local search to penalized edges.Source: §4.3 · p. 6

5 EXPERIMENTS

• The model is supervised to predict edge regret from edge weight, its sole input feature.The paper notes that additional features increase computational cost and reports edge weight as the most important feature among 11 tested.Source: §5 · p. 6
• The comparison includes Nearest Neighbour, Farthest Insertion, local search, Concorde, LKH-3, and three learning-based approaches.The approaches are evaluated using publicly available implementations and pretrained models where available.Source: §5 · p. 7
• Experiments fix computation time in one setting and measure mean optimality gap and optimal-solution counts, allowing direct comparisons across approaches.The fixed-time experiments allow up to 10 seconds per problem, including feature calculation, model evaluation, and initial-solution construction.Source: §5 · p. 7
• The benchmarks comprise 1,000 randomly generated 2D Euclidean instances each for TSP20, TSP50, and TSP100.The experiments also examine generalization from smaller to larger sets and from random instances to TSPLIB instances.Source: §5 · p. 7
• The approach always lies on the Pareto front for solution quality and computation time in the unfixed-time experiments.Pareto-optimal values are faster or better solutions; some starred results lack comparable per-instance runtimes.Source: §5 · p. 7, Table 1 · p. 8
• 18.845% to 2.622%: mean optimality gap when generalizing from 20-node instances to the 100-node problem set.The paper reports this as a 7× improvement.Source: §5 · p. 8

6 DISCUSSION

• After 10 seconds per instance, the approach converges to better solutions than the other approaches.The table reports mean optimality gap, its standard deviation, and the percentage of optimally solved problems.Source: Table 2 · p. 9
• Using the line graph lets the model store states and aggregate messages on edges without node-position features, which the authors suggest may support generalization.The line graph can be sparse even when the original Euclidean TSP graph is complete, but the model uses more GPU memory than models using the original graph.Source: §6 · pp. 8–9
• Learning edge regret from an edge and its neighbors implicitly assumes the symmetry of a TSP tour, which is invariant to the origin city.Sequence-based construction approaches can miss this symmetry, and producing the correct sequence becomes harder as the number of cities grows.Source: §6 · p. 9
• The authors argue that global regret applies to most routing problems, with a suitable local search procedure plugged in for each new problem.They note that 2-opt cannot be used for routing problems with pickup-and-drop-off constraints; their approach relies on supervised learning, with end-to-end training left for future work.Source: §6 · p. 9

7 CONCLUSION

• A GNN approximates each edge’s global regret to guide GLS, using the TSP line graph and edge weight as the only input feature.The approach is evaluated against recent learning-based methods, with a focus on the trade-off between solution quality and computation time.Source: §7 · p. 9
• The authors report that the approach converges to optimal solutions faster than the evaluated learning-based approaches.They state that the line-graph representation allows the model to use edge weights without node features.Source: §7 · p. 9

A IMPLEMENTATION DETAILS

• Experiments use one CPU core, 24 GB RAM, and one Tesla P100 GPU, with methods evaluated one at a time.The authors record actual tours and apply a common tour-cost and optimality-gap calculation; they use an objective threshold of 10^-7 to separate optimal from sub-optimal solutions.Source: A IMPLEMENTATION DETAILS · p. 13
• Training data comprise 100,000 randomly sampled 2D Euclidean TSP instances for each of the 20-, 50-, and 100-node sizes.Targets are edge regret values calculated using Concorde and LKH-3 with an edge fixed; the authors report empirically validating that LKH-3 configuration for instances of 100 nodes or fewer.Source: A IMPLEMENTATION DETAILS · p. 13
• The model trains for up to 100 epochs with early stopping, using Adam, an exponentially decaying learning rate, and an l2 loss.Training uses batch size 32 for 20- and 50-node sets and 15 for the 100-node set; the model has 3 message-passing layers and GLS uses 20 perturbation moves.Source: A IMPLEMENTATION DETAILS · p. 13
• The authors corrected an invalid-tour reporting error in Joshi et al.’s beam search and discarded invalid tours in their evaluation.They caution that their results may therefore differ from those originally reported by the authors.Source: A IMPLEMENTATION DETAILS · pp. 13–14

• The charts plot mean optimality gap against computation time per instance across three increasingly difficult problem sets.Source: Figure 3 · p. 15, §B.1 · p. 15
• Nearest Neighbour, LKH-3, and Concorde typically form the Pareto front among non-learning approaches.Source: Figure 3 · p. 15
• Kool et al. (2018) and our approach form the Pareto front among learning-based approaches.Source: Figure 3 · p. 15

B.2 CONVERGENCE PROFILE CHARTS

• Feature computation, model evaluation, and initial-solution construction appear as gaps before the traces, especially for Joshi et al. (2019).Source: §B.2 · p. 16
• Our method converges to optimal solutions faster than the evaluated learning-based approaches across the three problem sets.Source: Figure 4 · p. 16
• The profiles show mean optimality gap and percentage of optimally solved problems as computation time increases.Source: Figure 4 · p. 16, §B.2 · p. 16

C.1 GENERALIZATION TO LARGER INSTANCES

• The generalization plots are ordered by increasing difference between training- and test-set sizes.Source: §C.1 · p. 17
• Figure 5 compares solution quality over time across generalization tasks, with mean optimality gap and optimally solved share shown separately.Source: Figure 5 · p. 17

C.2 GENERALIZATION TO REAL-WORLD INSTANCES

• The real-world evaluation trains on random 100-node TSPs and tests on 29 TSPLIB instances of 50–200 nodes with 2D Euclidean distances.Source: §C.2 · p. 18, Table 3 · p. 18

D ANALYSIS OF ADDITIONAL INPUT FEATURES

• Additional features may improve predictions and GLS guidance, but incur extra computation time.Source: Table 4 · p. 19, D ANALYSIS OF ADDITIONAL INPUT FEATURES · p. 19
• Edge weight has the largest estimated total effect on validation loss, followed by neighbor rank, depot weight, edge width, and node width.The remaining features have little to no importance.Source: D ANALYSIS OF ADDITIONAL INPUT FEATURES · p. 19, Figure 6 · p. 20
• The sensitivity analysis samples 100 feature sets, trains each model for 35 epochs, and estimates feature effects on validation loss.Source: D ANALYSIS OF ADDITIONAL INPUT FEATURES · p. 19
• Adding the top five features slightly improves regret-prediction accuracy, but the benefit is cancelled by their computation time.The comparison uses models trained on 20-node problems and evaluated on the 20-, 50-, and 100-node sets.Source: D ANALYSIS OF ADDITIONAL INPUT FEATURES · p. 19, Table 5 · p. 20