AUTHOR(S): Rodrigo E. MoralesNavarro, Rafael RiveraLopez, Abelardo RodriguezLeon, Marco Antonio CruzChavez, Alina MartinezOropeza

TITLE A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem 
ABSTRACT This paper presents a parallel Variable Neighborhood Search (pVNS) algorithm for solving instances of the Traveling Salesman Problem (TSP). pVSN uses two parallelization levels in order to reach nearoptimal solutions for TSP instances. This parallel approach is evaluated by means of an experimental multiclusters of computers in which the nodes in each cluster uses several threads for calculating the path cost of a candidate solution and a message passing based communication scheme between two clusters is implemented for sharing their solutions. The results obtained indicate that the use of this parallelization scheme leads to an execution time reduction of the VNS method and one near optimal solution is reached due to a best exploitation of the solution space. 
KEYWORDS Variable neighborhood search, parallel algorithm, traveling salesman problem 
REFERENCES [1] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer, 2002. [2] K. Fujisawa, M. Kojima, A. Takeda and M. Yamashita, Solving Large Scale Optimization Problems via Grid and Cluster Computing, Journal of the Operations Research Society of Japan, 47(4), 2004, pp. 265–274. [3] E.G. Talbi, Parallel combinatorial optimization, Wiley, 2006. [4] M. Mezmaz, N. Melab and E.G. Talbi, An efficient load balancing strategy for gridbased branch and bound algorithm, Parallel computing, 33(4), 2007, pp. 302–313. [5] M.A. CruzChavez, A. Rodr ´ ´ıguezLeon, E.Y. ´ Avila ´ Melgar, F. JuarezP ´ erez, M.H. CruzRosales and ´ R. RiveraLopez, GeneticAnnealing Algorithm in Grid Environment for Scheduling Problems, Communications in Computer and Information Science: SecurityEnriched Urban Computing and Smart Grid, Springer, 2010, pp. 1–9. [6] G. Gutin and A.P. Punnen, The traveling salesman problem and its variations, Springer, 2002. [7] V. Zharfi and A. Mirzazadeh, A Novel Metaheuristic for Travelling Salesman Problem, Journal of Industrial Engineering, 2013, 5 pages, 2013. [8] M. Hahsler and K. Hornik, TSP – Infrastructure for the Traveling Salesperson Problem, Journal of Statistical Software, (23)2, pp. 1–21, 2007. [9] D.S. Johnson and L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, Local Search in Combinatorial Optimization, Wiley, pp. 215–310, 1997. [10] S.B. Liu, K.M. Ng and H.L. Ong, A New Heuristic Algorithm for the Classical Symmetric Traveling Salesman Problem, World Academy of Science, Engineering and Technology, 27(48), pp. 34–348 2007. [11] M.K. Rafsanjani, S. Eskandari and A.B. Saeid, A similaritybased mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem, Neural Computing and Applications, 26(1), pp. 213–222, 2015. [12] Y. Lin, Z. Bian and X. Liu, Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing–tabu search algorithm to solve the symmetrical traveling salesman problem. Applied Soft Computing, 49, pp. 937–952, 2016. [13] M.A. CruzChavez, A. Mart ´ ´ınezOropeza and S.A. SernaBarquera, Neighborhood Hybrid Structure for Discrete Optimization Problems, Proc. of IEEE CERMA 2010, pp. 108–113, 2010. [14] E. Mahdi, A Survey of R Software for Parallel Computing, American Journal of Applied Mathematics and Statistics, 2(4), pp. 224–230, 2014. [15] G. Bell and J. Gray, What’s next in highperformance computing?, Communications of the ACM, 45(2), pp. 91–95, 2002. [16] R. RiveraLopez, A. Rodr´ıguezLeon, M.A. Cruz ´ Chavez and I.Y. Hern ´ andezBaez, Tar ´ antula: Una ´ grid de clusters de computo para el desarrollo de apli ´ caciones paralelas y en grid en Mexico, ´ Memorias del Coloquio de Investigacion Multidisciplinaria ´ , Orizaba, MEX, 2011. [17] M.A. CruzChavez, A. Mart ´ ´ınezOropeza, J. del Carmen PeraltaAbarca, M.H. CruzRosales and M. Mart´ınezRangel, Variable Neighborhood Search for Nondeterministic Problems, ICAISC 2014 LNAI 8868, Springer, pp. 468–478, 2014. [18] D.L. Applegate, R.E. Bixby, V. Chvatal, and ´ W.J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press,2006. [19] D.S. Johnson and C.H. Papadimitriou, Computational Complexity, The Traveling Salesman Problem, Wiley, pp. 37–85, 1985. [20] D.B. Fogel, An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, Springer, pp. 139–144, 1988. [21] S. Lin and W. Kernighan, An Effective Heuristic for the Traveling Salesman Problem, Operations Research 21(2), pp. 498–516, 1973. [22] R. GonzalezVel ´ azquez and M.A. BandalaGarc ´ es, ´ Hybrid Algorithm: Scaling Hill and Simulated Annealing to Solve the Quadratic Allowance Problem, Proc. of 3th. LatinIberoamerican Workshop of Operation Research, 2009. [23] J. Pacheco and C. Delgado, Different Experiences Results with Local Search Applied to Path Problem, Electronic Journal of Electronics of Comunications and Works, 2(1), pp. 54–81, 2000. [24] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Algorithms and Complexity, Dover, 1998. [25] D.B. Kenneth, Cost Versus Distance in the Traveling Salesman Problem, Tech Report, UCLA Computer Science Dept, 1995. [26] H.R. Lourenc¸o and O.C. Martin, Iterated Local Search, Handbook of Metaheustics, 57, Springer, pp. 320–353, 2003. [27] O. Martin, S.W. Otto and E.W. Felten, Large Step Markov Chains for the Traveling Salesman Problem, Complex Systems, 5(3), pp. 299–326, 1991. [28] O. Martin, S.W. Otto and E.W. Felten, Large Step Markov Chains for the TSP Incorporating Local Search Heuristics, Operations Reasearch Letters, 11(4), pp. 219–224, 1992. [29] P. Hansen, N. Mladenovic, R. Todosijevi ´ c and ´ S. Hanafi, Variable neighborhood search: basics and variants, EURO Journal on Computational Optimization, pp. 1–32, 2016. 
Cite this paper Rodrigo E. MoralesNavarro, Rafael RiveraLopez, Abelardo RodriguezLeon, Marco Antonio CruzChavez, Alina MartinezOropeza. (2016) A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem. International Journal of Computers, 1, 278283 
