A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem

AUTHOR(S):

Rodrigo E. Morales-Navarro, Rafael Rivera-Lopez, Abelardo Rodriguez-Leon, Marco Antonio Cruz-Chavez, Alina Martinez-Oropeza

TITLE

A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem

PDF

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 near-optimal solutions for TSP instances. This parallel approach is evaluated by means of an experimental multi-clusters 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 grid-based branch and bound algorithm, Parallel computing, 33(4), 2007, pp. 302–313.

[5] M.A. Cruz-Chavez, A. Rodr ´ ´ıguez-Leon, E.Y. ´ Avila- ´ Melgar, F. Juarez-P ´ erez, M.H. Cruz-Rosales and ´ R. Rivera-Lopez, Genetic-Annealing Algorithm in Grid Environment for Scheduling Problems, Communications in Computer and Information Science: Security-Enriched 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 similarity-based 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. Cruz-Chavez, A. Mart ´ ´ınez-Oropeza and S.A. Serna-Barquera, 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 high-performance computing?, Communications of the ACM, 45(2), pp. 91–95, 2002.

[16] R. Rivera-Lopez, A. Rodr´ıguez-Leon, M.A. Cruz- ´ Chavez and I.Y. Hern ´ andez-Baez, 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. Cruz-Chavez, A. Mart ´ ´ınez-Oropeza, J. del Carmen Peralta-Abarca, M.H. Cruz-Rosales and M. Mart´ınez-Rangel, Variable Neighborhood Search for Non-deterministic 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. Gonzalez-Vel ´ azquez and M.A. Bandala-Garc ´ es, ´ Hybrid Algorithm: Scaling Hill and Simulated Annealing to Solve the Quadratic Allowance Problem, Proc. of 3th. Latin-Iberoamerican 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. Morales-Navarro, Rafael Rivera-Lopez, Abelardo Rodriguez-Leon, Marco Antonio Cruz-Chavez, Alina Martinez-Oropeza. (2016) A Parallel Variable Neighborhood Search Approach for Solving the Traveling Salesman Problem. International Journal of Computers, 1, 278-283