{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:06:32Z","timestamp":1760241992599,"version":"build-2065373602"},"reference-count":59,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2018,11,22]],"date-time":"2018-11-22T00:00:00Z","timestamp":1542844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global optimal tour. Based on the performed evaluation tests the proposed IntraClusTSP method provides an efficient incremental tour generation and it can improve the tour efficiency for every tested state-of-the-art methods including the most efficient Chained Lin-Kernighan refinement algorithm. As an application example, we apply IntraClusTSP to automatically determine the optimal number of clusters in a cluster analysis problem. The standard methods like Silhouette index, Elbow method or Gap statistic method, to estimate the number of clusters support only partitional (single level) clustering, while in many application areas, the hierarchical (multi-level) clustering provides a better clustering model. Our proposed method can discover hierarchical clustering structure and provides an outstanding performance both in accuracy and execution time.<\/jats:p>","DOI":"10.3390\/sym10120663","type":"journal-article","created":{"date-parts":[[2018,11,23]],"date-time":"2018-11-23T03:41:31Z","timestamp":1542944491000},"page":"663","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["IntraClusTSP\u2014An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem"],"prefix":"10.3390","volume":"10","author":[{"given":"L\u00e1szl\u00f3","family":"Kov\u00e1cs","sequence":"first","affiliation":[{"name":"Department of Information Technology, University of Miskolc, H-3515 Miskolc-Egyetemv\u00e1ros, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6254-9291","authenticated-orcid":false,"given":"L\u00e1szl\u00f3 Barna","family":"Iantovics","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Medicine, Pharmacy, Sciences and Technology of Targu Mures, R-540139 T\u00e2rgu Mure\u0219, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5027-5323","authenticated-orcid":false,"given":"Dimitris K.","family":"Iakovidis","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Biomedical Informatics, University of Thessaly, GR-35131 Lamia, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhao, C., and Parhami, B. (2018). Symmetric Agency Graphs Facilitate and Improve the Quality of Virtual Network Embedding. Symmetry, 10.","DOI":"10.3390\/sym10030063"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Jiang, W., Zhai, Y., Zhuang, Z., Martin, P., Zhao, Z., and Liu, J.B. (2018). Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs. Symmetry, 10.","DOI":"10.20944\/preprints201808.0007.v1"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Jos\u00e9, M.V., and Zamudio, G.S. (2018). Symmetrical Properties of Graph Representations of Genetic Codes: From Genotype to Phenotype. Symmetry, 10.","DOI":"10.3390\/sym10090388"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ball, F., and Geyer-Schulz, A. (2018). How Symmetric Are Real-World Graphs? A Large-Scale Study. Symmetry, 10.","DOI":"10.3390\/sym10010029"},{"key":"ref_5","first-page":"73","article-title":"NP-completeness of the Hamiltonian cycle problem for bipartite graphs","volume":"3","author":"Akiyama","year":"1980","journal-title":"J. Inf. Process."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0377-2217(92)90138-Y","article-title":"The Traveling Salesman Problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulations and traveling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_9","first-page":"26","article-title":"An exact algorithm for the traveling salesman problem with deliveries and collections","volume":"42","author":"Baldacci","year":"2003","journal-title":"Netw. Int. J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held","year":"1962","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., and Pelillo, M. (1999). The maximum clique problem. Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/mnsc.26.7.736","article-title":"Some new branching and bounding criteria for the asymmetric travelling salesman problem","volume":"26","author":"Carpaneto","year":"1980","journal-title":"Manag. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.dam.2014.03.012","article-title":"On the nearest neighbor rule for the metric traveling salesman problem","volume":"195","author":"Hougardy","year":"2015","journal-title":"Discret. Appl. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.ipl.2014.11.003","article-title":"A note on the traveling salesman reoptimization problem under vertex insertion","volume":"115","author":"Monnot","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_15","first-page":"046112","article-title":"Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement","volume":"77","author":"Schuetz","year":"2008","journal-title":"Phys. Rev."},{"key":"ref_16","first-page":"37","article-title":"\u201cO jist\u00e9mprobl\u00e9muminim\u00e1ln\u00edm\u201d [About a certain minimal problem]","volume":"3","year":"1926","journal-title":"Pr\u00e1cemor. P\u0159\u00edrodov\u011bd. Spol. vBrn\u011b III"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"854218","DOI":"10.1155\/2015\/854218","article-title":"Solving large-scale TSP using a fast wedging insertion partitioning approach","volume":"2015","author":"Xiang","year":"2015","journal-title":"Math. Probl. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0377-2217(94)90360-3","article-title":"The travelling salesman problem with pick-up and delivery","volume":"79","author":"Mosheiov","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1109\/MCI.2014.2326101","article-title":"Benchmarking optimization algorithms: An open source framework for the traveling salesman problem","volume":"9","author":"Weise","year":"2014","journal-title":"IEEE Comput. Intell. Mag."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1007\/s00453-017-0293-5","article-title":"An experimental evaluation of the best-of-many Christofides\u2019 algorithm for the traveling salesman problem","volume":"78","author":"Genova","year":"2017","journal-title":"Algorithmica"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ma, Z., Liu, L., and Sukhatme, G.S. (2016, January 12\u201314). An adaptive k-opt method for solving traveling salesman problem. Proceedings of the 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, USA.","DOI":"10.1109\/CDC.2016.7799275"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.eswa.2016.09.022","article-title":"Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem","volume":"67","author":"Ismkhan","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6459","DOI":"10.1016\/j.eswa.2014.04.015","article-title":"A survey on nature-inspired optimization algorithms with fuzzy logic for dynamic parameter adaptation","volume":"41","author":"Valdez","year":"2014","journal-title":"Expert Syst. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1002\/int.21893","article-title":"An effective Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem","volume":"32","year":"2017","journal-title":"Int. J. Intell. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.ejor.2008.07.022","article-title":"A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem","volume":"197","author":"Imran","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","article-title":"Tour merging via branch-decomposition","volume":"15","author":"Cook","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Johnson, D., and McGeoch, L. (2007). Experimental Analysis of Heuristics for the STSP. The Traveling Salesman Problem and Its Variations, Springer.","DOI":"10.1007\/0-306-48213-4_9"},{"key":"ref_29","first-page":"215","article-title":"The traveling salesman problem: A case study in local optimization","volume":"1","author":"Johnson","year":"1997","journal-title":"Local Search Comb. Optim."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1287\/opre.28.3.694","article-title":"Approximate traveling salesman algorithms","volume":"28","author":"Golden","year":"1980","journal-title":"Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1017\/S096354830000119X","article-title":"Lower bounds for insertion methods for TSP","volume":"3","author":"Azar","year":"1994","journal-title":"Comb. Probab. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","article-title":"An analysis of several heuristics for the traveling salesman problem","volume":"6","author":"Rosenkrantz","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"Hurkens, C.A. (1992, January 25\u201327). Nasty TSP instances for farthest insertion. Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, Pittsburgh PA, USA."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Cronin, T.M. (1990). Maintaining Incremental Optimality When Building Shortest Euclidean Tours (No. CSWD-92-TRF-0042), Army Cecom Signals Warfare.","DOI":"10.21236\/ADA256111"},{"key":"ref_35","first-page":"19","article-title":"An efficient general variable neighborhood search for large travelling salesman problem with time windows","volume":"23","year":"2016","journal-title":"Jugoslav J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.swevo.2015.02.003","article-title":"Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem","volume":"23","author":"Ariyasingha","year":"2015","journal-title":"Swarm Evol. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1287\/opre.40.6.1086","article-title":"New insertion and postoptimization procedures for the traveling salesman problem","volume":"40","author":"Gendreau","year":"1992","journal-title":"Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0305-0548(75)90015-5","article-title":"The clustered traveling salesman problem","volume":"2","author":"Chisman","year":"1975","journal-title":"Comput. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0377-2217(85)90309-1","article-title":"The symmetric clustered traveling salesman problem","volume":"19","author":"Jongens","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1016\/S0893-6080(03)00130-8","article-title":"Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks","volume":"16","author":"Mulder","year":"2003","journal-title":"Neural Netw."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Applegate, D., and Cook, W. (1993). Solving large-scale matching problems. Network Flows and Matching: First DIMACS Mathematical Problems in Engineering 7 Implementation Challenge, American Mathematical Society.","DOI":"10.1090\/dimacs\/012\/22"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0167-739X(94)00059-N","article-title":"A parallel 2-opt algorithm for the traveling salesman problem","volume":"11","author":"Verhoeven","year":"1995","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","article-title":"Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane","volume":"2","author":"Karp","year":"1977","journal-title":"Math. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","article-title":"Fast algorithms for geometric traveling salesman problems","volume":"4","author":"Bentley","year":"1992","journal-title":"ORSA J. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1515\/jaiscr-2015-0032","article-title":"Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm","volume":"5","author":"Ashour","year":"2015","journal-title":"J. Artif. Intell. Soft Comput. Res."},{"key":"ref_46","first-page":"243","article-title":"Clustering evolutionary computation for solving travelling salesman problems","volume":"3","author":"Phienthrakul","year":"2014","journal-title":"Int. J. Adv. Comput. Sci. Inf. Technol."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"8956","DOI":"10.1016\/j.eswa.2015.07.051","article-title":"Hybrid evolutionary algorithms for the multiobjective traveling salesman problem","volume":"42","author":"Psychas","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_48","first-page":"1275","article-title":"Efficiency analysis of quality threshold clustering algorithms","volume":"6","author":"Bednarik","year":"2012","journal-title":"Prod. Syst. Inf. Eng."},{"key":"ref_49","unstructured":"Garnier, R., and Taylor, J. (2001). Discrete Matrhematics for New Technolology, IoP Publisher."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1198\/016214503000000666","article-title":"Finding the number of clusters in a dataset: An information-theoretic approach","volume":"98","author":"Sugar","year":"2003","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_51","first-page":"28","article-title":"A Performance Comparison of GA and ACO Applied to TSP","volume":"117","author":"Haroun","year":"2015","journal-title":"Int. J. Comput. Appl."},{"key":"ref_52","unstructured":"Richter, D., Goldengorin, B., J\u00e4ger, G., and Molitor, P. (2007, January 14). Improving the efficiency of Helsgaun\u2019s Lin-Kernighan heuristic for the symmetric TSP. Proceedings of the Workshop on Combinatorial and Algorithmic Aspects of Networking, Halifax, NS, Canada."},{"key":"ref_53","unstructured":"Walshaw, C. (2001). A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem, CMS Press."},{"key":"ref_54","first-page":"823","article-title":"Cluster-reliability-induced OWA operators","volume":"32","author":"Ma","year":"2017","journal-title":"Int. J. Intell. Syst."},{"key":"ref_55","first-page":"111","article-title":"Finding groups in data","volume":"34","author":"Rousseeuw","year":"2003","journal-title":"Ser. Probab. Math. Stat."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1111\/1467-9868.00293","article-title":"Estimating the number of clusters in a data set via the gap statistic","volume":"63","author":"Tibshirani","year":"2001","journal-title":"J. R. Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1080\/01621459.1995.10476572","article-title":"Bayes factors","volume":"90","author":"Kass","year":"1995","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_58","first-page":"4245","article-title":"Gaussian mixture density modeling and decomposition with weighted likelihood","volume":"5","author":"Yang","year":"2004","journal-title":"J. Men\u2019s Health"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Liu, Y., Li, Z., Xiong, H., Gao, X., and Wu, J. (2010, January 13\u201317). Understanding of internal clustering validation measures. Proceedings of the 2010 IEEE International Conference on Data Mining, Sydney, Australia.","DOI":"10.1109\/ICDM.2010.35"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/12\/663\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:31:23Z","timestamp":1760196683000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/10\/12\/663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,22]]},"references-count":59,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["sym10120663"],"URL":"https:\/\/doi.org\/10.3390\/sym10120663","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2018,11,22]]}}}