SavedAdd your journal

Journals / Ekoist: Journal of Econometrics and Statistics / 2026 / Sayı: 44

A Consensus-Edge Initializer for Multi-start 2-opt on the Symmetric Euclidean Travelling Salesman Problem

Ahmet Çağlar Saygılı(MUNZUR ÜNİVERSİTESİ)0000-0003-0724-1395
Halim Kazan(İSTANBUL ÜNİVERSİTESİ)0000-0002-9234-6214
Pages
217–242
Publication Date
2026-07-03
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Thus, even a single aggregation step over 2-opt local minima yields a simple, reproducible seed that is beneficial in the practically relevant regime of moderate budgets and larger instances and approximately neutral elsewhere.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:We study a one-shot consensus-based initializer for multi-start 2-opt on symmetric Euclidean Travelling Salesman Problem (TSP) instances.
📊
Key Findings & Data:Given the M local minima from best-of-M 2-opt, we count undirected edge frequencies, greedily assemble a tour from the most frequent edges with a length-biased tie-break, and run a single additional 2-opt descent from this seed.
💡
Conclusion & Impact:Thus, even a single aggregation step over 2-opt local minima yields a simple, reproducible seed that is beneficial in the practically relevant regime of moderate budgets and larger instances and approximately neutral elsewhere.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Travelling Salesman Problem · local search · 2-opt

Abstract

We study a one-shot consensus-based initializer for multi-start 2-opt on symmetric Euclidean Travelling Salesman Problem (TSP) instances. Given the M local minima from best-of-M 2-opt, we count undirected edge frequencies, greedily assemble a tour from the most frequent edges with a length-biased tie-break, and run a single additional 2-opt descent from this seed. The local search operator is unchanged; the consensus stage reuses existing tours and adds only a small overhead beyond the M descents, and we characterise this overhead analytically while focusing evaluation on tour length improvements. On synthetic Euclidean instances from three generators, we evaluate performance over a grid of problem sizes n and restart budgets M. The consensus + 2-opt pipeline improves best-of-M 2-opt by roughly 3–6% in median tour length with high win rates for n≥500 and moderate M, while for small n and large M the baseline saturates and gains shrink to zero or slightly negative values. Thus, even a single aggregation step over 2-opt local minima yields a simple, reproducible seed that is beneficial in the practically relevant regime of moderate budgets and larger instances and approximately neutral elsewhere.

🔖

Cite This Article

