Comparison of eleven measures for estimating difficulty of open-loop TSP instances

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

From the theory of algorithms, we know that the time complexity of finding the optimal solution for a traveling salesman problem (TSP) grows exponentially with the number of targets. However, the size of the problem instance is not the only factor that affects its difficulty. In this paper, we review existing measures to estimate the difficulty of a problem instance. We also introduce MST branches and two other measures called greedy path and greedy gap. The idea of MST branches is to generate minimum spanning tree (MST) and then calculate the number of branches in the tree. A branch is a target, which is connected to at least two other targets. We perform an extensive comparison of 11 measures to see how well they correlate to human and computer performance. We evaluate the measures based on time complexity, prediction capability, suitability, and practicality. The results show that while the MST branches measure is simple, fast to compute, and does not need to have the optimal solution as a reference unlike many other measures. It correlates equally good or even better than the best of the previous measures-the number of targets, and the number of targets on the convex hull.

Keywords

TSP / open-loop TSP / difficulty of instances / MST / human TSP solving

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] C. H. Papadimitriou, The Euclidean travelling salesman problem is NP-complete, Theoretical Computer Science, 4 (1977), 237-244. doi: 10.1016/0304-3975(77)90012-3

[2] N. Phillips, R. Phillips, Rogaining: Cross-Country Navigation. Outdoor Recreation in Australia. ISBN 0-9593329-2-8.

[3] P. Fränti, R. Mariescu-Istodor, L. Sengupta, O-Mopsi: Mobile orienteering game for sightseeing, exercising, and education, ACM Transactions on Multimedia Computing, Communications, and Applications, 13 (2017), 1-12. doi: 10.1145/3115935

[4] L. Sengupta, P. Fränti, Predicting the difficulty of TSP instances using MST. IEEE Int. Conf. on Industrial Informatics (INDIN), (2019), 847-852. Helsinki. doi: 10.1109/INDIN41052.2019.8972232

[5] D. Vickers, T. Mayo, M. Heitmann, M. D. Lee, P. Hughes, Intelligence and individual differences on three types of visually presented optimisation problems. Personality and Individual Differences, 36 (2004), 1059-1071. doi: 10.1090/S0894-0347-1992-1124979-1

[6] M. J. Dry, K. Preiss, J. Wagemans, Clustering, randomness, and regularity: Spatial distributions and human performance on the traveling salesperson problem and minimum spanning tree problem, The Journal of Problem Solving, 4 (2012), 1‒ 17. doi: 10.1007/s002850170002

[7] S. M. Graham, A. Joshi, Z. Pizlo, The traveling salesman problem: A hierarchical model, Memory and Cognition, 28 (2000), 1191-1204. doi: 10.1016/j.media.2013.04.012

[8] M. J. Dry, M. D. Lee, D. Vickers, P. Hughes, Human performance on visually presented traveling salesperson problems with varying numbers of nodes, Journal of Problem Solving, 1 (2006), 4. doi: 10.7771/1932-6246.1004

[9] J. N. Macgregor, T. Ormerod, Human performance on the traveling salesman problem, Perception and Psychophysics, 58 (1996), 527-539. doi: 10.3758/BF03213088

[10] E. P. Chronicle, J. N. MacGregor, T. C. Ormerod, A. Burr, It looks easy! Heuristics for combinatorial optimisation problems, Q. J. Exp. Psychol., 59 (2006), 783-800. doi: 10.1080/02724980543000033

[11] T. Fischer, T. Stützle, H. Hoos, P. Merz, An analysis of the hardness of TSP instances for two high performance algorithms, Metaheuristics International Conference,(2005) 361-367.

[12] D. Applegate, R. Bixby, V. Chvátal, W. Cook, Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems, Math. Program, 97 (2003), 91-153. doi: 10.1007/s10107-003-0440-4

[13] K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur. J. Oper. Res., 126 (2000), 106-130. doi 10.1016/S0377-2217(99)00284-2

[14] K. Leyton-Brown, H. H. Hoos, F. Hutter, L. Xu, Understanding the empirical hardness of NP-complete problems, Communications of the ACM, 57 (2014), 98-107. doi: 10.1145/2594413.2594424

[15] P. Kromer, J. Platos, M. Kudelka, Network measures and evaluation of traveling salesman instance hardness, IEEE Symposium Series on Computational Intelligence (SSCI), (2017), 1-7.

[16] E. Ochodkova, S. Zehnalova, M. Kudelka, Graph construction based on local representativeness, International Computing and Combinatorics Conference, (2017), 654-665.

[17] D. Vickers, M. D. Lee, M. Dry, P. Hughes, J. A. McMahon, The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling salesperson problems, Perception and Psychophysics, 68 (2006), 32-42. doi: 10.3758/BF03193653

[18] J. N. MacGregor, Indentations and starting points in traveling sales tour problems: Implications for theory, Journal of Problem Solving, 5 (2012), 2-17. doi: 10.7771/1932-6246.1140

