Aim:
You are required to implement the Monte Carlo algorithm to solve the Odyssey of Ulysses 22 cities Travelling Salesman Problem (TSP). The problem (ulysses22.tsp) is available at TSPLIB (Links to an external site.)Links to an external site.. For your interest, here is an article about this problem: The Optimized Odyssey (Links to an external site.)Links to an external site..
Requirements:
You can use any programming languages to complete this assignment. However, if you want to use languages other than Matlab/Octave, you should make your program executable/runnable. For example, if you use Java, you need to compile it. If you use Python, make sure it can be run in a python online IDE such as TutorialPoint (Links to an external site.)Links to an external site.
. Your program should be able to read in the ulysses22.tsp file. Calculate distance based on Geographical distance. Please read this document (Links to an external site.)Links to an external site. (Section 2.4) to learn how to calculate Geographical distance. In order to check whether your implementation of the Geographical distance calculation is correct or not, you can download this file (Links to an external site.)Links to an external site., which gives you the optimal tour with the optimal distance of 7013. Implement the Monte Carlo algorithm. Execute 30 independent runs of your Monte Carlo algorithm with 1000 iterations and record the average distance and standard deviation from results of the 30 runs. Write a report to report your results. In the report, you should briefly introduce the Monte Carlo algorithm by using a flowchart and pseudo-code, discuss the pros and cons. You should also show intermediate solutions and their lengths at 1st, 500th and 1000th iterations during a typical run of your algorithm. You should plot a figure to show how the cost changes over the 1000 interactions of a typical run. You should also list all the average result and standard deviations obtained from the 30 runs of the algorithm.
Marking Scheme (total 10 points):
Correct calculation of the geographical distance. (1 marks).
Correct implementation of the Monte Carlo algorithm (4 marks)
Report: Satisfied requirement 6 (5 marks).
http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ulysses22.tsp https://www.zib.de/groetschel/pubnew/paper/groetschelpadberg2001a.pdf https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp95.pdf http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ulysses22.opt.tour
#Randomised #algorithms #travelling #salesman #problem
