An Improved Nearest Neighbor Algorithm for Solving TSP

Authors

  • Emran Islam  Research students, Department of Mathematics, Jahingirnagar University, Savar, Dhaka, Bangladesh
  • Mariam Sultana  Research students, Department of Mathematics, Jahingirnagar University, Savar, Dhaka, Bangladesh
  • Faruque Ahmed  Professor, Department of Mathematics, Jahingirnagar University, Savar, Dhaka, Bangladesh

Keywords:

Traveling Salesman Problem, Approximate algorithms, NNA

Abstract

Traveling salesman problem is one of the most important mathematical concepts having very high socio economic impact. But since TSP is NP-complete, finding an optimal solution becomes very hard when problem size increases. Conceptually TSP is very easy to understand but solving TSP is quite difficult than anyone can imagine. In this paper we have represented an improved form of nearest neighbor algorithm for solving TSP. We have also represented a comparative study between our proposed algorithm and original algorithm to test efficiency.

References

  1. Emran Islam, Mariam Sultana, Faruque Ahmed "A Tale of Revolution: Discovery and Development of TSP", International Journal of Mathematics Trends and Technology (IJMTT). V57(2):136-139 May 2018.
  2. Davendra, Donald, et al. "Chaos driven evolutionary algorithm for the traveling salesman problem." Traveling Salesman Problem, Theory and Applications (2010): 55-70.
  3. Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer Science & Business Media, 2006.
  4. Lenstra, Jan Karel, and AHG Rinnooy Kan. "Some simple applications of the travelling salesman problem." Journal of the Operational Research Society 26.4 (1975): 717-733.
  5. Punnen, Abraham P. "The traveling salesman problem: Applications, formulations and variations." The traveling salesman problem and its variations. Springer, Boston, MA, 2007. 1-28.
  6. Lenstra, Jan Karel. "Clustering a data array and the traveling-salesman problem." Operations Research 22.2 (1974): 413-414.
  7. Kizilates, Gzde, and Fidan Nuriyeva. "On the nearest neighbor algorithms for the traveling salesman problem." Advances in Computational Science, Engineering and Information Technology. Springer, Heidelberg, 2013. 111-118.
  8. Laporte, Gilbert. "The traveling salesman problem: An overview of exact and approximate algorithms." European Journal of Operational Research 59.2 (1992): 231-247.
  9. Johnson, D. S. "Performance guarantees for heuristics." The Traveling Salesman Problem: A. Guided Tour of Combinatorial Optimization (1985): 145-180
  10. Golden, Bruce, et al. "Approximate traveling salesman algorithms." Operations research 28.3-part-ii (1980): 694-711.
  11. Taiwo, Oloruntoyin Sefiu, et al. "IMPLEMENTATION OF HEURISTICS FOR SOLVING TRAVELLING SALESMAN PROBLEM USING NEAREST NEIGHBOUR ANDNEAREST INSERTIONAPPROACHES." (2013).
  12. Source of distances of five cities: www.distanceto.com"

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2018-06-30

Issue

Volume 3, Issue 5, May-June-2018

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Emran Islam, Mariam Sultana, Faruque Ahmed, " An Improved Nearest Neighbor Algorithm for Solving TSP" International Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 5, pp.668-672, May-June-2018.