如何将Graphhopper库应用于给定纬度/经度的坐标

Question

我想用坐标(纬度、经度(计算从一个地方到多个地方的最短路线。

现在的问题是如何将Graphhopper库应用于给定纬度/经度的坐标。

例如，对于一些给定城市的坐标(起始地点是柏林(，柏林、汉堡、比勒费尔德、多特蒙德、埃森、波恩、法兰克福、特里尔和帕德博恩，其中一条路线是：柏林->汉堡->比勒费尔德->Paderborn->多特蒙德->Essen->波恩->Trier->法兰克福

Answer 1

以下链接提供旅行推销员问题的实现：https://www.javatpoint.com/travelling-salesman-problem-in-java

我用解决方案得到了路线：

public class RouteHelper {
public static ArrayList<Integer> route = null;

public static double findHamiltonianCycle(double[][] distance, boolean[] visitCity, int currPos, int places, int count, double cost, double hamiltonianCycle) {
if(route == null) {
route = new ArrayList<>();
}

if (count == places && distance[currPos][0] > 0) { // an QJ: wieso bei 0? distance mit Start?
hamiltonianCycle = Math.min(hamiltonianCycle, cost + distance[currPos][0]);
route.add(currPos);
return hamiltonianCycle;
}

// BACKTRACKING STEP
for (int i = 0; i < places; i++) {
if (visitCity[i] == false && distance[currPos][i] > 0) {
// Mark as visited  
visitCity[i] = true;
hamiltonianCycle = findHamiltonianCycle(distance, visitCity, i, places, count + 1, cost + distance[currPos][i], hamiltonianCycle);  

// Mark ith node as unvisited  
visitCity[i] = false;  
}
}
return hamiltonianCycle;
}
}

主要：

double[][] distances = new double [coordinatesList.size()][coordinatesList.size()];
for(int j=0; j<coordinatesList.size();j++) {
for(int k=0; k<coordinatesList.size();k++) {
distances[j][k] = RouteHelper.distanceBetweenTwoCoordinates(coordinatesList.get(j), coordinatesList.get(k));
}
}
System.out.println(RouteHelper.findHamiltonianCycle(distances, new boolean[coordinatesList.size()], 0, coordinatesList.size(), 0, 0, 0));
model.put("shortestRouteAddressesList", RouteHelper.route);

route.add(currPos(；处于错误的位置：路线是一个很长的列表，有数千个条目

Answer 2

不带Graphhopper 的解决方案

public class RouteHelper {
public static Map<String, Coordinates> globalCoordinatesMap = null;
public static List<Integer> globalShortestRoute = null;
public static double globalActualRouteDistance = 0.0;

public static void shortestRouteByPermutation(int[] a, int k) {
if (k == a.length) {
double aDistanceOfRoundTrip = calculateDistance(a);
if(aDistanceOfRoundTrip < globalActualRouteDistance || globalShortestRoute == null) {
globalActualRouteDistance = aDistanceOfRoundTrip;
updateGlobalShortestRoute(a);
}
} 
else {
for (int i = k; i < a.length; i++) {
int temp = a[k];
a[k] = a[i];
a[i] = temp;
shortestRouteByPermutation(a, k + 1);
temp = a[k];
a[k] = a[i];
a[i] = temp;
}

}
}

private static void updateGlobalShortestRoute(int[] a) {
globalShortestRoute = new ArrayList<Integer>();
for(int i=0; i<a.length; i++) {
globalShortestRoute.add(a[i]);
}
}
private static double calculateDistance(int[] a) {
double distance = 0.0;
for(int i=0; i<a.length; i++) {
if(i==0 || i==a.length-1) {
distance = distance + distanceBetweenTwoCoordinates(globalCoordinatesMap.get(String.valueOf(0)), globalCoordinatesMap.get(String.valueOf(a[i])));
} else {
distance = distance + distanceBetweenTwoCoordinates(globalCoordinatesMap.get(String.valueOf(a[i])), globalCoordinatesMap.get(String.valueOf(a[i+1])));
}
}

return distance;
}
public static double distanceBetweenTwoCoordinates(final Coordinates c1, final Coordinates c2) {
double rad = Math.PI/180;
double a1 = Double.valueOf(c1.getLat()) * rad;
double a2 = Double.valueOf(c1.getLon()) * rad;
double b1 = Double.valueOf(c2.getLat()) * rad;
double b2 = Double.valueOf(c2.getLon()) * rad;

double dlat = b1 - a1;
double dlon = b2 - a2;

double a =  Math.sin(dlat/2) * Math.sin(dlat/2) + 
Math.cos(a1) * Math.cos(b1) * Math.sin(dlon/2) * Math.sin(dlon/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
double earthRadius = 6378.145;

double d = c * earthRadius;
return d;
}
}

在"；Main"：

List<Coordinates> coordinatesList = Geocoding.getCoordinatesForAddresses(addressList);
for(Coordinates c : coordinatesList) {
if(RouteHelper.globalCoordinatesMap==null) {
RouteHelper.globalCoordinatesMap = new HashMap<String, Coordinates>();
}
RouteHelper.globalCoordinatesMap.put(String.valueOf(c.getId()), c);
}

int[] aZiele = new int[coordinatesList.size()-1];
for(int a = 1; a<coordinatesList.size(); a++) {
aZiele[a-1] = a;
}
RouteHelper.shortestRouteByPermutation(aZiele, 0);

List<String> shortestRouteAddressesList = new ArrayList<String>();
shortestRouteAddressesList.add(addressList.get(0).getAddress());
for(int i=0; i<RouteHelper.globalShortestRoute.size(); i++) {
shortestRouteAddressesList.add(addressList.get(RouteHelper.globalShortestRoute.get(i)).getAddress());
}

//RouteHelper.globalCoordinatesMap = null;
//RouteHelper.globalShortestRoute=null;
//RouteHelper.globalActualRouteDistance = 0.0;