THEORY OF TRAVELLING SALESMAN PROBLEM

Sharifatul Aniza bt Suliman #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 sharifatulaniza@gmail.com
2 faidzms@ieee.org
 
 
Abstract—Some methods to solve the Traveling Salesman Problem (TSP) are examined in this paper. This paper shows some theories that are related in solving the TSP. Karl Menger was the first to study about the general form of the TSP. Then, Hassler, Whitney and Merill promote the issue. Schrijver explained that there is a definite portrayal about the connection amongst Menger and Whitney and the development of the TSP.  The TSP is typical of an extensive class of “hard” improvement issues that have captivated mathematicians and PC researchers for a considerable length of time. Symmetric traveling salesman problem (sTSP), asymmetric traveling salesman problem (aTSP), and multi traveling salesman problem (mTSP) are the class of the TSP. The motivation behind this paper is to demonstrate the mathematical theory and show for the traveling salesman problem. Towards the end of the paper, the mathematical theory of traveling salesman problem will be studied and stated clearly. Some conclusions are presented also.

Keywords: Traveling Salesman Problem, theory, TSP


REFERENCES

[1]	N. Biggs, E. Lloyd, and R. Wilson, "Graph Theory: 1736–1936, Clarendon Pr." ed: Oxford, 1986

[2]	D. K. a. Y. Hah, "A Parallel TSP (Travelling Salesman Problem) Algorithm Based on Divide-And-Conquer Strategy," Parallel Computing and Transputer Applications, vol. Volume 28 and 29, p. 763, September 1992.

[3]	S.-h. Zhan, J. Lin, Z.-j. Zhang, and Y.-w. Zhong, "List-Based Simulated Annealing Algorithm for Traveling Salesman Problem," Computational Intelligence and Neuroscience, vol. 2016, 2016.

[4]	H. R. Er and N. Erdogan, "Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster," arXiv preprint arXiv:1401.6267, 2014.

[5]	G. Laporte, "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, pp. 231-247, 1992.

[6]	P. Borovska, T. Ivanova, and H. Salem, "Efficient Parallel Computation of the Traveling Salesman Problem on Multicomputer Platform," in Proceedings of the International Scientific Conference ‘Computer Science, pp. 74-79, 2004.

[7]	A. Behzad and M. Modarres, "A new efficient transformation of the generalized traveling salesman problem into traveling salesman problem," in Proceedings of the 15th International Conference of Systems Engineering, pp. 6-8, 2002.

[8]	P. Borovska, "Solving the travelling salesman problem in parallel by genetic algorithm on multicomputer cluster," in Int. Conf. on Computer Systems and Technologies, pp. 1-6, 2006.

[9]	J. J. Hopfield and D. W. Tank, "“Neural” computation of decisions in optimization problems," Biological cybernetics, vol. 52, pp. 141-152, 1985.

[10]	R. Matai, M. L. Mittal, and S. Singh, Traveling salesman problem: An overview of applications, formulations, and solution approaches: INTECH Open Access Publisher, 2010.

[11]	A. Orman and H. P. Williams, "A survey of different integer programming formulations of the travelling salesman problem," Optimisation, economics and financial analysis. Advances in computational management science, vol. 9, pp. 93-106, 2006.

[12]	G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a large-scale traveling-salesman problem," Journal of the operations research society of America, vol. 2, pp. 393-410, 1954.

[13]	D. Applegate, R. Bixby, V. Chvátal, and W. Cook, "Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems," Mathematical programming, vol. 97, pp. 91-153, 2003.

[14]	W. contributors. (2016). Travelling salesman problem. Available: https://en.wikipedia.org/wiki/Travelling_salesman_problem

[15]	M. S. Daskin, "Facility Location Software for Windows 95 and above updated software to accompany," 2016.