1 回答

TA貢獻1898條經(jīng)驗 獲得超8個贊
我確實解決了這個問題。我用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有一個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;
}
添加回答
舉報