Parallel Branch and Bound Model Using Logarithmic Sampling (PBLS) for Symmetric Traveling Salesman Problem
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:54499", author = "Sheikh Muhammad Azam and Masood-ur-Rehman and Adnan Khalid Bhatti and Nadeem Daudpota", title = "Parallel Branch and Bound Model Using Logarithmic Sampling (PBLS) for Symmetric Traveling Salesman Problem", 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.", volume = "1", number = "6", pages = "1627-4", }
