An Improved Unordered Pair Bat Algorithm for Solving the Symmetrical Traveling Salesman Problem

• Autorzy: Nan, Zhang , Zhimin, Lv , Shen, Qiao , Ting, Li
• Języki publikacji: EN

Abstrakty

EN

Bat algorithm is an effective swarm intelligence optimization algorithm which is widely used to solve continuous optimization problems. But it still has some limitations in search process and can’t solve discrete optimization problems directly. Therefore, this paper introduces an unordered pair and proposes an unordered pair bat algorithm (UPBA) to make it more suitable for solving symmetric discrete traveling salesman problems. To verify the effectiveness of this method, the algorithm has been tested on 23 symmetric benchmarks and compared its performance with other algorithms. The results have shown that the proposed UPBA outperforms all the other alternatives significantly in most cases.

Słowa kluczowe

EN

symmetrical traveling salesman problem; discrete bat algorithm; unordered pair bat algorithm

• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2022
• Tom: Vol. 47, No. 1
• Strony: 87--103
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Nan, Zhang

• Collaborative Innovation Center of steel technology, University of Science and Technology Beijing, Beijing, China

autor

Zhimin, Lv

• Collaborative Innovation Center of steel technology, University of Science and Technology Beijing, Beijing, China,

autor

Shen, Qiao

• Collaborative Innovation Center of steel technology, University of Science and Technology, Beijing Beijing, China

autor

Ting, Li

• Beijing Jinghang Research Institute of Computing and Communication Beijing, China

Bibliografia

• [1] Abdel-Raouf O, Abdel-Baset M, El-Henawy I., An improved chaotic bat algorithm for solving integer programming problems, International Journal of Modern Education and Computer Science, 6, 8, 2014, 18.
• [2] Afrabandpey H, Ghaffari M, Mirzaei A, et al., A novel bat algorithm based on chaos for optimization tasks, 2014 Iranian Conference on Intelligent Systems (ICIS), IEEE, 2014, 1-6.
• [3] Al-Sorori, Wedad, A., Mohsen, and Walid Aljoby βer., An Improved Hybrid Bat Algorithm for Traveling Salesman Problem, International Conference on Bio-Inspired Computing: Theories and Applications, Springer, Singapore, 2016: 504-511.
• [4] 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 Systems with Applications, 38, 12, 2011, 14439-14450.
• [5] Cheng H, Yang S, Cao J, Dynamic genetic algorithms for the dynamic load balanced clustering problem in mobile ad hoc networks, Pergamon Press, Inc, 2013.
• [6] Crişan G C, Pintea C M, Palade V., Emergency management using geographic information systems: application to the first romanian traveling salesman problem instance, Knowledge and Information Systems, 50, 1, 2017, 265-285.
• [7] Dorigo M, Di Caro G, Ant colony optimization: a new meta-heuristic, Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), IEEE, 2, 1999, 1470-1477.
• [8] Eberhart R, Kennedy J, Particle swarm optimization, Proceedings of the IEEE international conference on neural networks, 4, 1995, 1942-1948.
• [9] Fischer A, Fischer F, Jäger G, et al., Exact algorithms and heuristic for the quadratic traveling salesman problem with an application in bioinformatics, Discrete Applied Mathematics, 166, 2014, 97-114.
• [10] Fister Jr I, Fister D, Yang X S., A hybrid bat algorithm, arXiv preprint arXiv, 2013,1303.6310.
• [11] Gandomi A H, Yang X S, Alavi A H, Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems, Engineering with computers, 29(1), 2013, 17-35.
• [12] Gandomi A H, Yang X S., Chaotic bat algorithm, Journal of Computational Science, 5(2), 2014, 224-232.
• [13] Glover F, Tabu search - part I, ORSA Journal on computing, 1(3), 1989, 190-206.
• [14] He X, Ding W J, Yang X S., Bat algorithm based on simulated annealing and Gaussian perturbations, Neural Computing and Applications, 25, 2, 2014, 459-468.
• [15] Hoffman K L, Padberg M, Rinaldi G., Traveling salesman problem, Encyclopedia of operations research and management science, Springer US, 2013, 1573 – 1578.
• [16] Lin Y, Bian Z, Liu X., Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing-tabu search algorithm to solve the symmetrical traveling salesman problem, Applied Soft Computing, 49, 2016, 937-952.
• [17] Mahi M, Baykan Ö K, Kodaz H., A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem, Applied Soft Computing, 30, 2015, 484-490.
• [18] Marichelvam M K, Prabaharam T., A bat algorithm for realistic hybrid flowshop scheduling problems to minimize makespan and mean flow time, ICTACT Journal on Soft Computing, 3, 1, 2012, 428-433.
• [19] Marichelvam M K, Prabaharan T, Yang X S, et al., Solving hybrid flow shop scheduling problems using bat algorithm, International Journal of Logistic Economics and Globalisation, 5, 1, 2013, 15-29.
• [20] 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, Information Sciences, 179, 10, 2009, 1454-1468.
• [21] Mirjalili S, Mirjalili S M, Yang X S., Binary bat algorithm, Neural Computing and Applications, 25(3-4), 2014, 663-681.
• [22] Osaba E, Yang X S, Diaz F, et al., An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems, Engineering Applications of Artificial Intelligence, 48, 2006, 59-71.
• [23] Ouaarab A, Ahiod B, Yang X S., Discrete cuckoo search algorithm for travelling salesman problem, Neural Computing and Applications, 24, 7-8, 2014, 1659-1669.
• [24] Pedro O, Saldanha R, Camargo R., A tabu search approach for the prize collecting traveling salesman problem, Electronic Notes in Discrete Mathematics, 41, 2013, 261-268.
• [25] Plateau G, Nagih., A 0-1 Knapsack Problems. Paradigms of Combinatorial Optimization, 2nd Edition, 2010, 215-242.
• [26] Ԛuiroz-Castellanos M, Cruz-Reyes L, Torres-Jimenez J et al., A grouping genetic algorithm with controlled gene transmission for the bin packing problem, Computers & Operations Research, 55, 2015, 52-54.
• [27] Saji Y, Riffi M E., A novel discrete bat algorithm for solving the travelling salesman problem, Neural Computing and Applications, 2015, 1-14.
• [28] Toth, Paolo, and Daniele Vigo, eds., Vehicle routing: problems, methods, and applications, Society for Industrial and Applied Mathematics, 2014.
• [29] Van Laarhoven P J M, Aarts E H L, Simulated annealing, Simulated annealing: Theory and applications, Springer, Dordrecht, 1987, 7-15.
• [30] Wang J, Ersoy O K, He M, et al., Multi-offspring genetic algorithm and its application to the traveling salesman problem, Applied Soft Computing, 43, 2016, 415-423.
• [31] Whitley D, A genetic algorithm tutorial, Statistics and computing, 4(2), 1994, 65-85.
• [32] Yang X S., A new metaheuristic bat-inspired algorithm, Nature inspired cooperative strategies for optimization (NICSO 2010), Springer Berlin Heidelberg, 2010, 65-74.
• [33] Zhou Y, Xie J, Li L, et al., Cloud model bat algorithm, The Scientific World Journal, 2014.

Uwagi

EN

This research is supported by the National Natural Science Foundation of China (grant number 51274043).

Identyfikatory

DOI

10.2478/fcds-2022-0004