Pith. sign in

REVIEW 3 major objections 6 minor 45 references

Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that adding a dynamically updated backbone frequency and a multi-armed bandit metric selector to LKH improves its ability to find optimal TSP tours, and that the same mechanism improves LKH-3 on CTSP and CVRPTW.

desk verdict Solid incremental TSP results undermined by a broken CTSP table that sinks the LKH-3 generalization claim. read the letter →

arxiv 2501.04072 v1 pith:3YAIUGVJ submitted 2025-01-07 cs.DS cs.AI

Long Wang , Jiongzhi Zheng , Zhengda Xiong , Kun He This is my paper · ORCID
classification cs.DScs.AI MSC 90C2790C59
keywords travelingsalesmanproblemLin-Kernighan-Helsgaunalgorithmmulti-armedbanditbackboneinformationlocalsearchvehicleroutingcoloredTSPcapacitatedVRPwithtimewindows
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Traveling salesman heuristics live or die by which edges they consider promising. LKH ranks candidate edges by the alpha-value, a fixed, globally computed measure, and the paper argues that this single fixed guide gets stuck in local optima. The paper claims that supplementing alpha with raw distance and a dynamically updated backbone frequency, the fraction of past local optima containing each edge, lets the search escape more often. A multi-armed bandit chooses, trial by trial, how to weight the three signals, and the resulting algorithm finds known optimal tours more often and in fewer trials than LKH on many instances with 500 to 85,900 cities. The same recipe inside LKH-3 is claimed to improve two routing variants, Colored TSP and Capacitated VRP with Time Windows.

What carries the argument

The object that carries the argument is the $\alpha bd_w$ evaluation metric, a normalized weighted sum of the $\alpha$-value and the $bd$-value, where $bd$ multiplies edge distance by $(1-b_{ij})$. The multi-armed bandit is the selector: at trial $t$ it picks arm $A_t$ with weight $w_{A_t}$, applies a discount $\gamma^{t-b_s}$ to gradually raise backbone influence, re-sorts each city's candidate set by $\alpha bd_w$, and runs the standard LinKernighan trial; the reward measures how much closer the resulting local optimum came to the lower bound. This mechanism turns accumulated search history into a changing guide for future candidate-edge choices.

What would settle it

On a hard TSP instance with a known optimum, record after the first 100 trials how many of the 100 most frequent backbone edges actually belong to the optimal tour. If that count is no higher than the count for a random edge sample, the backbone signal is uninformative and the claimed improvement must come from the bandit's metric diversity alone.

Watch

Extended reading notes

Core claim

The central discovery is that historical edge popularity, pseudo-backbone information extracted for free from the solver's own local optima, can be folded into LKH's candidate-edge ordering in a way that helps rather than hurts. The paper defines $b_{ij}=\eta_{ij}/t$, the fraction of completed trials in which edge $(i,j)$ appeared in a local optimum, combines it with distance into $bd(i,j)=(1-b_{ij})d(i,j)$, then normalizes and blends this with the $\alpha$-value through a weight $w$ to get the $\alpha bd_w$-value. Instead of committing to one $w$, the algorithm maintains a UCB bandit whose arms are different $w$ values; after each trial it rewards the chosen arm according to how much closer the local optimum came to the lower bound. A discount factor $\gamma^{t-b_s}$ gradually raises the backbone's influence as trials accumulate. The paper's experiments are presented as showing that this adaptive reordering of candidate edges, with no change to the underlying $k$-opt operator, improves solution quality and reduces trials-to-optimum compared with LKH, and that the same mechanism improves LKH-3 on the two tested routing variants.

Load-bearing premise

The load-bearing premise is that edges appearing often in the solver's own past local optima are genuinely better edges, and that the fixed schedule for trusting them more over time helps instead of misleads.

Editorial extensions

