Pith. sign in

REVIEW 3 major objections 5 minor 87 references

A Comparative Review of Parallel Exact, Heuristic, Metaheuristic, and Hybrid Optimization Techniques for the Traveling Salesman Problem

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This review claims its two new metrics, HIR and ASI, make hybrid and traditional parallel TSP solvers comparable, and concludes that hybrid, GPU-accelerated methods best balance efficiency and accuracy at scale.

desk verdict The survey half is a competent, useful summary of parallel TSP methods, but the only original contribution—the proposed metrics, especially ASI—is mathematically unsound and unvalidated; still, the review deserves referee time to force a fix or a cut. read the letter →

arxiv 2505.18278 v1 pith:VST3A5VJ submitted 2025-05-23 cs.DC

Rabab Alkhalifa , Fatima Alkhomayes , Boushra Almazroua , Dana Alhaidan , Maryam Alothman , Jumana Almuhaidib This is my paper
classification cs.DC MSC 90C2768W1090C59
keywords TravelingSalesmanProblemparallelcomputingmetaheuristicshybridalgorithmsGPUaccelerationevaluationmetricsmachinelearningforoptimizationquantum-inspired
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

Parallel solvers for the Traveling Salesman Problem are usually compared inside their own paradigm, so exact, heuristic, and hybrid approaches lack a common yardstick. This review tries to supply one: it surveys the field and proposes two new metrics, the Hybrid Integration Ratio and the Algorithmic Synergy Index, meant to quantify what a hybrid solver adds over its own components. Its substantive finding is that hybrid metaheuristics, especially GPU-accelerated ones, offer the most practical balance between efficiency and accuracy for large instances, while exact algorithms remain confined to small and medium problems. A reader should care because TSP underpins logistics, routing, and scheduling, and a fair way to compare solvers is a prerequisite for reproducible progress in that space.

What carries the argument

The load-bearing objects are the two proposed metrics. HIR, the Hybrid Integration Ratio, is defined as $$HIR = \frac{Q_{\text{hybrid}} - Q_{\text{best-standalone}}}{Q_{\text{best-standalone}}}\times 100,$$ the percentage gain of a hybrid over its strongest component. ASI, the Algorithmic Synergy Index, is defined as $$ASI = \frac{P_{\text{hybrid}}}{\sum_{i=1}^n P_{\text{individual }i}},$$ the ratio of hybrid performance to the arithmetic sum of its components' performances, with the threshold 1 separating synergy from redundancy. These metrics are what the paper claims make cross-paradigm comparison possible; the rest of the review is a structured survey of exact, heuristic/metaheuristic, and hybrid/emerging approaches, organized so that the metrics and the comparative conclusion have somewhere to land.

What would settle it

Apply Eq. 14 to a documented hybrid that beats every one of its components: with percentage-based qualities the denominator is the sum of the component percentages, so a hybrid at 99% with components at 60% and 50% gives $ASI \approx 0.90$, which the paper classifies as a redundant or ineffective combination. A single such counterexample among the hybrids the paper itself cites as successes shows the index does not measure what it claims.

Watch

Extended reading notes

Core claim

The paper's central claim is that the field of parallel TSP optimization lacks consistent benchmarks and evaluation metrics, and that its proposed measures fill that gap. The Hybrid Integration Ratio (HIR, Eq. 13) reports, as a percentage, how much better a hybrid solver's solution quality is than the best of its standalone components; the Algorithmic Synergy Index (ASI, Eq. 14) divides the hybrid's performance by the sum of its components' individual performances, so values above 1 indicate genuine synergy and values below 1 indicate a redundant combination. On the strength of the surveyed evidence - parallel branch-and-bound reaching only modest speedups, GPU-accelerated genetic and ant-colony hybrids reporting 40-fold speedups and over 80% parallel efficiency - the review concludes that hybrid and hardware-accelerated methods offer the most practical balance of efficiency and accuracy for large-scale TSP optimization, and that machine-learning-guided and quantum-inspired solvers are promising but not yet mature enough for routine use.

Load-bearing premise

The Algorithmic Synergy Index assumes that a hybrid's performance can be compared with the plain arithmetic sum of its components' performances, but percentages of optimality and speedups are not additive quantities, so the index can label a clearly superior hybrid as ineffective whenever the denominator exceeds the numerator.

Editorial extensions

