Traveling Salesman Problem (aka The Bicycle Thief)

Goals

Learn about the Traveling Salesman Problem, considered one of the most important theoretical problems in computer science.
Learn to adapt linked lists to the needs of your problem.

Submission

Submit Tour.java and your readme_tsp.txt file, and answer the questions. You may also submit an extra.zip file containing your extra credit implementation and any additional files it requires.

End-of-Semester Evaluation

Please take a few minutes to fill out our anonymous end-of-semester evaluation. While the University's evaluation gives limited (but helpful) feedback to your fellow students through Penn Course Review, to the Dean's office, and to our chair, this survey is a way to quickly give more directed feedback to us and to your TAs.

Background

Given N cities, the goal of a traveling salesman is to visit each of them exactly once (and arrive back home) while keeping the total distance traveled as short as possible. Stated more abstractly, the goal is to find a path connecting N points in a plane that passes through each point exactly once. Implement three greedy heuristics to find good (but not optimal) solutions to the traveling salesman problem (TSP). In doing this assignment, You should (i) learn about the notorious traveling salesman problem, (ii) get more practice with linked lists, and (iii) learn to adapt them to your problem.

1,000 points optimal tour

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 such as vehicle routing, circuit board drilling, VLSI design, robot control, X-ray crystallography, machine scheduling, and computational biology.

Greedy heuristics. The traveling salesman problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours and pick the shortest one; 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 in-order, nearest neighbor and smallest detour 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.

In-Order heuristic: Insert the next point at the end of the current tour. This heuristic is very useful for testing since it is among the simplest to implement, and it is easy to work out the solution by hand.
Nearest neighbor heuristic: Read in the next point, and add it to the current tour after the point to which it is closest. (If there is more than one point to which it is closest, insert it after the first such point you discover.)
Smallest increase heuristic: Read in the next point, and add it to the current tour where it will cause the shortest detour, i.e. where it results in the least possible increase in the tour length. (If there is more than one point, insert it after the first such point you discover.)

Getting Started:

Download data.zip archive and unzip it in the folder where you will complete your assignment, just as you did for NBody. This archive contains Point.java, TourInterface.java, client programs for each of the heuristics, the readme_tsp.txt template and a range of data files. There are several small data files in the zip archive for debugging purposes, as well as the larger data files that you need for the readme_tsp.txt questions. There is also a client program TSPTimer.java to help you do the performance analysis part of the assignment.
Study the Point.java API. Its main() method reads in data from standard input in the TSP input format and draws the points to standard draw.

Point.java represents a point in the plane, as described by 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 that)           // draw line segment between the two points
double distanceTo(Point that)       // return Euclidean distance between the two points

Each Point object can return a string representation of itself, draw itself to standard draw, draw a line segment from itself to another point using standard draw, and calculate the Euclidean distance between itself and another point.

Study the TourInterface.java API, which your Tour class must implement:



public interface TourInterface
------------------------------------------------------------------------------------------------------
  void show()                     // print the tour to standard output
  void draw(Point p)              // draw the tour to standard draw
                                  // any edge starting or ending at p should be in a distinct color
   int size()                     // number of points on tour
double distance()                 // return the total distance of the tour
  void insertInOrder(Point p)     // insert p at the end of the tour
  void insertNearest(Point p)     // insert p using nearest neighbor heuristic
  void insertSmallest(Point p)    // insert p using smallest increase heuristic

Part I: Tour Data Type

Your task is to create a Tour data type that represents the sequence of points visited in a TSP tour. It must implement the TourInterface interface.

Create your Tour class, with empty implementations of each method in the TourInterface class and appropriate header and method comments. Your class should implement TourInterface and should compile, but none of the methods should do anything. This gives you a skeleton that you can fill in and test piece by piece.
Represent the tour as a linked list, where each node contains a Point. At the end of the list, include one additional node that contains the first point on the tour. In other words, your list should contain two different nodes containing the first point on the tour, one at the beginning of the list and one at the end. You may design your linked list data structure however you like, (with or without sentinel nodes, iterative or recursive). Any classes you write should be inner classes of Tour.java (similar to the way Node is an inner class of LinkedList in the War! assignment). Since these are private, inner classes, they do not have to follow any specific API or be named in any specific way. You may adapt your own linked list code from the War! assignment, but you may not use Java's built-in LinkedList data type or anyone else's linked list code.
Write the following two constructors, both public:
- public Tour(); // Create an empty Tour
- public Tour(Point a, Point b, Point c, Point d); // Create a Tour with the four points a, b, c, d in that order. This constructor is useful for debugging. Your linked list structure for this case should match the following figure:

