根据 Java 中的 Google DistanceMatrix 响应计算二维距离矩阵
Calculating a 2d distance matrix from a Google DistanceMatrix response in Java
我正在尝试使用 Google 或工具库解决旅行商问题和车辆路径问题，在教程中发现 here，他们使用距离矩阵 whose i, j 条目是从位置 i 到位置 j 的距离（以英里为单位），其中位置按以下顺序给出：
- 纽约 1.洛杉矶 2.芝加哥 3.明尼阿波利斯 4.丹佛 5.达拉斯 6.西雅图 7.波士顿 8.旧金山 9.圣路易斯 10.休斯顿 11.凤凰城 12.盐湖城
它们的矩阵距离如下：
public final long[][] distanceMatrix = {
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
他们还提供了 tutorial 关于如何动态创建距离矩阵的方法，除了它在 Python 中，我不是很擅长，我正在使用 Java。
在我的 Java implementation 中，我正在使用 Java Client 并且我的代码看起来像
private static long[][] buildDistanceMatrix(int matrixSize, DistanceMatrix distanceMatrix) {
long[][] matrix = new long[matrixSize][matrixSize];
for (int i = 0; i < distanceMatrix.rows.length; i++) {
DistanceMatrixElement[] elements = distanceMatrix.rows[i].elements;
for (int j = 0; j < elements.length; j++) {
matrix[i][j] = elements[j].distance.inMeters;
}
}
return matrix;
}
public static void getDistanceMatrix(List<LatLng> origins, List<LatLng> destinations){
GeoApiContext context = new GeoApiContext.Builder()
.apiKey(GOOGLE_MAPS_API_KEY)
.build();
DistanceMatrixApiRequest distanceMatrixApiRequest = DistanceMatrixApi.newRequest(context)
.mode(TravelMode.DRIVING)
.trafficModel(TrafficModel.BEST_GUESS)
.departureTime(Instant.now().atZone(ZoneOffset.UTC).toInstant())
.destinations(destinations.toArray(new LatLng[destinations.size()]))
.origins(origins.toArray(new LatLng[origins.size()]));
distanceMatrixApiRequest.setCallback(new PendingResult.Callback<DistanceMatrix>() {
@Override
public void onResult(DistanceMatrix distanceMatrix) {
long[][] matrix = buildDistanceMatrix(destinations.size(), distanceMatrix);
System.out.println(Arrays.deepToString(matrix));
}
@Override
public void onFailure(Throwable throwable) {
throwable.printStackTrace();
}
});
}
结果看起来像
[[10196, 6647, 4881], [0, 0, 0], [0, 0, 0]]
我不明白python code中的矩阵是如何制作的，谁能帮我制定一下？
我的 DistanceMatrix 响应看起来像
"destinationAddresses": [
"Central St, Lusaka, Zambia",
"Unnamed Road, Lusaka, Zambia",
"Jacaranda Rd, Lusaka, Zambia"
],
"originAddresses": [
"1940 - 3 Munthaka Cl, Lusaka, Zambia"
],
"rows": [
{
"elements": [
{
"distance": {
"humanReadable": "10.2 km",
"inMeters": 10193
},
"duration": {
"humanReadable": "23 mins",
"inSeconds": 1352
},
"durationInTraffic": {
"humanReadable": "26 mins",
"inSeconds": 1549
},
"status": "OK"
},
{
"distance": {
"humanReadable": "6.6 km",
"inMeters": 6647
},
"duration": {
"humanReadable": "13 mins",
"inSeconds": 779
},
"durationInTraffic": {
"humanReadable": "14 mins",
"inSeconds": 839
},
"status": "OK"
},
{
"distance": {
"humanReadable": "4.9 km",
"inMeters": 4881
},
"duration": {
"humanReadable": "9 mins",
"inSeconds": 516
},
"durationInTraffic": {
"humanReadable": "9 mins",
"inSeconds": 538
},
"status": "OK"
}
]
}
]
}```
我确实解决了这个问题。我使用 Euclidean distance formular 得到距离矩阵
/// @brief Compute Euclidean distance matrix from locations array.
/// @details It uses an array of locations and computes
/// the Euclidean distance between any two locations.
private static long[][] computeEuclideanDistanceMatrix(long[][] locations) {
// Calculate distance matrix using Euclidean distance.
long[][] distanceMatrix = new long[locations.length][locations.length];
for (int fromNode = 0; fromNode < locations.length; ++fromNode) {
for (int toNode = 0; toNode < locations.length; ++toNode) {
if (fromNode == toNode) {
distanceMatrix[fromNode][toNode] = 0;
} else {
distanceMatrix[fromNode][toNode] =
(long) Math.hypot(locations[toNode][0] - locations[fromNode][0],
locations[toNode][1] - locations[fromNode][1]);
}
}
}
return distanceMatrix;
}
完整的解决方案看起来像
public static Assignment findWithVehicleRoutingProblem(List<LatLng> destinations, int numOfVehicles) {
long[][] distanceMatrix = RoutUtils.computeEuclideanDistanceMatrix(RoutUtils.scaleCoordinatesForEuclidean(destinations));
RoutingIndexManager manager = new RoutingIndexManager(distanceMatrix.length, numOfVehicles, 0);
RoutingModel routing = new RoutingModel(manager);
final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> {
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return distanceMatrix[fromNode][toNode];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
routing.addDimension(transitCallbackIndex, 0, 3000,
true,
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);
RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
return routing.solveWithParameters(searchParameters);
}
其中 findWithVehicleRoutingProblem 接受 destinations 的 arraylist。 LatLng 是一个简单的 class，看起来像
public class LatLng {
public double lat;
public double lng;
}
和scaleCoordinatesForEuclidean方法
private static final long DISTANCE_MATRIX_SCALE_FACTOR = 100000000000L;
private static long[][] scaleCoordinatesForEuclidean(List<LatLng> destinations) {
long[][] locations = new long[destinations.size()][destinations.size()];
for (int i = 0; i < destinations.size(); i++) {
long[] coordinate = {(long) (destinations.get(i).lat * DISTANCE_MATRIX_SCALE_FACTOR), (long) (destinations.get(i).lng * DISTANCE_MATRIX_SCALE_FACTOR)};
locations[i] = coordinate;
}
return locations;
}
我正在尝试使用 Google 或工具库解决旅行商问题和车辆路径问题，在教程中发现 here，他们使用距离矩阵 whose i, j 条目是从位置 i 到位置 j 的距离（以英里为单位），其中位置按以下顺序给出：
- 纽约 1.洛杉矶 2.芝加哥 3.明尼阿波利斯 4.丹佛 5.达拉斯 6.西雅图 7.波士顿 8.旧金山 9.圣路易斯 10.休斯顿 11.凤凰城 12.盐湖城
它们的矩阵距离如下：
public final long[][] distanceMatrix = {
{0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
{2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
{713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
{1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
{1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
{1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
{2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
{213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
{2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
{875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
{1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
{2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
{1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
};
他们还提供了 tutorial 关于如何动态创建距离矩阵的方法，除了它在 Python 中，我不是很擅长，我正在使用 Java。
在我的 Java implementation 中，我正在使用 Java Client 并且我的代码看起来像
private static long[][] buildDistanceMatrix(int matrixSize, DistanceMatrix distanceMatrix) {
long[][] matrix = new long[matrixSize][matrixSize];
for (int i = 0; i < distanceMatrix.rows.length; i++) {
DistanceMatrixElement[] elements = distanceMatrix.rows[i].elements;
for (int j = 0; j < elements.length; j++) {
matrix[i][j] = elements[j].distance.inMeters;
}
}
return matrix;
}
public static void getDistanceMatrix(List<LatLng> origins, List<LatLng> destinations){
GeoApiContext context = new GeoApiContext.Builder()
.apiKey(GOOGLE_MAPS_API_KEY)
.build();
DistanceMatrixApiRequest distanceMatrixApiRequest = DistanceMatrixApi.newRequest(context)
.mode(TravelMode.DRIVING)
.trafficModel(TrafficModel.BEST_GUESS)
.departureTime(Instant.now().atZone(ZoneOffset.UTC).toInstant())
.destinations(destinations.toArray(new LatLng[destinations.size()]))
.origins(origins.toArray(new LatLng[origins.size()]));
distanceMatrixApiRequest.setCallback(new PendingResult.Callback<DistanceMatrix>() {
@Override
public void onResult(DistanceMatrix distanceMatrix) {
long[][] matrix = buildDistanceMatrix(destinations.size(), distanceMatrix);
System.out.println(Arrays.deepToString(matrix));
}
@Override
public void onFailure(Throwable throwable) {
throwable.printStackTrace();
}
});
}
结果看起来像
[[10196, 6647, 4881], [0, 0, 0], [0, 0, 0]]
我不明白python code中的矩阵是如何制作的，谁能帮我制定一下？
我的 DistanceMatrix 响应看起来像
"destinationAddresses": [
"Central St, Lusaka, Zambia",
"Unnamed Road, Lusaka, Zambia",
"Jacaranda Rd, Lusaka, Zambia"
],
"originAddresses": [
"1940 - 3 Munthaka Cl, Lusaka, Zambia"
],
"rows": [
{
"elements": [
{
"distance": {
"humanReadable": "10.2 km",
"inMeters": 10193
},
"duration": {
"humanReadable": "23 mins",
"inSeconds": 1352
},
"durationInTraffic": {
"humanReadable": "26 mins",
"inSeconds": 1549
},
"status": "OK"
},
{
"distance": {
"humanReadable": "6.6 km",
"inMeters": 6647
},
"duration": {
"humanReadable": "13 mins",
"inSeconds": 779
},
"durationInTraffic": {
"humanReadable": "14 mins",
"inSeconds": 839
},
"status": "OK"
},
{
"distance": {
"humanReadable": "4.9 km",
"inMeters": 4881
},
"duration": {
"humanReadable": "9 mins",
"inSeconds": 516
},
"durationInTraffic": {
"humanReadable": "9 mins",
"inSeconds": 538
},
"status": "OK"
}
]
}
]
}```
我确实解决了这个问题。我使用 Euclidean distance formular 得到距离矩阵
/// @brief Compute Euclidean distance matrix from locations array.
/// @details It uses an array of locations and computes
/// the Euclidean distance between any two locations.
private static long[][] computeEuclideanDistanceMatrix(long[][] locations) {
// Calculate distance matrix using Euclidean distance.
long[][] distanceMatrix = new long[locations.length][locations.length];
for (int fromNode = 0; fromNode < locations.length; ++fromNode) {
for (int toNode = 0; toNode < locations.length; ++toNode) {
if (fromNode == toNode) {
distanceMatrix[fromNode][toNode] = 0;
} else {
distanceMatrix[fromNode][toNode] =
(long) Math.hypot(locations[toNode][0] - locations[fromNode][0],
locations[toNode][1] - locations[fromNode][1]);
}
}
}
return distanceMatrix;
}
完整的解决方案看起来像
public static Assignment findWithVehicleRoutingProblem(List<LatLng> destinations, int numOfVehicles) {
long[][] distanceMatrix = RoutUtils.computeEuclideanDistanceMatrix(RoutUtils.scaleCoordinatesForEuclidean(destinations));
RoutingIndexManager manager = new RoutingIndexManager(distanceMatrix.length, numOfVehicles, 0);
RoutingModel routing = new RoutingModel(manager);
final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> {
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return distanceMatrix[fromNode][toNode];
});
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
routing.addDimension(transitCallbackIndex, 0, 3000,
true,
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);
RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
return routing.solveWithParameters(searchParameters);
}
其中 findWithVehicleRoutingProblem 接受 destinations 的 arraylist。 LatLng 是一个简单的 class，看起来像
public class LatLng {
public double lat;
public double lng;
}
和scaleCoordinatesForEuclidean方法
private static final long DISTANCE_MATRIX_SCALE_FACTOR = 100000000000L;
private static long[][] scaleCoordinatesForEuclidean(List<LatLng> destinations) {
long[][] locations = new long[destinations.size()][destinations.size()];
for (int i = 0; i < destinations.size(); i++) {
long[] coordinate = {(long) (destinations.get(i).lat * DISTANCE_MATRIX_SCALE_FACTOR), (long) (destinations.get(i).lng * DISTANCE_MATRIX_SCALE_FACTOR)};
locations[i] = coordinate;
}
return locations;
}