Tavelling salesman tsp problem on the l1-metric plane

Assignment Help Application Programming

Reference no: EM13347662

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 = {P₁, P_2,..., P_n} of n points representing the locations of n cities. The coordinates of P_i is (x_i, y_i). For simplicity, the coordinates x_iand y_i are integers in [0..1000), i.e., 0 ≤ x_i, y_i ≤ 999, i= 1,2,..,n. The distance between P_iand Pjis defined as |x_i- x_j|+|y_i- y_j|.

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

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 P₁;

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 ← P₁;

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 P₁) 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: EM13347662

Questions Cloud

Prepare an assembly program that reads in a number of cents : prepare an assembly program that reads in a number of cents. the program will write out the number of dollars and cents

1 given the following code and the assembler equivalent to : 1. given the following code and the assembler equivalent to the rightfor i999 igt0 i-- xixiyiloopnbspnbsp

Question 1 a mary is celebrating her 30th birthday she has : question 1 a mary is celebrating her 30th birthday she has decided that as from her 31st birthday she must start to

Background informationchris white was a forestry technician : background informationchris white was a forestry technician who had been searching for several years for a business

Tavelling salesman tsp problem on the l1-metric plane : travelling salesman tsp problem on the l1-metric plane problem description a travelling salesman wants to make a tour

Industrial designindustrial design differs from : industrial designindustrial design differs from conventional design engineering in terms of largely aesthetic and

Background informationeileen timmons was a registered nurse : background informationeileen timmons was a registered nurse living in salmon river newfoundland. a single parent with

We want to divide n students into m groups of the same size : we want to divide n students into m groups of the same size where each student is a member of exactly one group. the

You will need to model each population in terms of a nite : you will need to model each population in terms of a ?nite number of individuals which can increase or decrease each

User Account

All Pages