×

zbMATH — the first resource for mathematics

IntraClusTSP – an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem. (English) Zbl 1425.90138
Summary: 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.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
68W15 Distributed algorithms
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Zhao, C.; Parhami, B.; Symmetric Agency Graphs Facilitate and Improve the Quality of Virtual Network Embedding; Symmetry: 2018; Volume 10 .
[2] Jiang, W.; Zhai, Y.; Zhuang, Z.; Martin, P.; Zhao, Z.; Liu, J.B.; Vertex Labeling and Routing for Farey-Type Symmetrically-Structured Graphs; Symmetry: 2018; Volume 10 .
[3] José, M.V.; Zamudio, G.S.; Symmetrical Properties of Graph Representations of Genetic Codes: From Genotype to Phenotype; Symmetry: 2018; Volume 10 .
[4] Ball, F.; Geyer-Schulz, A.; How Symmetric Are Real-World Graphs? A Large-Scale Study; Symmetry: 2018; Volume 10 .
[5] Akiyama, T.; Nishizeki, T.; Saito, N.; NP-completeness of the Hamiltonian cycle problem for bipartite graphs; J. Inf. Process.: 1980; Volume 3 ,73-76. · Zbl 0444.68058
[6] Laporte, G.; The Traveling Salesman Problem: An overview of exact and approximate algorithms; Eur. J. Oper. Res.: 1992; Volume 59 ,231-247. · Zbl 0760.90089
[7] Dantzig, G.B.; Fulkerson, D.R.; Johnson, S.M.; Solution of a large-scale traveling-salesman problem; Oper. Res.: 1954; Volume 2 ,393-410.
[8] Miller, C.E.; Tucker, A.W.; Zemlin, R.A.; Integer programming formulations and traveling salesman problems; J. Assoc. Comput. Mach.: 1960; Volume 7 ,326-329. · Zbl 0100.15101
[9] Baldacci, R.; Hadjiconstantinou, E.; Mingozzi, A.; An exact algorithm for the traveling salesman problem with deliveries and collections; Netw. Int. J.: 2003; Volume 42 ,26-41. · Zbl 1023.90050
[10] Held, M.; Karp, R.M.; A dynamic programming approach to sequencing problems; J. Soc. Ind. Appl. Math.: 1962; Volume 10 ,196-210. · Zbl 0106.14103
[11] Bomze, I.M.; Budinich, M.; Pardalos, P.M.; Pelillo, M.; The maximum clique problem; Handbook of Combinatorial Optimization: Boston, MA, USA 1999; ,1-74. · Zbl 1253.90188
[12] Carpaneto, G.; Toth, P.; Some new branching and bounding criteria for the asymmetric travelling salesman problem; Manag. Sci.: 1980; Volume 26 ,736-743. · Zbl 0445.90089
[13] Hougardy, S.; Wilde, M.; On the nearest neighbor rule for the metric traveling salesman problem; Discret. Appl. Math.: 2015; Volume 195 ,101-103. · Zbl 1331.90068
[14] Monnot, J.; A note on the traveling salesman reoptimization problem under vertex insertion; Inf. Process. Lett.: 2015; Volume 115 ,435-438. · Zbl 1318.90061
[15] Schuetz, P.; Caflisch, A.; Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement; Phys. Rev.: 2008; Volume 77 ,046112.
[16] Borůvka, O.; “O jistémproblémuminimálním” [About a certain minimal problem]; Prácemor. Přírodověd. Spol. vBrně III: 1926; Volume 3 ,37-58.
[17] Xiang, Z.; Chen, Z.; Gao, X.; Wang, X.; Di, F.; Li, L.; Zhang, Y.; Solving large-scale TSP using a fast wedging insertion partitioning approach; Math. Probl. Eng.: 2015; Volume 2015 ,854218. · Zbl 1394.90503
[18] Mosheiov, G.; The travelling salesman problem with pick-up and delivery; Eur. J. Oper. Res.: 1994; Volume 79 ,299-310. · Zbl 0815.90135
[19] Weise, T.; Chiong, R.; Lassig, J.; Tang, K.; Tsutsui, S.; Chen, W.; Yao, X.; Benchmarking optimization algorithms: An open source framework for the traveling salesman problem; IEEE Comput. Intell. Mag.: 2014; Volume 9 ,40-52.
[20] Genova, K.; Williamson, D.P.; An experimental evaluation of the best-of-many Christofides’ algorithm for the traveling salesman problem; Algorithmica: 2017; Volume 78 ,1109-1130. · Zbl 1372.90090
[21] Ma, Z.; Liu, L.; Sukhatme, G.S.; An adaptive k-opt method for solving traveling salesman problem; Proceedings of the 2016 IEEE 55th Conference on Decision and Control (CDC): ; Volume Volume 1 ,6537-6543.
[22] Lin, S.; Kernighan, B.W.; An effective heuristic algorithm for the traveling-salesman problem; Oper. Res.: 1973; Volume 21 ,498-516. · Zbl 0256.90038
[23] Ismkhan, H.; Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem; Expert Syst. Appl.: 2017; Volume 67 ,148-162.
[24] Valdez, F.; Melin, P.; Castillo, O.; A survey on nature-inspired optimization algorithms with fuzzy logic for dynamic parameter adaptation; Expert Syst. Appl.: 2014; Volume 41 ,6459-6466.
[25] Kóczy, L.T.; Földesi, P.T.; Szabó, B.; An effective Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem; Int. J. Intell. Syst.: 2017; Volume 32 ,862-876.
[26] Imran, A.; Salhi, S.; Wassan, N.A.; A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem; Eur. J. Oper. Res.: 2009; Volume 197 ,509-518. · Zbl 1159.90525
[27] Cook, W.; Seymour, P.; Tour merging via branch-decomposition; INFORMS J. Comput.: 2003; Volume 15 ,233-248. · Zbl 1238.90128
[28] Johnson, D.; McGeoch, L.; Experimental Analysis of Heuristics for the STSP; The Traveling Salesman Problem and Its Variations: Boston, MA, USA 2007; ,369-443. · Zbl 1113.90356
[29] Johnson, D.S.; McGeoch, L.A.; The traveling salesman problem: A case study in local optimization; Local Search Comb. Optim.: 1997; Volume 1 ,215-310. · Zbl 0947.90612
[30] Golden, B.; Bodin, L.; Doyle, T.; Stewart, W.; Approximate traveling salesman algorithms; Oper. Res.: 1980; Volume 28 ,694-711. · Zbl 0447.90081
[31] Azar, Y.; Lower bounds for insertion methods for TSP; Comb. Probab. Comput.: 1994; Volume 3 ,285-292. · Zbl 0811.90106
[32] Rosenkrantz, D.J.; Stearns, R.E.; Lewis, P.M.; An analysis of several heuristics for the traveling salesman problem; SIAM J. Comput.: 1977; Volume 6 ,563-581. · Zbl 0364.90104
[33] Hurkens, C.A.; Nasty TSP instances for farthest insertion; Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference: Pittsburgh, PA, USA 1992; .
[34] Cronin, T.M.; ; Maintaining Incremental Optimality When Building Shortest Euclidean Tours (No. CSWD-92-TRF-0042): Warrenton, VA, USA 1990; .
[35] Mladenović, N.; An efficient general variable neighborhood search for large travelling salesman problem with time windows; Jugoslav J. Oper. Res.: 2016; Volume 23 ,19-30.
[36] Ariyasingha, I.D.; Fernando, T.G.; Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem; Swarm Evol. Comput.: 2015; Volume 23 ,11-26.
[37] Gendreau, M.; Hertz, A.; Laporte, G.; New insertion and postoptimization procedures for the traveling salesman problem; Oper. Res.: 1992; Volume 40 ,1086-1094. · Zbl 0767.90087
[38] Chisman, J.A.; The clustered traveling salesman problem; Comput. Oper. Res.: 1975; Volume 2 ,115-119.
[39] Jongens, K.; Volgenant, T.; The symmetric clustered traveling salesman problem; Eur. J. Oper. Res.: 1985; Volume 19 ,68-75. · Zbl 0553.90100
[40] Mulder, S.; Wunsch, D.; Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks; Neural Netw.: 2003; Volume 16 ,827-832.
[41] Applegate, D.; Cook, W.; Solving large-scale matching problems; Network Flows and Matching: First DIMACS Mathematical Problems in Engineering 7 Implementation Challenge: Providence, RI, USA 1993; ,557-576. · Zbl 0788.90059
[42] Verhoeven, M.G.A.; Aarts, E.H.L.; Swinkels, P.C.J.; A parallel 2-opt algorithm for the traveling salesman problem; Future Gener. Comput. Syst.: 1995; Volume 11 ,175-182.
[43] Karp, R.M.; Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane; Math. Oper. Res.: 1977; Volume 2 ,209-224. · Zbl 0391.90091
[44] Bentley, J.J.; Fast algorithms for geometric traveling salesman problems; ORSA J. Comput.: 1992; Volume 4 ,387-411. · Zbl 0758.90071
[45] El-Samak, A.F.; Ashour, W.; Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm; J. Artif. Intell. Soft Comput. Res.: 2015; Volume 5 ,239-245.
[46] Phienthrakul, T.; Clustering evolutionary computation for solving travelling salesman problems; Int. J. Adv. Comput. Sci. Inf. Technol.: 2014; Volume 3 ,243-262.
[47] Psychas, I.D.; Delimpasi, E.; Marinaki, Y.; Hybrid evolutionary algorithms for the multiobjective traveling salesman problem; Expert Syst. Appl.: 2015; Volume 42 ,8956-8970.
[48] Bednarik, L.; Kovács, L.; Efficiency analysis of quality threshold clustering algorithms; Prod. Syst. Inf. Eng.: 2012; Volume 6 ,1275-1285.
[49] Garnier, R.; Taylor, J.; ; Discrete Matrhematics for New Technolology: Bristol, UK 2001; .
[50] Sugar, C.A.; James, G.M.; Finding the number of clusters in a dataset: An information-theoretic approach; J. Am. Stat. Assoc.: 2003; Volume 98 ,750-763. · Zbl 1046.62064
[51] Haroun, S.A.; Jamal, B.; Hicham, E.H.; A Performance Comparison of GA and ACO Applied to TSP; Int. J. Comput. Appl.: 2015; Volume 117 ,28-35.
[52] Richter, D.; Goldengorin, B.; Jäger, G.; Molitor, P.; Improving the efficiency of Helsgaun’s Lin-Kernighan heuristic for the symmetric TSP; Proceedings of the Workshop on Combinatorial and Algorithmic Aspects of Networking: ; ,99-111. · Zbl 1136.90462
[53] Walshaw, C.; ; A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem: London, UK 2001; .
[54] Ma, F.M.; Guo, Y.J.; Yi, P.T.; Cluster-reliability-induced OWA operators; Int. J. Intell. Syst.: 2017; Volume 32 ,823-836.
[55] Rousseeuw, P.J.; Kaufman, L.; Finding groups in data; Ser. Probab. Math. Stat.: 2003; Volume 34 ,111-112.
[56] Tibshirani, R.; Walther, G.; Hastie, T.; Estimating the number of clusters in a data set via the gap statistic; J. R. Stat. Soc. Ser. B (Stat. Methodol.): 2001; Volume 63 ,411-423. · Zbl 0979.62046
[57] Kass, R.E.; Raftery, A.E.; Bayes factors; J. Am. Stat. Assoc.: 1995; Volume 90 ,773-795. · Zbl 0846.62028
[58] Yang, X.; Kong, F.; Xu, W.; Liu, B.; Gaussian mixture density modeling and decomposition with weighted likelihood; J. Men’s Health: 2004; Volume 5 ,4245-4249.
[59] Liu, Y.; Li, Z.; Xiong, H.; Gao, X.; Wu, J.; Understanding of internal clustering validation measures; Proceedings of the 2010 IEEE International Conference on Data Mining: ; ,911-916.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.