We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Solving the TSP using Traditional Computing Approach

by Evans Baidoo, Stephen O. Oppong
journal cover thumbnail

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, Stephen O. Oppong . Solving the TSP using Traditional Computing Approach. International Journal of Computer Applications. 152, 8 ( Oct 2016), 13-19. DOI=10.5120/ijca2016911906

@article{ 10.5120/ijca2016911906,
author = { Evans Baidoo, Stephen O. Oppong },
title = { Solving the TSP using Traditional Computing Approach },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2016 },
volume = { 152 },
number = { 8 },
month = { Oct },
year = { 2016 },
issn = { 0975-8887 },
pages = { 13-19 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume152/number8/26339-2016911906/ },
doi = { 10.5120/ijca2016911906 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:57:38.340259+05:30
%A Evans Baidoo
%A Stephen O. Oppong
%T Solving the TSP using Traditional Computing Approach
%J International Journal of Computer Applications
%@ 0975-8887
%V 152
%N 8
%P 13-19
%D 2016
%I Foundation of Computer Science (FCS), NY, 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
Index Terms

Computer Science
Information Sciences

Keywords

Traditional Algorithms Travelling Salesman Problem Optimization Problem

Powered by PhDFocusTM