If this is right

  • If HIR and ASI are adopted, hybrid solver papers can report a single quantitative statement of added value over components instead of ad-hoc comparisons.
  • The review's conclusion redirects practical effort toward hybrid, GPU-accelerated solvers for large-scale TSPs, reserving exact algorithms for small-to-medium instances where optimality is required.
  • Adopting the paper's reporting standard (execution time, speedup, scalability, optimality gap, memory use, parallel efficiency) would make published TSP results reproducible across paradigms.
  • The review's research-gap analysis implies that ML-guided and quantum-inspired solvers need dedicated small-to-medium benchmarks before they can be compared fairly with classical heuristics.
  • HIR and ASI give future work a quantitative language for the claim that a hybrid is more than the sum of its parts, a phrase the field currently uses informally.

Reading between the lines

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

  • The ASI denominator assumes component performances add like lengths, which percentage-based quality and speedup do not; a hybrid scoring 99% over components at 60% and 50% would get $ASI \approx 0.90$ and be classified as redundant despite clearly outperforming every component. A ratio-based or geometric alternative would avoid this artifact.
  • HIR inherits a subtler bias: it inflates when the standalone components are weak, so the paper's own metric should be reported alongside absolute solution quality and the identity of the best component.
  • The proposed metrics could be validated cheaply by re-computing HIR and ASI from already-published hybrid-versus-component results; no new experiments are needed to test whether the indices track perceived synergy.
  • If the review's benchmarking standards were adopted, meta-analyses across papers on GPU-accelerated hybrids would become feasible, since the field currently lacks even a common reporting vocabulary.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper is a literature review of parallel approaches to the Traveling Salesman Problem, organized around exact methods, heuristics and metaheuristics, hybrids, and emerging ML/quantum techniques. It also introduces a set of proposed evaluation metrics—Heuristic Robustness Index (HRI), Hybrid Integration Ratio (HIR), Algorithmic Synergy Index (ASI), and Local Optima Avoidance Rate (LOAR)—intended to support cross-paradigm comparison of parallel TSP solvers. The review concludes that hybrid and hardware-accelerated methods offer the most practical balance between efficiency and accuracy for large-scale TSP instances, and it identifies open challenges such as load balancing, parameter sensitivity, generalization of learned heuristics, and the lack of standardized benchmarks.

Significance. If the proposed metric framework were sound, Section 4 would provide a useful starting point for comparing heterogeneous TSP solvers, an area the paper correctly identifies as underdeveloped. The review also offers a broad, readable taxonomy of parallel TSP techniques and a reasonable high-level survey of datasets and hybrid designs. However, the paper's only original technical content—the metric framework—is neither validated nor mathematically well-founded. In particular, the Algorithmic Synergy Index (Eq. 14) sums performance measures that are not additive across algorithms, so its interpretation as a synergy measure is uncalibrated and can contradict the qualitative behavior of the hybrid. Because the abstract explicitly advertises the metrics as a contribution, this flaw is load-bearing. The paper contains no experiments, no numerical illustrations, and no reproducible evaluation, and the metric definitions leave important quantities (tour cost vs. accuracy, higher-is-better vs. lower-is-better) unspecified. These issues currently outweigh the useful survey material.

major comments (3)
  1. [Section 4.4.2, Eq. (14)] The Algorithmic Synergy Index is not a meaningful metric for the performance measures the paper suggests. If P is solution quality expressed as a percentage, the denominator is a sum of percentages from independent algorithms, which has no operational interpretation. A hybrid with quality 99 compared against components with qualities 80 and 70 yields ASI = 99/150 = 0.66, i.e., labeled 'redundant or ineffective,' even though the hybrid strictly dominates both components. The same hybrid compared against components with qualities 40 and 30 yields ASI = 99/70 = 1.41, i.e., labeled 'synergistic,' without any change in the hybrid's behavior. Thus the index is uncalibrated and its value depends on the arbitrary choice of constituent algorithms. Since the abstract and Section 4.4 present ASI as a central component of the proposed evaluation framework, this is a load-bearing flaw that must be fixed by redefining or removing the index.
  2. [Section 4.3 and 4.4] The proposed metrics (HRI in Eq. 9, HIR in Eq. 13, ASI in Eq. 14, and LOAR in Section 4.3.3.3) are introduced but never validated, applied to a concrete TSP instance, or compared with existing evaluation practices. No experiments or numerical examples are provided. Furthermore, the definitions do not state whether Q and P denote tour cost (lower is better), optimality gap (lower is better), or accuracy (higher is better). HIR and HRI change their interpretation under these conventions; for example, Eq. (13) is only a meaningful relative improvement measure for higher-is-better quantities. The review's own Section 5 emphasizes the lack of standardized evaluation metrics, but Section 4 does not ground its proposals in any benchmark suite or normative definition. The metric framework therefore remains an unsubstantiated claim.
  3. [Section 4.4.1] The examples used to illustrate HIR mix incompatible performance dimensions. The definition in Eq. (13) is stated in terms of solution quality Q, but the accompanying examples cite a GA–ACO hybrid reaching 99% accuracy and a CUDA-based model achieving speedups exceeding 80%. Speedup is not a solution-quality measure, so using it as evidence for HIR obscures what the metric is intended to quantify. This further underscores the need for a precise, consistent definition of P and Q before any of the proposed indices can be used.
