9. TSP
Download Project
 Submit to TigerFile
Goals
 To learn about the notorious traveling salesperson problem.
 To learn to use linked lists.
 To get more practice with data types.
Getting Started

Download and expand the project
zip
file for this assignment, which contains the files you will need for this assignment. 
This is a partner assignment. (See instructions on Ed for creating a TigerFile group.)

Read Section 4.3. Pay particular attention to the parts that deal with linked lists.

In this assignment, “linked list” always refers to a “circularly linked list.”

Review the Case Study:
CircularQuote.java
before starting this assignment.
Background
Goal. Given \(n\) points in the plane, the goal of a traveling salesperson is to visit all of them and return to the starting point, while keeping the total length traveled as short as possible. In this assignment, you will implement and evaluate two greedy heuristics to find good, but not optimal, solutions to the traveling salesperson problem. For example the figure on the left (below) shows 1000 points in the plane. The figure on the right (below) shows an optimal tour for these points.
1,000 points  Optimal 

Context. The importance of the TSP does not arise from an overwhelming demand of salespeople to minimize their travel length, but rather from a wealth of other applications such as vehicle routing, circuit board drilling, VLSI design, robot control, Xray crystallography, machine scheduling, and computational biology.
Greedy heuristics. The TSP is a notoriously difficult combinatorial optimization problem. In principle, you can enumerate all possible tours and pick the shortest one; in practice, the number of tours is so staggeringly large (nearly n factorial) that this approach is useless. For large n, no one knows of 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 do not guarantee to produce the best possible tour. Such methods are called heuristics.
Approach
Your main task is to implement the nearest neighbor and smallest increase insertion heuristics for building a tour incrementally, one point at a time. Start with a onepoint tour (from the first point back to itself), and iterate the following process until there are no points left:

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 after the point 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.
Implementation Tasks
 You must implement one class:
Tour.java
 We provide several other classes and files:
Point.java
NearestNeighbor.java
SmallestInsertion.java
TSPTimer.java
TSPVisualizer.java
 data files
Point.java
We provide a Point
data type in the project folder. The Point
data type represents points, \((x, y)\) in the plane, as described by the following API:
public class Point {
// creates the point (x, y)
public Point(double x, double y)
// returns the Euclidean distance between the two points
public double distanceTo(Point that)
// draws this point to standard drawing
public void draw()
// draws the line segment between the two points
public void drawTo(Point that)
// returns a string representation of this point
public String toString()
}
Do not implement Point.java
 use the class we provided.
Tour
Create a Tour
data type that represents the sequence of points visited in a TSP tour. Represent the tour as a circularly linked list of nodes, one for each point in the tour. Each Node
contains two references:
 one to the associated
Point
and  the other to the next
Node
in the tour.
Within Tour.java
, define a nested class Node
in the standard way:
private class Node {
private Point p;
private Node next;
}
Your Tour
data type must implement the following API:
public class Tour {
// creates an empty tour
public Tour()
// creates the 4point tour a>b>c>d>a (for debugging)
public Tour(Point a, Point b, Point c, Point d)
// returns the number of points in this tour
public int size()
// returns the length of this tour
public double length()
// returns a string representation of this tour
public String toString()
// draws this tour to standard drawing
public void draw()
// inserts p using the nearest neighbor heuristic
public void insertNearest(Point p)
// inserts p using the smallest increase heuristic
public void insertSmallest(Point p)
// tests this class by directly calling all constructors and instance methods
public static void main(String[] args)
}
String representation format.
The toString()
returns a String
containing the points, one per line, by (implicitly or explicitly) calling the toString()
method for each point, starting with the first point in the tour.
Standard drawing format.
The draw()
method draws the tour to standard drawing by calling the drawTo()
method for each pair of consecutive points. It must produce no other output.
Requirements
 You must follow the prescribed API for
Tour.java
. We will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points.  You must not add public methods to the
Tour
API; however, you MAY add private instance variables or methods (which are only accessible in the class in which they are declared).  Each constructor must take constant time.
 All instance methods must take time linear (or better) in the number of points currently in the tour.
 Corner cases. You may assume that no
Point
argument isnull
.
Possible Progress Steps
These are purely suggestions for how you might make progress. You do not have to follow these steps.
Click here to show possible progress steps

