Mahmoodi Darani, N., Dolatnejad, A., Yousefikhoshbakht, M. (2015). A reactive bone route algorithm for solving the traveling salesman problem. Journal of Industrial Engineering and Management Studies, 2(2), 13-25.

N. Mahmoodi Darani; A. Dolatnejad; M. Yousefikhoshbakht. "A reactive bone route algorithm for solving the traveling salesman problem". Journal of Industrial Engineering and Management Studies, 2, 2, 2015, 13-25.

Mahmoodi Darani, N., Dolatnejad, A., Yousefikhoshbakht, M. (2015). 'A reactive bone route algorithm for solving the traveling salesman problem', Journal of Industrial Engineering and Management Studies, 2(2), pp. 13-25.

Mahmoodi Darani, N., Dolatnejad, A., Yousefikhoshbakht, M. A reactive bone route algorithm for solving the traveling salesman problem. Journal of Industrial Engineering and Management Studies, 2015; 2(2): 13-25.

A reactive bone route algorithm for solving the traveling salesman problem

^{1}Young Researchers And Elite club, Robatkarim Branch, Islamic Azad University, Robatkarim, Iran.

^{2}Young Researchers & Elite Club, Tehran North Branch, Islamic Azad University, Tehran, Iran.

^{3}Bu-Ali Sina University, Hamedan, Iran.

Abstract

The traveling salesman problem (TSP) is a well-known optimization problem in graph theory, as well as in operations research that has nowadays received much attention because of its practical applications in industrial and service problems. In this problem, a salesman starts to move from an arbitrary place called depot and after visits all of the nodes, finally comes back to the depot. The objective is to minimize the total distance traveled by the salesman. Because this problem is a non-deterministic polynomial (NP-hard) problem in nature, it requires a non-polynomial time complexity at runtime to produce a solution. Therefore, a reactive bone route algorithm called RBRA is used for solving the TSP in which several local search algorithms as an improved procedure are applied. 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 to other meta-heuristic algorithms.

Ahmadvand, M., YousefiKhoshbakht, M. and Mahmoodi Darani, 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. and Munlin, M. 2015, “Using K-means Radius Particle Swarm Optimization for the Travelling Salesman Problem”, IETE Technical Review, 1-9.

Barketau, M. and Pesch, E. 2015, “An approximation algorithm for a special case of the asymmetric travelling salesman problem”, International Journal of Production Research, DOI: 10.1080/00207543.2015.1113327.

Carpaneto G. and Toth P. 1980, “Some new branching and bounding criteria for the asymmetric travelling salesman problem”, Management Science, 26, 736-743.

Chen, S. M. and Chien, C. Y. 2011, “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), 14439-14450.

Chen, X., Tan, Z., Yang, G. and Cheng, W. 2012, “A hybrid algorithm to solve traveling salesman problem, In Advances in Electronic Engineering”, Communication and Management, 1, 99-105. Springer Berlin Heidelberg.

Clarke, G. and Wright, J.W., 1964, ‘Scheduling of vehicles from a central depot to a number of delivery points’, Operations Research, 12, 568-581.

Cochrane, E. M. and Beasley, J. E., 2003, “The co-adaptive neural network approach to the Euclidean traveling salesman problem”, Neural Networks, 16(10), 1499–1525.

Dorigo, M., Maniezzo, V. and 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.

Garey, M.R. and Johnson, D.S., 1979, “Computers and intractability: A guide to the theory of NP-completeness”, San Francisco: W.H. Freeman.

Gillett, B.E. and Miller, L.R., 1974, “A heuristic algorithm for the vehicle dispatch problem”, Operations Research, 22, 340-349.

Gutin, G. and Punnen, A., 2002, “The Traveling Salesman Problem and its Variations”, Kluwer Academic Publishers, Dordrecht.

Jaafar, A. and Samsudin, A., 2013, “An Improved Version of the Visual Digital Signature Scheme”, The International Arab Journal of Information Technology, 10(6), 20-32.

Jia, H., 2015, “A novel hybrid optimization algorithm and its application in solving complex problem”, International Journal of Hybrid Information Technology, 8(1), 1–10.

Johnson D.S. and McGeoch L.A., 2002, “Experimental analysis of heuristics for the STSP, in G. Gutin and A.P. Punnen (eds.)”, The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers, The Netherlands, 369–443.

Karp, R. M., 1997, “Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane”, Mathematics of Operations Research, 2, 209-224.

Lin S., 1965, “Computer solutions of the traveling salesman problem”, Bell System Technical Journal, 44, 2245-2269.

Masehian, E., Akbaripour H. and Mohabbati-Kalejahi N. 2014, “Solving the n-Queens Problem using a Tuned Hybrid Imperialist Competitive Algorithm”, The International Arab Journal of Information Technology, 11(6).

Masutti, T. A. S. and Castro, L. N. D., 2009, “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem”, Information Sciences, 179(10), 1454–1468.

Masutti, T. A. S. and Castro, L. N., 2009, “Neuroimmune approach to solve routing problems”, Neurocomputing, 72, 2189–2197.

Odili, J. B. and Mohmad Kahar, M. N., 2016, “Solving the Traveling Salesman’s Problem Using the African Buffalo Optimization”. Computational Intelligence and Neuroscience, 2016

Reeves C. R., 1993, editor. “Modern Heuristic Techniques for Combinatorial Problems”, Blackwell Scientific Publishing, Oxford, England.

Tarantilis, C.D., Zachariadis, E. and Kiranoudis, C., 2008, “A guided Tabu search for the heterogeneous vehicle routing problem”, Journal of the Operational Research Society, 59, 1659-1673.

Tarkov, M. S., 2015, “Solving the traveling salesman problem using a recurrent neural network”, Numerical Analysis and Applications, 8(3), 275-283.

Yang, J., Ding, R., Zhang, Y., Cong, M., Wang, F. and Tang, G., 2015, “An improved ant colony optimization (I-ACO) method for the quasi travelling salesman problem (Quasi-TSP)”, International Journal of Geographical Information Science, 29(9), 1534-1551.

Yousefikhoshbakht M., Didehvar F. and 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. and Sedighpour, M., 2012, “A Combination of Sweep Algorithm and Elite Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem”, Proceedings of the Romanian academy A, 13(4), 295-302.

Zhong W., Zhang J. and Chen, W., 2007, “A novel discrete particle swarm optimization to solve traveling salesman problem”, Evolutionary Computation, 3283–3287.