CS312- Artificial Intelligence: Lab 4 Solved

Task 4: TSP Competition

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. Travelling 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.​  
You need to submit the following:

Code​ 
Script to run your code called run.sh which accepts an input file name as argument​              
txt ( How to execute your file)
A brief report stating your methodology and iterative improvements. (pdf​ ​)​
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.​       

For Reference : 

 Genetic Algorithm​ s  

Genetic Algorithms for TSP Ant Colony Optimisation  

https://drive.google.com/file/d/1_bVHuoFoW-MlcBG8HQuGOpVl7qKESpSV/view?usp=sharing