minor comments (5)
  1. [Section 4.1.4] The paragraph beginning 'In parallel exact algorithms, memory is typically distributed across processors...' appears twice verbatim; one copy should be removed.
  2. [Section 3 and Table 2] Table 2 lists the Mona Lisa TSP as having 100,000 cities, while the text in Section 3 says it 'features over 10,000 nodes.' Please reconcile the two values (the actual instance size is 100,000).
  3. [Section 4.1.1, Eq. (1)] The Held-Karp complexity is written as 'T(n) = O(2 n·n2)' due to formatting; it should be O(n^2 · 2^n).
  4. [Section 4.3.1, Eq. (9)] HRI is defined as a normalized mean squared deviation, but the text calls it a 'normalized variance.' Clarify which quantity is intended and explicitly define Q_i and Qbar, including whether higher Q means better quality.
  5. [References] Reference [85] (Hudson et al.) lacks a year and a complete bibliographic record; references [46]/[50] and [47]/[51] duplicate the same datasets and should be unified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the metrics are definitions, and the review's conclusions rest on external literature rather than self-referential derivation.

full rationale

This paper is a literature review whose only original technical content is two proposed evaluation metrics in Section 4.4: HIR (Eq. 13) and ASI (Eq. 14). Neither metric is derived from data, fitted to a subset, or used to 'predict' a quantity that it was constructed from. HIR is explicitly defined as a relative improvement over the best standalone component, and ASI is explicitly defined as a ratio of hybrid performance to the sum of standalone performances. The accompanying interpretive statements ('>1 suggests a synergistic effect', '<1 indicates a redundant or ineffective combination') are definitional glosses on the ratio, not independently derived results. The skeptical objection that ASI is uncalibrated because performance measures are not additive is a correctness/validity concern about metric design, not a circularity concern: the paper does not disguise the additivity assumption as an empirical finding, nor does it fit ASI to data and then claim to predict synergy. No load-bearing self-citations appear: the references cited for cooperative hybrid metaheuristics and heterosis theory (refs. [81,82]) do not overlap with the present authors, and the paper's central conclusions about hybrid and hardware-accelerated solvers are drawn from third-party empirical studies cited throughout the review. There are no fitted parameters, no predictions generated from fitted values, no uniqueness theorems imported from the authors' prior work, and no known empirical pattern renamed as a new result. Accordingly, the derivation chain is self-contained as a review: the proposed metrics are offered as new definitions, and the survey conclusions are supported by external literature rather than by any equation that reduces to its own input.

Assumptions & free parameters 0 free parameters · 3 assumptions · 4 invented entities

The review's central claims rest on the accuracy of the cited literature, the exhaustiveness of its taxonomy, and the correctness of its proposed metrics. The proposed metrics, in turn, require assumptions about comparability and additivity that are not established.

assumptions (3)
  • domain assumption The reported results in the surveyed papers are accurate as summarized.
    The review does not re-run any experiments; it takes speedup and quality numbers from the cited literature at face value (Sections 2 and 5).
  • ad hoc to paper Performance indicators such as solution quality or speedup are additive across algorithm components.
    Used to define Algorithmic Synergy Index (ASI, Eq. 14); this assumption is not stated and is generally false for percentage-based quality or non-linear speedup.
  • domain assumption The taxonomy of methods (exact, heuristic, metaheuristic, hybrid) is exhaustive and non-overlapping.
    The entire comparison structure depends on this categorization, but the paper does not discuss edge cases such as matheuristics in detail.
invented entities (4)
  • Heuristic Robustness Index (HRI)
    purpose: Quantify consistency of heuristic performance across benchmark instances (Eq. 9).
    Defined in the paper but never computed or validated on any data.
  • Hybrid Integration Ratio (HIR)
    purpose: Measure hybrid improvement over best standalone component (Eq. 13).
    Defined but not applied to any experimental results.
  • Algorithmic Synergy Index (ASI)
    purpose: Measure emergent synergy of hybrid algorithms (Eq. 14).
    Defined but not applied; based on the questionable additivity assumption.
  • Local Optima Avoidance Rate (LOAR)
    purpose: Estimate how often a heuristic avoids local optima.
    The paper itself admits LOAR is 'less formally defined' (Section 4.3.3.3).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Comparative Review of Parallel Exact, Heuristic, Metaheuristic, and Hybrid Optimization Techniques for the Traveling Salesman Problem." pith.science (2026). https://pith.science/paper/VST3A5VJ

