An Analysis of various techniques to solve Travelling Salesman Problem: A Review

Abstract

Travelling Salesman problem is a nondeterministic polynomial time hard problem in combinatorial optimization studied in operational research and theoretical computer science. In this review paper several techniques like brute-force method, nearest neighbour, branch and bound, dijkstra shortest path algorithm, bellman ford, Floyd warshall algorithm and some heuristic techniques like ant colony optimization and genetic algorithm used to solve the travelling salesman problem are analysed. The comparison between these techniques is accomplished to state which is the better one for solving travelling salesman problem.

Keywords: Travelling Salesman Problem (TSP), Shortest Path Algorithm, Hamiltonian cycle Ant Colony Optimization (ACO), Genetic Algorithm (GA), Pheromone, Particle Swarm Optimization (PSO)