A NEW EFFICIENT ALGORITHM BASED ON BRANCH AND BOUND ALGORITHM FOR TRAVELLING SALESMAN PROBLEM ON GRID COMPUTING

Nurul Hizaty binti Md Deris #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban Negeri Sembilan, MALAYSIA

1 nurulhizatymdderis@gmail.com
2 faidzms@ieee.org

 
Abstract—This paper proposes a network branch and bound algorithm approach for solving the travelling salesman problem (TSP). This kind of problem is known as one of the best combinatorial optimization problems. The best method to solve the travelling salesman problem is branch and bound algorithm. Branch-and-bound is a computational standard used to understand different combinatorial advancement issues, specifically those which are not all that pleasantly organized as to allow exceptionally productive algorithms.

Keywords: branch and bound algorithm, travelling salesman problem, combinatorial optimization


REFERENCES

[1]	T. Ibaraki, "On the computational efficiency of branch-and-bound algorithms," Journal of the Operations Research Society of Japan, vol. 20, pp. 16-35, 1977.

[2]	W. Zhang and R. E. Korf, "A study of complexity transitions on the asymmetric traveling salesman problem," Artificial Intelligence, vol. 81, pp. 223-239, 1996.

[3]	A. Rastogi, A. K. Shrivastava, N. Payal, R. Singh, and A. Sharma, "A Proposed Solution to Travelling Salesman Problem using Branch and Bound," International Journal of Computer Applications, vol. 65, 2013.

[4]	M. Turkensteen, D. Ghosh, B. Goldengorin, and G. Sierksma, "Iterative patching and the asymmetric traveling salesman problem," Discrete Optimization, vol. 3, pp. 63-77, 2006.

[5]	R. Radharamanan and L. Choi, "A branch and bound algorithm for the travelling salesman and the transportation routing problems," Computers & Industrial Engineering, vol. 11, pp. 236-240, 1986.

[6]	A. Fischer, F. Fischer, G. Jäger, J. Keilwagen, P. Molitor, and I. Grosse, "Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics," Discrete Applied Mathematics, vol. 166, pp. 97-114, 2014.

[7]	G. Paletta, "The period traveling salesman problem: a new heuristic algorithm," Computers & Operations Research, vol. 29, pp. 1343-1352, 2002.

[8]	I. Muter, "A new formulation and approach for the black and white traveling salesman problem," Computers & Operations Research, vol. 53, pp. 96-106, 2015.

[9]	I.-C. Choi, S.-I. Kim, and H.-S. Kim, "A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem," Computers & Operations Research, vol. 30, pp. 773-786, 2003.

[10]	J. Majumdar and A. K. Bhunia, "Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times," Journal of Computational and Applied Mathematics, vol. 235, pp. 3063-3078, 2011.

[11]	J. G. Rakke, M. Christiansen, K. Fagerholt, and G. Laporte, "The traveling salesman problem with draft limits," Computers & Operations Research, vol. 39, pp. 2161-2167, 2012.

[12]	R. Germs, B. Goldengorin, and M. Turkensteen, "Lower tolerance-based Branch and Bound algorithms for the ATSP," Computers & Operations Research, vol. 39, pp. 291-298, 2012.

[13]	V. Mak and N. Boland, "Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs," Discrete Applied Mathematics, vol. 155, pp. 2093-2110, 2007.

[14]	E. Munapo, "A network branch and bound approach for the traveling salesman model," South African Journal of Economic and Management Sciences, vol. 16, pp. 52-63, 2013.