@misc{pith2026250518278,
  author       = {Pith},
  title        = {Pith review of: A Comparative Review of Parallel Exact, Heuristic, Metaheuristic, and Hybrid Optimization Techniques for the Traveling Salesman Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VST3A5VJ}},
  note         = {Machine review of arXiv:2505.18278}
}
read the original abstract

The Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem with wide-ranging applications in logistics, routing, and intelligent systems. Due to its factorial complexity, solving large-scale instances requires scalable and efficient algorithmic frameworks, often enabled by parallel computing. This literature review provides a comparative evaluation of parallel TSP optimization methods, including exact algorithms, heuristic-based approaches, hybrid metaheuristics, and machine learning-enhanced models. In addition, we introduce task-specific evaluation metrics to facilitate cross-paradigm analysis, particularly for hybrid and adaptive solvers. The review concludes by identifying research gaps and outlining future directions, including deep learning integration, exploring quantum-inspired algorithms, and establishing reproducible evaluation frameworks to support scalable and adaptive TSP optimization in real-world scenarios.

Figures

Figures reproduced from arXiv: 2505.18278 by the authors.

Figure 1
Figure 1. Modeling intercity distances as weighted edges in a complete graph. Example cities across Saudi Arabia serve as [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

87 extracted references · 73 canonical work pages

  1. [1]

    D. L. Applegate, R. E. Bixby, V. Chvatál, W. J. Cook, The Traveling Salesman Problem: A Computa- tional Study, Princeton University Press, 2006. URLhttp://www.jstor.org/stable/j.ctt7s8xg

    2006

  2. [2]

    Applegate, W

    D. Applegate, W. Cook, Concorde tsp solver (2006)

    2006

  3. [3]

    Dahiya, S

    C. Dahiya, S. Sangwan, Literature review on travelling salesman problem, International Journal of Research 5 (16) (2018) 1152–1155

    2018

  4. [4]

    D.Alquaamiz, L.Alothman, N.Aldakheel, R.Althukair, N.Nagy, Parallelizationdynamicprogramming algorithm for traveling salesman problem optimization, International Journal of Computer Science and Information Security (IJCSIS) 22 (3) (2024)

    2024

  5. [5]

    Dell’Amico, R

    M. Dell’Amico, R. Montemanni, S. Novellani, Matheuristic algorithms for the parallel drone scheduling traveling salesman problem, Annals of Operations Research 289 (2020) 211–226

    2020

  6. [6]

    V. V. Burkhovetskiy, B. Y. Steinberg, Parallelizing an exact algorithm for the traveling salesman problem, Procedia Computer Science 119 (2017) 97–102

    2017

  7. [7]

    Tschoke, R

    S. Tschoke, R. Lubling, B. Monien, Solving the traveling salesman problem with a distributed branch- and-bound algorithm on a 1024 processor network, in: Proceedings of 9th International Parallel Pro- cessing Symposium, IEEE, 1995, pp. 182–189

    1995

  8. [8]

    M. W. Al-Neama, I. A. Ahmed, S. M. Ali, A parallel algorithm to find the exact solution of the travelling salesman problem, Indonesian Journal of Electrical Engineering and Computer Science 31 (2) (2023) 917–924

    work page 2023

Show all 87 references
  1. [9]

    Barai, G

    A. Barai, G. Chennupati, N. Santhi, A.-H. A. Badawy, S. Eidenbenz, Modeling shared cache perfor- mance of openmp programs using reuse distance, arXiv preprint arXiv:1907.12666 (2019)

    2019 arXiv

  2. [10]

    C. G. Diderich, M. Gengler, Solving traveling salesman problems using a parallel synchronized branch and bound algorithm, in: H. Liddell, A. Colbrook, B. Hertzberger, P. Sloot (Eds.), High-Performance Computing and Networking, Springer Berlin Heidelberg, Berlin, Heidelberg, 19...

    1996

  3. [11]

    Clausen, Branch and bound algorithms-principles and examples, Department of computer science, University of Copenhagen (1999) 1–30

    J. Clausen, Branch and bound algorithms-principles and examples, Department of computer science, University of Copenhagen (1999) 1–30

    1999

  4. [12]

    Ladányi, T

    L. Ladányi, T. K. Ralphs, L. E. Trotter, Branch, Cut, and Price: Sequential and Parallel, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001, pp. 223–260.doi:10.1007/3-540-45586-8_6. URLhttps://doi.org/10.1007/3-540-45586-8_6

    2001 doi

  5. [13]

    S. J. Maher, T. K. Ralphs, Y. Shinano, Assessing the effectiveness of (parallel) branch-and-bound algorithms, arXiv preprint arXiv:2104.10025 (2021)

    2021 arXiv

  6. [14]

    Gohil, M

    A. Gohil, M. Tayal, T. Sahu, V. Sawalpurkar, Travelling salesman problem: Parallel implementations & analysis, arXiv preprint arXiv:2205.14352 (2022)

    2022 arXiv

  7. [15]

    Rokbani, R

    N. Rokbani, R. Kumar, A. Abraham, A. M. Alimi, H. V. Long, I. Priyadarshini, L. H. Son, Bi-heuristic ant colony optimization-based approaches for traveling salesman problem, Soft Computing 25 (2021) 3775–3794

    2021

  8. [16]

    L. A. da Silveira, J. L. Soncco-Álvarez, T. A. de Lima, M. Ayala-Rincón, Parallel island model genetic algorithms applied in np-hard problems, in: 2019 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2019, pp. 3262–3269. 18

    2019

  9. [17]

    Peng, Parallel genetic algorithm for travelling salesman problem, in: International conference on automation control, algorithm, and intelligent bionics (ACAIB 2022), Vol

    C. Peng, Parallel genetic algorithm for travelling salesman problem, in: International conference on automation control, algorithm, and intelligent bionics (ACAIB 2022), Vol. 12253, SPIE, 2022, pp. 259–267

    2022

  10. [18]

    Abbasi, M

    M. Abbasi, M. Rafiee, et al., Efficient parallelization of a genetic algorithm solution on the traveling salesman problem with multi-core and many-core systems, International Journal of Engineering 33 (7) (2020) 1257–1265

    2020

  11. [19]

    Katiyar, N

    S. Katiyar, N. Ibraheem, A. Q. Ansari, Ant colony optimization: a tutorial review, in: National conference on advances in power and control, 2015, pp. 99–110

    2015

  12. [20]

    Delévacq, P

    A. Delévacq, P. Delisle, M. Gravel, M. Krajecki, Parallel ant colony optimization on graphics processing units, Journal of Parallel and Distributed Computing 73 (1) (2013) 52–61

    2013

  13. [21]

    L. Yang, T. Jiang, R. Cheng, Tensorized ant colony optimization for gpu acceleration, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2024, pp. 755–758

    2024

  14. [22]

    Mavrovouniotis, S

    M. Mavrovouniotis, S. Yang, Evolving neural networks using ant colony optimization with pheromone trail limits, in: 2013 13th UK Workshop on Computational Intelligence (UKCI), IEEE, 2013, pp. 16–23

    2013

  15. [23]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, Optimization by simulated annealing, science 220 (4598) (1983) 671–680

    1983

  16. [24]

    Sonuc, B

    E. Sonuc, B. Sen, S. Bayir, A cooperative gpu-based parallel multistart simulated annealing algorithm for quadratic assignment problem, Engineering science and technology, an international journal 21 (5) (2018) 843–849

    2018

  17. [25]

    Borisenko, S

    A. Borisenko, S. Gorlatch, Parallelizing metaheuristics for optimal design of multiproduct batch plants on gpu, in: International Conference on Parallel Computing Technologies, Springer, 2017, pp. 405–417

    2017

  18. [26]

    de Almeida Dantas, E

    B. de Almeida Dantas, E. N. Cáceres, An experimental evaluation of a parallel simulated annealing ap- proach for the 0–1 multidimensional knapsack problem, Journal of Parallel and Distributed Computing 120 (2018) 211–221

    2018

  19. [27]

    Sere, Application of parallel distributed computing for global optimization with simulated an- nealing, Ph.D

    D.-A. Sere, Application of parallel distributed computing for global optimization with simulated an- nealing, Ph.D. thesis, Medical University of Vienna (2019)

    2019

  20. [28]

    Glover, Tabu search—part i, ORSA Journal on computing 1 (3) (1989) 190–206

    F. Glover, Tabu search—part i, ORSA Journal on computing 1 (3) (1989) 190–206

    1989

  21. [29]

    Talbi, Metaheuristics: from design to implementation, John Wiley & Sons, 2009

    E.-G. Talbi, Metaheuristics: from design to implementation, John Wiley & Sons, 2009

    2009

  22. [30]

    Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics 8 (2002) 541–564

    E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics 8 (2002) 541–564

    2002

  23. [31]

    N. Hou, F. He, Y. Zhou, Y. Chen, An efficient gpu-based parallel tabu search algorithm for hard- ware/software co-design, Frontiers of Computer Science 14 (2020) 1–18

    2020

  24. [32]

    S. D. Ekçişioğlu, P. M. Pardalos, M. G. Resende, Parallel metaheuristics for combinatorial optimization, Models for Parallel and Distributed Computation: Theory, Algorithmic Techniques and Applications (2002) 179–206

    2002

  25. [33]

    T. G. Crainic, J.-Y. Potvin, M. Gendreau, Parallel tabu search, Université de Montréal, Centre de recherche sur les transports, 2005

    2005

  26. [34]

    Dudek-Dyducb, T

    E. Dudek-Dyducb, T. Dyducb, Travelling salesman problem - parallel algorithms, IFAC Proceedings Volumes 28 (10) (1995) 657–662, 7th IFAC Symposium on Large Scale Systems: Theory and Applica- tions 1995, London, UK, 11-13 July, 1995.doi:https://doi.org/10.1016/S1474-6670(17)515...

    1995 doi

  27. [35]

    Soylu, A

    E. Soylu, A. Uysal, A hybrid genetic-ant colony algorithm for travelling salesman problem, International Journal of Engineering Science and Application 1 (3) (2017) 86–90

    2017

  28. [36]

    F. S. Gharehchopogh, I. Maleki, M. Farahmandian, New approach for solving dynamic traveling sales- man problem with hybrid genetic algorithms and ant colony optimization, International Journal of Computer Applications 53 (1) (2012)

    2012

  29. [37]

    Vinyals, M

    O. Vinyals, M. Fortunato, N. Jaitly, Pointer networks, in: C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, R. Garnett (Eds.), Advances in Neural Information Processing Systems, Vol. 28, Curran Associates, Inc., 2015. URLhttps://proceedings.neurips.cc/paper_files/paper/2015/file/ ...

    2015

  30. [38]

    W. Kool, H. van Hoof, M. Welling, Attention, learn to solve routing problems!, in: International Conference on Learning Representations, 2018

    2018

  31. [39]

    C.K.Joshi, T.Laurent, X.Bresson, Anefficientgraphconvolutionalnetworktechniqueforthetravelling salesman problem, arXiv preprint arXiv:1906.01227 (2019)

    2019 arXiv

  32. [40]

    L. Xin, W. Song, Z. Cao, J. Zhang, NeuroLKH: Combining deep learning model with lin-kernighan- helsgaun heuristic for solving the traveling salesman problem, in: A. Beygelzimer, Y. Dauphin, P. Liang, J. W. Vaughan (Eds.), Advances in Neural Information Processing Systems, 2021...

    2021

  33. [41]

    Y. Yang, A. Whinston, A survey on reinforcement learning for combinatorial optimization, in: 2023 IEEE World Conference on Applied Intelligence and Computing (AIC), IEEE, 2023, pp. 131–136

    2023

  34. [42]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, arXiv preprint quant-ph/0001106 (2000)

    2000 arXiv

  35. [43]

    Han, J.-H

    K.-H. Han, J.-H. Kim, Quantum-inspired evolutionary algorithm for a class of combinatorial optimiza- tion, IEEE Transactions on Evolutionary Computation 6 (6) (2002) 580–593.doi:10.1109/TEVC. 2002.804320

    2002

  36. [44]

    Venturelli, D

    D. Venturelli, D. J. Marchand, G. Rojo, Quantum annealing implementation of job-shop scheduling, arXiv preprint arXiv:1506.08479 (2015)

    2015 arXiv

  37. [45]

    J. King, S. Yarkoni, J. Raymond, I. Ozfidan, A. D. King, M. M. Nevisi, J. P. Hilton, C. C. McGeoch, Quantum annealing amid local ruggedness and global frustration, Journal of the Physical Society of Japan 88 (6) (2019) 061007

    2019

  38. [46]

    URLhttps://www.math.uwaterloo.ca/tsp/data/

    Tsp test data, University of Waterloo, accessed: 2025-03-23. URLhttps://www.math.uwaterloo.ca/tsp/data/

    2025

  39. [47]

    URLhttps://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html

    Mona lisa tsp art problem, University of Waterloo, accessed: 2025-03-23. URLhttps://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html

    2025

  40. [48]

    P. K. Jakob Bossek, tspgen: Tsp instance generation, tspgen, accessed: 2025-03-23. URLhttps://jakobbossek.github.io/tspgen/

    2025

  41. [49]

    Geological Survey, Usgs national transportation dataset (ntd) downloadable data collection, usgs, accessed: 2025-03-23 (2023)

    U.S. Geological Survey, Usgs national transportation dataset (ntd) downloadable data collection, usgs, accessed: 2025-03-23 (2023). URLhttps://www.sciencebase.gov/catalog/item/4f70b1f4e4b058caae3f8e16

    2023

  42. [50]

    Reinelt, Tsplib—a traveling salesman problem library, ORSA journal on computing 3 (4) (1991) 376–384

    G. Reinelt, Tsplib—a traveling salesman problem library, ORSA journal on computing 3 (4) (1991) 376–384. 20

    1991

  43. [51]

    R.Bosch, A.Herman, Continuouslinedrawingsviathetravelingsalesmanproblem, Operationsresearch letters 32 (4) (2004) 302–303

    2004

  44. [52]

    Basel Iii, T

    J. Basel Iii, T. R. Willemain, Random tours in the traveling salesman problem: analysis and application, Computational Optimization and Applications 20 (2) (2001) 211–217

    2001

  45. [53]

    U. G. Survey, Usgs national transportation dataset (ntd) downloadable data collection (2014)

    2014

  46. [54]

    Y. Zhuo, T. Zhang, F. Du, R. Liu, A parallel particle swarm optimization algorithm based on gpu/cuda, Applied Soft Computing 144 (2023) 110499

    2023

  47. [55]

    Janson, D

    S. Janson, D. Merkle, M. Middendorf, Parallel ant colony algorithms, Parallel Metaheuristics: A New Class of Metaheuristics (2005) 171–201

    2005

  48. [56]

    Sohn, Generalized speculative computation of parallel simulated annealing, Annals of Operations Research 63 (1) (1996) 29–55

    A. Sohn, Generalized speculative computation of parallel simulated annealing, Annals of Operations Research 63 (1) (1996) 29–55

    1996

  49. [57]

    E. E. Witte, R. D. Chamberlain, M. A. Franklin, Parallel simulated annealing using speculative com- putation, IEEE Transactions on Parallel & Distributed Systems 2 (04) (1991) 483–494

    1991

  50. [58]

    Yavits, A

    L. Yavits, A. Morad, R. Ginosar, The effect of communication and synchronization on amdahl’s law in multicore systems, Parallel Computing 40 (1) (2014) 1–16

    2014

  51. [59]

    Bertuletti, S

    M. Bertuletti, S. Riedel, Y. Zhang, A. Vanelli-Coralli, L. Benini, Fast shared-memory barrier synchro- nization for a 1024-cores risc-v many-core cluster, in: International Conference on Embedded Computer Systems, Springer, 2023, pp. 241–254

    2023

  52. [60]

    Koziris, G

    C.Giannoula, N.Vijaykumar, N.Papadopoulou, V.Karakostas, I.Fernandez, J.Gómez-Luna, L.Orosa, N. Koziris, G. Goumas, O. Mutlu, Syncron: Efficient synchronization support for near-data-processing architectures, in: 2021 IEEE International Symposium on High-Performance Computer A...

    2021

  53. [61]

    The Traveling Salesman Problem, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 527–562. doi:10.1007/978-3-540-71844-4_21. URLhttps://doi.org/10.1007/978-3-540-71844-4_21

    2008 doi

  54. [62]

    X.-B. Hu, E. Di Paolo, A hybrid genetic algorithm for the travelling salesman problem, in: Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), Springer, 2007, pp. 357–367

    2007

  55. [63]

    39, 2025, pp

    S.Zhou, Y.Ding, C.Zhang, Z.Cao, Y.Jin, Dualopt: Adualdivide-and-optimizealgorithmforthelarge- scale traveling salesman problem, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, 2025, pp. 27178–27186

    2025

  56. [64]

    URLhttps://www.sciencedirect.com/science/article/pii/S0377221710006065

    C.Rego, D.Gamboa, F.Glover, C.Osterman, Travelingsalesmanproblemheuristics: Leadingmethods, implementations and latest advances, European Journal of Operational Research 211 (3) (2011) 427– 441.doi:https://doi.org/10.1016/j.ejor.2010.09.010. URLhttps://www.sciencedirect.com/sc...

    2011 doi

  57. [65]

    M. Held, R. M. Karp, A dynamic programming approach to sequencing problems, Journal of the Society for Industrial and Applied mathematics 10 (1) (1962) 196–210

    1962

  58. [66]

    Catanzaro, L

    D. Catanzaro, L. Gouveia, M. Labbé, Improved integer linear programming formulations for the job sequencing and tool switching problem, European journal of operational research 244 (3) (2015) 766– 777

    2015

  59. [67]

    J. T. Linderoth, E. K. Lee, M. W. Savelsbergh, A parallel, linear programming-based heuristic for large-scale set partitioning problems, INFORMS Journal on Computing 13 (3) (2001) 191–209. 21

    2001

  60. [68]

    D. M. Chitty, Applying aco to large scale tsp instances, in: Advances in Computational Intelligence Systems: Contributions Presented at the 17th UK Workshop on Computational Intelligence, September 6-8, 2017, Cardiff, UK, Springer, 2018, pp. 104–118

    2017

  61. [69]

    Alba, Parallel metaheuristics: a new class of algorithms, John Wiley & Sons, 2005

    E. Alba, Parallel metaheuristics: a new class of algorithms, John Wiley & Sons, 2005

    2005

  62. [70]

    Abdelkafi, J

    O. Abdelkafi, J. Lepagnot, L. Idoumghar, Parallel hybrid ant colony optimization on gpu to solve travelling salesman problem, in: ROADEF-15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, 2014

    2014

  63. [71]

    Melab, E.-G

    N. Melab, E.-G. Talbi, et al., Gpu computing for parallel local search metaheuristics, IEEE Transactions on Computers 62 (1) (2013) 173–185

    2013

  64. [72]

    Skinderowicz, Implementing a gpu-based parallel max–min ant system, Future Generation Computer Systems 106 (2020) 277–295

    R. Skinderowicz, Implementing a gpu-based parallel max–min ant system, Future Generation Computer Systems 106 (2020) 277–295

    2020

  65. [73]

    X. Wei, L. Ma, H. Zhang, Y. Liu, Multi-core-, multi-thread-based optimization algorithm for large-scale traveling salesman problem, Alexandria Engineering Journal 60 (1) (2021) 189–197

    2021

  66. [74]

    Zhang, Depth-first branch-and-bound versus local search: A case study, in: AAAI/IAAI, 2000, pp

    W. Zhang, Depth-first branch-and-bound versus local search: A case study, in: AAAI/IAAI, 2000, pp. 930–935

    2000

  67. [75]

    C.Rego, D.Gamboa, F.Glover, C.Osterman, Travelingsalesmanproblemheuristics: Leadingmethods, implementations and latest advances, European journal of operational research 211 (3) (2011) 427–441

    2011

  68. [76]

    J. Wang, J. Huang, S. Rao, S. Xue, J. Yin, An adaptive genetic algorithm for solving traveling sales- man problem, in: Advanced Intelligent Computing Theories and Applications. With Aspects of Artifi- cial Intelligence: 4th International Conference on Intelligent Computing, IC...

    2008

  69. [77]

    P. V. T. Dat, L. Doan, H. T. T. Binh, Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using llms, arXiv preprint arXiv:2412.14995 (2024)

    2024 arXiv

  70. [78]

    Kshirsagar, S

    P. Kshirsagar, S. Akojwar, Hybrid heuristic optimization for benchmark datasets, International Journal of Computer Application 146 (7) (2016)

    2016

  71. [79]

    M. d. A. C. e Silva, C. da Costa Silveira, L. dos Santos Coelho, A new biogeography-based optimization approach based on shannon–wiener diversity index to pid tuning in multivariable system, in: ABCM symposium series in mechatronics, Vol. 5, 2012, pp. 592–601

    2012

  72. [80]

    Saxena, M

    R. Saxena, M. Jain, S. Bhadri, S. Khemka, Parallelizing ga based heuristic approach for tsp over cuda and openmp, in: 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, 2017, pp. 1934–1940

    2017

  73. [81]

    T. Cai, S. Zhang, Z. Ye, W. Zhou, M. Wang, Q. He, Z. Chen, W. Bai, Cooperative metaheuristic algorithm for global optimization and engineering problems inspired by heterosis theory, Scientific Reports 14 (1) (2024) 28876

    2024

  74. [82]

    R. Senkerik, A brief overview of the synergy between metaheuristics and unconventional dynamics, AETA 2018-Recent Advances in Electrical Engineering and Related Sciences: Theory and Application (2020) 344–356

    2020

  75. [83]

    M. A. Ismail, A gpu accelerated parallel genetic algorithm for the traveling salesman problem, Journal of Soft Computing and Data Mining 5 (2) (2024) 137–150

    2024

  76. [84]

    A. L. B. Almeida, J. de Castro Lima, M. A. M. Carvalho, Revisiting the parallel tempering algo- rithm: High-performance computing and applications in operations research, Computers & Operations Research (2025) 107000. 22

    2025

  77. [85]

    Hudson, Q

    B. Hudson, Q. Li, M. Malencia, A. Prorok, Graph neural network guided local search for the traveling salesperson problem, in: International Conference on Learning Representations

  78. [86]

    Ouyang, Y

    W. Ouyang, Y. Wang, P. Weng, S. Han, Generalization in deep rl for tsp problems via equivariance and local search, SN Computer Science 5 (4) (2024) 369

    2024

  79. [87]

    Linganathan, P

    S. Linganathan, P. Singamsetty, Genetic algorithm to the bi-objective multiple travelling salesman problem, Alexandria Engineering Journal 90 (2024) 98–111.doi:https://doi.org/10.1016/j.aej. 2024.01.048. URLhttps://www.sciencedirect.com/science/article/pii/S1110016824000590 23

    2024 doi

Pith tools

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