如何将 Graphhopper 库应用于给定 latitude/longitude 的坐标？

Question

我想用坐标（纬度，经度）计算从一个地方到多个地方的最短路线

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

例如一些给定城市的坐标（起点是柏林），柏林、汉堡、比勒费尔德、多特蒙德、埃森、波恩、法兰克福、特里尔和帕德博恩，一条路线是：柏林 -> 汉堡 -> 比勒费尔德 -> 帕德博恩 -> 多特蒙德 -> 埃森 -> 波恩 -> 特里尔 -> 法兰克福

Answer 1

下面link提供了旅行商问题的实现： 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;
    }
}

在“主要”中：

    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;

如何将 Graphhopper 库应用于给定 latitude/longitude 的坐标？

How do I apply the Graphhopper library for coordinates with given latitude/longitude?

java

shortest-path

graphhopper