Meta-Heuristic Solution Approaches for Traveling Salesperson Problem

Year 2018, Volume: 6 Issue: 3, 21 - 26, 30.09.2018

Omar Mohammed Ahmed Ahmed Humar Kahramanlı

Abstract

The traveling salesperson problem (TSP) is the NP-hard optimization
problems which have been widely studied over the past years. TSP creates a
Hamiltonian cycle where each node is visited once and only once to minimize the
total traveled distance. TSPs are difficult to be solved using classical
mathematical methods. Even with nowadays computers solving TSP problems with
these methods takes very plenty of time. Therefore, many efficient optimization
methods have been focused for academic proposes for the TSP all the times. Most
of the TSP problems are now solved by meta-heuristic methods, that provides a
satisfactory solutions in real-time. Meta-heuristic algorithms were inspired
from behaviors of animals and insects such as ants, bees, fish schools, bird
flocks and mammals.This paper focuses on three meta-heuristic methods: Whale
Optimization Algorithm (WOA), Particle Swarm Optimization (PSO) algorithm and
Grey Wolf Optimizer (GWO). The problem for application was selected from
TSPLIB. Probably the best implemented solutions were Whale Optimization
Algorithm and Grey Wolf Optimizer which can be recommended as primary algorithm
to solve the TSP or to start with the meta-heuristic solution

Keywords

Travelling salesperson problem, Meta-heuristic optimization, Whale Optimization Algorithm, Grey Wolf Optimizer, Particle Swarm Optimization

References

