The work of the student is to propose, implement and test a heuristic algorithm for the solution of the Euclidean Traveling Salesman Problem.

Students are provided with a set of 10 instances (ALGO_cup_2016_problems.zip file attached. Notice that the Euclidean coordinates (xi,yi) are real numbers but the computed dij distances must be integer. In the zip file for some problems the best known solution is also reported). For each instance students have to compute the shortest possible tour. Students are allowed to run their algorithm on each instance how many times they like with the constraint that each run can not be longer than 3 minutes on a single processor. Results must be replicable (in case we need to check the validity of your solutions) so please keep all the parameters of your best runs (remember also to store random seeds). For each instance the following error is computed:

((student_tour_length – best_known_result)/ best_known_result

The average of the 10 errors is the final result of your work. In case more students reach the same average, we consider date and time of the email with the results submission are considered.

The student who obtains the best average result will be rewarded with the 14th Coppa Algoritmi and he will have the right to present in class his work to the other students. At the end of the semester (by May 2nd 12.00p.m) each student has to send by email the result of his work and a short document with the description of the adopted approach.

To facilitate the submission an Exel file (ALGO_cup_2016_studentname.xls) is attached, where all the ten instances are listed. Please change the studentname extension with your real name and send this file and the description by email.