Randomised algorithms for travelling salesman problem

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

Share This Post

Email
WhatsApp
Facebook
Twitter
LinkedIn
Pinterest
Reddit

Order a Similar Paper and get 15% Discount on your First Order

Related Questions

Module 6 Discussion     Treatments for Genitourinary Tract Disorders 1. Describe

Module 6 Discussion     Treatments for Genitourinary Tract Disorders 1. Describe urinary tract infection, causes, symptoms and treatment 2. Discuss treatment for benign prostatic hyperplasia 3. Describe overactive bladder, causes, symptoms and treatment  4. Treatment options and recommendations for different STIs (Chlamydia, Gonorrhea and Syphilis) Submission Instructions: · Your initial

  Part 1: Creating a Transition Plan Read “Case Scenario: Alex.” Create an IDEA-compliant transition plan for Alex using a template of your choice. The

  Part 1: Creating a Transition Plan Read “Case Scenario: Alex.” Create an IDEA-compliant transition plan for Alex using a template of your choice. The plan should address the following. Identify Alex’s strengths, preferences, and interests. Measurable postsecondary goals for education/vocational training, jobs and employment, and independent living. Support for