Document Type: Original Article
Authors
- N. Mahmoodi Darani ^{1}
- A. Dolatnejad ^{2}
- M. Yousefikhoshbakht ^{} ^{3}
^{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.
Keywords
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.
Bachir Menai, M. E. and Batouche M. 2005, “Solving the maximum satisfiability problem using an evolutionary local search”, The International Arab Journal of Information Technology, 2(2), 154-161.
Balachandar S. R. and Kannan K. 2007, “Randomized gravitational emulation search algorithm for symmetric traveling salesman problem”, Applied Mathematics and Computation, 192 (2), 413-421.
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.
Bianchi L., Knowles, J. and Bowler, N. 2005, “Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms”, European Journal of Operational Research, 162(1), 206-219.
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.
Cordeau J. F., Dell’Amico, M. and Iori, M., 2010, “Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading”, Computers & Operations Research, 37(5), 970-980.
Créput, J. C, and Koukam, A., 2009, “A memetic neural network for the Euclidean traveling salesman problem”, Neurocomputing, 72(4-6), 1250-1264.
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.
Hernandez-Perez, H., Rodríguez-Martín, I. and Salazar-Gonzalez, J. J., 2009, “A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem”, Computers & Operations Research, 36(5), 1639-1645.
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.
Karapetyan D. and Gutin, G., 2011, “Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem”, European Journal of Operational Research, 208 (3), 221–232.
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.
Liu Y. H., 2007, “A hybrid scatter search for the probabilistic traveling salesman problem”, Computers & Operations Research, 34(10), 2949-2963.
López-Ibáñez M. and Blum C., 2010, “Beam-ACO for the traveling salesman problem with time windows”, Computers & Operations Research, 37(9), 1570-1583.
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.
Michalewicz, Z., 1994, “Genetic Algorithms + Data Structures = Evolution Programs”. Springer-Verlag, 2nd edition.
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.
Reinelt, G., 2012, “Tsplib95”, 1995, http://comopt.ifi.uni-heidelberg. de/software/TSPLIB95.
Shi X. H., Liang Y. C., Lee H. P., Lu C. and Wang, Q.X., 2007, “Particle swarm optimization-based algorithms for TSP and generalized TSP”, Information Processing Letters, 103(5), 169-176.
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.
Thiago A.S., Masutti L. and Castro N., 2009, “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem”, Information Sciences, 179(10), 1454-1468.
Xiao, M., and Nagamochi, H., 2016, “An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4”, Theory of Computing Systems, 58(2), 241-272.
Yadlapalli S., alik W.A., Darbha S. and Pachter M., 2009, “A Lagrangian-based algorithm for a Multiple Depot”, Multiple Traveling Salesmen Problem, Nonlinear Analysis: Real World Applications, 10(4), 1990-1999.
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., 2013, “New Imperialist Competitive Algorithm to solve the travelling salesman problem”, International Journal of Computer Mathematics, 90 (7), 1495-1505.
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.
Wang C., 2010, “A hybrid algorithm based on genetic algorithm and ant colony optimization for Traveling Salesman Problems”, Information Science and Engineering 2nd International Conference on Date of Conference, 4257 – 4260.
Weber B., 2006, “Distributed Hybrid Metaheuristics for Optimization”, Work paper, 1-12.
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, 818–823.
Zhong W., Zhang J. and Chen, W., 2007, “A novel discrete particle swarm optimization to solve traveling salesman problem”, Evolutionary Computation, 3283–3287.