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 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach

by Chetan Chauhan, Ravindra Gupta, Kshitij Pathak
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 52 - Number 4
Year of Publication: 2012
Authors: Chetan Chauhan, Ravindra Gupta, Kshitij Pathak
10.5120/8189-1550

Chetan Chauhan, Ravindra Gupta, Kshitij Pathak . Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach. International Journal of Computer Applications. 52, 4 ( August 2012), 12-19. DOI=10.5120/8189-1550

@article{ 10.5120/8189-1550,
author = { Chetan Chauhan, Ravindra Gupta, Kshitij Pathak },
title = { Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach },
journal = { International Journal of Computer Applications },
issue_date = { August 2012 },
volume = { 52 },
number = { 4 },
month = { August },
year = { 2012 },
issn = { 0975-8887 },
pages = { 12-19 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume52/number4/8189-1550/ },
doi = { 10.5120/8189-1550 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:51:24.660162+05:30
%A Chetan Chauhan
%A Ravindra Gupta
%A Kshitij Pathak
%T Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach
%J International Journal of Computer Applications
%@ 0975-8887
%V 52
%N 4
%P 12-19
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Traveling salesperson problem is one of the problem in mathematics and computer science which haddrown attention as it is easy to understand and difficult to solve. In this paper, we survey the various methods/techniques available to solve traveling salesman problem and analyze it to make critical evaluation of their time complexities. An implementation of the traveling salesman problem using dynamic programming is also presented in this paper which generates optimal answer and tested with 25 cities and it executes in reasonable time.

References
  1. Applegate, D. L. , Bixby, R. E. , Chv?tal, V. & Cook, W. J. (2006). The Traveling Salesman Problem: AComputational Study, Princeton University Press, Princeton, New Jersey.
  2. CormenT. H. , Leiserson, C. E. , Rivest, R. L. & Stein, C. (2001). Introduction to Algorithms, Second Edition, MIT Press Cambridge, Massachusetts.
  3. The Traveling Salesman Problem: A case study in local optimization by David S. Johnson and Lyle A. McGeoch 1995
  4. D. L. Applegate, R. E. Bixby, V. Chv´atal, W. J. Cook, The Traveling Salesman Problem, A Computational Study, Princeton University Press, Princeton and Oxford, 2006.
  5. http://en. wikipedia. org/wiki/Traveling_salesman_probl-em.
  6. Applegate, D. L. , R. E. Bixby, V. Chvátal, and W. J. Cook (2007). The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). , Chapter 1–5,12–17. Princeton, NJ, USA: Princeton University Press.
  7. A Multilevel Scheme for the Traveling Salesman Problem Øystein M. Hjertenes University of Bergen 2002.
  8. V. Chachra, P. M. Ghare, J. M. Moore, Applications of Graph Theory Algorithms, Elsevier North Holland, Inc. , 1979.
  9. Dantzig, G. , R. Fulkerson, and S. Johnson (1954). Solution of a large scale traveling salesman problem. Technical Report P-510, RAND Corporation, Santa Monica, California, USA.
  10. Karp, R. M. (1972). Reducibility among combinatorial problems. In R. Miller and J. Thatcher (Eds. ), Complexity of Computer Computations, New York, USA. , pp. 85–103. Plenum Press.
  11. Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg.
  12. S. Kirkpatrick, C. D. G. J. and M. P. Vecchi (1983, May). Optimization by simulated annealing. Science 220(4598), 671–680.
  13. Hopfield, J. J. and D. W. Tank (1985). "Neural" computation of decisions in optimization problems. Biological Cybernetics 52, 141–152. 10. 1007/BF00339943.
  14. Bentley, J. L. (1992). Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing 4(4), 387–411.
  15. http://www. iwr. uniheidelberg. de/groups/comopt/softwar-e/TSPLIB95/
  16. Reinelt, G. (1991, Fall). Tsplib - a traveling salesman problem library. ORSA, Journal On Computing 3(4), 376–384.
  17. G. Dantzig, R. Fulkerson, and S. Johnson. Solution of a large scale traveling salesman problem. Operations Research, 2:393–410, 1954.
  18. A. H. Land and A. Doig. An automatic method for solving discrete programming problems. Econometrica, 28:497–520, 1960.
  19. J. D. Little, K. G. Murty, D. W. Sweeney, and C. Karel. An algorithm for the traveling salesman problem. Operations Research, 11(6):972– 989, 1963.
  20. Okano, H. (2009). Study of Practical Solutions for Combinatorial Optimization Problems. Ph. D. thesis, School of Information Sciences, Tohoku University.
  21. Dantzig, G. , Fulkerson, R. , Johnson, S. : Solution of a large-scale traveling salesman problem. Operations Research 2, 393{410, 1954.
  22. http://en. wikipedia. org/wiki/Christofides_algorithm
  23. The Traveling Salesman Problem: A case study in local optimization by David S. Johnson and Lyle A. McGeoch 1995
  24. D. S. Johnson and L. A. McGeoch. The Traveling Salesman Problem: A Case Study. In E. H. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization. Wiley and Sons, New York, NY, USA, 1997.
  25. The Traveling Salesman Problem: A case study in local optimization by David S. Johnson and Lyle A. MuGeoch 1995
  26. D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, II, An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput. 6 (1977), 563-581.
  27. G. Reinelt. The traveling salesman: Computational solutions for TSP applications. Springer Verlag, Berlin, Germany, 1994. LNCS 840.
  28. G. Reinelt. The traveling salesman: Computational solutions for TSP applications. Springer Verlag, Berlin, Germany, 1994. LNCS 840.
  29. A. M. Frieze, Worst-case analysis of algorithms for traveling salesman problems, Methods of Operations Research 32 (1979), 97-112.
  30. D. S. Johnson and L. A. McGeoch, "The TravelingSalesman Problem: A Case Study in Local Optimization",November 20, 1995.
  31. G. Gutin and A. Yeo. Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Applied Mathematics, 119(1-2):107–116, 2002.
  32. http://en. wikipedia. org/wiki/Hill_climbing
  33. S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21:498–516, 1973.
  34. S. Kirkpatrick, C. D. Gelatt Jr. , and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
  35. I. A. Wood and T. Downs. Fast optimization by demon algorithms. In T. Downs, M. Frean, and M. Gallagher, editors, Proceedings of the Ninth Australian Conference on Neural Networks (ACNN98), Queensland, Australia, pages 245–249, 1989.
  36. S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
  37. N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6):1087–1092, 1953.
  38. R. W. Eglese. Simulated annealing: A tool for operational research. European Journal of Operational Research, 46(3):271–281, 1990.
  39. F. Glover. Heuristics for integer programming using surrogate constraints. Decision Sciences, 8(1):156–166, 1977.
  40. M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Ant autocatalytic optimizing process. Technical Report TR91-016, Politenico di Milano, 1991.
  41. M. Dorigo, G. Di Caro, and L. M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5(2):137–172, 1999
  42. A. Fraser. Simulation of genetic systems by automatic digital computers. I. introduction. Australian Journal of Biological Science, 10:484–491, 1957.
  43. A. Fraser. Simulation of genetic systems by automatic digital computers. II. Effects of linkage on rates of advanced under-selection. Australian Journal of Biological Science, 10:492–499, 1957.
  44. J. H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, 1975.
Index Terms

Computer Science
Information Sciences

Keywords

Traveling Salesman problem Heuristic approach Dynamic Programming Greedy Method Exact Solution Approaches

Powered by PhDFocusTM