Calculating the geographic and euclidean distances for TSP in Java

Question

Basically I'm using data from TSPLIB and I have this spec .

This is how I calculated the Euclidean distance (according to the above spec):

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;
}

This is how I calculated the geographic distance (according to the above spec):

public static double calculateGeoDistance(double lat1, double lon1, double lat2, double lon2) {
    double lat1Rad = coordinates2Radians(lat1);
    double lat2Rad = coordinates2Radians(lat2);
    double lon1Rad = coordinates2Radians(lon1);
    double lon2Rad = coordinates2Radians(lon2);

    double R = 6378.388;

    double q1 = Math.cos(lon1Rad - lon2Rad);
    double q2 = Math.cos(lat1Rad - lat2Rad);
    double q3 = Math.cos(lat1Rad + lat2Rad);

    double distance = (R * Math.acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
    return distance;
}

private static double coordinates2Radians(double coordinate) {
    double deg = Math.round(coordinate);
    double min = coordinate - deg;
    double rad = Math.PI * (deg + 5.0 * min / 3.0) / 180.0; 
    // NOTE: Bug in TSPLIB95 Docu. Divide by 300 instead of 3.0.
    // 5.0 * 60 / 300 = 1 (60 minutes are 1 degree)
    // or use Math.PI * (deg in decimal) / 180.0; 
    return rad;
}

But this problem is that I'm getting results that are less than the TSPLIB optimal (that cant be possible!). Is there something wrong with my calculation? I have tried calculating the optimal using predefined data and distances and I do get the optimal, I'm not sure why this isnt working..

Many thanks.

a) which "above spec" are you referring to? b) Why can't the distances be shorter, compared to what is given in the TSPLIB instances? I mean, there, the distances are the ones along the possible routes, so they are obviously longer than the geographical distance between two points, aren't they? — Dominik Sandjaja, Feb 19 '14 at 12:42
Sorry this is the spec: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/DOC.PS @DaDaDom — MTA, Feb 19 '14 at 13:37
Because the optimal path is the shortest path found - I'm pretty sure it means that what I have has a bug. I just dont know how to check if my calculation is wrong.. I dont know what could be wrong @DaDaDom — MTA, Feb 19 '14 at 13:41
Your equation doesn't look right to me. It may be equivalent to the standard Haversine formulation, but if so, it's not a trivial transformation. I recommend you look at http://www.movable-type.co.uk/scripts/latlong.html — andand, Feb 19 '14 at 15:43
This is a bug in the calculation. Divide by 300 instead of 3.0 to get the correct result. I commented also in the code. — Gunnar Bernstein, May 04 '21 at 20:44

score 0 · Answer 1 · answered Feb 19 '14 at 15:50

0

Your conversion to radians looks suspicious. I would try:

private static double coordinates2Radians(double coordinate) {
    return Math.PI * coordinate / 180.0;
}

Also, I would use the equations at the Movable Type site I mentioned in my comment above.

answered Feb 19 '14 at 15:50

andand

17,134
11
53
79

Thanks for the reply. I just used the same approach (it looks the same, dont think i missed anything) on page 7 of the spec (the link is above). I dont know what formulation is used in this spec but it doesnt look like Haversine formulation. – MTA Feb 19 '14 at 17:10
I am getting more reasonable results after changing the 'coorsinares2Radians' function but i dont understand why because that is not how it is calculated in the spec.. do you have any ideas? Thanks. – MTA Feb 19 '14 at 17:26
I am still finding paths that are less than the optimal.. really cannot understand why! – MTA Feb 19 '14 at 17:39

score 0 · Answer 2 · answered Jun 10 '15 at 00:12

This might be helpful to you to read the FAQ of TSPLIB

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html

Check the Q: I get wrong distances for problems of type GEO.

I followed that implementation instead of what is listed in the TSPLIB 95 spec. My implementation (in Groovy):

static int[][] distancesInGEO(List nodes) {
    int dim = nodes.size();
    double[] latitude = new double[dim];
    double[] longitude = new double[dim];

    final double PI = 3.141592;
    for (int i = 0; i < dim; i++) {
        int deg = (int) (nodes[i].x);
        double min = nodes[i].x - deg;
        latitude[i] = PI * (deg + 5 * min / 3) / 180;
        deg = (int) nodes[i].y;
        min = nodes[i].y - deg;
        longitude[i] = PI * (deg + 5 * min / 3) / 180;
    }

    int[][] d = new int[dim][dim];

    final double RRR = 6378.388;
    for (int i = 0; i < dim; i++)
        for (int j = i + 1; j < dim; j++) {
            double q1 = cos(longitude[i] - longitude[j]);
            double q2 = cos(latitude[i] - latitude[j]);
            double q3 = cos(latitude[i] + latitude[j]);
            d[i][j] = (int) (RRR * acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
            d[j][i] = d[i][j];
        }
    return d;
}

I'm guessing that your problem was resulted from following the spec and using nint to calculate degree. But that is actually wrong. For example the input 10.53 means 10 degree and 53 minutes. But if you use the nint to round 10.53, then you'll get 11 degree, and subsequent computation of minute will also be wrong.

Calculating the geographic and euclidean distances for TSP in Java

2 Answers2