Travelling salesman problem

Assignment Help Programming Languages
Reference no: EM131595

TRAVELLING SALESMAN (TSP) PROBLEM ON THE L1-METRIC PLANE

  • Problem description: A travelling salesman wants to make a tour of the cities and returns back to the starting point. What is the minimum length tour?
  • Formal Definition:

o Input: A set S = {P1, P2, ..., Pn} of n points representing the locations of n cities. The coordinates of Pi is (xi, yi). For simplicity, the coordinates xi and  yi are integers in [0..1000), i.e.,  0  ≤ xi, yi  ≤ 999, i= 1,2,..,n. The distance between Pi and Pj is defined as |xi- xj|+|yi- yj|.

o Output: A TSP tour that starts from P1, visit all the cities (Pi, i=2,3..,n) and return back to starting point P1

o Objective: Minimize the total length of the TSP tour.

HEURISTICS

  • Minimum Spanning Tree (MST) Based Heuristic

o Construct a MST, T, for the points in S from starting point P1;

o Traverse around T to get the initial TSP tour for S;

o Exploit the triangular inequality and remove unnecessary visits in the TSP tour.

o Compute the length of the tour.

  • Nearest Neighbour Heuristic

o current position ← P1;

o Loop for n-1 steps

- At each step, choose to visit next the city that is closest to the current position;

- Update the current position;

o Including the closing edge (back to P1) in the tour;

o Compute the length of the tour.

TASKS

1. Implement the MST Based Heuristic;

2. Implement the Nearest Neighbour Heuristic;

3. Implement a function, randomSetGenerator that will generate a set of random points on the L1-metric Plane.

4. Conduct the following experiment for n=100

o Repeat the following for 10 times

- Call randomSetGenerator to generate a set S of n random points.

  • Feed S to the MST Based Heuristic. Record the length of the tour and the execution time.
  • Feed S to the Nearest Neighbour Heuristic. Record the length of the tour and the execution time.

o Compute the average length of the tour and the average execution time for the MST Based Heuristic.

o Compute the average length of the tour and the average execution time for the Nearest Neighbour Heuristic.

5. Repeat the above experiments for n = 200, 300, 400, 500, 600, 700, 800, 900 and 1000. Collect the statistics (average length of the tour and average execution time) from the experiments. Compare the two heuristics in term of the average length of the tour and average execution time.

Reference no: EM131595

Questions Cloud

Write an assembly program : Prepare an Assembly program that reads in a number of cents.
Vliw processor : VLIW processor - assembler
Calculate the risk : Calculate the risk and expected return for each asset.
Twin peaks building supplies : Chris White was a forestry technician who had been searching for several years for a business opportunity to combine with his forestry career
Travelling salesman problem : Travelling Salesman Problem on the L1-metric plane.
Project specification and plan : The Project Specification is a description of what you are working to achieve, and a Plan is the schedule proposed to achieve it
Capital improvement phase of the project : The governing body of the Order decided that it was no longer feasible to operate the convent, which had been built about sixty years ago, so it was advertised locally for sale.
Mathematical formulation of the model : Mathematical formulation of the model
Optimal translocation strategies : Optimal Translocation Strategies - use stochastic dynamic programming (SDP) to ?nd the optimal decisions

Reviews

Write a Review

Programming Languages Questions & Answers

  Write a haskell program to calculates a balanced partition

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition,

  Create an application to run in the amazon ec2 service

In this project you will create an application to run in the Amazon EC2 service and you will also create a client that can run on local machine and access your application.

  Explain the process to develop a web page locally

Explain the process to develop a Web page locally

  Write functions

These 14 questions covers java class, Array, link list , generic class.

  Programming assignment

If the user wants to read the input from a file, then the output will also go into a different file . If the user wants to read the input interactively, then the output will go to the screen .

  Write a prolog program using swi proglog

Write a Prolog program using swi proglog

  Create a custom application using eclipse

Create a custom Application Using Eclipse Android Development

  Create a application using the mvc architecture

create a application using the MVC architecture. No scripting elements are allowed in JSP pages.

  Develops bespoke solutions for the rubber industry

Develops bespoke solutions for the rubber industry

  Design a program that models the worms behavior

Design a program that models the worm's behavior.

  Writing a class

Build a class for a type called Fraction

  Design a program that assigns seats on an airplane

Write a program that allows an instructor to keep a grade book and also design and implement a program that assigns seats on an airplane.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd