Optimization of the Travelling Salesman Problem via Algorithms based on Physical Phenomena

Numerical optimization concerns finding the minima of a specific mathematical object to certain parameters. A powerful optimization technique has limitless applications in every science and engineering field. In this research, we investigate the application of various optimization algorithms to the Travelling Salesman Problem (TSP): Given a salesman and N cities, what is the shortest path the salesman can take such that he/she visits all N cities exactly once and returns to the starting city? TSP is an NP-hard problem, where its solution cannot be computed in a polynomial time or simply, very ``quick''. With this, optimization algorithms can be used to find or approximate the best solution. We use two simple algorithms -- Nearest Neighbor and Two Opt-- along with three more complicated algorithms -- Simulated Annealing, Genetic Algorithm, and Particle Swarm Optimization -- which are all based on physical or natural principles. We conclude that the three complex algorithms are much more efficient; however, the two simpler ones still provide a useful path length reduction although without a complete optimization. The results can be applied to other more complicated optimization problems such as crystal structure prediction with a complex energy landscape.