If this is right

  • LKH's candidate-order mechanism can be made adaptive without altering the $k$-opt core, so any LK-family solver could adopt the same bandit-plus-backbone wrapper.
  • On instances where LKH already finds the optimum, MABB-LKH typically reaches it in fewer trials, so the practical gain is time-to-optimum as well as success rate on hard instances.
  • The extension to LKH-3 implies the method transfers to constrained and vehicle-routing problems that are solved by transformation to constrained TSP.
  • The ablation results imply that no single hand-tuned weighting of alpha, distance, and backbone dominates; the bandit's dynamic choice is what provides the gain.
  • Because the backbone needs roughly 100 trials to accumulate, the benefit is small on very short runs and grows with instance size, consistent with the paper's observation that the cumulative gap widens on larger instances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The reward in Equation (6) depends on the quality of the lower bound $L(T)$; on problem families with weak lower bounds, such as some asymmetric or non-metric instances, the bandit's reward signal would be noisier, so the method's transfer may be less smooth than the two tested VRP variants suggest.
  • A direct test of the backbone hypothesis would compare MABB-LKH against a version using an oracle edge frequency derived from the known optimal tour; the gap between the two would quantify how much headroom remains in the pseudo-backbone extraction.
  • The fixed geometric discount schedule $\gamma^{t-b_s}$ is a modelling choice; an adaptive schedule driven by the bandit's own confidence could make the method robust to instances where backbone information is slow to stabilize.
  • Because the method only re-orders candidate edges, it could be composed with learned candidate-edge generators rather than viewed as an alternative: the backbone and bandit would then guide a smaller, pre-filtered candidate set.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes MABB-LKH, an extension of the Lin-Kernighan-Helsgaun heuristic for TSP. The method maintains pseudo-backbone edge frequencies computed from its own historical local optima, combines them with alpha-values and distances through a weighted metric alpha_bd_w, and uses a UCB-based multi-armed bandit to select the combination weight in each trial. The same machinery is applied to LKH-3, yielding MABB-LKH-3, and is tested on CTSP and CVRPTW. The paper reports that MABB-LKH improves over LKH on 45 TSPLIB instances and over NeuroLKH on instances up to 6,000 cities, and that MABB-LKH-3 improves over LKH-3 on many CTSP and CVRPTW benchmarks, with an ablation study attributing part of the gain to the bandit mechanism.

Significance. If the reported results are taken at face value, the contribution is practically useful: it obtains state-of-the-art-quality TSP solutions with a lightweight, training-free mechanism that reuses search statistics, and the same recipe is plausibly portable to other LKH-3 solvable problems. The strengths include a broad TSP testbed (45 instances, ten runs each), a public code link, and an ablation study that isolates the MAB component. However, the central generalization claim to LKH-3 rests on a CTSP table that is internally inconsistent, and the experimental protocol leaves open a tuning-on-test-set explanation. These issues are load-bearing and must be resolved before the claims can be accepted.

major comments (3)
  1. [Section 5.4, Table 5] The CTSP results in Table 5 are internally inconsistent and cannot support the claimed comparison. In the small-instance block, the MABB-LKH-3 column is a cyclic shift of the LKH-3 column: e.g., eil21-2 reports MABB-LKH-3 Best 726813, which is exactly the LKH-3 Best for eil101-4, and eil31-4 reports MABB-LKH-3 Best 144918, which is exactly the LKH-3 Best for eil21-2; the pattern continues through eil101-7. In the large-instance block, entries such as fnl2461_3 (MABB-LKH-3 Best 64,074,850 vs LKH-3 Best 105,477) differ by orders of magnitude. The text's summary that MABB-LKH-3 is 'better in 25, worse in 11' instances cannot be derived from the printed numbers. Because the LKH-3/CTSP generalization is a stated central contribution, this table must be corrected or that claim removed before the paper can be evaluated.
  2. [Section 5.1.1, Table 1] The hyperparameters bs, m, s, c, and gamma were tuned with SMAC3, but the manuscript does not state which instances were used for tuning. If the same TSPLIB, CTSP, and CVRPTW instances used in Tables 2-13 were used for tuning, then the reported comparisons are partly in-sample and the observed advantages may reflect parameter fitting rather than algorithmic merit. Please report the exact tuning protocol, including the instance sets and budget, and provide validation on held-out instances or a nested evaluation.
  3. [Section 5.4, Tables 6-13] The CVRPTW comparison aggregates results over groups of instances and over 10 runs without reporting standard deviations, per-instance counts, or significance tests. Several claimed improvements are small enough to be within run-to-run variation; for example, Table 8 R1 improves only from 11750.58 to 11737.58 (about 0.11%), and Table 10 C1 improves from 7289.88 to 7264.20 (about 0.35%). The global statement of 'significant improvement' is not statistically supported without this information. Please provide per-instance results with variance estimates or appropriate significance tests.
