Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

Authors: Fatma A. Karkory, Ali A. Abudalmola

Abstract:

The travelling salesman problem (TSP) is a combinatorial optimization problem in which the goal is to find the shortest path between different cities that the salesman takes. In other words, the problem deals with finding a route covering all cities so that total distance and execution time is minimized. This paper adopts the nearest neighbor and minimum spanning tree algorithm to solve the well-known travelling salesman problem. The algorithms were implemented using java programming language. The approach is tested on three graphs that making a TSP tour instance of 5-city, 10 –city, and 229–city. The computation results validate the performance of the proposed algorithm.

Keywords: Heuristics, minimum spanning tree algorithm, Nearest Neighbor, Travelling Salesman Problem (TSP).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088390

References:

[1] E. L Lawler, J. K. Lenstra, A. H. G.Rinnooy Kan, and D.B.Shmoys, editors. “The Traveling Salesman Problem”, Wiley, 1985
[2] http://en.wikipedia.org/wiki/Traveling_salesman_problem
[3] Keld Helsgaun ,”An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic”, Department of Computer Science, Roskilde University,DK-4000 Roskilde, Denmark
[4] Asia – Pasific Journal of Operational Research 18(2001) 77-87,Sim Kim LAU and Li-Yen SHUE, “solving traveling salesman problems with an intelligent search approach” .