Roman Bazylevych; Bohdan Kuz; Roman Kutelmakh; Remy Dupas; Bhanu Prasad; Yll Haxhimusa; Lubov Bazylevych

A Parallel Ring Method for Solving a Large-scale Traveling Salesman Problem

Full Text (PDF, 1103KB), PP.1-12

Views: 0 Downloads: 0

Author(s)

Roman Bazylevych ^1,2 Bohdan Kuz ¹ Roman Kutelmakh ¹ Remy Dupas ^3,4 Bhanu Prasad ^5,* Yll Haxhimusa ⁶ Lubov Bazylevych ⁷

1. Lviv Polytechnic National University, Lviv, Ukraine

2. University of Information Technology and Management, Rzeszow, Poland

3. Univ. Bordeaux, IMS, UMR 5218, F-33405 Talence, France

4. CNRS, IMS, UMR 5218, F-33405 Talence, France

5. Department of Computer and Information Sciences, Florida A&M University, Tallahassee, Florida, USA

6. Section of Artificial Intelligence, Medical University of Vienna, Austria and Faculty of Electrical and Computer Engineering, University of Prishtina, Kosova

7. Institute of Applied Problems of Mathematics and Mechanics NASU, Lviv, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2016.05.01

Received: 7 Sep. 2015 / Revised: 4 Jan. 2016 / Accepted: 23 Feb. 2016 / Published: 8 May 2016

Index Terms

TSP, parallelization, combinatorial optimization, clustering

Abstract

A parallel approach for solving a large-scale Traveling Salesman Problem (TSP) is presented. The problem is solved in four stages by using the following sequence of procedures: decomposing the input set of points into two or more clusters, solving the TSP for each of these clusters to generate partial solutions, merging the partial solutions to create a complete initial solution M0, and finally optimizing this solution. Lin-Kernighan-Helsgaun (LKH) algorithm is used to generate the partial solutions. The main goal of this research is to achieve speedup and good quality solutions by using parallel calculations. A clustering algorithm produces a set of small TSP problems that can be executed in parallel to generate partial solutions. Such solutions are merged to form a solution, M0, by applying the "Ring" method. A few optimization algorithms were proposed to improve the quality of M0 to generate a final solution Mf. The loss of quality of the solution by using the developed approach is negligible when compared to the existing best-known solutions but there is a significant improvement in the runtime with the developed approach. The minimum number of processors that are required to achieve the maximum speedup is equal to the number of clusters that are created.

Cite This Paper

Roman Bazylevych, Bohdan Kuz, Roman Kutelmakh, Rémy Dupas, Bhanu Prasad, Yll Haxhimusa, Lubov Bazylevych, "A Parallel Ring Method for Solving a Large-scale Traveling Salesman Problem", International Journal of Information Technology and Computer Science(IJITCS), Vol.8, No.5, pp.1-12, 2016. DOI:10.5815/ijitcs.2016.05.01

Reference

[1]D. Applegate, R. Bixby, V. Chvátal, W. Cook, D. Espinoza, M. Goycoolea and K. Helsgaun, “Certification of an Optimal TSP Tour Through 85,900 Cities”, Operations Research Letters, 37 (2009), pp. 11—15.

[2]D. Applegate, W. Cook, A. Rohe, “Chained Lin-Kernighan for Large Traveling Salesman Problems”, INFORMS J. Comput, 15 (1), pp. 82-92, 2003.

[3]K. Appel, W. Haken, J. Koch, “Every Planar Map is Four Colorable”, Journal of Mathematics, vol. 21, pp. 439-567, 1977.

[4]R. Bazylevych, R. Kutelmakh, B. Prasad, L. Bazylevych, “Decomposition and Scanning Optimization Algorithms for TSP”, Proceedings of the International Conference on Theoretical and Mathematical Foundations of Computer Science, Orlando, USA, pp. 110-116, 2008.

