Skip to main content

0. Getting Started


A. Goals

The purpose of the Travelling Salesman Problem (TSP) assignment is to practice implementing linked lists. The specific goals are to:


B. Background

A travelling salesman needs to visit each of n cities exactly once, and arrive back home, keeping the total distance travelled as short as possible. In this assignment, you will write a program to find a path connecting n points that passes through each point exactly once.

The travelling salesman problem is a notoriously difficult combinatorial optimization problem. There does not exist an efficient algorithm to find the optimal tour, the tour of smallest distance. The only way to find the optimal tour is to use brute force: to compute the distance of all possible tours. The problem with this is that there are n! (n factorial) possible tours; enumerating them all and computing their distance would be very slow.

However, there are efficient ways to find a tour that is near-optimal; these methods are called heuristics. You will implement two heuristics to find good (but not optimal) solutions to the traveling salesman problem. You will also implement a simpler method which creates a tour by traveling to points in order.

1000 points 1000 pts tour
1,000 points Optimal tour through the same 1,000 points

The travelling salesman problem has a wealth of applications such as vehicle routing, circuit board drilling, circuit board design, robot control, X-ray crystallography, machine scheduling, and computational biology.


C. Your program

In this assignment, you will write a Tour class that models a tour using a linked list of Point objects.

You will implement the following methods to insert points into a tour.


D. Designing the Requirement and Interface

Open HW7 on Codio and look at the files provided, or you can download them here. The provided files contain files you can use for testing as well as some helper classes and interfaces you will need:

Review the class material and textbook chapters on linked lists.


1. Tour Class

In this section, you will write Tour, implementing TourInterface. The Tour is represented by a linked list which contains nodes. Each node contains a point which is essentially just a coordinate. Make sure you understand the distinction between the Tour, nodes, and points after reading section 1.


A. The Point Class

The Point class file that represents a point, contained by a node, in a tour. Open it in Codio and study it carefully. The API is as follows:

public class Point
----------------------------------------------------------------------------------------
Point(double x, double y)       // create the Point (x, y)
String toString()               // return String representation
void draw()                    // draw Point using PennDraw
void drawTo(Point that)        // draw line segment between this  
                               // Point and that
double distanceTo(Point that)  // return Euclidean distance 
                               // between this Point and that 

B. The Tour Class

Create a skeleton for your Tour class, which must implement TourInterface:

public interface TourInterface
----------------------------------------------------------------------------------------
String toString()                 //create a String representation 
                                  // of the Tour
void draw(Point p)       // draw the Tour using PennDraw
                         // any edge starting or ending at p 
                         // should be in a distinct color
int size()                      // number of Points in this 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 the nearest        
                                // neighbor heuristic	
void insertSmallest(Point p)    // insert p using the smallest   
                                   increase heuristic

Write method stubs for each method declaration in the TourInterface interface. The stubs for methods with non-void return types must each return a dummy value so that Tour.java compiles.

Add appropriate header comments and method comments.


C. The Node Class

The Node class we have provided will form the basis of your Tour class’s linked list structure. Each Node stores a single Point in your Tour’s path and a reference to the next Node in the path. Its API is as follows:

public class Node
--------------------------------------------------------------------------------------
Node(Point p)                // create a Node containing Point p
Node(Node n, Point p)        // create a Node containing Point p and   
                             // with n as its next Node in the list

Declare (do not initialize yet) the following private fields in your Tour class:

When your Tour class’s linked list is not empty, both head and lastNode must be different instances of the Node class (two different objects) yet each Node must store the same Point object. That is, there will be two different Nodes in memory each of which contains a reference to one common Point in memory. Note that this is different from having each Node refer to distinct Point objects with equivalent values. The purpose of this is to represent the cyclical nature of the salesman’s route; he begins and ends at his home. This is a required implementation detail.

You may not use Java’s built-in LinkedList class to implement your linked list. You should also not write your own class called LinkedList since your Tour class will handle all linked list functionality.


D. Constructor and toString()

Implement a single constructor for your Tour class that takes no arguments and creates an empty Tour. This means that both head and lastNode will be null.

toString() returns a String representation of the Tour (the first Point should show up at the end as well, just like it does in your linked list structure). Call toString() on each Point to get a String representation of the Point. Your output must match this description exactly in order to pass the autograder tests.

If the Tour is empty (has no Nodes), toString() should return the empty String.

Required Testing: Add a main in which you create an empty tour and print it out. Your program should now simply print a blank line. Once this works, submit and make sure you also pass the empty tour submission test.


E. insertInOrder()

To facilitate testing, you will need to implement insertInOrder() so you can add Nodes to your tour.

insertInOrder(Point p) adds a node storing Point p as the “last” node of the Tour.

Remember that your Tour class should always maintain lastNode at the end of the linked list referring to the same Point as the first node in the tour.

If the Tour is initially empty, make sure that after this method finishes, your linked list contains two Node objects, both referring to the same Point.