Saygılı, A. Ç., Kazan, H. (2026). A Consensus-Edge Initializer for Multi-start 2-opt on the Symmetric Euclidean Travelling Salesman Problem. Ekoist: Journal of Econometrics and Statistics, Sayı: 44, 217–242. https://doi.org/10.26650/ekoist.2026.44.1824864

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (74)

  1. Applegate, D. L., Bixby, R. E., Chvátal, V., Cook, W. J. (2007). The traveling salesman problem. In A Computational Study. Princeton University Press. https://doi.org/10.1515/9781400841103 google scholar
  2. Applegate, D. L., Cook, W., & Rohe, A. (2003). Chained lin-kernighan for large traveling salesman problems. INFORMS Journal on Computing, 15(1), 82–92. https://doi.org/10.1287/ijoc.15.1.82.15157 google scholar
  3. Arora, S. (1996). Polynomial time approximation schemes for euclidean TSP and other geometric problems. Proceedings of 37th Conference on Foundations of Computer Science, 2–11. https://doi.org/10.1109/SFCS.1996.548458 google scholar
  4. Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2017). Neural combinatorial optimization with reinforcement learning. https://arxiv.org/abs/1611.09940 google scholar
  5. Benjamini, Y., & Hochberg, Y. (1995). Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodological), 57(1), 289–300. https://doi.org/10.1111/j.2517-6161.1995.tb02031.x google scholar
  6. Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9), 509–517. https://doi.org/10.1145/361002.361007 google scholar
  7. Bentley, J. L. (1992). Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing, 4(4), 387–411. https://doi.org/10.1287/ijoc.4.4.387 google scholar
  8. Berger, R. L., & Hsu, J. C. (1996). Bioequivalence trials, intersection-union tests, and equivalence confidence sets. Statistical Science, 11(4), 283–319. https://doi.org/10.1214/ss/1032280304 google scholar
  9. Blackman, D., & Vigna, S. (2021). Scrambled linear pseudorandom number generators. ACM Trans. Math. Softw., 47(4). https://doi.org/10.1145/3460772 google scholar
  10. Boese, K. D. (1995). Cost versus distance in the Traveling Salesman Problem (Technical Report Nos. TR-950018). UCLA Computer Science Department. google scholar
  11. Boese, K. D., Kahng, A. B., & Muddu, S. (1994). A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16(2), 101–113. https://doi.org/10.1016/0167-6377(94)90065-5 google scholar
  12. Cliff, N. (1993). Dominance statistics: Ordinal analyses to answer ordinal questions. In Psychological Bulletin (No. 3; Vol. 114, pp. 494–509). American Psychological Association. https://doi.org/10.1037/0033-2909.114.3.494 google scholar
  13. Costa, P. R. d. O. da, Rhuggenaath, J., Zhang, Y., & Akcay, A. (2020). Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In S. J. Pan & M. Sugiyama (Eds.), Proceedings of the 12th asian conference on machine learning (Vol. 129, pp. 465–480). PMLR. https://proceedings.mlr.press/v129/costa20a.html google scholar
  14. Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812. https://EconPapers.repec.org/RePEc:inm:oropre:v:6:y:1958:i:6:p:791-812 google scholar
  15. Dong, C., Ernst, C., Jäger, G., Richter, D., & Molitor, P. (2009). Effective heuristics for large euclidean TSP instances based on pseudo backbones. In S. Cafieri, A. Mucherino, G. Nannicini, F. Tarissan, & L. Liberti (Eds.), Proceedings of the 8th cologne-twente workshop on graphs and combinatorial optimization (pp. 3–6). google scholar
  16. Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. Biosystems, 43(2), 73–81. https://doi.org/10.1016/S0303-2647(97)01708-5 google scholar
  17. Englert, M., Röglin, H., & Vöcking, B. (2014). Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68(1), 190–264. https://doi.org/10.1007/s00453-013-9801-4 google scholar
  18. Englert, M., Röglin, H., & Vöcking, B. (2016). Smoothed analysis of the 2-opt algorithm for the general TSP. ACM Trans. Algorithms, 13(1). https://doi.org/10.1145/2972953 google scholar
  19. Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109–133. https://doi.org/10.1007/BF01096763 google scholar
  20. Flood, M. M. (1956). The traveling-salesman problem. Operations Research, 4(1), 61–75. https://EconPapers.repec.org/RePEc:inm:oropre:v:4:y:1956:i:1:p:61-75 google scholar
  21. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74–94. https://doi.org/10.1287/inte.20.4.74 google scholar
  22. Glover, F., Laguna, M., & Marti, R. (2007). Principles of tabu search. Approximation Algorithms and Metaheuristics, 23(1), 1–12. google scholar
  23. Hains, D. R., Whitley, L. D., & Howe, A. E. (2011). Revisiting the big valley search space structure in the TSP. Journal of the Operational Research Society, 62(2), 305–312. https://doi.org/10.1057/jors.2010.116 google scholar
  24. Heins, J., Schäpermeier, L., Kerschke, P., & Whitley, D. (2024). Dancing to the state of the art? In M. Affenzeller, S. M. Winkler, A. V. Kononova, H. Trautmann, T. Tušar, P. Machado, & T. Bäck (Eds.), Parallel problem solving from nature, PPSN XVIII (pp. 100–115). Springer Nature Switzerland. google scholar
  25. Held, M., & Karp, R. M. (1970). The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6), 1138–1162. https://doi.org/10.1287/opre.18.6.1138 google scholar
  26. Held, M., & Karp, R. M. (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1(1), 6–25. https://doi.org/10.1007/BF01584070 google scholar
  27. Helsgaun, K. (2000). An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106–130. https://doi.org/10.1016/S0377-2217(99)00284-2 google scholar
  28. Helsgaun, K. (2009). General k-opt submoves for the lin-kernighan TSP heuristic. Mathematical Programming Computation, 1(2), 119–163. https://doi.org/10.1007/s12532-009-0004-6 google scholar
  29. Helsgaun, K. (2018). Using POPMUSIC for candidate set generation in the lin-kernighan-helsgaun TSP solver. Roskilde Universitet. google scholar
  30. Hougardy, S., & Schroeder, R. T. (2014). Edge elimination in TSP instances. In D. Kratsch & I. Todinca (Eds.), Graph-theoretic concepts in computer science (pp. 275–286). Springer International Publishing. google scholar
  31. Jäger, G., Dong, C., Goldengorin, B., Molitor, P., & Richter, D. (2014). A backbone based TSP heuristic for large instances. Journal of Heuristics, 20(1), 107–124. https://doi.org/10.1007/s10732-013-9233-y google scholar
  32. Johnson, D. S., & McGeoch, L. A. (1997). The traveling salesman problem: A case study in local optimization. Local Search in Combinatorial Optimization, 1(1), 215–310. google scholar
  33. Johnson, D. S., & McGeoch, L. A. (2007). Experimental analysis of heuristics for the STSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 369–443). Springer US. https://doi.org/10.1007/0-306-48213-4_9 google scholar
  34. Joshi, C. K., Laurent, T., & Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. https://arxiv.org/abs/1906.01227 google scholar
  35. Kilby, P., Slaney, J., & Walsh, T. (2005). The backbone of the travelling salesperson. International Joint Conference on Artificial Intelligence, 19, 175. google scholar
  36. Kool, W., Hoof, H. van, & Welling, M. (2019). Attention, learn to solve routing problems! https://arxiv.org/abs/1803.08475 google scholar
  37. Letchford, A. N., & Pearson, N. A. (2008). Good triangulations yield good tours. Computers & Operations Research, 35(2), 638–647. https://doi.org/10.1016/j.cor.2006.03.025 google scholar
  38. Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516. https://doi.org/10.1287/opre.21.2.498 google scholar
  39. Ma, Q., Ge, S., He, D., Thaker, D., & Drori, I. (2019). Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. https://arxiv.org/abs/1911.04936 google scholar
  40. Manthey, B., & Rhijn, J. van. (2025). Improved smoothed analysis of 2-opt for the euclidean TSP. Algorithmica, 87(7), 1008–1039. https://doi.org/10.1007/s00453-025-01309-9 google scholar
  41. Manthey, B., & Veenstra, R. (2013). Smoothed analysis of the 2-opt heuristic for the TSP: Polynomial bounds for gaussian noise. In L. Cai, S.-W. Cheng, & T.-W. Lam (Eds.), Algorithms and computation (pp. 579–589). Springer Berlin Heidelberg. google scholar
  42. Mitchell, J. S. B. (1999). Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4), 1298–1309. https://doi.org/10.1137/S0097539796309764 google scholar
  43. Nagata, Y. (1997). Edge assembly crossover:a high-power genetic algorithm for the traveling salesman problem. Proceedings of the 7th Internatinal Conferencenon Genetic Algorithms, 450–457. https://cir.nii.ac.jp/crid/1572824498906398336 google scholar
  44. Nagata, Y. (2006). New EAX crossover for large TSP instances. In T. P. Runarsson, H.-G. Beyer, E. Burke, J. J. Merelo-Guervós, L. D. Whitley, & X. Yao (Eds.), Parallel problem solving from nature - PPSN IX (pp. 372–381). Springer Berlin Heidelberg. google scholar
  45. Nagata, Y., & Kobayashi, S. (2012). A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2), 346–363. https://doi.org/10.1287/ijoc.1120.0506 google scholar
  46. Norman Cliff. (1996). Ordinal methods for behavioral data analysis (1st ed.). Psychology Press / Lawrence Erlbaum Associates. https://doi.org/10.4324/9781315806730 google scholar
  47. Punnen, A. P. (2007). The traveling salesman problem: Applications, formulations and variations. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 1–28). Springer US. https://doi.org/10.1007/0-306-48213-4_1 google scholar
  48. Rego, C., Gamboa, D., Glover, F., & Osterman, C. (2011). Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European Journal of Operational Research, 211(3), 427–441. https://doi.org/10.1016/j.ejor.2010.09.010 google scholar
  49. Reinelt, G. (1991). TSPLIB–a traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376 google scholar
  50. Resende, M. G. C., & Ribeiro, C. C. (2014). GRASP: Greedy randomized adaptive search procedures. In E. K. Burke & G. Kendall (Eds.), Search methodologies: Introductory tutorials in optimization and decision support techniques (pp. 287–312). Springer US. https://doi.org/10.1007/978-1-4614-6940-7_11 google scholar
  51. Schuirmann, D. J. (1987). A comparison of the two one-sided tests procedure and the power approach for assessing the equivalence of average bioavailability. Journal of Pharmacokinetics and Biopharmaceutics, 15(6), 657–680. https://doi.org/10.1007/BF01068419 google scholar
  52. Stutzle, T., & Dorigo, M. (2002). A short convergence proof for a class of ant colony optimization algorithms. IEEE Transactions on Evolutionary Computation, 6(4), 358–365. https://doi.org/10.1109/TEVC.2002.802444 google scholar
  53. Sultana, N., Chan, J., Abbasi, B., Sarwar, T., & Qin, A. K. (2024). Learning to guide local search optimisation for routing problems. Operations Research Letters, 55, 107136. https://doi.org/10.1016/j.orl.2024.107136 google scholar
  54. Taillard, É. D., & Helsgaun, K. (2019). POPMUSIC for the travelling salesman problem. European Journal of Operational Research, 272(2), 420–429. https://doi.org/10.1016/j.ejor.2018.06.039 google scholar
  55. Taillard, É. D., Voss, S., Ribeiro, C. C., & Hansen, P. (2002). Popmusic – partial optimization metaheuristic under special intensification conditions. In Essays and surveys in metaheuristics (pp. 613–629). Springer US. https://doi.org/10.1007/978-1-4615-1507-4_27 google scholar
  56. Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215–225. https://doi.org/10.1145/321879.321884 google scholar
  57. Tsutsui, S. (2002). Probabilistic model-building genetic algorithms in permutation representation domain using edge histogram. In J. J. M. Guervós, P. Adamidis, H.-G. Beyer, H.-P. Schwefel, & J.-L. Fernández-Villacañas (Eds.), Parallel problem solving from nature – PPSN VII (pp. 224–233). Springer Berlin Heidelberg. google scholar
  58. Tsutsui, S., Pelikan, M., & Ghosh, A. (2006). Edge histogram based sampling with local search for solving permutation problems. International Journal of Hybrid Intelligent Systems, 3(1), 11–22. https://doi.org/10.3233/HIS-2006-3102 google scholar
  59. Vargha, A., & Delaney, H. D. (2000). A critique and improvement of the CL common language effect size statistics of McGraw and wong. Journal of Educational and Behavioral Statistics, 25(2), 101–132. https://doi.org/10.3102/10769986025002101 google scholar
  60. Wang, L., Zheng, J., Xiong, Z., & He, K. (2025). Multi-armed bandit and backbone boost lin-kernighan-helsgaun algorithm for the traveling salesman problems. Arxiv. 2025. https://arxiv.org/abs/2501.04072 google scholar
  61. Wang, Y. (2015). Statistical analysis of frequency graph for traveling salesman problem. Journal of Intelligent & Fuzzy Systems, 28(3), 1109–1118. https://doi.org/10.3233/IFS-141394 google scholar
  62. Wang, Y. (2018). A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals. Filomat, 32(5), 1697–1702. [suspicious link removed] google scholar
  63. Wang, Y. (2019). Sufficient and necessary conditions for an edge in the optimal hamiltonian cycle based on frequency quadrilaterals. Journal of Optimization Theory and Applications, 181(2), 671–683. https://doi.org/10.1007/s10957-018-01465-9 google scholar
  64. EKOIST Journal of Econometrics and Statistics, x, 1–26 16 google scholar
  65. A Consensus-Edge Initializer for Multi-start 2-opt on the Symmetric Euclidean TSP Saygılı & Kazan, 2026 google scholar
  66. Wang, Y., & Han, Z. (2020). The frequency of the optimal hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem. In Z. Zhang, W. Li, & D.-Z. Du (Eds.), Algorithmic aspects in information and management (pp. 513–524). Springer International Publishing. google scholar
  67. Wang, Y., & Shen, R. (2021). The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem. In Z. Cai, J. Li, & J. Zhang (Eds.), Theoretical computer science (pp. 177–195). Springer Singapore. google scholar
  68. Wellek, S. (2010). Testing statistical hypotheses of equivalence and noninferiority (2nd ed.). Chapman; Hall/CRC. https://doi.org/10.1201/EBK1439808184 google scholar
  69. Westlake, W. J. (1976). Symmetrical confidence intervals for bioequivalence trials. Biometrics, 32(4), 741–744. https://doi.org/10.2307/2529259 google scholar
  70. Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics Bulletin, 1(6), 80–83. https://doi.org/10.2307/3001968 google scholar
  71. Wilson, E. B. (1927). Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158), 209–212. https://doi.org/10.1080/01621459.1927.10502953 google scholar
  72. Zhang, W., & Looks, M. (2005). A novel local search algorithm for the traveling salesman problem that exploits backbones. IJCAI, 5, 343–384. google scholar
  73. Zheng, J., He, K., Zhou, J., Jin, Y., & Li, C.-M. (2021). Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem. AAAI, 35(14), 12445–12452. https://doi.org/10.1609/aaai.v35i14.17476 google scholar
  74. Zheng, J., He, K., Zhou, J., Jin, Y., & Li, C.-M. (2023). Reinforced lin-kernighan-helsgaun algorithms for the traveling salesman problems. Knowledge-Based Systems, 260, 110144. https://doi.org/10.1016/j.knosys.2022.110144 google scholar