minor comments (6)
  1. [Abstract and keywords] 'Lin-Kernighan-Helsguan' should be 'Lin-Kernighan-Helsgaun'.
  2. [Section 5.4, first paragraph] The sentence 'The comparison results between MABB-LKH with LKH-3' should read 'MABB-LKH-3 with LKH-3'.
  3. [Tables 6-13 captions] The captions repeatedly say 'Solomom'; this should be 'Solomon'.
  4. [Figure 2] The x-axis instance order mixes different sizes, and the cumulative-gap curves are hard to distinguish for the smaller instances. Sorting by instance size and using distinct markers would improve readability.
  5. [Algorithm 1, line 14] The notation w_A_t is not defined explicitly; please state that w_A_t is the weight associated with the arm selected at trial t.
  6. [Equation (7)] The indexing V_t^i overloads the trial subscript and the arm superscript; clarifying the time-step and arm indices would avoid ambiguity.

Circularity Check

1 steps flagged · score 6.0 of 10

The CTSP comparison in Table 5 is internally inconsistent: the MABB-LKH-3 Best column is a shifted copy of the LKH-3 Best column, so the claimed generalization to LKH-3 reduces to relabeling the baseline's own results.

  1. renaming known result [Table 5 (rows eil21-2, eil31-4, eil101-4), Section 5.4]
    "eil31-4 315964 315964.0 4.0 0.00 144918 144918.0 1.0 0.00 eil21-2 144918 144918.0 1.0 0.00 726813 726813.0 92.0 0.02 eil101-4 726813 726813.0 41.0 0.01"

    In the 20-row small CTSP block, every MABB-LKH-3 Best value is exactly the LKH-3 Best value of a different row: eil21-2 MABB = 726813 equals LKH-3 eil101-4 (726813), and eil31-4 MABB = 144918 equals LKH-3 eil21-2 (144918); the whole block is a cyclic shift of the baseline column. The claimed 'significant improvement' over LKH-3 is therefore not an independent measurement; the reported new-algorithm result is, by construction, the baseline's own result relabeled, so the improvement claim reduces to a column shift rather than to a derived prediction.

full rationale

The algorithmic core (Eqs. 2-7 and Algorithm 1) is not circular: the backbone frequency b_ij is defined from the algorithm's own historical local optima, the combined metric is a weighted sum of alpha, distance, and b_ij, and the MAB reward is based on solution quality; none of these quantities is the target result itself, and the alpha-value comes from standard 1-tree theory. The self-citations [22,34] supply only the UCB selection mechanism and a comparison baseline, so they are not load-bearing. Five hyperparameters were tuned with SMAC3 (Table 1), and no train/test split is reported; this is an overfitting risk, but not a demonstrated circular reduction. The one concrete reduction is in Table 5: in the small CTSP block the MABB-LKH-3 Best column is a cyclic shift of the LKH-3 Best column (eil21-2 MABB = 726813 equals LKH-3 eil101-4; eil31-4 MABB = 144918 equals LKH-3 eil21-2). Hence the reported 'better in 25, worse in 11' summary cannot be derived from the printed numbers, and the central claim of generalization to LKH-3 on CTSP rests on a relabeled baseline. This is a construction-level equivalence in the evidence for a central claim, so the circularity score is 6.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claim depends on four heuristic assumptions and five tuned hyperparameters. The pseudo-backbone statistic is an aggregate of the algorithm's own history, not an external ground truth, so the method's validity is empirical. No new physical or mathematical entity is introduced.

