Manuscript Number : CSEIT1835159

An Improved Nearest Neighbor Algorithm for Solving TSP

Authors(3) :-Emran Islam, Mariam Sultana, Faruque Ahmed

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.

Authors and Affiliations

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

Traveling Salesman Problem, Approximate algorithms, NNA

  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"

Publication Details

Published in : Volume 3 | Issue 5 | May-June 2018
Date of Publication : 2018-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 668-672
Manuscript Number : CSEIT1835159
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

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. |          | BibTeX | RIS | CSV

Article Preview