Author: Ilya Borovik, BS4-DS

Application of Simulated Annealing to the Travelling Salesman problem as a solution to Assignment #2 in Advanced Statistics course at Innopolis University.

The task is to solve the Traveling Salesman problem for the 30 most popular Russian cities.

Report

Images and plots

Video animations

To run the code yourself:

• clone repository using git clone https://github.com/ilya16/simulated-annealing
• install dependencies using pip install -r requirements.txt

Initial dataset contains a description of all cities in Russia. The top 30 cities are chosen by the population.

SA implementation follows the notes from the Task. A few considerations are made to improve performance:

• Path distances are computed in constant O(1) time by observing the fact that two successive paths x_{t+1} and x_{t} differ only in two positions.
• Early stopping is used when acceptance ratio alpha becomes equal to np.nan. Acceptable non-nan paths are observed and one of them is chosen at random to continue the search. When all possible paths cannot be accepted (alpha=np.nan for all new paths) algorithm ends execution. A more detailed description is available in report

Simulated Annealing is compared for four different values of annealing rate: 0.9 (fast), 0.95 (middle), 0.99 (slow) and 0.997 (very slow).

For each experiment run the same initial path is used:

Distances of optimal paths for each annealing rate and number of taken iterations are shown in the table below:

Combined convergence rates plot:

Convergence rates and optimal paths for each annealing rate are shown below.

Convergence animation

Convergence animation

Convergence animation

Convergence animation

Simulated Annealing can indeed solve the Traveling Salesman problem and find optimal (to some extend) solutions in a small amount of time.

Slow cooling in SA converges to a better solution, however, results may depend on the pseudo random procedure of sampling the next path from the distribution of paths.