CSD 3939 Home Page The Next Page
Middlesex Logo

CSD 3939 Course Work 1

The Travelling Salesman Problem

Due Date: End of Week 11 (Dec 14 and 15 2017)

20% of Overall Course Mark


The coursework is to build a system in Java that solves travelling salesman problems. The travelling salesman problem is to go to each city exactly once and return to the start. Solving the problem should give a path and the length of the path. There are optimal solutions, that is solutions with the shortest path.

Sample files are provided below. They have n lines for n cities. The first integer in the line is the city number (starting with 1 and ending with n) and the second and third integers are the X and Y coordinates of the city. Distance is standard Euclidean distance.

The code should be written entirely by the student. You are entirely welcome to discuss the project with others, but you need to write every single character. If you use an algorithm described elsewhere, please include a reference to that in the report.

The system should be run on the training TSPs, and submitted by 5 pm on 14th. At 5 pm, the test TSPs will be released. The student should run their unmodified system on the test mazes, gather the results and submit the final project. This should be submitted by 5 pm on December 15th to Unihelp.

The system should solve the three training sets ( train problem 1, train problem 2, train problem 3, old train problem 2 (not marked), and old train problem 3 (not marked)).
The tests sets are final test 1, final test 2, final test 3, and final test 4.
Note that you need to make a complete circuit. -----------------


Marking scheme:
PointsArea
10Self Marking Sheet
10Solve First Training Problem
10Get Optimal Result for All Three Training Problems.
10Describe Algorithm(s) Used
10Quality of Code
20Get Optimal Results for the First Three Tests
20Get Optimal Results for First Three Tests in under a minute.
10Best system on Fourth Test (Path length times time.)

The student should provide a self marking sheet with their opinion of their own score. You can not get this wrong if you submit it. Additionally, the student should describe the algorithm or algorithms used. This need not be a long description; typically a paragraph will do, but for simple algorithms less is fine.

The quality of the code will be marked. This includes comments, variable, function and class names, and class structure.

Times: the final 10 points involve time. The student needs to use the system clock to time the algorithm. Use System.nanoTime(); Report times for all solutions and the first solution. The best combination of result multiplied by time on the fourth test will get 10 points. Others may also get points on this criterion.

Submission notes: you should email the system to the tutor on the 14th. The code should not change after 5 on the 14th. The only thing that should change is the reported results of the test problems. It should run from Eclipse. Instructions for running are welcome.

Please submit the code, the mark sheet, and analysis to unihelp in the Sheppard Library; get a receipt. You are also welcome to email a copy to the tutor. You must email a copy of the system to the tutor before the test data is released if you want any of the 50 points available for the test data.