Call for Paper

CAE solicits original research papers for the July 2021 Edition. Last date of manuscript submission is June 30, 2021.

Read More

A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem

Evans Baidoo. Published in Algorithms.

Communications on Applied Electronics
Year of Publication: 2016
Publisher: Foundation of Computer Science (FCS), NY, USA
Authors: Evans Baidoo
10.5120/cae2016652386

Evans Baidoo. A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem. Communications on Applied Electronics 5(10):29-36, September 2016. BibTeX

@article{10.5120/cae2016652386,
	author = {Evans Baidoo},
	title = {A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem},
	journal = {Communications on Applied Electronics},
	issue_date = {September 2016},
	volume = {5},
	number = {10},
	month = {Sep},
	year = {2016},
	issn = {2394-4714},
	pages = {29-36},
	numpages = {8},
	url = {http://www.caeaccess.org/archives/volume5/number10/659-2016652386},
	doi = {10.5120/cae2016652386},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Much attention has be drawn by the Travelling salesman problem lately as it is one of the problem in mathematics and computer science which although is easy to understand but very difficult to solve.

In this paper, a preliminary study is undertaken to construct a minimum spanning tree algorithm to approximately solve the TSP.

An implementation of the travelling salesman problem using a modified pure minimum spanning tree algorithm is also presented. The propose algorithm provides an evaluation of the cost of a round trip and it executes in practical time. The algorithm verifies from a constructed tour and presents a shortcut path to all destinations. The proposed approach performance is benchmark with a case study.

References

  1. http://en.wikipedia.org/wiki/Travelling salesman problem.
  2. Whitely, D., Starkweather, T. and D’Ann, F. 1989. Scheduling problems and traveling salesman: The genetic edge recombination operator, in Proc.3rd Int. Conf. Genetic Algorithms, 1989, pp.133–140.
  3. Clarke, G. and Wright, J.W. 1964. Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res., vol. 12, pp. 568–581, 1964.G. http://dx.doi.org/10.1287/opre.12.4.568
  4. Korostensky, C. and Gonnet, G. H. 2000. Using traveling salesman problem algorithms for evolutionary tree construction, Bioinformatics, vol. 16, no. 7, pp. 619–627, 2000. http://dx.doi.org/10.1093/bioinformatics/16.7.61
  5. Alizadeh, F., Karp, R. M., Newberg, L. A. and Weisser D. K., 1993. Physical mapping of chromosomes: A combinatorial problem in molecular biology, in Proc. 4th ACM-SIAM Symp. Discrete Algorithms (SODA), 1993, pp. 52–76.
  6. Kirkpatrick, S., Gelatt Jr, C. D. and Vecchi, M. P. 1983. Optimization by simulated annealing, Science, vol. 220, pp. 498–516, 1983. http://dx.doi.org/10.1126/science.220.4598.671
  7. Li, W.2011. A Parallel Multi-Start Search Algorithm for Dynamic Traveling Salesman Problem. 10th International Conference on Experimental Algorithm, pp 65-75, 2011.
  8. R. Matai, S. Singh, M. L. Mittal,“Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches,”Traveling Salesman Problem, Theory and Applications. InTech, 2010.
  9. http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
  10. Hendtlass, T. 2010. TSP Optimisation Using Multi Tours Ants, 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, pp. 523-532, 2010.
  11. https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
  12. Graham, R. L., and Hell, P. 1985. On the history of the minimum spanning tree problem. Annals of the History of Computing 1985;7:43}57.
  13. Maffioli, F. 1981. Complexity of optimum undirected tree problems: a survey of recent results. In: Ausiello G, Lucertini M, editors. Analysis and design of algorithms in combinatorial optimization. International Center for Mechanical Sciences. CISM Courses and Lectures, 266. New York: Springer, 1981. p. 107}28.
  14. Pierce, A. R. 1974. Bibliography on algorithms for shortest path, shortest spanning tree and related circuit routing problems (1956}1974). Networks1975;5:129}49.
  15. Fredman, M. L., and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimizationalgorithms. J. ACM 34, 596–615.
  16. Gabow, H. N., Galil, Z., Spencer, T., and Tarjan, R. E. 1986. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109–122.
  17. Cuneyt F. B. and Khalil S. H. 2001. Minimum-weight spanning tree algorithms. A survey and empirical study, Computer & Operations Research 28(2001) 767-785
  18. http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2028%20-%20Approximation%20Algorithm.htm
  19. Cook, W. 2009. History of the TSP." The Traveling Salesman Problem. Oct 2009. Georgia Tech, 22 Jan 2010. .
  20. Lawler, E. L, Lenstra, J. K., Rinnooy Kan, A.H.G and.Shmoys, D.B 1985. The Traveling Salesman Problem. John Wiley & Sons.
  21. Sharad, N. et al. 2013. Solving Travelling Salesman Problem using Firefly Algorithm. International Journal for Research in Science & Advanced Technologies Issue-2, Volume-2, 053-057

Keywords

Minimum Spanning Tree, Travelling Salesman Problem