×

Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem. (English) Zbl 1485.90113

Summary: Different algorithmic performances are required in different engineering fields for solving both the symmetric and asymmetric traveling salesman problem (STSP and ATSP), both of which are commonly referred to as TSP. In the background of small-scale TSP, according to the principle of the optimal Hamiltonian loop, this paper describes an angular bisector insertion algorithm (ABIA) that can solve TSP. The main processes of ABIA are as follows. First, the angular bisector of the point group is constructed. Second, the farthest vertex perpendicular to the angular bisector is identified as the search criterion. Finally, for both STSP and ATSP, initial loop formation rules and vertex insertion rules are constructed. Experiments were conducted for all STSP and ATSP instances with up to 100 points in the TSPLIB database. The performance of ABIA was compared with that of the 2-point farthest insertion algorithm, convex hull insertion algorithm, branch-and-bound algorithm, and a genetic algorithm. The experimental results show that, for small-scale TSP (up to 40 points), the runtime of ABIA is second only to the convex hull insertion algorithm, and the gap between ABIA and the optimal solution is second only to the exact algorithm. ABIA offers good overall performance in solving small-scale TSP.

MSC:

90C27 Combinatorial optimization

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, JA; Murty, USR, Graph theory with applications (1976), New York: The Macmillan Press Ltd, New York · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[2] Davis L (1985) Applying adaptive algorithms to epistatic domains. In: Proceedings of the 9th international joint conference on artificial intelligence. Los Angeles, CA, USA. 162-164
[3] De Jong, K.; De Jong, KA, An analysis of the behavior of a class of genetic adaptive systems (1975), Michigan: University of Michigan, Michigan
[4] Dirac, GA, Some theorems on abstract graphs, Proc London Math Soc, s3-2, 69-81 (1952) · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
[5] Ezugwu, AES; Adewumi, AO, Discrete symbiotic organisms search algorithm for travelling salesman problem, Expert Syst Appl, 87, 70-78 (2017) · doi:10.1016/j.eswa.2017.06.007
[6] Golden, B.; Bodin, L.; Doyle, T.; Stewart, W., Approximate traveling salesman algorithms, Oper Res, 28, 694-711 (1980) · Zbl 0447.90081 · doi:10.1287/opre.28.3.694
[7] Gower, JC, Some distance properties of latent root and vector methods used in multivariate analysis, Biometrika, 53, 325-338 (1966) · Zbl 0192.26003 · doi:10.1093/biomet/53.3-4.325
[8] Hore, S.; Chatterjee, A.; Dewanji, A., Improving variable neighborhood search to solve the traveling salesman problem, Appl Soft Comput J, 68, 83-91 (2018) · doi:10.1016/j.asoc.2018.03.048
[9] Hui, W., Comparison of several intelligent algorithms for solving TSP problem in industrial engineering, Syst Eng Proc, 4, 226-235 (2012) · doi:10.1016/j.sepro.2011.11.070
[10] Ismail, AH, Domino algorithm: a novel constructive heuristics for traveling salesman problem, IOP Conf Ser Mater Sci Eng (2019) · doi:10.1088/1757-899X/528/1/012043
[11] Jünger, M.; Reinelt, G.; Rinaldi, G., The traveling salesman problem, Handbooks Oper Res Manag Sci, 7, 225-330 (1995) · Zbl 0832.90118 · doi:10.1016/S0927-0507(05)80121-5
[12] Kanda, J.; de Carvalho, A.; Hruschka, E., Meta-learning to select the best meta-heuristic for the traveling salesman problem: a comparison of meta-features, Neurocomputing, 205, 393-406 (2016) · doi:10.1016/j.neucom.2016.04.027
[13] Ore, O., Note on hamilton circuits, Am Math Mon, 67, 55 (1960) · Zbl 0089.39505 · doi:10.2307/2308928
[14] Pan, G.; Li, K.; Ouyang, A.; Li, K., Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP, Soft Comput, 20, 555-566 (2016) · doi:10.1007/s00500-014-1522-3
[15] Rao, W.; Jin, C., An improved greedy heuristic based on solving traveling salesman problem, Oper Res Manag Sci, 6, 1-9 (2012)
[16] Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA J Comput, 3, 376-384 (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[17] Reinelt, G., The traveling salesman: computational solutions for TSP applications (1994), Berlin, Heidelberg: Springer-Verlag, Berlin, Heidelberg · Zbl 0825.90720
[18] Rosenkrantz, DJ; Stearns, RE; Lewis Ii, PM, An analysis of several heuristics for the traveling salesman problem * under the title approximate algorithms for the traveling salesperson problem, SIAM J Comput, 6, 563-581 (1977) · Zbl 0364.90104 · doi:10.1137/0206041
[19] Sakurai, Y.; Onoyama, T.; Kubota, S., A Multi-world intelligent genetic algorithm to interactively optimize large-scale TSP, Proc 2006 IEEE Int Conf Inf Reuse Integr IRI-2006 (2006) · doi:10.1109/IRI.2006.252421
[20] Siemiński, A.; Kopel, M., Solving dynamic TSP by parallel and adaptive ant colony communities, J Intell Fuzzy Syst, 37, 7607-7618 (2019) · doi:10.3233/JIFS-179366
[21] Ursani, Z.; Corne, DW, Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem, J Optim, 2016, 1-15 (2016) · Zbl 1509.90175 · doi:10.1155/2016/4786268
[22] Xiang, Z.; Chen, Z.; Gao, X., Solving large-scale TSP using a fast wedging insertion partitioning approach, Math Probl Eng (2015) · Zbl 1394.90503 · doi:10.1155/2015/854218
[23] Yang, Z.; Xiao, MQ; Ge, YW, A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods, Eur J Oper Res, 265, 65-80 (2018) · Zbl 1374.90332 · doi:10.1016/j.ejor.2017.07.024
[24] Yang L, Hu X, Li K, et al (2019) Nested simulated annealing algorithm to solve large-scale TSP problem. In: International symposium on intelligence computation and applications. Springer, pp 473-487
[25] Zhang, ZC; Han, W.; Mao, B., Adaptive discrete cuckoo algorithm based on simulated annealing for solving TSP, Acta Electron Sin, 46, 1849-1857 (2018)
[26] Zhong Y, Lin J, Wang L, Hui Z (2018) Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem. Swarm Evol Comput S2210650216304680
[27] Zhu J, Huai L, Cui R (2017) Research and Application of Hybrid Random Selection Genetic Algorithm. In: 2017 10th International Symposium on Computational Intelligence and Design (ISCID). pp 330-333
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.