Use Simulated Annealing for the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization, in which the target is to find the shortest route for the salesman through various cities. In every known algorithm that solves this problem exactly, increasing the number of cities increases the running time of the problem exponentially.

Simulated annealing is a probabilistic technique to approximate the global optimum. Inspired by metallic annealing, where metal is first heated and then cooled to increase its ductility, the step size of simulated annealing is initially kept high to traverse the entire solution space and is gradually decreased to improve the accuracy of the solution.

In this project, we will implement the simulated annealing algorithm and apply it to find an approximate solution to TSP.