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.