This is a Python project which computes a heuristic solution to the Travelling Salesman Problem in ~3 minutes.

The program applies different strateges to datasets of different sizes using a combination of greedy, 2-opt, dismantling cross path, and simulated annealing algorithms.

It also provides a visualization module to present to result graphically.

This project runs on Python3.

The program applies different strategies to datasets of different sizes to get the best tour possible in ~3 minutes.
It first uses greedy_rotate to find a reasonably short path to begin with.
Then,

• for datasets with <= 50 nodes:
      simulated_annealing is used to further optimize the path.
      If you have good luck it might find you the optimal path.
• for datasets with > 50 and <= 500 nodes:
      cross_path_dismantling followed by two_opt are used to further optimize the path,
      because the size of the dataset is too large for simulated_annealing to yield a good result in 3 minutes.
• for datasets with >500 nodes:
      only two_opt is used to further optimize the path,
      becasue the dataset size is tpp big even for cross_path_dismantling to complete within 3 minutes.

• solve_tsp.py is the main script which parses the input dataset and outputs the result.
• algo/ contains the 4 algorithm modules.
• plotter/ contains the TSP tour visualization module.
• datasets/ contains a collection of datasets for demonstration.

Install all the dependencies from Pypi:

$ pip install -r requirements.txt

For a quick start, run

$ python solve_tsp.py <input-file-directory>
# example: python solve_tsp.py datasets/wi29.txt

The result will be stored in a newly created output-tour.txt in the same directory.

To specify the output file, run

$ python solve_tsp.py <input-file-directory> <output-file-directory>
# example: python solve_tsp.py datasets/wi29.txt output.txt

To visualize the result, add the -v flag

$ python solve_tsp.py <input-file-directory> <output-file-directory> -v
# example: python solve_tsp.py datasets/wi29.txt output.txt -v

A sample visualization:

To see more information about the usage, run

$ python solve_tsp.py -h

The program takes a dataset formatted as follows:

1 20833.3333 17100.0000
2 20900.0000 17066.6667
3 21300.0000 13016.6667
4 21600.0000 14150.0000
5 21600.0000 14966.6667
6 21600.0000 16500.0000
7 22183.3333 13133.3333
8 22583.3333 14300.0000
9 22683.3333 12716.6667
10 23616.6667 15866.6667

The program creates an output file formatted as follows:

tour cost: 27767
tour: [7, 3, 2, 6, 8, 12, 13, 15, 23, 24, 26, 19, 25, 27, 28, 22, 21, 20, 16, 17, 18, 14, 11, 9, 10, 5, 0, 1, 4, 7]

• algo.greedy_rotate: a greedy path finder, except it takes every node in the dataset as the starting point and computes the greedy path once, then returns the shortest one among them.
• algo.two_opt: a basic 2-opt path optimizer.
• algo.cross_path_dismantling: a path optimizer which detects cross paths and dismantles them.
• algo.simulated_annealing: a basic simulated annealing path optimizer.