Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Java Expert


Home >> Java

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

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

• Formal Definition:

- Input: A set S = {P1, P2, …, Pn} of n points representing the locations of n cities. The coordinates of Pi is (xi, yi). For straightforwardness, 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|.

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

- Objective: Minimize the total length of TSP tour.

HEURISTICS

• Minimum Spanning Tree (MST) Based Heuristic

- Construct a MST, T, for the points in S from beginning point P1;

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

- Exploit the triangular inequality and remove needless visits in the TSP tour.

- Evaluate the length of the tour.

• Nearest Neighbor Heuristic

- Present position ← P1;

- Loop for n-1 steps

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

- Update present position;

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

- Evaluate 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 subsequent experiment for n=100

- Repeat the following for 10 times

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

• Feed S to 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 implementation time.

- Evaluate the average length of the tour and the average execution time for the MST Based Heuristic.

- Evaluate 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.

Programming language: recommend Java.

Java, Programming

  • Category:- Java
  • Reference No.:- M91646

Have any Question? 


Related Questions in Java

Tennis score boardyou will write a gui that can be used to

Tennis Score Board You will write a GUI that can be used to keep track of the score during a lawn tennis match at Wimbledon. You will be using MVC (Model View Controller) so you will submit the Model and then the View an ...

Java application - distancecalculatorcreate a java

Java Application - DistanceCalculator Create a Java application named DistanceCalculator.java to solve the following problem. An application is needed to allow a user to enter two cities and display the distances between ...

Assignmentbullusing html css and javascript design a

Assignment • Using HTML, CSS and JavaScript. Design a webpage with the following: • The design of all Web pages in the site must include: o a header at the top of the page, o a horizontal navigation bar below the header, ...

Questions for java programing answer each question with at

QUESTIONS FOR JAVA PROGRAMING (answer each question with at least 5 sentences) 1. Discuss why it is necessary to use repetitive and selective statement. Use segment codes to demonstrate your understanding. Explain why yo ...

Write a java application using netbeans integrated

Write a Java application using NetBeans Integrated Development Environment (IDE) that calculates the total annual compensation of a salesperson. Consider the following factors: • A salesperson will earn a fixed salary of ...

Assignmentpersonasas has been outlined there are three

Assignment Personas As has been outlined there are three specific groups who would be considered the core demographic for the users of this site. Sue Smith Age: 35 years old Gender: Female Location: Vancouver, BC Educati ...

Java application product and inventoryreadingchapter 9 of

Java Application Product and Inventory Reading Chapter 9 of the text Moodle: Class Coding Style Java Classes Java Application Product and Inventory Product.java Create a class to encapsulate the data and behavior of a pr ...

1how does java support the concept of encapsulation2

1. How does Java support the concept of encapsulation? 2. Describe the difference between an object and a class. 3. What is the difference between the contents of a Java variable of a primitive type and a Java variable o ...

Assignment introduction to programming using java1 write a

Assignment: Introduction to Programming Using Java 1. Write a program that uses one of the Map classes to implement a contact list. Contact information should include first name, last name, a phone number and an email ad ...

Jva programmingmodify the given java application attached

JAVA PROGRAMMING Modify the given Java application (attached) using NetBeans IDE to meet these additional and changed business requirements: • The application will now compare the total annual compensation of at least tw ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen