Improved greedy approach for travelling salesman problem to be used as a teaching tool

Abstract

The travelling salesman problem (TSP) is a NP-hard problem in combinatorial optimization. A solution to this problem can be successfully used in touring airports to find shortest routes through selections of airports in the world. The travelling salesman problem can be solved by using ant colony optimization, genetic algorithms, simulation annealing, etc. However, these approaches require advanced data structures and they are hard to implement using simple programming languages such as php and javascript. Furthermore, these conventional approaches use advanced mathematical concepts which cannot be understood by researchers without strong mathematical background. The greedy approach can also be used to find an approximation to the shortest route. The greedy strategy follows the heuristic that at each stage, visit an unvisited city nearest to the current city. However, the pure use of greedy algorithm may fail to produce optimal solution and get stuck in a suboptimal solution. The objective of this study is to provide a solution to overcome this drawback in the greedy approach in solving the travelling salesmen problem. First, the route is found using greedy approach. Then the route is modified at appropriate positions so that the length is reduced. The benefits of the proposed solution are threefold: (1) it reduces the use of computational resources and gives better results than using the pure greedy approach; (2) it uses the array data structure which can be easily implemented by using any programming language; (3) it can be easily understood and modified by researchers from non-mathematics background.