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

TSP Solver using Constructive Method of Heuristic Approach

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

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 53 - Number 1
Year of Publication: 2012
Authors: Chetan Chauhan, Ravindra Gupta, Kshitij Pathak
10.5120/8387-1993

Chetan Chauhan, Ravindra Gupta, Kshitij Pathak . TSP Solver using Constructive Method of Heuristic Approach. International Journal of Computer Applications. 53, 1 ( September 2012), 33-38. DOI=10.5120/8387-1993

@article{ 10.5120/8387-1993,
author = { Chetan Chauhan, Ravindra Gupta, Kshitij Pathak },
title = { TSP Solver using Constructive Method of Heuristic Approach },
journal = { International Journal of Computer Applications },
issue_date = { September 2012 },
volume = { 53 },
number = { 1 },
month = { September },
year = { 2012 },
issn = { 0975-8887 },
pages = { 33-38 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume53/number1/8387-1993/ },
doi = { 10.5120/8387-1993 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:53:01.633971+05:30
%A Chetan Chauhan
%A Ravindra Gupta
%A Kshitij Pathak
%T TSP Solver using Constructive Method of Heuristic Approach
%J International Journal of Computer Applications
%@ 0975-8887
%V 53
%N 1
%P 33-38
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Traveling salesperson problem (TSP) is one of the problem in mathematics and computer science which had drown attention as it is easy to understand and difficult to solve. In this paper, we implemented a heuristic approach for TSP using constructive method which generates satisfactory results in asymptotically linear time. Earlier work consider complete graph as a input to TSP. TSP solver generated by proposed approach can work with non-complete graph as well as complete graph.

References
  1. Applegate, D. L. , Bixby, R. E. , Chv?tal, V. & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational 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. 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.
  6. 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.
  7. 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.
  8. 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.
  9. S. Kirkpatrick, C. D. G. J. and M. P. Vecchi (1983, May). Optimization by simulated annealing. Science 220(4598), 671–680.
  10. Hopfield, J. J. and D. W. Tank (1985). "Neural" computation of decisions in optimization problems. Biological Cybernetics 52, 141–152. 10. 1007/BF00339943.
  11. Bentley, J. L. (1992). Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing 4(4), 387–411.
  12. http://www. iwr. uniheidelberg. de/groups/comopt/softwar-e/TSPLIB95/
  13. Reinelt, G. (1991, Fall). Tsplib - a traveling salesman problem library. ORSA, Journal On Computing 3(4), 376–384.
  14. K. N. Krishnaswamy, AppaIyer Sivakumar, M. Mathirajan (2009). Management Research Methodology: Integration of Methods and Techniques. Pearson Education India
  15. Edward A. Silver, R. Victor, V. Vidal, Dominique de Werra (1980). A tutorial on heuristic methods. European Journal of Operational Research Volume 5, Issue 3, Pages 153–162
  16. Michael Ball, Michael Magazine (1981). The design and analysis of heuristics. Networks Volume 11, Issue 2, pages 215–219.
  17. Weiner, P. , "Heuristics", Networks 5 (1975) 101-103. [621/H].
  18. Stelios H. ZANAKIS, James R. EVANS, Alkis A. VAZACOPOULOS (1989). Heuristic methods and applications: A categorized survey. European Journal of Operational Research 43 , 88-110 North-Holland
  19. Turban, E. (1990). Decision support and expert system. Macmillan series in information system.
  20. Chetan Chauhan, Ravindra Gupta and Kshitij Pathak. Article: Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach. International Journal of Computer Applications 52(4):12-19, August 2012. Published by Foundation of Computer Science, New York, USA.
  21. http://www. tsp. gatech. edu/sweden/index. html
Index Terms

Computer Science
Information Sciences

Keywords

Traveling Salesman problem Heuristic approach Constructive method Exact Solution Approaches

Powered by PhDFocusTM