• J.H. Holland, “Adaptation in Natural and Artificial Systems”, The MIT Press, 1992. D. Bookstaber, “Simulated Annealing for Traveling Salesman Problem”, 1997. F. Glover, E. Tilliard, D.E. Werra, “A user’s guide to Tabu Search, Annals of Operations Research”, 41, 3-28,1993. M. Doroto, M. Gambardella, “Ant colonies for the traveling salesman problem”, IRIDIA, Université Libre de Bruxelles, Belgium. P. A. Moscato, “On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Toward Memetic Algorithms,” Caltech, Pasadena, CA, Tech. Rep. California Technical Institute concurrent computation program report 826, 1989. K.V. Frisch, "Decoding the language of the bee," Science, vol. 185, no. 4152, pp. 663 - 668, 1974. X.S. Yang, X.-S., “Firefly algorithms for multimodal optimization”, International symposium on stochastic algorithms, 169-178, 2009. X.S. Yang,, “Nature-inspired Metaheuristic Algorithm”. Luniver Press, 2nd Edition 2010. D.S.Huang, Ji-XiangDu, “A constructive hybrid structure optimization method ology for radial basis probabilistic neural networks”, IEEET.NeuralNetw19 (2008) 2099–2115. X. Liu, C. Xiu, “A novel hysteretic chaotic neural network and its applications”, Neurocomputing, 70 (13-15), 2561-2565, 2007. F. Han, Qing-Hua Ling, D.S. Huang, “An improved approximation approach incorporating particle swarm optimization and a priori information into neural networks”, NeuralComput.Appl19, 255–261, 2010. H. A. Abbass, “MBO: Marriage in honey bees optimization –a haplometrosis polygynous swarming approach”, In: Proceedings of the 2001 congress on evo- lutionary computation, p. 207–14, 2001. J. Huant, D. Cooke, “Learning using an artificial immune system”, J.Netw. Comput. Appl, 189–212, 1996. G.A. Croes, “A method for solving traveling salesman problem”, Oper.Res6, 791–812, 1958. S. Lin, “Computer solutions of the traveling salesman problem”, BellSyst.Tech.J 44, 2245–2269, 1965. S. Lin, B.W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem”, Oper.Res 21 498–516, 1973. K. Helsgaun, “An effective implementation of the lin-lemighan traveling salesman heuristic”, Eur.J.Oper.Res12, 106–130, 2000. G. Tao, Z. Michalewicz,”Evolutionary Algorithms for the TSP, Parallel Problem Solving from Nature”, 1498, 803-812, 1998. E.L. Lawler, D.E Wood, “Branch-and-bound methods: A survey”, Operations research, 14 (4), 699-719, 1966. R.E. Bellman, S.E. Dreyfus, “Applied Dynamic Programming”, Princeton University Press, Princeton, New Jersey, 1962. P. Merz, B Freisleben, “Genetic local search for the TSP: new results”, Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pp.159-163, 1997. J.H. Yang, X.H.Shi, M.Marchese, “An ant colony optimization method for generalized TSP problem”, Prog.Nat.Sci18, 1417–1422, 2008. F. Samanlioglu W.G.Ferrell Jr, M.E.Kurz, “A memetic random key genetic algorithm for a symmetric multi-objective traveling salesman problem”, Computers & Industrial Engineering Volume 55, Issue 2, September 2008, Pages 439-449 S. Mirjalili, S.M. Mirjalili, A. Lewis, “Grey wolf optimizer”, Adv Eng Softw 2014;69:46–61. L.D. Mech “Alpha status, dominance, and division of labor in wolf packs”. Can J Zool,77:1196–203, 1999. C. Muro, R. Escobedo, L. Spector, R. Coppinger, “Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations”, Behav Process, 88:192–7, 2011. S. Mirjalili, A. Lewis, ”The whale optimization algorithm”, Advances in Engineering Software, 95, 51-67, 2016. W. A. Watkins, W.E. Schevill,”Aerial observation of feeding behavior in four baleen whales: Eubalaena glacialis, Balaenoptera borealis, Megaptera novaean-gliae, and Balaenoptera physalus”, J Mammal, 155–63, 1979 . J.A. Goldbogen, A.S. Friedlaender, J. Calambokidis, M.F. Mckenna, M. Simon, D.P. Nowacek, “Integrative approaches to the study of baleen whale diving behavior, feeding performance, and foraging ecology”. BioScience, 63:90–100, 2013. J. Kennedy, R. Eberhart, “Particle swarm optimization,” in IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948, 1995. K.P. Wang, L. Huang, C.-G. Zhou, W. Pang, ”Particle swarm optimization for traveling salesman problem,” in Machine Learning and Cybernetics, 2003 International Conference on, pp. 1583-1585, 2003. G. Reinelt,”TSPLIB http://www.iwr.uni-heidelberg.de/groups/ comopt/software,” TSPLIB95, 1995, last accessed December, 2016. M. Bouzidi, M.E. Riffi, “Adaptation of the Harmony Search Algorithm to Solve the Travelling Salesman Problem”, Journal of Theoretical & Applied Information Technology, 62 (1). E. Osaba, X.S. Yang, F. Diaz, P. Lopez-Garcia, R. Carballedo, “An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems”, Engineering Applications of Artificial Intelligence, 48, 59-71, 2016. I. Mzili, M.E. RIFFI, “Discrete penguins search optimization algorithm to solve the traveling salesman problem”, Journal of Theoretical & Applied Information Technology, 72 (3), 2015 A. Bouzidi, M.E. Riffi, “Discrete cat swarm optimization to resolve the traveling salesman problem”, International Journal, 3 (9), 2013. A. Agharghor, M.E. Riffi, “Hunting Search Algorithm to Solve the Traveling Salesman Problem”, Journal of Theoretical & Applied Information Technology, 74 (1), 2015. S. Saud, H. Kodaz, I. Babaoğlu, “Solving Travelling Salesman Problem by Using Optimization Algorithms”, KnE Social Sciences, 3 (1), 17-32, 2018. L. Zhou, L. Ding, X. Qiang,”A multi-population discrete firefly algorithm to solve TSP”, In: Bio-Inspired Computing-Theories and Applications, Eds: Springer, p. 648-653, 2014.