Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is an NP-hard problem with high number of possible solutions. The complexity increases with the factorial of n nodes in each specific problem. Meta-heuristic algorithms are an optimization algorithm that able to solve TSP problem towards a satisfactory solution. To date, there are many meta-heuristic algorithms introduced in literatures which consist of different philosophies of intensification and diversification. This paper focuses on 6 heuristic algorithms: Nearest Neighbor, Genetic Algorithm, Simulated Annealing, Tabu Search, Ant Colony Optimization and Tree Physiology Optimization. The study in this paper includes comparison of computation, accuracy and convergence.