|
 |
|
|
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 17th. At 5 pm, the test TSPs will be released. The student should run their unmodified system on the tests, gather the results and submit the final project. This should be submitted by 5:00 pm on November 18th to myunihub.
The system should solve the three training sets:
train problem 1,
train problem 2, and
train problem 3.
The test sets for Dec 2018 are
old final test 1, 2018,
old final test 2, 2018,
old final test 3, 2018 , and
old final test 4, 2018.
The old test sets and other test sets are
old final test 1,
old final test 2,
old final test 3, and
old final test 4.
old train problem 2 (not marked),
old train problem 3 (not marked)),
old final test 1 2019,
old final test 2 2019,
old final test 3 2019 , and
old final test 1 2020,
old final test 2 2020,
old final test 3 2020,
old final test 4 2020,
old final test 4 2019.
old final test 1 2021,
old final test 2 2021,
old final test 3 2021, and
old final test 4 2021.
The final tests for Dec 2022:
final test 1 2022,
final test 2 2022,
final test 3 2022, and
final test 4 2022.
Note that you need to make
a complete circuit.
Marking scheme:
| Points | Area |
|---|---|
| 10 | Self Marking Sheet |
| 10 | Solve First Training Problem |
| 10 | Get Optimal Result for All Three Training Problems. |
| 10 | Describe Algorithm(s) Used |
| 10 | Quality of Code |
| 20 | Get Optimal Results for the First Three Tests |
| 20 | Get Optimal Results for First Three Tests in under a minute. |
| 10 | Best system on Fourth Test (Path length squared 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 path length squared 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 17th. The code should not change after 5 on the 17th. 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 the coursework 1 folder of CST 3170 on myunihub. 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.