[5]R. Bazylevych, R. Kutelmakh, R. Dupas, L. Bazylevych, “Decomposition Algorithms for Large-Scale Clustered TSP”, Proceedings of the 3rd Indian International Conference on Artificial Intelligence, Pune, India, pp. 255-267, 2007.

[6]R. Bazylevych, B. Prasad, R. Kutelmakh, R. Dupas, L. Bazylevych, “A Decomposition Algorithm for Uniform Traveling Salesman Problem”, Proceedings of the 4th Indian International Conference on Artificial Intelligence, Tumkur, India, pp. 47-59, 2009.

[7]R. Bazylevych, R. Kutelmakh, B. Kuz, “Algorithm for Solving Large Scale TSP Problem by “Ring” Method”, “Visnyk” of the Lviv Polytechnic National University “Computer Sciences and Information Technologies”, No. 686, Lviv, pp. 179 – 182, 2010 (in Ukrainian).

[8]R. Bazylevych, R. Dupas, B. Prasad, B. Kuz, R. Kutelmakh, L. Bazylevych, “A Parallel Approach for Solving a Large-Scale Traveling Salesman Problem”, Proceedings of the 5th Indian International Conference on Artificial Intelligence, Tumkur, India, pp. 566-579, 2011.

[9]Concorde: http://www.tsp.gatech.edu/data/art/index.html.

[10]B. Delaunay, “Sur la sphère vide”, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, No 7: pp. 793–800, 1934.

[11]DIMACS TSP Challenge Results: http://www.akira.ruc.dk/~keld/Research/LKH/DIMACS_results.html.

[12]T. Fischer, P. Merz, “A Distributed Chained Lin-Kernighan Algorithm for TSP Problems”, Proceedings of the 19th International Parallel and Distributed Processing Symposium, Denver, USA, 2005.

[13]J. Gómez, R. Poveda, E. León. Grisland, “A parallel genetic algorithm for finding near optimal solutions to the traveling salesman problem”, Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation, ACM New York, USA, pp. 2035-2040, 2009.

[14]Y. Haxhimusa, E. Carpenter, J. Catrambone, D. Foldes, E. Stefanov, L. Arns and Z. Pizlo, “2D and 3D Traveling Salesman Problem”, The Journal of Problem Solving, vol. 3, No. 2, pp. 168 – 193, 2011.

[15]K. Helsgaun, “An Effective Implementation of k-Opt Moves for the Lin–Kernighan TSP Heuristic”, Datalogiske Skrifter, Writings on Computer Science, No. 109, Roskilde University, 2006.

[16]K. Helsgaun, “An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic”, European Journal of Operational Research, 126 (1), pp. 106-130, 2000.

[17]S. Huang, L. Zhu, F. Zhang, Y. He, H. Xue, “Distributed Evolutionary Algorithms to TSP with Ring Topology”, Computational Intelligence and Intelligent Systems, Communications in Computer and Information Science, Volume 51, pp. 225-231, 2009.

[18]L.F. Hulyanytskyi, A.V. Sapko, “Decomposition approach to solving the traveling salesman problem of high size”, Packages of applied software, and numerical methods. V.M. Glushkov Institute of Cybernetics of Ukrainian Academy of Sciences, Kyiv, pp. 8-13, 1988.

[19]C. Li, G. Sun, D. Zhang, S. Liu, “A Hierarchical Distributed Evolutionary Algorithm to TSP”, Advances in Computation and Intelligence, Lecture Notes in Computer Science, Volume 6382, pp. 134-139, 2010.

[20]S. Lin, B.W. Kernighan, “An Effective Heuristic Algorithm for the Traveling Salesman Problem”, Operation research, Vol. 21, No. 2, pp. 498-516, 1973.

[21]Mona Lisa TSP Challenge: http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html.

[22]Z. Pizlo, E. Stefanov, J. Saalweachter, Z. Li, Y. Haxhimusa and W. Kropatsch, “Traveling Salesman Problem: A Foveating Pyramid Model”, The Journal of Problem Solving, vol. 1, No. 1, pp. 83 – 101, 2006.

