Parallel Branch and Bound Model Using Logarithmic Sampling (PBLS) for Symmetric Traveling Salesman Problem

Authors: Sheikh Muhammad Azam, Masood-ur-Rehman, Adnan Khalid Bhatti, Nadeem Daudpota

Abstract:

Very Large and/or computationally complex optimization problems sometimes require parallel or highperformance computing for achieving a reasonable time for computation. One of the most popular and most complicate problems of this family is “Traveling Salesman Problem". In this paper we have introduced a Branch & Bound based algorithm for the solution of such complicated problems. The main focus of the algorithm is to solve the “symmetric traveling salesman problem". We reviewed some of already available algorithms and felt that there is need of new algorithm which should give optimal solution or near to the optimal solution. On the basis of the use of logarithmic sampling, it was found that the proposed algorithm produced a relatively optimal solution for the problem and results excellent performance as compared with the traditional algorithms of this series.

Keywords: Parallel execution, symmetric traveling salesman problem, branch and bound algorithm, logarithmic sampling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060986

References:

[1] Applegate, R.E. Bixby, V. Chvatal, and W. Cook (1994) "Finding cuts in the TSP" a preliminary report distributed at The Mathematical Programming Symposium, Ann Arbor, Michigan, August 1994.
[2] D. Applegate, R.E. Bixby, V. Chvatal, and W. Cook (1998) "On the solution of traveling salesman problems" Documenta Mathematica - Extra Volume, ICM III 645-658.
[3] Irina Dumitrescu and Thomas St¨utzle," Combinations of Local Search and Exact Algorithms", S. Cagnoni et al. (Eds.): EvoWorkshops 2003, LNCS 2611, pp. 211-223, 2003.
[4] Chantal Korostensky, and Gaston H. Gonnet, "Using traveling salesman problem algorihms for evolutionary tree consturction" Institute of scientific computing , 8092 ETH Zurich, Switzerland, January 23,2000.
[5] Bapna, S. De, S."An intelligent search strategy for solving the symmetric traveling salesman problem" Systems, Man, and Cybernetics, 1991. 'Decision Aiding for Complex Systems, Conference Proceedings., 1991 IEEE International Conference, pp579-583 vol.1
[6] Jano I . van Hemert and Neil B. Urquhart, "Phase transition properties of clustered traveling salesman problem instances generated with evolutionary computation" Parallel Problem Solvers from Nature VIII, pages 150-159, 2004.
[7] Chuan-Kang Ting; Sheng-Tun Li; Chungnan Lee; "TGA: a new integrated approach to evolutionary algorithms" Evolutionary Computation, 2001. IEEE Proceedings of the 2001 Congress,Volume 2, 27-30 May 2001 PP:917 - 924.
[8] Chris Walshaw, "A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem" Mathematics Research Report: 01/IM/80, September 27, 2001.
[9] Irina Dumitrescu and Thomas St¨utzle, "Combinations of Local Search and Exact Algorithms"S. Cagnoni et al. (Eds.): EvoWorkshops 2003, LNCS 2611, pp. 211-223, 2003.
[10] Freisleben, B.; Merz, P.; "A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems" Evolutionary Computation, 1996., Proceedings of IEEE International Conference on,20-22 May 1996 Page(s):616 - 621.
[11] Jens Clausen, "Branch and bound algorithms principles and examples ", department of comp sc., university of Copenhagen, Universitetsparken 1, DK-2100 Corpenhagen, Denmark.(March 12,1999)
[12] R. C. T. Lee, R. C. Chang, S.S. Tseng, and Y. T. Tsai, An Introduction to the Design and Analysis of Algorithms, 2nd Ed, FLAG Publishers, 2002.
[13] Grigni, M.; Koutsoupias, E.; Papadimitriou, C.; "An approximation scheme for planar graph TSP" Foundations of Computer Science, 1995. Proceedings., IEEE ,36th Annual Symposium,23-25 Oct. 1995 pp:640 - 645.