free parameters (5)
  • bs = 100
    Number of warm-up trials before backbone and MAB are used; tuned by SMAC3 over {50,100,200,500}.
  • m = 5
    Number of MAB arms (weight levels); tuned over {3,4,5,6,7}.
  • s = 0.06
    MAB step size for updating arm values; tuned over {0.01,...,0.1}.
  • c = 20
    UCB exploration bias; tuned over {0.5,...,50}.
  • gamma = 0.998
    Weight discount factor that increases backbone influence over trials; tuned over {0.995,...,0.999}.
assumptions (5)
  • domain assumption Edges appearing more frequently in historical local optima are more likely to be in the optimal tour (pseudo-backbone assumption).
    Section 4.1, Eq. 2; no formal justification, core to the bd-value.
  • ad hoc to paper Normalized linear combination of alpha and bd values preserves a useful candidate-edge ordering.
    Section 4.2, Eq. 4; the weight is chosen by bandit, no theory.
  • ad hoc to paper The reward in Eq. 6 is a suitable credit assignment for the chosen arm within one trial.
    Section 4.3.2; relies on local optimum quality and lower bound L(T).
  • ad hoc to paper Backbone information becomes more valuable as trials accumulate, so discounting alpha's weight exponentially is beneficial.
    Section 4.4, Algorithm 1 line 14; asserted, not demonstrated beyond ablation.
  • domain assumption The alpha-value candidate set machinery from LKH is a valid base for candidate edge selection.
    Inherited from Helsgaun 2000; the paper does not re-derive it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems." pith.science (2026). https://pith.science/paper/3YAIUGVJ

@misc{pith2026250104072,
  author       = {Pith},
  title        = {Pith review of: Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3YAIUGVJ}},
  note         = {Machine review of arXiv:2501.04072}
}
abstract

The Lin-Kernighan-Helsguan (LKH) heuristic is a classic local search algorithm for the Traveling Salesman Problem (TSP). LKH introduces an $\alpha$-value to replace the traditional distance metric for evaluating the edge quality, which leads to a significant improvement. However, we observe that the $\alpha$-value does not make full use of the historical information during the search, and single guiding information often makes LKH hard to escape from some local optima. To address the above issues, we propose a novel way to extract backbone information during the TSP local search process, which is dynamic and can be updated once a local optimal solution is found. We further propose to combine backbone information, $\alpha$-value, and distance to evaluate the edge quality so as to guide the search. Moreover, we abstract their different combinations to arms in a multi-armed bandit (MAB) and use an MAB model to help the algorithm select an appropriate evaluation metric dynamically. Both the backbone information and MAB can provide diverse guiding information and learn from the search history to suggest the best metric. We apply our methods to LKH and LKH-3, which is an extension version of LKH that can be used to solve about 40 variant problems of TSP and Vehicle Routing Problem (VRP). Extensive experiments show the excellent performance and generalization capability of our proposed method, significantly improving LKH for TSP and LKH-3 for two representative TSP and VRP variants, the Colored TSP (CTSP) and Capacitated VRP with Time Windows (CVRPTW).

Figures

Figures reproduced from arXiv: 2501.04072 by the authors.