[23]K. Rocki, R. Suda, “Large scale parallel iterated local search algorithm for solving traveling salesman problem”, Proceedings of the 2012 Symposium on High Performance Computing, Article No. 8, Society for Computer Simulation International, San Diego, USA 2012.

[24]TSP Art Instances: http://www.math.uwaterloo.ca/tsp/data/art/index.html.

[25]USA TSP Challenge: http://www.math.uwaterloo.ca/tsp/data/usa/index.html.

[26]USA TSP Challenge Results: http://www.math.uwaterloo.ca/tsp/data/usa/leaders.html.

[27]D.S. Johnson, L.A. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization”, E.H.L. Aarts, J.K. Lenstra (Eds.), Ch. Local Search, Combinatorial Optimization, Wiley, New York, pp. 215–310, 1997.

[28]G. Gutin, A.P. Punnen, The Traveling Salesman Problem and its Variations, Kluwer Academic Publishers, Dordrecht, 2002.

[29]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, The Traveling Salesman Problem, Wiley, New York, 1985.

[30]A.L. Yuille, “Generalized Deformable Models Statistical Physics and Matching Problems”, Neural Computation, 2 pp. 1–24, 1990.

[31]W. Wolfe, M. Parry, J. MacMillan, “Hopfield-style Neural Networks and the TSP”, Proceedings of the IEEE International Conference on Neural Networks, IEEE World Congress on Computational Intelligence, vol. 7, pp. 4577–4582, 1994.

[32]J. Andrews, J.A. Sethian, “Fast Marching Methods for the Continuous Traveling Salesman Problem”, Proceedings of the National Academy of Sciences of the United States of America, 104 (4), pp. 1118–1123, 2007.

[33]J.N. MacGregor, T.C. Ormerod, “Human Performance on the Traveling Salesman Problem”, Perception & Psychophysics, 58, pp. 527–539, 1996.

[34]J.N. MacGregor, T.C. Ormerod, E.P. Chronicle, “A Model of Human Performance on the Traveling Salesperson Problem”, Memory & Cognition, 28, pp. 1183–1190, 2000.

[35]S.M. Graham, A. Joshi, Z. Pizlo, “The Traveling Salesman Problem: A Hierarchical Model”, Memory & Cognition, 28, pp. 1191–1204, 2000.

[36]D. Vickers, M. Butavicius, M. Lee, M., A. Medvedev, “Human Performance on Visually Presented Traveling Salesman Problems”, Psychological Research, 65, pp. 34–45, 2001.

[37]J.M. Wiener, N.N. Ehbauer, H. Mallot, “Planning Paths to Multiple Targets: Memory Involvement and Planning Heuristics in Spatial Problem Solving”, Psychological Research, 77, pp. 644–658, 2009.

[38]Y. Haxhimusa, W.G. Kropatsch, Z. Pizlo, A. Ion, “Approximating TSP Solution by MST based Graph Pyramid”, Image and Vision Computing, 27, pp. 887–896, 2009.

[39]S. Arora, “Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems”, Proceedings of the IEEE Symp. Foundations of Computer Science, pp. 2–11, 1996.

[40]A.V. Kryazhimskiy, V.B. Savinov, “The travelling-salesman Problem with Moving Objects”, J. Comput. Syst. Sci. Int., pp. 144–148, 1993.

[41]B.S. Everitt, S. Landau, M. Leese, D. Stahl, Miscellaneous Clustering Methods, Cluster Analysis, 5th Edition, John Wiley & Sons, 2011.

[42]G.E. Blelloch, J.C. Hardwick, G.L. Miller, D. Talmor, “Design and Implementation of a Practical Parallel Delaunay Algorithm”, Algorithmica, 24, pp. 243–269, 1999.

[43]M.T. Adham, P.J. Bentley, “An Artificial Ecosystem Algorithm Applied to the Travelling Salesman Problem”, Genetic and Evolutionary computation conference, Vancouver, BC, Canada, 2014.

International Journal of Information Technology and Computer Science (IJITCS)