[19] D. Vickers, M. D. Lee, M. Dry, P. Hughes, The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems, Memory and Cognition, 31 (2003), 1094-1104. doi: 10.3758/bf03196130

[20] J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, P. Am. Math. Soc., 7 (1956), 48-50. doi: 10.1090/S0002-9939-1956-0078686-7

[21] R. C. Prim, Shortest connection networks and some generalizations, The Bell System Technical Journal, 36 (1957), 1389-1401. doi: 10.1002/j.1538-7305.1957.tb01515.x

[22] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[23] J. Rosenkrantz, R. E. Stearns, P. M. Lewis II, An analysis of several heuristics for the travelling salesman problem, SIAM J. Comput., 6 (1977), 563-581. doi: 10.1137/0206041

[24] P. Fränti, H. Nenonen, Modifying Kruskal algorithm to solve open loop TSP. Multidisciplinary International Scheduling Conference (MISTA), (2019), 584-590.

[25] P. Fränti, T. Nenonen, M. Yuan, Converting MST to TSP path by branch elimination, Applied Sciences, 11 (2021), 1-17. doi: 10.3390/app11010177

[26] G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, Eur. J. Oper. Res., 59 (1992), 231-247. doi: 10.1016/0377-2217(92)90138-Y

[27] L. Sengupta, R. Mariescu-Istodor, P. Fränti, Planning your route: Where to start?. Computational Brain and Behavior, 1 (2018), 252-265. doi: 10.1007/s42113-018-0018-0

[28] J. N. MacGregor, E. P. Chronicle, T. C. Ormerod, Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem, Memory and Cognition, 32 (2004), 260-270. doi: 10.3758/bf03196857

[29] R. Mariescu-Istodor, P. Fränti, Solving large-scale TSP problem in 1 hour: Santa Claus Challenge 2020, Frontiers in Robotics and AI, 8 (2021).

[30] A. M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Inform. Process. Lett., 9 (1979), 216-219. doi: 10.1016/0020-0190(79)90072-3

[31] T. C. Ormerod, E. P. Chronicle, Global perceptual processing in problem solving: The case of the traveling salesperson, Perception and Psychophysics, 61 (1999), 1227-1238. doi : 10.3758/bf03207625

[32] M. J. Dry, E. L. Fontaine, Fast and efficient discrimination of traveling salesperson problem stimulus difficulty, The Journal of Problem Solving, 7 (2014), 9. doi: 10.7771/1932-6246.1160

[33] B. Braden, The surveyor's area formula, The College Mathematics Journal, 17 (1986), 326-337. doi: 10.1080/07468342.1986.11972974

[34] D. L. Applegate, R. E. Bixby, V. Chvatal, W. J. Cook, The traveling salesman problem: a computational study, Princeton University Press, 2011

[35] L. V. Quintas, F. Supnick, Extreme Hamiltonian circuits. Resolution of the convex-even case, Proceedings of the American Mathematical Society, 16 (1965), 1058-1061. doi: 10.2307/2035616

[36] I. Van Rooij, U. Stege, A. Schactman, Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies, Memory and Cognition, 31 (2003), 215-220. doi: 10.3758/BF03194380

[37] J. Q. Yang, J. G. Yang, G. L. Chen, Solving large-scale TSP using adaptive clustering method, IEEE International Symposium on Computational Intelligence and Design, 1 (2009), 49-51. doi: 10.1109/ISCID.2009.19

[38] J. N. MacGregor, Effects of cluster location on human performance on the traveling salesperson problem, The Journal of Problem Solving, 5 (2013), 3. doi: 10.7771/1932-6246.1151

[39] J. Žunić, K. Hirota, Measuring shape circularity, Iberoamerican Congress on Pattern Recognition, (2008), 94-101. Springer, Berlin, Heidelberg.

[40] A. Schick, M. Fischer, R. Stiefelhagen, Measuring and evaluating the compactness of superpixels, International Conference on Pattern Recognition (ICPR), (2012), 930-934.

[41] L. Sengupta, R. Mariescu-Istodor, P. Fränti, Which local search operator works best for the open-loop TSP? Applied Sciences, 9 (2019), 3985. doi: 10.3390/app9193985

[42] I. Jormanainen, P. Korhonen, Science festivals on computer science recruitment, Koli Calling International Conference on Computing Education Research (Koli Calling’10), (2010), 72-73.

[43] J. N. MacGregor, T. C. Ormerod, E. P. Chronicle, Spatial and contextual factors in human performance on the travelling salesperson problem, Perception, 28 (1999), 1417-1427. doi: 10.1068/p2863

[44] J. N. MacGregor, T. C. Ormerod, E. P. Chronicle, A model of human performance on the traveling salesperson problem, Memory and Cognition, 28 (2000), 1183-1190. doi: 10.3758/BF03211819

[45] Q. Zhao, P. Fränti, WB-index: A sum-of-squares based index for cluster validity, Data Knowl. Eng., 92 (2014), 77-89. doi: 10.1016/j.datak.2014.07.008