If you need to iterate over your linked list without specifically doing anything to it, you can do the following:

Node curr = head;
while (curr.next != null) {
	curr = curr.next
}

Required Testing: Add code to main to create nodes with the following four points and add them to your tour using insertInOrder():

The following image shows the structure of the link list these insertions should create:

tour

Print out the tour using System.out.println You should see the following output (including a blank line at the end):

(0.0, 0.0)
(1.0, 0.0)
(1.0, 1.0)
(0.0, 1.0)
(0.0, 0.0)

Once this test passes, submit your code and make sure it passes our toString() tests for insertInOrder() as well. (At this point, your code will still fail the tests for size() and distance().)


F. Utility Methods

Implement the size(), distance(), and draw() methods of Tour. There are many good ways to implement these methods, using for loops, while loops, or recursion. The choice is up to you.

size() returns the number of Points in the Tour, (counting the point in Head and lastNode only once).

distance() returns the total length of the Tour from Point to Point. Use the distanceTo(Point p) method of a Point to find its distance to p. An empty Tour has a distance of 0.0.

draw(Point p) draws the entire Tour from Point to Point using functions that call PennDraw code. Both edges adjacent to the input Point p should be drawn in a different color (if p is null, none of the edges should be in a different color). Use the drawTo(Point q) method of a Point to draw a line from it to q. As we have provided VisualizeTour to handle setting up PennDraw’s canvas for drawing your Tour, all this function needs to do is call the drawTo method to draw every line segment between adjacent Points. If an empty Tour calls the draw method, the method should simply return without drawing anything.

The image below shows what our reference draws when we call tour.draw(a) (refer to section E for the value of a). tour is the four-point Tour we created for testing.

tour image

Required Testing: Add code to main to test each of these methods on an empty tour, a tour containing only one point, a tour containing two points, and a tour containing four points. We encourage you to include additional tests as well. When you are certain all of your own tests work, submit and make sure our tests pass as well.

As you debug your code, you may find this Java execution visualizer helpful. (It was created by daveagp.)


2. Insertion Heuristics


A. Testing with VisualizeTour

The VisualizeTour program included provides a user interface for you to test the methods you have written in Tour. Run it with a filename argument (one of the files we provide) in the terminal to animate the construction of your Tour. In the table at the bottom of this page, we have listed the values of size() and distance() that your methods should obtain for each insert method, as well as the PennDraw output that draw() should produce.

You might find it helpful to write a helper function that, given a point, inserts a new Node after a given Node.

Required Testing: Check that your in-order insertion method works for at least the input files tsp0.txt, tsp1.txt, tsp2.txt, tsp3.txt, tsp4.txt, tsp5.txt, tsp8.txt, tsp10.txt, and tsp100.txt. Both the drawing itself, and the size and distance, need to match the reference outputs at the bottom of the page. Do not continue until insertInOrder works for all these cases!


B. insertNearest()

insertNearest(Point p) adds a Node storing the Point p to the Tour after the closest Point (Node) already in the Tour.

If there are multiple closest Points with equal distances to p, insert p after the first such Point in the linked list.

Your method must behave as insertInOrder() does when the linked list is empty.

Required Testing: Make sure your VisualizeTour results match the figures below for the Nearest-Neighbor Heuristic for all test cases through tsp100.txt. Both the drawing itself, and the size and distance, need to match. Then submit and make sure it passes our submission tests as well.


C. insertSmallest()

insertSmallest(Point p) adds a Node storing Point p to the Tour in the position where it would cause the smallest increase in the Tour’s distance.

Do not compute the entire Tour distance for each position of p. Instead, compute the incremental distance: the change in distance from adding p between Points s and t is the sum of the distances from s to p and from p to t, minus the original distance from s to t.

If there are multiple positions for p that cause the same minimal increase in distance, insert p in the first such position.

Your method must behave as insertInOrder() does when the linked list is empty.

If you wrote a helper function when writing insertInOrder() that inserts a given Point after a given Node, you may find it useful again here.

Comment out all print statements in Tour before running VisualizeTour on a file of more than 100 Points. Otherwise, you will be waiting for a long time for VisualizeTour to finish.

Required Testing: Make sure your VisualizeTour results match the figures below for all test cases through tsp100.txt. Both the drawing itself, and the size and distance, need to match. Then submit and make sure it passes our submission tests as well.


D. Reference Output

Test your nearest-neighbor heuristic and smallest-increase heuristic methods using VisualizeTour. The following are the values and PennDraw output that your Tour methods should give for each of the provided input files. Note that for the files containing large quantities of points, such as mona-50k.txt, your program may take a long time to build the tour. You may have to wait for several moments, staring at a blank white PennDraw canvas, before your tour is visualized.