Figure 1
Figure 1. Examples of sequential and non-sequential 𝑘-opt moves. The non-sequential move combines two distinct infeasible 𝑘-opt moves to form a feasible tour, as shown in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Comparison of MABB-LKH to its variants and LKH. appropriate guiding information and jump out of the local optima. The performance of each algorithm with a single metric is similar and not as ideal, indicating that designing a wonderful evaluation metric empirically is very hard, and our proposed MAB model suggests a way of using learning￾based methods to assist local search algorithms. Results in [PITH_FULL_IMAGE:f… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 43 canonical work pages

  1. [1]

    The truck dispatching problem

    George B Dantzig and John H Ramser. The truck dispatching problem. Management Science, 6(1):80–91, 1959

    1959

  2. [2]

    Braun and Joachim M

    Mikio L. Braun and Joachim M. Buhmann. The noisy euclidean traveling salesman problem and learning. In Advances in Neural Information Processing Systems 14, pages 351–358, 2001

    work page 2001

  3. [3]

    Reinforcementlearningforsolvingthevehiclerouting problem

    MohammadRezaNazari,AfshinOroojlooy,LawrenceV.Snyder,and MartinTakác. Reinforcementlearningforsolvingthevehiclerouting problem. InAdvances in Neural Information Processing Systems 31, pages 9861–9871, 2018

    work page 2018

  4. [4]

    Deepreinforcementlearningforsolvingthehet- erogeneous capacitated vehicle routing problem.IEEE Transactions on Cybernetics, 52(12):13572–13585, 2022

    JingwenLi,YiningMa,RuizeGao,ZhiguangCao,AndrewLim,Wen Song,andJieZhang. Deepreinforcementlearningforsolvingthehet- erogeneous capacitated vehicle routing problem.IEEE Transactions on Cybernetics, 52(12):13572–13585, 2022

    work page 2022

  5. [5]

    The pollution traveling salesmanproblemwithrefueling

    Angelo Sifaleras Panagiotis Karakostas. The pollution traveling salesmanproblemwithrefueling. Computers&OperationsResearch , 167:106661, 2024

    work page 2024

  6. [6]

    Arrival and service time dependencies in the single-and multi-visit selective traveling salesman problem.Computers & Operations Research, 166:106632, 2024

    Gilbert Laporte David Canca, Eva Barrena. Arrival and service time dependencies in the single-and multi-visit selective traveling salesman problem.Computers & Operations Research, 166:106632, 2024

    work page 2024

  7. [7]

    A hybrid genetic algo- rithm for the min–max multiple traveling salesman problem.Com- puters & Operations Research, 162:106455, 2024

    Changhyun Kwon Sasan Mahmoudinazlou. A hybrid genetic algo- rithm for the min–max multiple traveling salesman problem.Com- puters & Operations Research, 162:106455, 2024

    work page 2024

  8. [8]

    Qinghua Wu Yongliang Lu, Una Benlic. A population algorithm based on randomized tabu thresholding for the multi-commodity pickup-and-delivery traveling salesman problem.Computers & Op- erations Research, 101:285–297, 2019

    work page 2019

Show all 45 references
  1. [9]

    An effective implementation of the Lin–Kernighan traveling salesman heuristic.European Journal of Operational Re- search, 126(1):106–130, 2000

    Keld Helsgaun. An effective implementation of the Lin–Kernighan traveling salesman heuristic.European Journal of Operational Re- search, 126(1):106–130, 2000

    2000

  2. [10]

    A powerful genetic al- gorithm using edge assembly crossover for the traveling salesman problem

    Yuichi Nagata and Shigenobu Kobayashi. A powerful genetic al- gorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2):346–363, 2013

    2013

  3. [11]

    Lin and B

    S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498–516, 1973

    1973

  4. [12]

    Ejection chains, reference structures and alternating path methods for traveling salesman problems

    Fred Glover. Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Applied Mathematics, 65(1-3):223–253, 1996

    1996

  5. [13]

    Computersolutionsofthetravelingsalesmanproblem

    ShenLin. Computersolutionsofthetravelingsalesmanproblem. Bell System Technical Journal, 44(10):2245–2269, 1965

    1965

  6. [14]

    Traveling salesman problem heuristics: Leading methods, imple- mentations and latest advances

    Cesar Rego, Dorabela Gamboa, Fred Glover, and Colin Osterman. Traveling salesman problem heuristics: Leading methods, imple- mentations and latest advances. European Journal of Operational Research, 211(3):427–441, 2011. Wang et al.: Preprint submitted to Elsevier Page 13 of 1...

    2011

  7. [15]

    General k-opt submoves for the Lin–Kernighan TSPheuristic

    Keld Helsgaun. General k-opt submoves for the Lin–Kernighan TSPheuristic. MathematicalProgrammingComputation ,1:119–163, 2009

    2009

  8. [16]

    Thetraveling-salesmanproblem and minimum spanning trees

    MichaelHeldandRichardM.Karp. Thetraveling-salesmanproblem and minimum spanning trees. Operations Research, 18(6):1138– 1162, 1970

    1970

  9. [17]

    The symmetric traveling salesman problem and edge exchanges in minimal 1-trees.European Journal of Operational Research, 12(4):394–403, 1983

    Ton Volgenant and Roy Jonker. The symmetric traveling salesman problem and edge exchanges in minimal 1-trees.European Journal of Operational Research, 12(4):394–403, 1983

    1983

  10. [18]

    A novel local search algorithm for the traveling salesman problem that exploits backbones

    Weixiong Zhang and Moshe Looks. A novel local search algorithm for the traveling salesman problem that exploits backbones. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 343–384, 2005

    2005

  11. [19]

    Introduction to multi-armed bandits.Founda- tions and Trends in Machine Learning, 12(1-2):1–286, 2019

    Aleksandrs Slivkins. Introduction to multi-armed bandits.Founda- tions and Trends in Machine Learning, 12(1-2):1–286, 2019

    2019

  12. [20]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit algorithms. Cambridge University Press, 2020

    2020

  13. [21]

    Study of genetic algorithm with reinforcement learning to solve the TSP.Expert Systems with Ap- plications, 36(3):6995–7001, 2009

    Fei Liu and Guangzhou Zeng. Study of genetic algorithm with reinforcement learning to solve the TSP.Expert Systems with Ap- plications, 36(3):6995–7001, 2009

    2009

  14. [22]

    BandMaxSAT: A local search MaxSAT solver with multi-armed bandit

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Li, and Felip Manyà. BandMaxSAT: A local search MaxSAT solver with multi-armed bandit. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, pages 1901–1907, 2022

    1901

  15. [23]

    An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing prob- lems

    Keld Helsgaun. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing prob- lems. Roskilde: Roskilde University, 12, 2017

    2017

  16. [24]

    Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song

    Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems 30, pages 6348–6358, 2017

    2017

  17. [25]

    In Advances in Neural Information Processing Systems 28, pages 2692–2700, 2015

    OriolVinyals,MeireFortunato,andNavdeepJaitly.Pointernetworks. In Advances in Neural Information Processing Systems 28, pages 2692–2700, 2015

    2015

  18. [26]

    Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem

    Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 8132–8140, 2023

    2023

  19. [27]

    Le, Mohammad Norouzi, and SamyBengio

    Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and SamyBengio. Neuralcombinatorialoptimizationwithreinforcement learning. In Proceedings of the 5th International Conference on Learning Representations, 2017

    2017

  20. [28]

    H-TSP: Hierarchically solving the large-scale travellingsalesmanproblem

    XuanhaoPan,YanJin,YuandongDing,MingxiaoFeng,LiZhao,Lei Song, and Jiang Bian. H-TSP: Hierarchically solving the large-scale travellingsalesmanproblem. arXivpreprintarXiv:2304.09395 ,2023

    2023 arXiv

  21. [29]

    Marcelo O. R. Prates, Pedro H. C. Avelar, Henrique Lemos, Luís C. Lamb,andMosheY.Vardi.LearningtosolveNP-completeproblems: AgraphneuralnetworkfordecisionTSP. In Proceedingsofthe33rd AAAI Conference on Artificial Intelligence, pages 4731–4738, 2019

    2019

  22. [30]

    Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning

    Paulo R d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. InProceedings of the 12th Asian Conference on Machine Learning, pages 465–480. PMLR, 2020

    2020

  23. [31]

    Learningtosearch feasible and infeasible regions of routing problems with flexible neural k-opt

    YiningMa,ZhiguangCao,andYeowMengChee. Learningtosearch feasible and infeasible regions of routing problems with flexible neural k-opt. InAdvances in Neural Information Processing Systems 36, 2024

    2024

  24. [32]

    GLOP:Learningglobalpartitionandlocalconstruction for solving large-scale routing problems in real-time.arXiv preprint arXiv, 2312:08224, 2023

    Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and FanzhangLi. GLOP:Learningglobalpartitionandlocalconstruction for solving large-scale routing problems in real-time.arXiv preprint arXiv, 2312:08224, 2023

    2023

  25. [33]

    NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem

    Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem. InAdvances in Neural Information Processing Systems 34, pages 7472–7483, 2021

    2021

  26. [34]

    CombiningreinforcementlearningwithLin-Kernighan-Helsgaun algorithm for the traveling salesman problem

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. CombiningreinforcementlearningwithLin-Kernighan-Helsgaun algorithm for the traveling salesman problem. InProceedings of the 35thAAAIConferenceonArtificialIntelligence ,pages12445–12452, 2021

    2021

  27. [35]

    A backbone-search heuristic for efficient solving of hard 3-SAT formulae

    Olivier Dubois and Gilles Dequen. A backbone-search heuristic for efficient solving of hard 3-SAT formulae. InProceedings of the 17th International Joint Conference on Artificial Intelligence, pages 248– 253, 2001

    2001

  28. [36]

    Configuration landscape analysis and backbone guidedlocalsearch.:PartI:Satisfiabilityandmaximumsatisfiability

    Weixiong Zhang. Configuration landscape analysis and backbone guidedlocalsearch.:PartI:Satisfiabilityandmaximumsatisfiability. Artificial Intelligence, 158(1):1–26, 2004

    2004

  29. [37]

    Transforming asymmetric into sym- metric traveling salesman problems: Erratum.Operations Research Letters, 5(4):215–216, 1986

    Roy Jonker and Ton Volgenant. Transforming asymmetric into sym- metric traveling salesman problems: Erratum.Operations Research Letters, 5(4):215–216, 1986

    1986

  30. [38]

    Technicalnote—anoteonthemultipletravelingsalesmen problem

    M.R.Rao. Technicalnote—anoteonthemultipletravelingsalesmen problem. Operations Research, 28(3-part-i):628–632, 1980

    1980

  31. [39]

    Thetraveling-salesmanproblem and minimum spanning trees: Part II.Mathematical Programming, 1(1):6–25, 1971

    MichaelHeldandRichardM.Karp. Thetraveling-salesmanproblem and minimum spanning trees: Part II.Mathematical Programming, 1(1):6–25, 1971

    1971

  32. [40]

    Cascaded algorithm-selection and hyper-parameter optimization with extreme-region upper confi- dence bound bandit

    Yi-Qi Hu, Yang Yu, and Jun-Da Liao. Cascaded algorithm-selection and hyper-parameter optimization with extreme-region upper confi- dence bound bandit. InProceedings of the 28th International Joint Conference on Artificial Intelligence, pages 2528–2534, 2019

    2019

  33. [41]

    SMAC3: A versatile bayesian optimization packageforhyperparameteroptimization

    Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. SMAC3: A versatile bayesian optimization packageforhyperparameteroptimization. JournalofMachineLearn- ing Research, 23(54):1–9, 2022

    2022

  34. [42]

    Iterated two-phase local search for the colored traveling salesmen problem.Engineering Applications of Artificial Intelligence, 97:104018, 2021

    Pengfei He and Jin-Kao Hao. Iterated two-phase local search for the colored traveling salesmen problem.Engineering Applications of Artificial Intelligence, 97:104018, 2021

    2021

  35. [43]

    PengfeiHe,Jin-KaoHao,andQinghuaWu.Groupingmemeticsearch for the colored traveling salesmen problem.Information Sciences, 570:689–707, 2021

    2021

  36. [44]

    Algorithmsforthevehicleroutingandschedul- ing problems with time window constraints.Operations Research, 35(2):254–265, 1987

    MariusM.Solomon. Algorithmsforthevehicleroutingandschedul- ing problems with time window constraints.Operations Research, 35(2):254–265, 1987

    1987

  37. [45]

    A parallel hybrid evolution- arymetaheuristicforthevehicleroutingproblemwithtimewindows

    Hermann Gehring and Jörg Homberger. A parallel hybrid evolution- arymetaheuristicforthevehicleroutingproblemwithtimewindows. In Proceedings of EUROGEN99, volume 2, pages 57–64, 1999. Wang et al.: Preprint submitted to Elsevier Page 14 of 14

    1999

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.