Golder 地图中的路线规划--获取校车行驶最佳路线的算法
最编程
2024-03-28 18:10:13
...
最近在做校车行驶路线规划的开发任务,为了获取一个最优的路线,我把所有站点能组成的路线罗列出来,然后计算这些组合出来的路线的总路程,最后比较获取最短的一个即为最终的最优路线
需要注意的地方:
1.各站点距离最好是计算前临时获取,这样能保证获取到实时的路线,因为城市建设会导致路线变化
2.每次规划,最多只能规划18个站点(起始站点+16个途径站点+终点站点)
3.高德API每天请求距离测量的接口是有次数限制的,需要登录控制台查看
4.假设存在A、B、C四个站点,需要获取A->B、B->A 、A->C、C->A、B->C、C->B所有站点之间的距离,获取次数为总站点数n*(n-1)
两站点间距离的bean
@Data
public class SiteDistance {
private Long startId; //开始站点Id
private Long endId; //结束站点Id
private Double distance;//站点间距离
}
以下为获取校车行驶的最优路径的算法
/**
* @Description siteIds的List第一个元素必须是学校站点,siteDistances的List应该包含各个点对所有的其他点的距离
* @Param
* @return
* @Date 2019/2/25 9:48
**/
public Map<String, Object> getBestRoute(List<Long> siteIds, List<SiteDistance> siteDistances){
//将距离数据,以"startId-endId"为key,distance为value保存在map中
Map<String, Double> distanceMap = new HashMap<>();
for (SiteDistance siteDistance: siteDistances) {
distanceMap.put(siteDistance.getStartId()+"-"+siteDistance.getEndId(), siteDistance.getDistance());
}
//获取各站点可能组成的所有路径
List<List<Long>> idCombine = new ArrayList<>();
perm(siteIds, 1,siteIds.size()-1, idCombine);
//获取总路程最短的一个组合
return getMinDistanceRoute(idCombine, distanceMap);
}
/**
* @Description 获取最短总路程的路径
* @Date 2019/2/25 8:46
**/
public Map<String, Object> getMinDistanceRoute(List<List<Long>> idCombine, Map<String, Double> distanceMap){
Map<String, Object> result = new HashMap<>();
Double minTotal = null;//最短路程
int minIndex = 0;//最短索引
for (int i=0;i<idCombine.size();i++) {
//将起始站点加到最后作为结束站点
List<Long> routeSites = new ArrayList<>();
routeSites.addAll(idCombine.get(i));
routeSites.add(routeSites.get(0));
//获取一条路线的总路程
Double totalDistance = getTotalDistance(routeSites, distanceMap);
if(null == minTotal || totalDistance < minTotal){
minTotal = totalDistance;//保存最短的路线路程
minIndex = i;//保存最短路线的索引
}
}
//将起始站点加到最后作为结束站点
List<Long> routeSites = new ArrayList<>();
routeSites.addAll(idCombine.get(minIndex));
routeSites.add(routeSites.get(0));
result.put("routeSites", routeSites);
result.put("totalDistance", minTotal);
return result;
}
//获取一条路线的总路程
public double getTotalDistance(List<Long> routeSites, Map<String, Double> distanceMap){
Double totalDistance = 0d;
for(int i = 1;i<routeSites.size();i++){
//从map中查询两站点之间的距离
totalDistance += distanceMap.get(routeSites.get(i-1) + "-" + routeSites.get(i));
}
return totalDistance;
}
/*
* 对数组arr进行全排列
* 全排列的范围:begin -> end
*/
public static void perm(List<Long> list,int begin,int end, List<List<Long>> result){
//设置递归的出口,即当需要全排列的范围只有一个元素,则全排结束,此数组为全排列
if(begin==end){
result.add(list);
List<Long> arr = new ArrayList<>();
for(int i=0;i<=end;i++){
arr.add(list.get(i));
//System.out.print(list.get(i) + " ");
}
//System.out.println();
result.add(arr);
return;
}else{
//for循环将begin -> end中的每一个数放到begin位置中去,并实现全排列
for(int j=begin;j<=end;j++){
swap(list,begin,j); //for循环将begin -> end中的每一个数放到begin位置中去
perm(list,begin+1,end, result); //假设begin位置确定,那么对begin+1 -> end中的数组进行全排列
swap(list,begin,j); //换过去后再将数组还原
}
}
}
public static void swap(List<Long> list,int i,int j){
Long temp=list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}