Due date: End of Week 11.

Brief

• Write code for a heuristic algorithm that solves the travelling salesman problem for a set of cities. That is, find the route that visits each city once and only once, returning to the starting city, that minimises the totakl distance travelled.
• Download the set of 100 Spanish towns and cities and distance matrix.
• Use the above code to find the optimal circular route around the set of cities.
• Write a two page report on your work.

Further Details

• You will submit a maximum of three pages including any references, figures and tables; and one fully documented Jupyter Notebook.
• If you exceed 3 pages only the first three pages will be read and the rest discarded.
• You are free to use whatever report structure you wish.
• You will also submit a single Jupyter Notebook including all code used to solve the problem. This includes any functions or classes used to write the heuristic algorithm, the use of those functions or classes to solve the problem, and any analysis.
• A marker should be able to exactly reproduce all reported results using the provided Jupyter Notebook.

Example

Here is an example report and Jupyter Notebook for the dominating set problem (as seen in Session 5):

• Example report.
• Example notebook.

Supplementary data:

• french_locations.csv
• french_distances.csv
• france.geojson (taken from here.)

How it will be marked

• THE CODE (50%)
  • Correctness (20%)
  • Clarity & Readability (20%)
  • Appropriateness (10%)
• THE REPORT (50%)
  • Comprehension & Understanding (25%)
  • Organisation & Clarity (25%)