計算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的地理位置和歐氏距離

回答

相關問題