File In-Order Insertion('o') Nearest-Neighbor Heuristic('n') Smallest-Increase Heuristic('s')
tsp0.txt Size: 0
Distance: 0.0000
Size: 0
Distance: 0.0000
Size: 0
Distance: 0.0000
tsp1.txt Size: 1
Distance: 0.0000
Size: 1
Distance: 0.0000
Size: 1
Distance: 0.0000
tsp2.txt Size: 2
Distance: 632.46
tour 2
Size: 2
Distance: 632.46
tour 2
Size: 2
Distance: 632.46
tour 2
tsp3.txt Size: 3
Distance: 832.46
tour 3
Size: 3
Distance: 832.46
tour 3
Size: 3
Distance: 832.46
tour 3
tsp4.txt Size: 4
Distance: 963.44
tour 4 in order
Size: 4
Distance: 956.06
tour 4 nearest
Size: 4
Distance: 839.83
tour 4 smallest
tsp5.txt Size: 5
Distance: 2595.1
tour 5 in order
Size: 5
Distance: 2595.1
tour 5 nearest
Size: 5
Distance: 1872.8
tour 5 smallest
tsp8.txt Size: 8
Distance: 3898.9
tour 8 in order
Size: 8
Distance: 3378.8
tour 8 nearest
Size: 8
Distance: 2545.6
tour 8 smallest
tsp10.txt Size: 10
Distance: 2586.7
tour 10 in order
Size: 10
Distance: 1566.1
tour 10 nearest
Size: 10
Distance: 1655.7
tour 10 smallest
tsp100.txt Size: 100
Distance: 25547
tour 100 in order
Size: 100
Distance: 7389.9
tour 100 nearest
Size: 100
Distance: 4887.2
tour 100 smallest
tsp1000.txt Size: 1000
Distance: 3.2769e+05
tour 1000 in order
Size: 1000
Distance: 27869
tour 1000 nearest
Size: 1000
Distance: 17266
tour 1000 smallest
bier127.txt Size: 127
Distance: 21743
bier in order
Size: 127
Distance: 6494.0
bier nearest
Size: 127
Distance: 4536.8
bier smallest
circuit1290.txt Size: 1290
Distance: 4.303e+05
circuit in order
Size: 1290
Distance: 25030
circuit nearest
Size: 1290
Distance: 14596
circuit smallest
germany15112.txt Size: 15112
Distance: 4.2116e+06
germany in order
Size: 15112
Distance: 93119
germany nearest
Size: 15112
Distance: 55754
germany smallest
mona-20k.txt Size: 20000
Distance: 4.9650e+06
mona 20k in order
Size: 20000
Distance: 94894
mona 20k nearest
Size: 20000
Distance: 56334
mona 20k smallest
mona-50k.txt Size: 50000
Distance: 1.2366e+07
mona 50k in order
Size: 50000
Distance: 1.6168e+05
mona 50k nearest
Size: 50000
Distance: 95598
mona 50k smallest
mona-100k.txt Size: 100001
Distance: 2.4795e+07
mona 100k in order
Size: 100001
Distance. 2.6272e+05
mona 100k nearest
Size: 100001
Distance: 1.5472e+05
mona 100k smallest
usa13509.txt Size: 13509
Distance: 3.9108e+06
usa in order
Size: 13509
Distance: 77450
usa nearest
Size: 13509
Distance: 45075
usa smallest

3. Extra Credit


A. Extra Credit

For extra credit, implement a better heuristic in a class TourEC that implements the TourECInterface interface. You are not required to use the Tour or Point classes for your extra credit solution. If you use a modified version of these classes to implement TourEC, include them in your extra.zip; otherwise, your TA may be unable to compile your code.

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. Try to write a TourEC that implements one of the heuristics below.

Here are some heuristics you may choose to implement.

Farthest insertion The farthest insertion heuristic is just like the smallest increase insertion heuristic described in the assignment, except that the Points need not be inserted in the same order as the input. Start with a Tour consisting of the two Points that are farthest apart. Repeat the following:

You will have to store all of the unused Points in an appropriate data structure, until they get inserted into the Tour. If your code takes a long time, your algorithm probably performs approximately n3steps. If you’re careful and clever, this can be improved to n2 steps.

Node interchange local search Run the original greedy heuristic (or any other heuristic). Then, repeat the following:

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 that you might first expect (e.g., make sure your code handles the case when the two Points occur consecutively in the original Tour).

Edge interchange local search Run the original greedy heuristic (or any other heuristic). Then, repeat the following:

This requires some care, as you will have to reverse the orientation of the links in the original Tour between Nodes 3 and 2. After performing this heuristic, there will be no crossing edges in the Tour, although it need not be optimal.


B. Enrichment


4. Submission


A. Readme

Complete readme_tsp.txt in the same way that you have done for previous assignments.


B. Submission

Submit Tour.java and readme_tsp.txt on gradescope.

You may also submit a TourEC.java file for extra credit. If your TourEC.java requires any additional files, including a modified Point.java or Tour.java, make sure to submit those as well.