Application a Modified Imperialist Competitive Algorithm for Solving the Traveling Salesman Problem

Authors

1 Young Researchers Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran

2 College of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Abstract

This paper proposes a modified Imperialist Competitive Algorithm (MICA) for solving the Traveling Salesman Problem (TSP) that is different with common Imperialist Competitive Algorithm (ICA) in assimilation policy between Imperialist and colonies countries and revolution of colonies. Furthermore, the 3-opt local search is used for increasing performance of the algorithm. The new ICA algorithm is  tested on nineteen instances of TSBLIB and its performance is compared with  ICA, Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Evolutionary Algorithm (EA) and Bee Colony Optimization (BCO). Extensive computational tests confirm the effectiveness of the proposed approach.

[1] Park, Y.B. (2001), A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines, International Journal of Productions Economics, 73(2), 175–188. مجید یوسفی خوشبخت، فرزاد دیدهور، فرهاد رحمتی 46 [2] Saleh, H.A. and Chelouah R. (2004), The design of the global navigation satellite system surveying networks using genetic algorithms, Engineering Applications of Artificial Intelligence, 17, 111–122.
[3] Chan, D. and Mercier, D. (1989), IC insertion: An application of the traveling salesman problem, International Journal of Production Research, 27, 1837–1841. [4] Lawler, E.L., Lenstra, J.K. and Shmoys D.B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York. [5] Brummit, B. and Stentz, A. (1996), Dynamic mission planning for multiple mobile robots, Proceedings of the IEEE International Conference on Robotics and Automation, 3, 2396-2401.
[6] Zhang, W. (1993), Truncated branch-and-bound: A case study on the asymmetric tsp, in: Working Note of AAAI 1993 Spring Symposium: AI and NP-Hard Problems, Stanford, CA, 160–166. [7] Bektas, T. (2006), The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34, 209 – 219. [8] Yadlapalli S., Malik W.A., Darbhaa S. and Pachter M. (2004),
A Lagrangian-based algorithm for a Multiple Depot, Multiple Traveling Salesmen Problem, Nonlinear Analysis: Real World Applications, 10(4), 1990-1999. [9] Gavish B. and Srikanth K. (1986), An optimal solution method for largescale multiple traveling salesman problems, Operations Research, 34(5), 698–717. [10] Gromicho J., Paixao J. and Branco I. (1992), Exact solution of multiple traveling salesman problems, In: MustafaAkgül, et al., editors.Combinatorial optimization. NATO ASI Series, Berlin: Springer, F82, 291–292. [11] Garey, M.R. and Johnson, D.S. (1979), Computers and intractability: A guide to the theory of NP-completeness, San Francisco: W.H. Freeman. [12] Karp, R.M. (1977), Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane, Mathematics of Operations Research, 2, 209-224. [13] Qu, H., Yi, Z. and Tang, H. (2007), A columnar competitive model for solving multi-traveling salesman problem, Chaos Solitons and Fractals, 31, 1009–1019. [14] Ryan, J.L., Bailey, T.G., Moore J.T. and Carlton W.B. (1998), Reactive Tabu search in unmanned aerial reconnaissance
simulations, Proceedings of the 1998 winter simulation conference, 1, 873–879. کاربرد یک الگوریتم اصلاحی رقابت استعماری برای حل مساله فروشنده دورهگرد 47 [15] Zhang, T., Gruver, W. A. and Smith, M. H. (1999), Team scheduling by genetic search, Proceedings of the second international conference on intelligent processing and manufacturing of materials, 2, 839–844. [16] Prins, C. (2009), Two memetic algorithms for heterogeneous fleet vehicle routing problems, Engineering Applications of Artificial Intelligence, 22, 916–928. [17] Nemati, K., Shamsuddin, S.M. and Saberi Kamarposhti, M. (2011), Using Imperial Competitive Algorithm for Solving Traveling Salesman Problem and Comparing the Efficiency of the Proposed Algorithm with Methods in Use, Australian Journal of Basic and Applied Sciences, 5(10), 540-543. [18] Vasquez, M., Dupont, A. and Habet. D. (2005), Metaheuristics: Progress as real Problem Solvers, MIC-Kluwer. [19] Wang, C.H. and Lu, J.Z. (2009), A hybrid genetic algorithm that optimizes capacitated vehicle routing problems, Expert Systems with Applications, 36, 2921–2936. [20] Zhang, X. and Tang, L. (2009), A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, 30, 848–855. [21] Ai, T. J. and Kachitvichyanukul, V. (2009), Particle swarm optimization and two solution representations for solving the capacitated vehicle
routing problem, Computers & Industrial Engineering, 56, 380–387. [22] Atashpaz-Gargari, E. and Lucas, C. (2007), Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, In: Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, 4661–4667. [23] Kaveh, A. and Talatahari, S. (2010), Optimum design of skeletal structures using imperialist competitive algorithm, Computers & Structures, 88 (21-22), 1220-1229. [24] Niknam, T., Taherian Fard, E., Pourjafarian, N. and Rousta, A. (2011), An efficient hybrid algorithm based on modified imperialist competitive algorithm and K-means for data clustering, Engineering Applications of Artificial Intelligence, 24(2), 306-317. [25] Lucas, C., Nasiri-Gheidari, Z. and Tootoonchian, F. (2010), Application of an imperialist competitive algorithm to the design of a linear induction motor, Energy Conversion and Management, 51(7), 1407- 1411. مجید یوسفی خوشبخت، فرزاد دیدهور، فرهاد رحمتی 48 [26] Rajabioun, R., Atashpaz-Gargari, E. and Lucas, C. (2008), Colonial Competitive Algorithm as a Tool for Nash Equilibrium Point Achievement,
Lecture Notes in Computer Science, 5073, 680-695. [27] Khabbazi, A., Atashpaz-Gargari, E. and Lucas, C. (2009), Imperialist competitive algorithm for minimum bit error rate beamforming, International Journal of Bio-Inspired Computation, 1(1), 125–133. [28] Pellegrini, P. (2005), Application of two nearest neighbor approaches to a rich vehicle routing problem, TR/IRIDIA/2005-15, IRIDIA, Universite Librede Bruxelles, Brussels, Belgium. [29] Ray, S.S., Bandyopadhyay, S. and Pal, S.K. (2004), New operators of genetic algorithms for traveling salesman problem, Proceedings of the 17th International Conference on Pattern Recognition, 2,
497–500. [30] Shen, G. and Zhang, Y.Q. (2011), A new evolutionary algorithm using shadow price guided operators, Applied Soft Computing, 11(2), 1983- 1992. [31] Zhong, W., Zhang, J. and Chen, W. (2007), A novel discrete particle swarm optimization to solve traveling salesman problem, Evolutionary Computation, IEEE Congress on, 3283–3287. [32] Wong, L.P., Low, M.Y.H. and Chong, C.S. (2008), A bee colony optimization algorithm for traveling salesman problem, Modeling & Simulation, AICMS 08. Second Asia International Conference on, 818– 823.