Guide for the 380CT Assignment on TSP

The actual part you need to submit is the Metaheuristics section. The rest is meant to introduce you to the basics.

Lab 5

• Ensure you have Jupyter, and load Investigating TSP.ipynb.

  • Either launch Anaconda through AppsAnywhere, or if you are working on your machine then I recommend installing Anaconda.

• Familiarise yourself with Jupyter functionaility. Consider taking LinkedIn Learning courses (free through the university) or any suitable alternatives. Here is a recommended set (e.g. each member of the group takes one):

  • Introducing Jupyter
  • Get Ready for Your Coding Interview
  • Python for Data Visualization
  • Python: Programming Efficiently
  • Python Statistics Essential Training

• Study Investigating TSP.ipynb.

  • Can you improve any of the functions implemented in Investigating TSP.ipynb to make them mor efficient?
  • See how large you can make $n$ while testing exhaustive_search().
  • Check that greedy_nearest_neighbours() is correct. If not then fix it!

• Read the Wikipedia article on TSP. Pay attention to th Computing a solution section, and especially to the 2-opt and 3-opt techniques for defininf neighbourhoods.

• Experiment with generating your own graph families. For example:

  • Euclidean graphs: generate points using (x,y) coordinates, then generate the adjacency matrix by calculating all the required distances. Recall that the distance between two points (x₁,y₁) and (x₂,y₂) is sqrt[(x₁-x₂)²+(y₁-y₂)²].
  • Graphs with obvious shortest cycle: think of a graph where all the distances are 2 except for the edges on a predefined cycle, where the distance is 1. Such a graph would be useful for testing/debugging the nearest neighbours greedy search.

Graph ideas...

Whiteboard from a tutorial session:

Bibliography

• Applegate, DL, Bixby, RE, Chvátal, V, Cook, WJ, 2007, The Traveling Salesman Problem: A Computational Study, Princeton University Press, Princeton.
• Cook, WJ 2012, In Pursuit of the Traveling Salesman: Mathematics at the Limit of Computation, Princeton University Press, Princeton.
• Glover, F, & Kochenberger, GA (eds) 2002, Handbook of Metaheuristics, Kluwer Academic Publishers, Secaucus.
• Gutin, G, & Punnen, AP (eds) 2002, The Traveling Salesman Problem and Its Variations, Springer, New York, NY.
• Pintea, C.-M., 2014. Advances in Bio-inspired Computing for Combinatorial Optimization Problems. 1st ed. 2014.
• Steven, SS 2008, The Algorithm Design Manual, Springer, England.
  • You may also find its companion website useful.
• Talbi, E.-G., 2009. Metaheuristics from design to implementation, Hoboken, NJ: John Wiley & Sons.