根据 Java 中的 Google DistanceMatrix 响应计算二维距离矩阵

Calculating a 2d distance matrix from a Google DistanceMatrix response in Java

我正在尝试使用 Google 或工具库解决旅行商问题和车辆路径问题,在教程中发现 here,他们使用距离矩阵 whose i, j 条目是从位置 i 到位置 j 的距离(以英里为单位),其中位置按以下顺序给出:

  1. 纽约 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 接受 destinationsarraylistLatLng 是一个简单的 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;
}