1

I am trying to solve the Travelling Salesman Problem and Vehicle routing problem with the Google Or tools library, in the tutorial found here, they use a distance Matrix whose i, j entry is the distance from location i to location j in miles, where the locations are given in the order below:

  1. New York 1. Los Angeles 2. Chicago 3. Minneapolis 4. Denver 5. Dallas 6. Seattle 7. Boston 8. San Francisco 9. St. Louis 10. Houston 11. Phoenix 12. Salt Lake City

And their matrix distance looks like:

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

They further provide a tutorial on how to create a distance matrix dynamically except it is in Python and I am a not very good in it, I am using Java.

In my Java implementation I am using the Java Client and my code looks like

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();

            }
        });
    }

And the result looks like

[[10196, 6647, 4881], [0, 0, 0], [0, 0, 0]]

I do not understand how the matrix was made in the python code, can someone help me formulate it?

My DistanceMatrix response looks like

"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"
            }
        ]
    }
]

}```
4

1 回答 1

1

我确实解决了这个问题。我用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);
}

WherefindWithVehicleRoutingProblem需要一个arraylistof destinations。LatLng是一个简单的类，看起来像

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;
}
于 2019-10-02T09:59:19.067 回答