Implement the method show(). It should print out each Point in tour in order using System.out.println(). The first point's repeat node at the end of the list is an implementation detail and should not be counted. Once you have gotten this working, you are encouraged to modify it and/or add additional tests to main() as you add functionility to your Tour class.



  // main method for testing
  public static void main(String[] args) {
    // define 4 points forming a square
    Point a = new Point(100.0, 100.0);
    Point b = new Point(500.0, 100.0);
    Point c = new Point(500.0, 500.0);
    Point d = new Point(100.0, 500.0);

    // Set up a Tour with those four points
    // The constructor should link a->b->c->d->a
    Tour squareTour = new Tour(a, b, c, d);

    // Output the Tour
    squareTour.show();
  }

If your method is working properly, you will get the following output for the 4 city problem above.



(100.0, 100.0)
(500.0, 100.0)
(500.0, 500.0)
(100.0, 500.0)

Implement the method size() to return the total number of points in the tour. The first point's repeat node at the end of the list is an implementation detail and should not be counted. If the tour has 0 points, you should return 0.
Implement the method distance(). It is very similar to show(), except that you will need to invoke the method distanceTo() in the Point data type. Add a call to Tour's distance() method in the main() and print out the distance and size. The 4-point example has a distance of 1600.0. If the tour has 0 points, distance() should return 0.0.
Implement the method draw(Point p). It is also very similar to show(), except that you will need to invoke the method drawTo() in the Point data type. If the tour has 0 points, you should not draw anything. Any edge that starts or ends at the point p should be drawn in a different color from the rest of the tour. (For example, our reference implementation draws those edges in red instead of black.) If p is null, then all edges should be drawn in the usual color. This is useful to animate which point and edges were just added when building up the tour. Refer to the documentation for StdDraw.setPenColor() on the StdDraw reference page to see how to change colors in StdDraw.
You will need to include the statements
```
StdDraw.setXscale(0, 600);
StdDraw.setYscale(0, 600);
```
in your main() before you call the Tour draw() method. The four point example above should produce a square.

Part II: Creating the Tour

Implement insertInOrder() to add a point to the end of your tour. To test this method, use the supplied client program, OrderInsertion.java and specify one of the shorter input files (e.g. tsp10.txt) as a command-line argument. The order of the points output should match the order of the points in the input file. Points will get added to your tour at a rate of 1 per second. The edges leading in and out of the last point should be drawn in a different color if you implement Tour.draw() correctly. (You can speed up the animation by reducing the wait time to something smaller than 1000ms in the call to StdDraw.show() in OrderInsertion.)

