Traveling Salesperson Problem - Assignment 2

CSCI 136
Fundamentals of Computer Science II
Spring 2020

ASSIGNMENT 2 - Traveling Salesperson Problem

In this assignment, you will be implementing several heuristics to find a short path through a set of points. In the process, you will gain experience with linked lists and also learn about a famous problem in computer science.

Given 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. Implement one straightforward (but not great) and two greedy heuristics to find good (but not optimal) solutions to the traveling salesperson problem (TSP).

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.

Approaches. The traveling salesperson 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 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.

In Order heuristic: Read in the next point, and add it to the current tour in order to the previous point. Obviously, this will not result in an efficient route, but it gives you a way to start testing your code.
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.

Getting started. Create a folder and unzip newest zip file TSPStudent.zip into that folder. This file contains various data files as well as some of the provided classes you will be using. Note in the assignment you only need to create the Tour.py data type, the rest of the programs are already completed and they do not need to be modified.

Point data type. The Point data type represents a point in the plane, as described by the following API. This class has been implemented for you - you do not need to modify it.

class Point (2D point data type)
---------------------------------------------------------------------------------------
       __init__(float x, float y)   # create the point (x, y)
string toString()                   # return string representation
       draw()                       # draw point using standard draw
       drawTo(Point that)           # draw line segment between the two points
float  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.

Tour data type. Your task is to 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.py, define a class Node in the way we talked about in class:

class Node :
    def __init__(self):
        self.p = None       # This will hold the data, in this case a 2D point
        self.next = None    # This will be the pointer to the next node

Your Tour data type must implement the following API:

class Tour
----------------------------------------------------------------------------------------------
       __init__()                               # create an empty tour
       show()                                   # print the tour to standard output
       draw()                                   # draw the tour to standard draw
   int size()                                   # number of points on tour
 float distance()                               # return the total distance of the tour
       insertInOrder(Point p)                   # insert p using in order heuristic
       insertNearest(Point p)                   # insert p using nearest neighbor heuristic
       insertSmallest(Point p)                  # insert p using smallest increase heuristic

Each Tour object should be able to print its constituent points to standard output (the screen), draw its points to standard draw, count its number of points, compute its total distance, and insert a new point using any of the three heuristics. The constructor creates an empty tour (that is, a linked list with no nodes).

Input and testing. The input file format will begin with two numbers w and h, followed by pairs of x- and y-coordinates. These first two numbers may or may not be integers, so you may need to convert them. 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:

% type tsp1000.txt
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.py, you can use the client programs InOrderInsertion.py, NearestInsertion.py, and SmallestInsertion.py to read in the points from file run the associated heuristic, print the resulting tour and its distance to standard output (the screen); and draw the resulting tour to standard draw. Your code will implement the methods to carry this out, as described above, and should be able to do this using only the methods in the Point class, but you will need to import StdDraw in your Tour.py code if you wish to test the drawing part in your test main.

% python InOrderInsertion.py tsp1000.txt
Tour distance = 327693.76217093336
(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)

% python NearestInsertion.py tsp1000.txt
Tour distance = 27868.710634854797
(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)

% python SmallestInsertion.py tsp1000.txt
Tour distance = 17265.628155352584
(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)

Analysis. In the header of your Tour.py, provide the results of running all heuristic programs for different values of N. Explain why one provides a much shorter path than the other.

Testing. You can use the Autograder.py, program to test your code.

Grading

Grade Item	Points Possible	Points Earned
Program Compiles and Runs	2
Comments on All Classes, Methods and Header	4
Implemented __init__() Correctly	2
Implemented insertInOrder(p) Correctly	4
Implemented show() Correctly	2
Implemented draw() Correctly	2
Implemented size() Correctly	2
Implemented distance() Correctly	2
Implemented insertNearest(p) Correctly	4
Implemented insertSmallest(p) Correctly	4
Write Up of Results across Several Test Files	2

Total	30

Submission. Submit your program Tour.py using Moodle. Be sure each submitted source file has the required header with your name, and a description of the program. Also, each method should have appropriate comments. For extra-credit, please submit a single zip file containing all your programs/graphics/sounds via the special extra-credit drop box at the top of the Moodle page. If you are submitting work for extra credit be sure to also submit your regular lab assignment to the Lab 2 dropbox as well.

I'm not sure how to get started. What do you recommend? A good way to proceed in this assignment (and most programs) is to implement methods one at a time, starting with the simplest method first. After creating each method, write test code to see if the new method does what is suppose to. In this assignment, you can implement whatever test code you like in the main method in Tour.py. So a possible way to proceed is to implement the Tour constructor, then create some test code that creates an empty tour. Once this is working, implement the next simplest method (e.g. insertInOrder should come first and then size or distance). Test this method and make sure you get the right answers, and so on.

Do I need to follow the prescribed API? Yes, I 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 may add private methods to your code if they help you in your implementation.

Do I need to implement a circular linked list? Yes, because: 1) that is what was asked for, and 2) the code is simpler using a circular linked list compared to using a null-terminated one.

What should my program do if the tour has 0 points? The size() method should return 0; the distance() method should return 0.0; the show() method should write nothing to standard output; the draw() method should draw nothing to standard draw.

How do I represent positive infinity in Python? Use float('inf').

How long should my programs take to execute? It took my (rather slow) Linux machine 2 minutes to solve the usa13509.txt problem with InOrderInsertion.py, and 8 minutes to solve it using SmallestInsertion.py. It could take substantially less time if you have a faster computer. If your code takes much much longer, try to discover why.

How can I produce an animation of the heuristic in action? It's easy and instructive to watch the tour update after each insertion. InOrderInsertiong.py, SmallestInsertion.py and NearestInsertion.py take an optional command-line argument that puts the program into animation mode. I would suggest using a number substantially less than 1.0. Animating the drawing significantly slows down the execution time.

Can I use Python's built in linked list library? Absolutely not! One of the main goals of this assignment is to gain experience writing and using linked structures. The Python libraries can only take you so far, and you will quickly discover applications which cannot be solved without devising your own linked structures.

What's the largest TSP tour ever solved exactly? The "record" for the largest TSP problem ever solved exactly is a 85,900-point instance that arose from microchip design in the 1980s. It took over 136 CPU-years to solve. It is in the tsp.zip file, the optimal solution value is a little more than 71,000.

What is the distance of the best known tour for tsp1000.txt? At the last check, Mark Tengi held the Princeton COS 126 record with a tour of length 15892.3. Using the Concorde TSP solver, we found a solution of length 15476.519. Currently Montana Tech CSCI 136 does not have a record.

Extra credit (up to 5 points). 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. You will be famous if you can break either the Princeton record or that from the Concorde TSP Solver. Note: the tour length must be less than the smallest insertion heuristic! Be sure to describe in the header of your extra-credit program the heuristic(s) you added.

Page last updated: December 28, 2020