A Hybrid Modified Meta-heuristic Algorithm for Solving the Traveling Salesman Problem

Document Type : Research Paper


1 Department of Mathematics, Payame Noor University, Tehran, Iran

2 Young Researchers & Elites Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran

3 Department of Mathematics and Computer Science, Amirkabir University of Technology


The traveling salesman problem (TSP) is one of the most important combinational optimization problems that have nowadays received much attention because of its practical applications in industrial and service problems. In this paper, a hybrid two-phase meta-heuristic algorithm called MACSGA used for solving the TSP is presented. At the first stage, the TSP is solved by the modified ant colony system (MACS) in each iteration, and at the second stage, the modified genetic algorithm (GA) and 2-opt local search are used for improving the solutions of the ants for that iteration. This process avoids the premature convergence and makes better solutions. Computational results on several standard instances of TSP show the efficiency of the proposed algorithm compared with the GA, ant colony optimization and other meta-heuristic algorithms. 


Main Subjects

Ahmadvand, M., YousefiKhoshbakht, M., &MahmoodiDarani, N. (2012).Solving the Traveling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm.Journal of Advances in Computer Research, 3(3), 75-84.
Anantathanavit, M., &Munlin, M. (2015).Using K-means Radius Particle Swarm Optimization for the Travelling Salesman Problem. IETE Technical Review, 1-9.
Balachandar, S. R., & Kannan, K. (2007).Randomized gravitational emulation search algorithm for symmetrictraveling salesmanproblem. Applied Mathematics and Computation, 192(2), 413-421.
Battarra, M., & Pessoa, A. A. (2014). Subramanian, A., Uchoa, E., Exact algorithms for the traveling salesman problem with draft limits. European Journal of Operational Research, 235(1), 115-128.
Dorigo, M., Maniezzo, V., &Colorni, A. (1996).Ant System: Optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man, and Cybernetics—Part B, 26(1), 29-41.
Glover, F. (1986).Future paths for integer programming and links to artificial intelligence.Computer Operation Research, 13, 533.549.
Hernandez-Perez, H., Rodríguez-Martín, I., & Salazar-Gonzalez, J. J. (2009).Ahybrid GRASP/VND heuristic for the one-commodity pickup-and-deliverytravelingsalesman problem.Computers & Operations Research, 36(5), 1639-1645.
Karapetyan, D., &Gutin, G. (2011).Lin-Kernighan Heuristic Adaptations for the GeneralizedTravelingSalesmanProblem.European Journal of Operational Research, 208(3), 221-232.
Lin, S. (1965). Computer solutions of the traveling salesman problem.Bell System Technical Journal, 44, 2245-2269.
Marinakis, Y., &Marinaki, M. (2010).AHybrid Multi-Swarm Particle Swarm Optimization algorithm for the ProbabilisticTravelingSalesmanProblem.Computers & Operations Research, 37(3), 432-442.
Odili, J. B., &MohmadKahar, M. N. (2016).Solving the Traveling Salesman’s Problem Using the African Buffalo Optimization. Computational Intelligence and Neuroscience.
Qinghong, WU.,&Jihui, Z. (1999). ACO with the characteristic of Mutation, Computer research and development, 240-245.
Sedighpour, M., YousefiKhoshbakht, M., &MahmoodiDarani, N. (2011). An Effective Genetic Algorithm for Solving the Multiple Traveling Salesman Problem. Journal of optimization in Industrial Engineering, 4(8), 73-79.
Tsai, C. F.,&Tsai.C.W. (2002).A new approach for solving large traveling salesman problem using evolution ant rules,  in Neural Networks, IJCNN 2002, Proc. of the 2002 Int’l Joint Conf., Honolulu, IEEE Press, 540-1545.
Wong, L. P., Low, M. Y. H., & Chong, C. S. (2008). A bee colony optimization algorithm for traveling salesman problem. Modeling & Simulation, 2008.AICMS 08.Second Asia International Conference, 818–823.
Xiao, M., &Nagamochi, H. (2016).An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4. Theory of Computing Systems, 58(2), 241-272.
YousefiKhoshbakht, M., Didehvar, F., & Rahmati, F. (2013). Modification of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem, Romanian Journal of information science and technology, 16(1), 65–80.
Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2014).Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm. International Journal of Production Research, 52(9), 2565-2575.
YousefiKhoshbakht, M., &Sedighpour, M. (2012).A New Imperialist Competitive Algorithm to Solve the Traveling Salesman Problem.International Journal of Computer Mathematics, 90(7), 1495-1505.
YousefiKhoshbakht, M., Sedighpour, M., &Mahmoodabadi, E. (2011).A Modified Elite ACO Based Avoiding Premature Convergence for Traveling Salesman Problem. Journal of Industrial Engineering International, 7(15), 68-75.
Zhong, W., Zhang, J., & Chen, W. (2007). A novel discrete particle swarm optimization to solve traveling salesman problem. Evolutionary Computation, 3283–3287.