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.
