Solving the Traveling Salesman Problem Based on The Genetic Reactive Bone Route Algorithm whit Ant Colony System

Majid Yousefikhoshbakht, Nasrin Malekzadeh, Mohammad Sedighpour

Abstract

The TSP is considered one of the most well-known combinatorial optimization tasks and researchers have paid so much attention to the TSP for many years. 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, a hybrid meta-heuristic algorithm called REACSGA is used for solving the TSP. In REACSGA, a reactive bone route algorithm that uses the ant colony system (ACS) for generating initial diversified solutions and the genetic algorithm (GA) as an improved procedure are applied. Since the performance of the Metaheuristic algorithms is significantly influenced by their parameters, Taguchi Method is used to set the parameters of the proposed algorithm. The proposed algorithm is tested on several standard instances involving 24 to 318 nodes from the literature. The computational result shows that the results of the proposed algorithm are competitive with other metaheuristic algorithms for solving the TSP in terms of better quality of solution and computational time respectively. In addition, the proposed REACSGA is significantly efficient and finds closely the best known solutions for most of the instances in which thirteen best known solutions are also found.


Keywords

Reactive Bone Route Algorithm; Genetic Algorithm; Ant Colony System; Traveling Salesman Problem; NP-hard Problems

Full Text:

PDF

References

Balachandar, S. R., Kannan, K. (2007). Randomized gravitational emulation search algorithm for symmetric traveling salesman problem, Applied Mathematics and Computation, 192(2), 413-421. http://dx.doi.org/10.1016/j.amc.2007.03.019

Chen, S. M., 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. http://dx.doi.org/10.1016/j.eswa.2011.04.163

Cordeau, J. F., Dell’Amico, M., Iori, M. (2010). Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading, Computers & Operations Research, 37(5), 970-980. http://dx.doi.org/10.1016/j.cor.2009.08.003

Créput, J. C., Koukam, A. (2009). A memetic neural network for the Euclidean traveling salesman problem, Neurocomputing, 72(4-6), 1250-1264. http://dx.doi.org/10.1016/j.neucom.2008.01.023

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

Hernández-Pérez, H., Rodríguez-Martín, I., Salazar-González, 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. http://dx.doi.org/10.1016/j.cor.2008.03.008

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

Johnson, D.S., 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.

López-Ibáñez, M., Blum, C. (2010). Beam-ACO for the traveling salesman problem with time windows, Computers & Operations Research, 37(9), 1570-1583. http://dx.doi.org/10.1016/j.cor.2009.11.015

Masehian, E., Akbaripour, H., 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., 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. http://dx.doi.org/10.1016/j.ins.2008.12.016

Renaud, J., Fayez, F., Boctor, F. (1998). An efficient composite heuristic for the symmetric generalized traveling salesman problem, European Journal of Operational Research, 108(3), 571-584. http://dx.doi.org/10.1016/S0377-2217(97)00142-2

Rochat, Y., Taillard, E.D. (1995). Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1(1), 47–167. http://dx.doi.org/10.1007/bf02430370

Shi, X. H., Liang Y. C., Lee H. P., Lu C., Wang, Q.X. (2007). Particle swarm optimization-based algorithms for TSP and generalized TSP, Information Processing Letters, 103(5), 169-176. http://dx.doi.org/10.1016/j.ipl.2007.03.010

Tarantilis, C. D., Kiranoudis, C. T. (2002). BoneRoute: An adaptive memory-based method for effective fleet management. Annals of operations Research, 115(1-4), 227-241. http://dx.doi.org/10.1023/A:1021157406318

Tarantilis, C. D., Kiranoudis, C. T. (2007). A flexible adaptive memory-based algorithm for real-life transportation operations: two case studies from dairy and construction sector, European Journal of Operational Research, 179(3), 806-822. http://dx.doi.org/10.1016/j.ejor.2005.03.059

Thiago, A.S., Masutti, L., 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. http://dx.doi.org/10.1016/j.ins.2008.12.016

Yadlapalli, S., Malik, W.A., Darbha, S., Pachter, M. (2009). A Lagrangian-based algorithm for a Multiple Depot, Multiple Traveling SalesmenProblem, Nonlinear Analysis: Real World Applications, 10(4), 1990-1999. http://dx.doi.org/10.1016/j.nonrwa.2008.03.014

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., Sedighpour, M. (2013). New Imperialist Competitive Algorithm to solve the travelling salesman problem, International Journal of Computer Mathematics, 90(7), 1495-1505. http://dx.doi.org/10.1080/00207160.2012.758362

Yousefikhoshbakht, M., 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. The2nd International Conference Information Science and Engineering, 4257-4260. http://dx.doi.org/10.1109/ICISE.2010.5689028

Weber, B. (2006). Distributed Hybrid Metaheuristics for Optimization, Work paper, 1-12.

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. http://dx.doi.org/10.1109/AMS.2008.27

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

Abstract Views

371
Metrics Loading ...

Metrics powered by PLOS ALM


 

Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Annealing Ant Colony Optimization with Mutation Operator for Solving TSP
Abdulqader M. Mohsen
Computational Intelligence and Neuroscience  vol: 2016  first page: 1  year: 2016  
doi: 10.1155/2016/8932896



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317