The Travelling Salesman Problem (TSP) Solution

In this project you will have fun trying out ideas to solve a very hard problem: The Traveling

Salesman Problem (TSP).

 

You are given a set of n cities and for each pair of cities c1 and c2, the distances between

them d(c1, c2). Your goal is to find an ordering (called a tour) of the cities so that the distance you travel is minimized. The distance you travel is the sum of the distances from the first

city in the ordering to the second city, plus the distance second city to the third city, and so

on until you reach the last city, and then adding the distance from the last city to the first city.  For example if the cities are Seattle, Portland, Corvallis and Boise. The total distance traveled visiting the cities in this order is:

d(tour) = d(Seattle,Portland) + d(Portland, Corvallis) + d(Corvallis,Boise) + d(Boise, Seattle) In this project, you will only need to consider the special case where the cities are locations

in a 2D grid (given by their x and y coordinates) and the distance between two cities c1 = (x1,

y1) and c2 = (x2, y2) is given by their Euclidean distance. To avoid floating point precision problems in computing the square-root, we will always round the distance to the nearest integer.  In other words you will compute the distance between cities c1 and c2 as:

 



(
 
d(c1, c2) = nearestint


 



2
 
(x1 − x2)


 



2
 
+ (y1 − y2)  )

 

For example, if the three cities are given by the coordinates c1= (0, 0), c2 = (1, 3), c3 = (6, 0), then a tour that visits the cities in order c1 – c2 – c3 – c1 has the distance

 

d(tour) = d(c1, c2) + d(c2, c3) + d(c3, c1)

 

where

 



(
 
d(c1, c2) = nearestint

 

 



=
 
nearestint

(


(0 − 1)2 + (0 − 3)2 )

 

(−1)2  + (−3)2 )

 

= nearestint(   1 + 9)

= nearestint(   10)

 

 

= nearestint(3.1622…)

= 3

 



(
 
d(c2, c3) = nearestint


2

(1 − 6)


+ (3 − 0)2 )

 



=
 
nearestint

(


 



2
 
(−5)  + (3)2 )

 

= nearestint(   25 + 9)

= nearestint(   34)

= nearestint(5.8309…)

= 6

 



(
 
d(c3, c1) = nearestint


2

(6 − 0)


+ (0 − 0)2 )

 



=
 
nearestint

(


 



2
 
(6)  + (0)2 )

 

= nearestint(   36 + 0)

= nearestint(   36)

= nearestint(6)

= 6

 

So that d(tour ) = 3 + 6 + 6 = 15.

 

Project Specification

 

Your group will research at least three different algorithms for solving the TSP problem. Each group member should research a different algorithm and provide pseudocode for that algorithm even if it is not implemented.  There is much literature on methods to “solve” TSP please cite any sources you use. Your group will design and implement at least one algorithm for finding the best tour you can for the TSP problem. TSP is not a problem for which you will be able to easily find optimal solutions.  It is difficult. Your goal is to find the best solution you can in a certain time frame.  Use any programming language you want that runs on flip2.engr.oregonstate.edu.

 

Your program must:

 

•   Accept problem instances on the command line

 

•   Name the output file as the input file’s name with .tour appended (for example input

tsp_example_1.txt  will output  tsp_example_1.txt.tour)

 

•     Compile/Execute correctly and without debugging on flip2.engr.oreognstate.edu according to specifications and any documentation you provide.
Input specifications:

 

•   A problem instance will always be given to you as a text file.

 

•   Each line defines a city and each line has three numbers separated by white space.

 

o The first number is the city identifier

 

o The second number is the city’s x-coordinate

 

o The third number is the city’s y-coordinate.

 

Output  specifications:

 

•     You must output your solution into another text file with n+1 lines, where n is the number of cities.

 

•   The first line is the length of the tour your program computes.

 

•     The next n lines should contain the city identifiers in the order they are visited by your tour.

 

o Each city must be listed exactly once in this list.

 

o  This is the certificate for your solution and your solutions will be checked. If they are not valid you will not receive credit for them.


 

Example instances:  We have provided you with three example instances. They are available on Canvas and are provided according to the input specifications.

 

•   tsp_example_[*].txt           Input files

 

•     tsp_example_[*].txt.tour    Example outputs corresponding to these three input cases.



The optimal tour lengths for example instances 1, 2, and 3 are 108159, 2579 and 1573084, respectively.  Clearly these do not match the values in the tour files. You should use these values to evaluate your algorithm.  For full credit it is required that the ratio of

 

(your solution)/(optimal  solution) <= 1.25,  in an unlimited amount of time.

 

Note: The 1.25 bound is only required for the specific instances that I give you. I am not requiring proof of a 1.25-approximation algorithm. Some 2-approximation algorithms will satisfy the 1.25 bound on these specific instances.


Testing

 

A testing procedure tsp-verifier.py is given that we will use to verify your solutions. Usage to test example an instance is:  (NOTE: requires TSPAllVisitied.py)

 

 

 

 

python tsp-verifier.py   inputfilename  solutionfilename

 

You should test that your outputs are correct.  By “correct” we mean that the distances have been computed correctly not that the solution is optimal.



Competition


We will hold a completion. The competition will require your program to find the best solution possible to one or more test instances within a fixed amount of time (e.g. 3 minutes). The competition instances will be available on Monday Week 10 at 8:00 am PST. You will not be told the optimal tour length for these instances. You will post your results to the competition instances to the competition discussion board.

 

Project Report

 

You will submit a project report containing the following:

 

•     A description of at least three different methods/algorithms for solving the Traveling Salesman Problem along with pseudocode.  Summarize any other research your group did.

 

•     A verbal description of your algorithm(s) as completely as possible. You may select more than one algorithm to implement.

 

•   A discussion on why you selected the algorithm(s).

 

•   Pseudo code

 

•     Your “best” tours for the three example instances and the time it took to obtain these tours. No time limit.

 

•     Your best solutions for the competition test instances. Time limit 3 minutes and unlimited time.

 

 

 

Submission

 

•     All files (including a REDME), solutions and report must be zipped and submitted to TEACH by Friday Week 10 at 11:59pm PST.  Only the report will be submitted to Canvas.

 

 

 

Check List

 

•   Does your program correctly compute tour lengths for simple cases?

 

 

•   Does your program read input files and options from the command line?

 

 

•   Does your program meet the output specifications?

 

 

•   Did you check that you produce solutions that verify correctly?

 

 

•   Did you find solutions to the example instances?

 

 

•     Did you find solutions to the competition instances? Post your results to the competition discussion board to be eligible for extra-credit points.

 

•   Does your code compile/run without issue according to your documentation?

 

Have you submitted your report to Canvas? In the comment section post the onid username of the person who submitted to TEACH.

 

•   Have you submitted your report, your solutions to the test cases, your source code and

 

README file to TEACH?