Travelling Salesman Problem Using Branch And Bound Technique

P.Rajarajeswari; D.Maheswari

doi:https://doi.org/10.14445/22315373/IJMTT-V66I5P528

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 66 | Issue 5 | Year 2020 | Article Id. IJMTT-V66I5P528 | DOI : https://doi.org/10.14445/22315373/IJMTT-V66I5P528

Travelling Salesman Problem Using Branch And Bound Technique

P.Rajarajeswari, D.Maheswari

Abstract

In this paper Branch and bound technique is applied to solve the Travelling Salesman Problem (TSP) whose objective is to minimize the cost. Given a set of cities and the distance between every pair of cities, the problem of finding the shortest route between a set of points and locations that must be visited. Here fuzzy cost is considered as an interval number and further they are transformed into a crisp problem that is solved by branch and bound technique. This is illustrated by means of a numerical example.

Keywords

Interval numbers, Hexagonal numbers, Branch and Bound technique, ranking function

References

[1] Balas.B, Branch and Bound methods for the Travelling Salesman Problem, Management Science Research Report no. MSRR 488, March 1983.
[2] Chandrasekaran.S, Kokila.G, Saju.J, A New Approach to solve Fuzzy Travelling salesman Problems by using Ranking Functions, International Journal of Science and Research, Vol.4, 5 May 2015.
[3] Dhanasekar.S, Hariharan.S, Sekar.P, “Classical Travelling Salesman Problem based approach to solving Fuzzy TSP using Yagers Ranking, International Journal of Computer Applications, Vol.74, 2013, no.13, (0975-8887).
[4] Ding, Cheng, Y, He, M.: Two-Level Genetic algorithm for Clustered Traveling Salesman Problem with Application in Large Scale TSPs, Tsinghua Science and Technology, Vol.12.No.4 (2007) pp. 459-465.
[5] Nilofer et al,” The New Approach to Traveling Salesman Problem using Branch and Bound Method with case study of Domino‟s Pizza Centers”, Advances in Fuzzy Mathematics. ISSN 0973-533X Volume 12, Number 4 (2017), pp. 1017-1033.
[6] Rajarajeswari.P, Maheswari.D, “A New Approach For Solving Travelling Salesman Problem”, Journal of Applied Science and Computations, ISSN NO: 1076-5131, Volume VII, Issue IV, April/2020.
[7] Rastogi. A.K, Shrivastava. A. K, Payal. N, Singh. R, A Proposed solution to Travelling Salesman Problem using Branch and Bound, International Journal of Computer Applications, Vol.65, 2013, No.5, (0975-8887).
[8] Weiner.R, Branch and Bound Implementation for the Traveling salesperson Problem, Journal of Object Technology, Vol.2, 2003, no.2.

Citation :

P.Rajarajeswari, D.Maheswari, "Travelling Salesman Problem Using Branch And Bound Technique," International Journal of Mathematics Trends and Technology (IJMTT), vol. 66, no. 5, pp. 202-206, 2020. Crossref, https://doi.org/10.14445/22315373/IJMTT-V66I5P528