Parameterising Simulated Annealing for the Travelling Salesman Problem

Abstract

The Travelling Salesman Problem is a well known NP-Hard problem. Given a list of cities, find the shortest path that visits all cities once.

Simulated annealing is a well known stochastic method for solving optimisation problems and is a well known non-exact algorithm for solving the TSP. However, it's effectiveness is dependent on initial parameters such as the starting temperature and cooling rate which is often chosen empirically.

The goal of this project is to:

• Determine if the optimal starting temperature and cooling rate can be parameterised off the input
• Visualise the solving process of the TSP

Usage

Running the code

Examples of common commands to run the files are shown below. However, both src/main.py and src/benchmark.py have a --help that explains the optional flags.

# To visualise annealing on a problem set from the input file
python3 -m src.main -f <input_file>

# To visualise TSP on a random graph with 
   
     number of cities
   
python3 -m src.main -c <city_count>

# Benchmark the parameters using all problems in the data folder
python3 -m src.benchmark

Keyboard Controls

There are also ways to control the visualisation through key presses while it plays.

Creating your own model

If you would like to create your own instance of the TSP problem and visualise it:

1. Create a new file
2. Within this file ensure you have the line NODE_COORD_SECTION, and below that EOF.
3. Between those two lines, you can place the coordinates of the cities, i.e. for the nth city, have a line like , where x and y are the x and y coordinates of the city.
4. Run python3 -m src.main -f , where is the path to the file you have just made.

Files

FAQ

What do you use to generate the graphics?

This project uses the p5py library for visualisation. Unfortunately, (to of my knowledge) this may not work with WSL.

What are the results of your research?

Idk. Still working on it.

What can I do to contribute?

Pog.

This is more of a "what I would I do if I have more time" but whatever, let's say you actually are interested. Disclaimer - the code isn't particularly polished (from me pivoting project ideas multiple times).

• If you're up for a challenge, it would be interesting to implement LKH (Lin-Kernighan heuristic) efficiently
• Implement other algorithms - they just need to extend the Solver abstract class to work with the frontend
• Add a whatever city you want and it's coordinates to data/world.tsp!