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

• 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.
• CormenT. H. , Leiserson, C. E. , Rivest, R. L. & Stein, C. (2001). Introduction to Algorithms, Second Edition, MIT Press Cambridge, Massachusetts.
• The Traveling Salesman Problem: A case study in local optimization by David S. Johnson and Lyle A. McGeoch 1995
• 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.
• 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.
• 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.
• 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.
• 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.
• S. Kirkpatrick, C. D. G. J. and M. P. Vecchi (1983, May). Optimization by simulated annealing. Science 220(4598), 671–680.
• Hopfield, J. J. and D. W. Tank (1985). "Neural" computation of decisions in optimization problems. Biological Cybernetics 52, 141–152. 10. 1007/BF00339943.
• Bentley, J. L. (1992). Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing 4(4), 387–411.
• http://www. iwr. uniheidelberg. de/groups/comopt/softwar-e/TSPLIB95/
• Reinelt, G. (1991, Fall). Tsplib - a traveling salesman problem library. ORSA, Journal On Computing 3(4), 376–384.
• K. N. Krishnaswamy, AppaIyer Sivakumar, M. Mathirajan (2009). Management Research Methodology: Integration of Methods and Techniques. Pearson Education India
• 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
• Michael Ball, Michael Magazine (1981). The design and analysis of heuristics. Networks Volume 11, Issue 2, pages 215–219.
• Weiner, P. , "Heuristics", Networks 5 (1975) 101-103. [621/H].
• 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
• Turban, E. (1990). Decision support and expert system. Macmillan series in information system.
• 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.
• http://www. tsp. gatech. edu/sweden/index. html