Description
TSP Problem Description: Given a set of cities (coordinates) and distances between them, find the best (shortest) tour (visiting all cities exactly once and returning to the origin city) in a given amount of time, viz. Traveling Salesman Problem.
Note: You are free to implement any algorithm for this competition.
Input Format:
You will be given files in the following format:
● First line will contain either euclidean or non euclidean indicating whether the distances between the cities are Euclidean or not.
● Second line will contain the number of cities ( N ). E.g. 100 (Indices 0 – 99)
● Next N lines will contain the two-dimensional coordinates (space separated) of the cities.
● Next N lines will contain N space separated distances between cities, in order.
● All coordinates and distances will be floating point numbers.
Sample input files have been attached on moodle.
Output Format:
Your output should be following:
● Each line will contain tours as space separated indices of cities. Do not write the origin city’s index at last again. Rotated tours will be considered the same. Invalid tours will be considered as no tours at all.
● The time limit for running your code is 300s, after which your process will be terminated. Make sure to print your best tours to stdout as soon as you find them because only the last valid tour will be considered for evaluation. And also print the tour length in each round.
● Do not use multi-threading for this assignment.
Evaluation
● You will be evaluated on the basis of the cost of your tours.
● Refer to test cases from the previous assignment(trial) so that you can evaluate your performance and improve before the final submission.
● Judgment will be made in a relative fashion with some thresholding.
● We are also attaching results from previous batches so that you can compare your results.
● The maximum points are 100.
Evaluation Criteria: Relative (based on tour found)
Note: This assignment will have a higher weightage compared to other tasks till now.
The deadlines are to be strictly followed.
NOTE:
2. Submit the following files named with your group number.
a. Code: <group_number>.py
b. Input file if there (input.txt)
<group_number>.pdf
c. Report:(A brief report stating your methodology and iterative improvements.)
d. Readme.txt ( How to execute your program)
3. Mode of submission is moodle.
