Call for Paper - November 2023 Edition
IJCA solicits original research papers for the November 2023 Edition. Last date of manuscript submission is October 20, 2023. Read More

Solving the TSP using Traditional Computing Approach

Print
PDF
 
Download Full Text
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 152 - Number 8
Year of Publication: 2016
Authors:
Evans Baidoo, Stephen O. Oppong
10.5120/ijca2016911906

Evans Baidoo and Stephen O Oppong. Solving the TSP using Traditional Computing Approach. International Journal of Computer Applications 152(8):13-19, October 2016. BibTeX

@article{10.5120/ijca2016911906,
	author = {Evans Baidoo and Stephen O. Oppong},
	title = {Solving the TSP using Traditional Computing Approach},
	journal = {International Journal of Computer Applications},
	issue_date = {October 2016},
	volume = {152},
	number = {8},
	month = {Oct},
	year = {2016},
	issn = {0975-8887},
	pages = {13-19},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume152/number8/26339-2016911906},
	doi = {10.5120/ijca2016911906},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

From the last decade, even though there have been sudden advances in present technology in all areas, there exist some real-world NP composite problems that still escape scientists. The Travel salesman Problem is no exception. As it is an NP-Hard problem, lots of divergent solutions have been created to determine in shortest possible time, the optimal solution. Traditional algorithms are one of the oldest suggested solutions which present successful solutions that are to a larger extent optimal except in few occasions which may be close to the optimal. In this paper, a variant of the classical TSP, Random TSP (RTSP) is computed using various traditional algorithms. Their performances are evaluated with emphasis on length of tour and the algorithm effectiveness. Also, this paper presents the comparison among the algorithms based on a variety of parameters that facilitated to decide the superior algorithm with regards to their needs.

References

  1. Applegate, D. L., Bixby, R.E., Chvátal, V., and Cook, W. J. 2006. The Travelling Salesman Problem: A Computational Study. Pinceton Series in Applied Mathematics: Princeton.
  2. 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, http://dx.doi.org/10.1287/opre.12.4.568
  3. Whitely, D. Starkweather, T. and D’Ann, F. 1989. Scheduling problems and travelling salesman: The genetic edge recombination operator, in Proc.3rd Int. Conf. Genetic Algorithms, pp.133–140.
  4. Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing, Science, vol. 220, pp. 498–516, http://dx.doi.org/10.1126/science.220.4598.671
  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), pp. 52–76.
  6. Korostensky C. and Gonnet, G. H. 2000. Using traveling salesman problem algorithms for evolutionary tree construction, Bioinformatics, vol. 16, no. 7, pp. 619–627, http://dx.doi.org/10.1093/bioinformatics/16.7.619
  7. Zelinka, I. 2002. Umělá intelligence v problémech globální optimalizace. Praha: BEN-technická literatúra.
  8. Johnson D.S., and McGeoch, L.A. 1995. The Traveling Salesman Problem: A Case Study in Local Optimization, November 20,
  9. http://www.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html
  10. Eugene Lawler, L., Lenstra, J.K., Rinnooy Kan, A.H.G, and Shmoys, D.B., 1985. The Traveling Salesman Problem, John Wiley & Sons.
  11. http://lcm.csa.iisc.ernet.in/dsa/node187.html.
  12. Dantzig, G. B., Fulkerson, D. R., and Johnson, S. M., 1954. Solution of a large-scale traveling-salesman problem, Operations Res 2: 393–410.
  13. Land, A. H., and Doig A. G., 1960. An automatic method of solving discrete programming problems, Econometrica 28: 497–520.
  14. Little J. D. C., Murty K. G., Sweeney D. W and Karel C., 1963. An algorithm for the traveling salesman problem . Opns Res 11: 972–989.
  15. Martin G. T., 1966. Solving the traveling salesman problem by integer programming. Working Paper, CEIR, New York.
  16. Ellis Horowitz, Sartaz Sahni, and Rajasekaran. 1998. Fundamentals of Computer Algorithms. W.H. Freeman and Company, Indian Edition published by Galgotia Publications, 2000.
  17. Oloruntoyin Sefiu Taiwo et al, 2013. Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbor And Nearest Insertion Approaches, International Journal of Advance Research. Volume 1, Issue 3, March 2013, Online: ISSN 2320-9194

Keywords

Traditional Algorithms, Travelling Salesman Problem, Optimization Problem