×

zbMATH — the first resource for mathematics

Coordinating particle swarm optimization, ant colony optimization and \(K\)-Opt algorithm for traveling salesman problem. (English) Zbl 1446.90137
Giri, Debasis (ed.) et al., Mathematics and computing. Third international conference, ICMC 2017, Haldia, India, January 17–21, 2017. Proceedings. Singapore: Springer. Commun. Comput. Inf. Sci. 655, 103-119 (2017).
Summary: This paper combines the features of swap sequence and swap operation based Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) and \(K\)-Opt operation, a hybrid algorithm, is proposed to solve the well-known Traveling Salesman Problem (TSP). The interchange of two cities of a path of a TSP is known as a swap operation and a sequence of such operations is called a swap sequence. Using swap operation and swap sequence PSO operations are redefined to solve TSP. Here ACO is used a small number of iterations to generate an initial swarm of PSO. Then PSO operations are made on this swarm a sufficient number of times to find optimal path. During PSO iterations if a particle does not change its position for a predefined number of iterations then \(K\)-Opt operation is made on it a finite number of times to improve its position. The algorithm is tested with bench mark test problems from TSPLIB and it is observed that the algorithm is more efficient with respect to accuracy as well as execution time to solve standard TSPs (Symmetric as well as Asymmetric) compared to existing algorithms. Details of the proposed algorithm along with swap operation, swap sequence and K-opt operation for the algorithm are elaborately discussed for the readers.
For the entire collection see [Zbl 1411.65007].
MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
LKH; TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akhand, M.A.H., Akter, S., Rashid, M.A.: Velocity tentative particle swarm optimization to solve TSP. In: 2013 International Conference on Electrical Information and Communication Technology (EICT), pp. 1-6. IEEE Conference Publications (2014)
[2] Angeline, P.J.: Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Porto, V.W., Saravanan, N., Waagen, D., Eiben, A.E. (eds.) EP 1998. LNCS, vol. 1447, pp. 601-610. Springer, Heidelberg (1998). doi:10.1007/BFb0040811
[3] Bontoux, B., Feillet, D.: Ant colony optimization for the traveling purchaser problem. Comput. Oper. Res. 35(2), 628-637 (2008) · Zbl 1141.90036
[4] Changdar, C., Mahapatra, G.S., Pal, R.: An efficient genetic algorithm for multi-objective solid traveling salesman problem under fuzziness. Swarm Evol. Comput. 15, 27-37 (2014)
[5] Chen, S.M., Chien, C.Y.: Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst. Appl. 38, 14439-14450 (2011)
[6] Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of large scale traveling salesman problem. Oper. Res. 2, 393-410 (1954) · Zbl 1414.90372
[7] Dorigo, M., Di Caro, G.: The ant colony optimization meta-heuristic. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 11-32. McGraw-Hill, London (1999)
[8] Dorigo, M., Gambardella, L.M.: Ant colonies for the traveling salesman problem. Biosystems 43, 73-81 (1997)
[9] Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part-B Cybern. 26(1), 29-41 (1996)
[10] Eberhart, R., Kennedy, J.: A new optimizer using particles swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine, Human Science, Nagoya, Japan, pp. 39-43. IEEE Service Center, Piscataway (1995)
[11] Fan, H.: Discrete particle swarm optimization for TSP based on neighborhood. J. Comput. Inf. Syst. (JCIS) 6, 3407-3414 (2010)
[12] Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. 14, 403-417 (2002) · Zbl 1238.90054
[13] Geng, X.T., Chen, Z.H., Yang, W., Shi, D.Q., Zhao, K.: Solving the traveling sales-man problem based on an adaptive simulated annealing algorithm with greedy search. Appl. Soft Comput. 11(4), 3680-3689 (2011)
[14] Guchhait, P., Maiti, M.K., Maitia, M.: Two storage inventory model of a deteriorating item with variable demand under partial credit period. Appl. Soft Comput. 13, 428-448 (2013)
[15] Guchhait, P., Maiti, M.K., Maitia, M.: Inventory model of a deteriorating item with price and credit linked fuzzy demand: a fuzzy differential equation approach. Oper. Res. Soc. India 51(3), 321-353 (2013) · Zbl 1332.90010
[16] Gunduz, M., Kiran, M.S., Ozceylan, E.: A hierarchic approach based on swarm intelligence to solve traveling salesman problem. Turk. J. Electr. Eng. Comput. Sci. 23, 103-117 (2015)
[17] Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1, 119-163 (2009) · Zbl 1180.90269
[18] Ibaraki, T., Imahori, S., Kubo, M., Masuda, T., Uno, T., Yagiura, M.: Effective local search algorithm for routing and scheduling problems with general time window constraints. Transp. Sci. 39(2), 206-232 (2005)
[19] Junqiang, W., Aijia, O.: A hybrid algorithm of ACO and delete-cross method for TSP. In: 2012 International Conference on Industrial Control and Electronics Engineering (ICICEE), pp. 1694-1696. IEEE (2012)
[20] Jolai, F., Ghanbari, A.: Integrating data transformation techniques with Hopfield neural networks for solving traveling salesman problem. Expert Syst. Appl. 37, 5331-5335 (2010)
[21] Karaboga, D., Gorkemli, B.: A combinatorial artificial bee colony algorithm for traveling salesman problem. In: 2011 International Symposium on Innovations in Intelligent Systems and Applications, Istanbul, Turkey
[22] Kennedy, J., Eberhart, R.: Particle swarm optimization. IEEE Int. Conf. Neural Netw. 4, 1942-1948 (1995)
[23] Khanra, A., Maiti, M.K., Maiti, M.: Profit maximization of TSP through a hybrid algorithm. Comput. Ind. Eng. 88, 229-236 (2015)
[24] Lopez-Ibanez, M., Blum, C.: Beam-ACO for the traveling salesman problem with time windows. Comput. Oper. Res. 37(9), 1570-1583 (2010) · Zbl 1190.90165
[25] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985) · Zbl 0562.00014
[26] Liang, J.J., Qin, A.K., Suganthan, P.N., Baskar, S.: Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. J. Evol. Comput. 10(3), 281-295 (2006)
[27] Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21(2), 498-516 (1973) · Zbl 0256.90038
[28] Majumdar, J., Bhunia, A.K.: Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. J. Comput. Appl. Math. 235(9), 3063-3078 (2011) · Zbl 1210.65113
[29] Mavrovouniotis, M., Yang, S.: Ant colony optimization with immigrants schemes for the dynamic traveling salesman problem with traffic factors. Appl. Soft Comput. 13(10), 4023-4037 (2013)
[30] Mahi, M., Baykan, O.K., Kodaz, H.: A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman Problem. Appl. Soft Comput. 30, 484-490 (2015)
[31] Masutti, T.A.S., de Castro, L.N.: A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf. Sci. 179(10), 1454-1468 (2009)
[32] Miliotis, P.: Using cutting planes to solve the symmetric travelling salesman problem. Math. Program. 15, 177-188 (1978). North-Holland Publishing Company · Zbl 0393.90059
[33] Moon, C., Kim, J., Choi, G., Seo, Y.: An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur. J. Oper. Res. 140, 606-617 (2002) · Zbl 0998.90066
[34] Nguyen, H.D., Yoshihara, I., Yamamori, K., Yasunaga, M.: Implementation of an effective hybrid GA for large scale traveling salesman problem. IEEE Trans. Syst. Man Cybern. Part-B Cybern. 37(1), 92-99 (2007)
[35] Othman, Z.A., Srour, A.I., Hamdan, A.R., Ling, P.Y.: Performance water flow-like algorithm for TSP by improving its local search. Int. J. Adv. Comput. Technol. 5(14), 126 (2013)
[36] Petberg, M.W., Homg, S.: On the symmetric traveling salesman problems: a computational study. Math. Program. Stud. 12, 87-107 (1980)
[37] Pasti, R., De Castro, L.N.: A Neuro-immune network for solving the traveling salesman problem. In: Proceedings of International Joint Conference on Neural Networks, IJCNN 2006, pp. 3760-3766 (2006)
[38] Petersen, H.L., Madsen, O.B.G.: The double traveling salesman problem within multiple stack formulation and heuristic solution approaches. Eur. J. Oper. Res. 198, 339-347 (2009) · Zbl 1163.90816
[39] Padberg, M., Rinaldi, G.: Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6(1), 1-7 (1987) · Zbl 0618.90082
[40] Sierksma, G.: Hamiltonicity and the 3-OPT procedure for the traveling salesman problem. Appl. Math. 22(2), 351-358 (2014) · Zbl 0818.90126
[41] Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C., Wang, Q.X.: Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf. Process. Lett. 103(5), 169-176 (2007) · Zbl 1187.90238
[42] Tsai, C.F., Tsai, C.W., Tseng, C.C.: A new hybrid heuristic approach for solving large traveling salesman problem. Inf. Sci. 166, 67-81 (2004) · Zbl 1076.90063
[43] Wang, K.P., Huang, L., Zhou, C.G., Pang, W.: Particle swarm optimization for traveling salesman problem. Int. Conf. Mach. Learn. Cybern. 3, 1583-1585 (2003)
[44] Yan, X.
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.