计算Java中TSP的地理位置和欧氏距离

基本上我使用的是TSPLIB的数据，我有这个规范。计算Java中TSP的地理位置和欧氏距离

这是我的计算出的欧几里德距离（根据上述规格）：

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

这是（根据上述规格）我怎样计算出来的所述地理距离：

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

但是，这个问题是我得到的结果比TSPLIB最优（这是不可能的！）。我的计算有什么问题吗？我已经尝试使用预定义的数据和距离来计算最佳值，并且我确实得到了最优值，但我不确定为什么这个不起作用。

非常感谢。

来源

2014-02-19 RegUser

a）你指的是“以上规格”？ b）为什么距离比TSPLIB实例中的距离更短？我的意思是，那里的距离是沿着可能路线的距离，所以它们明显长于两点之间的地理距离，是不是？ –

对不起，这是规范：http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/DOC.PS @DaDaDom – RegUser

因为最佳路径是找到的最短路径 - 我很确定这意味着我有一个错误。我只是不知道如何检查我的计算是否错误..我不知道什么可能是错的@DaDaDom – RegUser

您的转换为弧度看起来很可疑。我会尝试：

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

另外，我想在我在我的评论中提及上面的Movable Type网站上使用的公式。

来源

2014-02-19 15:50:05 andand

感谢您的答复。我只是在规范的第7页上使用了相同的方法（它看起来相同，不认为我错过了任何东西）（链接在上面）。我不知道在这个规格中使用了什么配方，但它看起来不像Haversine配方。 – RegUser

更改'coorsinares2Radians'函数后，我得到了更合理的结果，但我不明白为什么，因为这不是如何在规范中计算..你有什么想法吗？谢谢。 – RegUser

我仍然发现路径不到最佳..真的不明白为什么！ – RegUser

这可能有助于您阅读TSPLIB

的常见问题

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

检查问：我得到的类型GEO的问题错了距离。

我遵循该实现而不是TSPLIB 95规范中列出的内容。我的实现（在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; 
}

我猜测，你的问题是由于以下的规范和使用nint计算的程度。但那实际上是错误的。例如，输入10.53意味着10度和53分钟。但是如果你使用nint来凑合10.53，那么你会得到11度，并且随后的分钟计算也是错误的。

来源

2015-06-10 00:12:01

计算Java中TSP的地理位置和欧氏距离

回答

相关问题