Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
380CT_2023_TSP-Guidance/README.md
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
44 lines (30 sloc)
3.75 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Guide for the 380CT Assignment on TSP | |
Your work must be done in `Template.ipynb`. The actual part you need to work on is the **Metaheuristics section**. | |
The rest is meant to introduce you to the basics. | |
Start by first creating your repository, from this, by clicking on the green button **Use this template**. Then, clone your repository to your local machine. You can then open the notebook in Jupyter. | |
--- | |
- Ensure you have **Jupyter**. | |
- Either install [Jupyter](https://jupyter.org/install) alone or [Anaconda](https://www.anaconda.com/distribution). | |
- 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](https://www.linkedin.com/learning/introducing-jupyter/present-data-like-a-pro-with-jupyter) | |
- [Python for Data Visualization](https://www.linkedin.com/learning/python-for-data-visualization/setting-marker-type-and-colors) | |
- [Python Statistics Essential Training](https://www.linkedin.com/learning/python-statistics-essential-training/the-power-of-visualization) | |
- Load and study `Investigating TSP.ipynb`. | |
- Read the [Wikipedia article on TSP](https://en.wikipedia.org/wiki/Travelling_salesman_problem). Pay attention to the **Computing a solution** section, and especially to the `2-opt` techniques for defining neighbourhoods. | |
--- | |
- Now you can use `Template.ipynb` to start writing the part you need to submit (about meta-heuristics). | |
- I propose you work as follows (You don't have to follow this though!): | |
* Ensure you are familiar with the TSP problem and 2-opt local search techniques. (See this [Wikipedia article](https://en.wikipedia.org/wiki/Travelling_salesman_problem)) | |
* Watch the [guest lecture videos](https://github.coventry.ac.uk/pages/ab3735/380CT_2022/lectures/lecture7/) and check the literature related to TSP and the meta-heuristics you are thinking of. | |
* Write the code for the meta-heuristic that you have chosen. I recommend GRASP. | |
- You may try Google Colab and/or Microsoft Azure if that helps you work better, but please be aware that I am not sure about their GDPR compliance. | |
I should emphasise here that "exhaustive search" and "greedy" are **not* meta-heuristics, nor are 2-opt. Ensure this is clear to you. | |
## Bibliography | |
- Applegate, DL, Bixby, RE, Chvátal, V, Cook, WJ, 2007, [The Traveling Salesman Problem: A Computational Study](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA5199622620002011), Princeton University Press, Princeton. | |
- Cook, WJ 2012, [In Pursuit of the Traveling Salesman: Mathematics at the Limit of Computation](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA5199665280002011), Princeton University Press, Princeton. | |
- Glover, F, & Kochenberger, GA (eds) 2002, [Handbook of Metaheuristics](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA51109755880002011), Kluwer Academic Publishers, Secaucus. | |
- Gutin, G, & Punnen, AP (eds) 2002, [The Traveling Salesman Problem and Its Variations](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA51125059450002011), Springer, New York, NY. | |
- Pintea, C.-M., 2014. [Advances in Bio-inspired Computing for Combinatorial Optimization Problems](https://locate.coventry.ac.uk/permalink/f/1r06c36/COV_ALMA5155140430002011). 1st ed. 2014. | |
- Steven, SS 2008, [The Algorithm Design Manual](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA5190160580002011), Springer, England. | |
- You may also find its [companion website](http://algorist.com/problems/Traveling_Salesman_Problem.html) useful. | |
- Talbi, E.-G., 2009. [Metaheuristics from design to implementation](https://locate.coventry.ac.uk/permalink/f/gr8698/COV_ALMA51117060170002011), Hoboken, NJ: John Wiley & Sons. |