Review the
CircularQuote
case study from precept. This exercise illustrates circularly linked lists and how to use thedo {...} while (...)
loop to traverse them. 
Study the
Point
API. In this assignment, you will use the constructor to create a point, thetoString()
method to print it, thedistanceTo()
method to compute the distance between two points, and thedrawTo()
method to draw a line segment connecting two points. 
Create a file
Tour.java
. Include the standard linked list data typeNode
as a nested class. Include one instance variable, sayfirst
, of typeNode
that is a reference to the first node of the circularly linked list. 
To assist with debugging, define the constructor that takes four points as arguments and constructs a circularly linked list using those four points. First, create four
Node
objects and assign one point to each. Then, link the nodes to one another in a circular manner. 
Implement the
size()
method. 
To test the
size()
method, write amain()
method that defines four points, constructs a newTour
object using those four points, and calls itssize()
method. For example, base your example on this template, though you should try defining your own points:public static void main(String[] args) { // define 4 points that are the corners of 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); // create the tour a > b > c > d > a Tour squareTour = new Tour(a, b, c, d); // print the size to standard output int size = squareTour.size(); StdOut.println("Number of points = " + size); }

Implement the
length()
method. It is very similar to thesize()
method, except that you need to access two successive points in the tour and call thedistanceTo()
method from thePoint
data type. Using the example above, thelength()
method on the 4point tour—the length should be1600.0
. (Again, test thelength()
method using different points for a 4point tour.)// print the tour length to standard output double length = squareTour.length(); StdOut.println("Tour length = " + length);

Implement the
toString()
method. It is similar in structure tosize()
, except that you must create aStringBuilder
object and append eachPoint
to theStringBuilder
object. Test thetoString()
method on the 4point tour. You should get the following output:// print the tour to standard output StdOut.println(squareTour);
(100.0, 100.0) (500.0, 100.0) (500.0, 500.0) (100.0, 500.0)

Implement the
draw()
method. It is very similar tolength()
, except that you will need to call thedrawTo()
method from thePoint
data type. You will also need to include the following statements inmain()
to resize the x and ycoordinates of standard drawing.StdDraw.setXscale(0, 600); StdDraw.setYscale(0, 600);

Congratulations on reaching this point: writing linked list code is always a challenge!

Implement
insertNearest(Point p)
. To determine which node to insert the pointp
after, compute the Euclidean distance between each point in the tour and p by traversing the circularly linked list. As you proceed, store the node containing the closest point and its distance top
. After you have found the closest node, create a node containingp
, and insert it after the closest node. This involves changing the next field of both the newly created node and the closest node.
To test
insertNearest
, try inserting various points into a 4point tour. 
Once you are confident inserting various points into a 4point tour, you can further test:
 Compile the
NearestInsertion.java
client.  The file
tsp10nearest.ans
contains the resulting tour for the 10point problem, which has length 1566.1363. Note that the optimal tour, the filetsp10optimal.ans
, has length 1552.9612 so this rule does not, in general, yield the best tour.  Run the client:
javaintrocs NearestInsertion < tsp10.txt
 Compare your results to
tsp10nearest.ans
 Compile the


After completing the
insertNearest(Point p)
method, you should be able write theinsertSmallest(Point p)
method by yourself, without any hints. The only difference is that you want to insert the pointp
where it will result in the least possible increase in the total tour length.
Again, to test
insertSmallest
, try inserting various points into a 4point tour. 
Once you are confident inserting various points into a 4point tour, you can further test:
 Compile the
SmallestInsertion.java
client.  The file
tsp10smallest.ans
has length 1655.7462. In this case, the smallest insertion heuristic actually does worse than the nearest insertion heuristic (although this is not typical).  Run the client:
javaintrocs SmallestInsertion < tsp10.txt
 Compare your results to
tsp10smallest.ans
 Compile the

Frequently Asked Questions
Click here for answers to some frequently asked questions.

What should the various methods do if the tour has no points? The
size()
method should return0
; thelength()
method should return0.0
; thetoString()
method should return the empty string; thedraw()
method should draw nothing to standard drawing. 
How do I represent infinity in Java? Use
Double.POSITIVE_INFINITY
. 
How can I produce an animation of the heuristic in action? It’s easy and instructive—just redraw the tour after each insertion. See the instructions in SmallestInsertion.java. It could take a while on a big input file, so you might want to modify it so that it redraws only after every 20 insertions or so. Note: when timing your program, don’t show the animation or else this may become the bottleneck.

What is the file
Tour$Node.class
? When you declare a nested class likeNode
, the Java compiler uses the$
symbol to mark its name. 
How can the suggested definition of private class
Node
work when it has no constructor declared? If you do not declare a constructor, Java automatically defines a noargument constructor that sets all of the instance variables to their default values (here null sincePoint
andNode
are reference types). 
What is a
NullPointerException
? You can get one by initializing a variable of typeNode
, sayx
, tonull
and then accessingx.next
orx.p
. This can happen in your insertion routine if you inadvertently break up the circularly linked list. 
When should I create a new linkedlist node with the keyword
new
? To create a tour with \(n\) points, you should usenew
exactly \(n\) times withNode
, once per invocation ofinsert()
. It is unnecessary (and bad style) to use new with your listtraversal variables since this allocates memory that you never use. 
When I run
TSPTimer.java
with 10,000 points, it already takes more than a minute. What should I do? You have a performance error. Try to discover why (think analysis of algorithms) and explain it in your readme.txt file. 
When I run
TSPTimer.java
with 10,000 points, my nearest neaighbor insertion heuristic runs quickly, but my smallest insertion heuristic takes forever. How can I fix this? You probably have a loop that looks at inserting the new point at each possible insertion point. That is fine. However, if you are calling thelength()
method to compute the new tour length at each potential insertion point, you are effectively adding a second loop inside your first loop (even though it is a single method call), which is too slow. You do not need to recompute the entire tour length for each possible insertion point. Instead, compute the change in the tour length and keep track of which insertion point results in the smallest such change. 
Can I use Java’s built in
LinkedList
class? Absolutely not! One of the main goals of this assignment is to gain experience writing and using linked structures. The Java libraries can take you only so far, and you will quickly discover applications which cannot be solved without devising your own linked structures. (For example, Java’s built inLinkedList
is not circular.)
Testing

A good debugging strategy for most programs is to test your code on inputs that you can easily solve by hand. Start with 1 and 2point problems. Then, do a 4point problem. Choose the data so that it is easy to work through the code by hand. Draw pictures. If your code does not do exactly what your hand calculations indicate, determine where they differ. Use the
StdOut.println()
method to trace. 
The input files for this assignment include many sample inputs. Most are taken from TSPLIB.

The input format begins with two integers width and height, followed by pairs of x and ycoordinates. All xcoordinates will be real numbers between 0 and width; all ycoordinates will be real numbers between 0 and height. For example,
tsp1000.txt
contains the following data:> more tsp1000.txt 800 800 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 programNearestInsertion.java
, which reads the points from standard input; runs the nearest neighbor heuristic; prints the resulting tour, its length, and its number of points to standard output; and draws the resulting tour to standard drawing.SmallestInsertion.java
is analogous but runs the smallest increase heuristic. For example:
# Nearest Neighbor # Smallest Increase
> javaintrocs NearestInsertion < tsp1000.txt > javaintrocs SmallestInsertion < tsp1000.txt
(185.0411, 457.8824) (185.0411, 457.8824)
(198.3921, 464.6812) (195.8296, 456.6559)
(195.8296, 456.6559) (193.0671, 450.2405)
(216.8989, 455.126) (200.7237, 426.3461)
(213.3513, 468.0186) (200.5698, 422.6481)
(241.4387, 467.413) (217.4682, 434.3839)
(259.0682, 473.7961) (223.1549, 439.8027)
(221.5852, 442.8863) (221.5852, 442.8863)
... ...
(264.57, 410.328) (186.8032, 449.9557)
Tour length = 27868.7106 Tour length = 17265.6282
Number of points = 1000 Number of points = 1000
Nearest Neighbor  Smallest Increase 

 Interactive visualizer. The client
TSPVisualizer.java
in an interactive TSP visualizer. When you click a point in the window, it will add it to your tour. It displays both the nearest neighbor heuristic tour (in red) and the smallest insertion heuristic (in blue). You can toggle the visibility of the two tours by typingn
(for nearest neighbor) ors
(for smallest insertion). For example:
> javaintrocs TSPVisualizer tsp1000.txt
Showing Both Heuristics  Showing Smallest Increase Heuristic 

Analysis  readme.txt
In your readme.txt
, estimate the running time (in seconds) of your program as a function of the number of points n. You should use the client program TSPTimer.java
to help you estimate the running time as a function of the input size n. TSPTime
r takes a commandline argument n, runs the two heuristics on a random input of size n, and prints how long each took. Run the two heuristics for n = 1,000, and repeatedly double n until the execution time exceeds 60 seconds.
In order to get consistent timing results:
 Repeat each experiment for n more than once.
 Execute
javaintrocs
using theXint
flag. TheXint
flag turns off various compiler optimizations, which helps normalize and stabilize the timing data that you collect. For example:
> javaintrocs Xint TSPTimer 1000
Tour length = 26338.42949015926
Nearest insertion: 0.056 seconds
Tour length = 15505.745750759515
Smallest insertion: 0.154 seconds
Submission
Submit to TigerFile
: the files Tour.java
, readme.txt
and acknowledgments.txt
files.
Leaderboard  Optional
Submit to Leaderboard  View Current Leaderboard
You can also implement a better TSP heuristic for class fame and glory. You are not required to use the Tour
data type or linked lists. We will award a special prize to whoever finds the shortest tour for a mystery tour with about 1,000 points. Here are some ideas.

API requirements. Name your program
TSP.java
. The only public method inTSP.java
ismain()
, which reads a sequence of points from standard input (in the standard format) and prints the resulting tour to standard output, one point per line. 
Performance requirements. It must solve a 1,000point instance in at most a few seconds and a 10,000point tour in at most a minute.

Submission. Submit the following to the TSP Leaderboard:
TSP.java
; any accompanying files; and
leaderboard.txt
, which includes your experimental results and describes your heuristic.
Here are some ideas for finding a better TSP tour. None of the methods guarantees to find an optimal tour, but they often lead to good tours in practice.
Crossing edges.
If two edges in a tour cross, you can decrease the length of the tour by replacing the pair that crosses with a pair that does not cross.Farthest insertion.
It is just like the smallest increase insertion heuristic described in the assignment, except that the cities need not be inserted in the same order as the input. Start with a tour consisting of the two cities that are farthest apart. Repeat the following:
 For each city not in the tour, consider the shortest distance from that city to a city already in the tour. Among all cities not in the tour, select the city whose distance is largest.
 Insert that city into the tour in the position where it causes the smallest increases in the tour distance. You will have to store all of the unused cities in an appropriate data structure, until they get inserted into the tour. If your code takes a long time, your algorithm probably performs approximately \(n^3\) steps. If you’re careful and clever, this can be improved to \(n^2\) steps.
Node interchange local search.
Run the original greedy heuristic (or any other heuristic). Then repeat the following:
 Choose a pair of cities.
 Swap the two cities if this improves the tour. For example, if the original greedy heuristic returns 1–5–6–2–3–4–1, you might consider swapping 5 and 3 to get the tour 1–3–6–2–5–4–1. Writing a function to swap two nodes in a linked list provides great practice with coding linked lists. Be careful: it can be a little trickier than you might first expect (e.g., make sure your code handles the case when the two cities occur consecutively in the original tour).
Edge exchange local search.
Run the original greedy heuristic (or any other heuristic). Then repeat the following:
 Choose a pair of edges in the tour, say 1–2 and 3–4.
 Replace them with 1–3 and 2–4 if this improves the tour. This requires some care, as you will have to reverse the orientation of the links in the original tour between nodes 3 and 2 so that your data structure remains a circularly linked list. After performing this heuristic, there will be no crossing edges in the tour, although it need not be optimal.
Enrichment

Here’s a 13,509point 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 record for the largest TSP problem ever solved exactly is a 85,900point instance that arose from microchip design in the 1980s. It took over 136 CPUyears to solve.

Here’s an excellent and very accessible book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, William J. Cook about the TSP.

Here’s a nice pictorial survey of the history of the TSP problem.

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.
Copyright © 2000–2022 Robert Sedgewick and Kevin Wayne, All Rights Reserved