Solving TSP using TSPLIB Data Java

2.1k views Asked by At

basically I got some Symmetric TSP data from TSPLIB http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ and then I try to build a path by first clustering the cities, building subtours for each cluster and then connecting the clusters. but the results I am getting for the complete Tour are extremely low compared to the optimal value. This leads me to believe that I have done something wrong but it is completely over my head, I have no idea why this is happening.

This is the data file 'Burma14':

1  16.47       96.10
2  16.47       94.44
3  20.09       92.54
4  22.39       93.37
5  25.23       97.24
6  22.00       96.05
7  20.47       97.02
8  17.20       96.29
9  16.30       97.38
10  14.05       98.12
11  16.53       97.38
12  21.52       95.59
13  19.41       97.13
14  20.09       94.55

I read this data from the file and produce a city object for each point.

Then I produce Individuals. These are basically subpaths the are randomly created from the available cities. An individual travel between two cities e.g. City1 -> City2.

I then build the path, which is basically the solution to the TSP.

First, clusters are generated as follows:

1 cluster cities [City_3, City_4]
2 cluster cities [City_1, City_8, City_9, City_11, City_2, City_10]
3 cluster cities [City_5, City_6, City_12]
4 cluster cities [City_7, City_13, City_14]

Then the subtours are created for each cluster as follows:

SubTour: | [[City_4, City_3]] |
Cost: 2.445178930058085

SubTour: | [[City_10, City_9], [City_9, City_11], [City_11, City_8], [City_8, City_1], [City_1, City_2]] |
Cost: 6.29233886113867

SubTour: | [[City_12, City_6], [City_6, City_5]] |
Cost: 4.107068449867602

SubTour: | [[City_14, City_7], [City_7, City_13]] |
Cost: 3.5647520864865525

These subtours are then connected to form a Complete Tour as follows:

Complete Tour: [| [[City_14, City_7], [City_7, City_13]] |, | [[City_12, City_6],    [City_6, City_5]] |, | [[City_4, City_3]] |, | [[City_2, City_1], [City_1, City_8], [City_8, City_11], [City_11, City_9], [City_9, City_10]] |]
Complete Tour Cost: 34.92630477283413

This is how I calculate the Euclidean Distance:

public static double calculateDistance(double x1, double y1, double x2, double y2){
    double xDistance = Math.abs(x1 - x2);
    double yDistance = Math.abs(y1 - y2);
    double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );

    return distance;
}

I really really cannot understand why my optimal cost is 34.92630477283413 but the optimal cost on this site http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html for burma14 is 3323. I have tried ulysses16 data set (from the some website) and I still have the same problem. I really do appreciate any sort of help of guidance.

Thank you.

0

There are 0 answers