acceptodds
Under review as a conference paper at ICLR 2027

Unlocking Traditional TSP Heuristic Guided-Sampling via Neural Instance Modification

Abstract

The Traveling Salesman Problem (TSP) is one of the most representative NP-hard problems. Traditional heuristic tour constructors are computationally efficient and highly practical, but their deterministic behavior limits exploration and often leads to local optima. In contrast, neural-based heuristic tour constructors alleviate this issue through guided-sampling and typically achieve superior solution quality, but at the cost of expensive training. To bridge this gap, we propose TSP-MDF, a novel instance modification framework that equips traditional deterministic heuristic tour constructors with guided-sampling capability. Specifically, TSP-MDF introduces a neural-based instance modifier that strategically shifts node coordinates to sample multiple modified instances, on which the base traditional heuristic tour constructor constructs tours that are mapped back to the original instance, allowing traditional tour constructors to explore higher-quality tours and escape local optima. At the same time, benefiting from our instance modification formulation, the neural-based instance modifier can be trained efficiently without any ground-truth supervision, ensuring the framework maintains practicality. Extensive experiments on large-scale TSP benchmarks and real-world benchmarks demonstrate that TSP-MDF can significantly improve the performance of traditional heuristics tour constructors and with an extremely short training time.

Primary area:
optimization
Keywords:
Traveling Salesman Problem, Heuristics, Reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_52XaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

This paper proposes an approach that combines a neural-based method with traditional heuristic TSP methods. By learning how to iteratively optimize the input data of the TSP, this approach aims to improve the solution quality achieved by traditional TSP methods without incurring the high training costs typically associated with general neural-based methods.

Critical strengths
  1. This paper proposes a paradigm that uses data-driven fine-tuning to optimize traditional algorithms, enabling them to find better solutions more quickly. This method learns how to improve the traditional approach from each attempt.

  2. Experiments have shown that, compared to traditional heuristic TSP methods, this method can find better solutions more quickly; and compared to neural-based methods, it requires less training time and yields excellent results.

Critical weaknesses

The author did not clearly explain the motivation behind the method’s design or its underlying logic. My understanding is that this method essentially transforms “learning how to construct a good route” into “learning how to guide an algorithm that already knows how to construct routes so that it produces the correct solution.” However, since the ultimate goal is to alter the algorithm’s selection preferences, why not directly learn the weights of the edges between different cities, or directly modify the weight assigned to selecting a particular city, rather than achieving this indirectly through coordinate transformations? The author provides some qualitative explanations in the paper, such as: “Inspired by prompt engineering in LLMs, where input prompts are carefully modified to guide the model toward better responses, our TSP-MDF introduces an additional pre-processing stage prior to the initial tour construction stage, as shown in Figure 1.” However, even prompt engineering guides an LLM to make the correct choices by indicating which decisions are more important and how to proceed—it does not involve modifying the input data to achieve this guidance.

Questions for authors
  1. No experiments were provided to solve the confusion regarding the aforementioned weakness.
  2. Traditional non-learning methods include not only very basic approaches like Nearest and Farthest, but also methods that introduce perturbations into the strategy. They don’t always stick to a single path—so what would happen if you applied your method to them?
  3. The method described in this paper adopts a parameterized approach that incorporates the prior knowledge of traditional algorithms. Under these circumstances, if most of the decisions made by the traditional algorithm are already reasonably sound, the network may only need to drive changes in a few key decisions, rather than precisely determining the visit order of all nodes. However, what if the traditional method simply cannot reach the optimal solution—if it is far from the optimal solution and no amount of data adjustment can fix it? Does such a scenario exist? In that case, this is essentially a form of fine-tuning—how would it converge?
  4. Furthermore, different coordinate modifications may yield the same path; therefore, there may not be a single exact solution for a valid modification. This is why this design may be easier to learn, but it is not a strict, universal guarantee. Modifying the coordinates of all nodes remains a high-dimensional problem; many modifications may change nothing at all, or they may severely disrupt the constructor’s judgment. Whether good modifications are easily selected depends on the distribution of modifications, the algorithm’s sensitivity, and the training design—all of which affect the method’s generalization ability. So how can this be addressed?

If the author can clearly explain why the design focuses on changing the input rather than changing selection preferences, I would consider raising my score.

Reviewer_z1HhOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TSP-MDF, a framework that learns to perturb TSP node coordinates so that deterministic construction heuristics can generate diverse candidate tours. The instance modifier is trained without ground-truth solutions using reinforcement learning and self-imitation. Experiments on synthetic and TSPLib benchmarks show consistent improvements over Nearest and Farthest Insertion.

Critical strengths

S1. Simple and practical framework.

Perturbing input coordinates to obtain diverse tours from deterministic heuristics is intuitive and easy to integrate, requiring neither ground-truth labels nor modifications to the base solver.

S2. Efficient training and consistent improvements.

Training takes only a few minutes on TSP-500/1000 using a single GPU. The method consistently improves both insertion heuristics across synthetic and TSPLib benchmarks, with useful ablation studies.

Critical weaknesses

W1. Weak baselines and unclear novelty.

The random baseline in Table 3 produces severely distorted instances, suggesting poorly calibrated perturbations. Without stronger training-free baselines, such as tuned small/sparse random perturbations or randomized insertion, it is unclear how much the learned GNN contributes. Moreover, perturbing TSP instances to escape local optima has been studied previously (Codenotti et al., 1996; Charon & Hudry, 1993, 2000), but these works are not discussed.

W2. Limited generality and computational comparisons.

Separate models are trained for each problem scale, and only two closely related insertion heuristics are evaluated. Furthermore, the method uses approximately 3,000 heuristic evaluations per instance, but lacks wall-clock-matched comparisons against simpler alternatives such as multi-start insertion with 2-opt.

Questions for authors

Q1. Under the same sampling or runtime budget, how does TSP-MDF compare with tuned small/sparse random perturbations, randomized insertion, and multi-start insertion with 2-opt?

Q2. What distinguishes TSP-MDF from classical instance perturbation methods (e.g., Codenotti et al., 1996; Charon & Hudry, 2000)? Can a model trained on one scale or heuristic generalize to others without retraining?

Reference

  • Codenotti B, Manzini G, Margara L, et al. Perturbation: An efficient technique for the solution of very large instances of the Euclidean TSP[J]. INFORMS Journal on Computing, 1996, 8(2): 125-133.
  • Charon I, Hudry O. The noising method: a new method for combinatorial optimization[J]. Operations Research Letters, 1993, 14(3): 133-137.
  • Charon I, Hudry O. Application of the noising method to the travelling salesman problem[J]. European Journal of Operational Research, 2000, 125(2): 266-277.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.