You should see the following output when running insertInOrder() on tsp10.txt and tsp1000.txt (you should comment out the animation lines or speed the animation up a lot in OrderInsertion before attempting tsp1000.txt:

> java OrderInsertion tsp10.txt (110.0, 225.0) (161.0, 280.0) (325.0, 554.0) (490.0, 285.0) (157.0, 443.0) (283.0, 379.0) (397.0, 566.0) (306.0, 360.0) (343.0, 110.0) (552.0, 199.0) Tour distance = 2586.6759 Number of points = 10

> java OrderInsertion tsp1000.txt (185.0411, 457.8824) ... (334.9344, 524.7824) (396.0952, 150.0943) (462.1732, 486.3889) (193.5595, 527.8311) (331.8716, 533.5717) (748.401, 462.4281) (94.0231, 544.9736) (254.982, 302.2548) Tour distance = 327693.7622 Number of points = 1000

10 points ordered 1000 points ordered

Implement insertNearest(). To determine where to insert the point p, compute the Euclidean distance between each point in the tour and p. As you proceed, store the node containing the closest point and its distance to p. After you have found the closest node, create a node containing p, and insert it after the closest node. If p is equally close to more than one point in the tour, insert it after the first such point. As a check, tsp10-nearest.ans cotains resulting tour for the 10 city problem which has distance 1566.1363. Note that the optimal tour tsp10-optimal.ans has distance 1552.9612 so this rule does not, in general, yield the best tour. Look below to get instructions on how to test insertNearest().
Implement insertSmallest(). You should add p where it will result in the shortest detour from the current tour, i.e. where it will result in the smallest increase in total tour length. If you add p between points s and t in the current tour, the length of the detour is the distances from s to p and from p to t, less the distance from s to t.
As a check, tsp10-smallest.ans contains the result tour, which has distance 1655.7462. In this case, the smallest insertion heuristic actually does worse than the nearest insertion heuristic (although this is not typical).
Input and testing. The input format will begin with two integers w and h, followed by pairs of 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. Many test data files are available. As an example, tsp1000.txt contains the following data:
```
775 768
185.0411 457.8824
247.5023 299.4322
701.3532 369.7156
563.2718 442.3282
144.5569 576.4812
535.9311 478.4692
383.8523 458.4757
329.9402 740.9576
...
254.9820 302.2548
```

After implementing Tour.java, use the client program NearestInsertion.java to read in the points from standard input, run the nearest neighbor heuristic; print the resulting tour, its distance, and its number of points to standard output; and draw the resulting tour to standard draw. SmallestInsertion.java is analogous but runs the smallest insertion heuristic.

> java NearestInsertion tsp1000.txt (185.0411, 457.8824) (198.3921, 464.6812) (195.8296, 456.6559) (216.8989, 455.126) (213.3513, 468.0186) (241.4387, 467.413) (259.0682, 473.7961) (221.5852, 442.8863) ... (264.57, 410.328) Tour distance = 27868.7106 Number of points = 1000

> java SmallestInsertion tsp1000.txt (185.0411, 457.8824) (195.8296, 456.6559) (193.0671, 450.2405) (200.7237, 426.3461) (200.5698, 422.6481) (217.4682, 434.3839) (223.1549, 439.8027) (221.5852, 442.8863) ... (186.8032, 449.9557) Tour distance = 17265.6282 Number of points = 1000

1000 points nearest 1000 points smallest

Note that NearestInsertion and SmallestInsertion only print out the tour if it contains fewer than 20 points. This makes them a bit more practical for large data sets.
By default, NearestInsertion and SmallestInsertion will both add points at a rate of 4 points/second, and will animate the tour as it grows. If you implemented Tour.draw() correctly, the edges that were just added at each step will be a different color from your other edges. Change the delay in the call to StdDraw.show() to change the animation speed, or comment out the four lines controlling animation entirely to diable it. These lines are clearly commented in each program.
Note: Remove or comment out any debugging print statements before testing the large input files or your program will take forever to run. Large inputs will produce so much debug output you won't be able to interpret it anyway. If you want to animate large input files, you might also want to modify the animation to only redraw every 20 insertions.
If you'd like to check your work, for usa13509.txt we get distances of 77449.9794 and 45074.7769 for nearest insertion and smallest insertion, respectively. For circuit1290.txt we get 25029.7905 and 14596.0971.

Part III: Analysis

Estimate the running times of your programs as a function of the number of points N.

Use TSPTimer.java to run the nearest and smallest heuristics for N = 1,000, and repeatedly double N until you reach 128000. Just compile TSPTimer and run it with N as the only command line argument. You should be able to reason about whether each heuristic is logarithmic, linear, n log n, quadratic, cubic, etc., then verify that the actual times fit the expected pattern. Document the times in your readme file.
When timing your programs, TSPTimer does not animate the results on the screen because this would be a major bottleneck.

Contest and extra credit.

Implement a better heuristic in a class TourEC.java. 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. The speed of your program may vary depending on your computer, but in general it should be at most five minutes for tsp1000.txt. You are also not required to use the Tour data type or TourInterface interface for you extra credit solution.

Any code beyond TourEC.java necessary to run your extra credit should be included in extra.zip. You do not have to use Point.java or any of your code from the main part of the assignment. (You may also modify Point.java in any way you wish for the extra credit.) However, if you do use any of that code, you should include it in your extra.zip file or your TA may not be able to compile your program.

Be warned that this is a relatively difficult extra credit, although it gives an opportunity to learn a great deal about an extremely important problem. Answer the relevant questions in the readme_tsp.txt file. We will award a special prize to the student who finds the shortest tour around the 1,000-point set.

Enrichment

The best known tour for tsp1000.txt is a solution of length 15476.519, which was found using the Concorde TSP solver.
Georgia Tech's TSP site contains a wealth of interesting information including many applications of the TSP and two TSP games.
Here's a 13,509 city problem that contains each of the 13,509 cities in the continental US with population over 500. The optimal solution was discovered in 1998 by Applegate, Bixby, Chvatal and Cook using theoretical ideas from linear and integer programming. The following 15,112 city problem was solved to optimality in April, 2001, and is the current world record. It took 585,936,700 CPU seconds (along with alot of cleverness) to find the optimal tour through 15,112 cities in Germany.
Some folks even use the TSP to create and sell art. Check out Bob Bosch's page. You can even make your own TSP artwork.
Here is a New York Times article on finding an optimal traveling politician tour in the state of Iowa.
Here's a survey article on heuristics for the TSP.