COS 126 Traveling Salesperson Problem |
Programming Assignment |
Given a set of N points in the plane, the goal of a traveling salesperson is to visit all of them (and arrive back home) while keeping the total distance traveled as short as possible. Write a program to compute an approximate solution to the traveling salesperson problem (TSP), and use it to find the shortest tour that you can, connecting a given set of points in the plane.
Perspective. The importance of the TSP does not arise from an overwhelming demand of salespeople to minimize their travel distance, but rather from a wealth of other applications, many of which seem to have nothing to do with the TSP at first glance. Real world application areas include: vehicle routing, circuit board drilling, VLSI design, robot control, X-ray crystallography, machine scheduling, and computational biology.
Greedy heuristics. The traveling salesperson problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours, but, in practice, the number of tours is so staggeringly large (roughly N factorial) that this approach is useless. For large N, no one knows an efficient method that can find the shortest possible tour for any given set of points. However, many methods have been studied that seem to work well in practice, even though they are not guaranteed to produce the best possible tour. Such methods are called heuristics. Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally. Start with a one-point tour (from the first point back to itself), and iterate the following process until there are no points left.
Point data type. Point.java represents a point in the plane. Each Point object can print itself to standard output, plot itself using standard draw, plot a line segment from itself to another point, and calculate the Euclidean distance between itself and another point. The Point class has the following API:
public class Point (2D point data type) --------------------------------------------------------------------------------------- Point(double x, double y) // create the point (x, y) String toString() // return string representation void draw() // draw point using standard draw void drawTo(Point b) // draw line segment between the two points double distanceTo(Point b) // return Euclidean distance between the two points
Tour data type. Next, create a Tour data type that represents the sequence of points visited in a TSP tour. Represent the tour as a circular linked list of nodes, one for each point. Each Node will contain a Point and a reference to the next Node in the tour. Within Tour.java, define a nested class Node in the standard way.
Each Tour object should be able to print its constituent points to standard output, plot its points using standard draw, compute its total distance, and insert a new point using either of the two heuristics. Write a class named Tour that has the following API:private class Node { private Point p; private Node next; public Node(Point p) { // create one Node this.p = p; this.next = null; } }
public class Tour (TSP tour data type) --------------------------------------------------------------------------------------- Tour() // create an empty tour Tour(Point a, Point b, Point c, Point d) // create a 4 point tour for debugging void show() // print the tour to standard output void draw() // draw the tour double distance() // return the total distance of the tour void insertSmallest(Point p) // insert p using smallest insertion heuristic void insertNearest(Point p) // insert p using nearest neighbor heuristic
Input format. The input format will begin with two integers w and h, followed by pairs of real-valued x and y coordinates. All x coordinates will be real numbers between 0 and w; all y coordinates will be real numbers between 0 and h. As an example, the file tsp4.txt contains the following data
% more tsp4.txt 600 600 532.6531 247.7551 93.0612 393.6735 565.5102 590.0000 10.0000 10.0000
Testing. Many test data files are also available. Once you implement Tour.java, use the client program NearestInsertion.java to run the nearest insertion heuristic and print the resulting tour and its distance to standard output. Program SmallestInsertion.java is analogous but runs the smallest insertion heuristic. Programs NearestInsertionDraw.java and SmallestInsertionDraw.java are similar but they also plot the results using StdDraw. The programs read data from standard input. So, you should invoke as follows.
% java NearestInsertion < tsp10.txt
Analysis. Estimate the running time of your program as a function of N. Using TSPTimer, run the heuristics for increasing N as long as the execution time is less than 100 seconds. (i.e., Start with N = 1000, and repeatedly double N until the execution time is over 100 seconds.)
Getting started. The subdirectory tsp from the COS126 ftp site contains Point.java and two versions (with and without graphics) of the client programs for each heuristic. There are several small data files for debugging purposes, as well as the larger data files that you need for the readme questions. There is a client program TspTimer.java that you can use to help you do the performance analysis part of the assignment. The directory also contains StdIn.java, StdDraw.java, StdOut.java and this assignment's readme.txt file.
Submission. Submit Tour.java. Also, submit a readme.txt file and answer the questions.
Contest and extra credit.
Implement a better heuristic. For example,
observe that any tour with paths that cross can be transformed
into a shorter one with no crossing paths: add that improvement to
your program.
Here are some
other ideas.
Name your extra credit program ExtraCredit.java and submit it
along with any accompanying files.
Answer the relevant questions in the readme.txt file.
We will award a special prize to whomever finds the shortest
tour around the 1000-point set.