高德地图之路线规划 多点路线规划路线最短原则之二 TSP算法

经过这段时间的使用和研究，我发现点和点之间的最短路线并不是最优的。针对所有点的组合可能，
得到的最短路线才是最好的（也就是TSP方法），然后再结合点对点之间的距离进行比较，得到的才是相对最优方案。

举例：A、B、C、D四个点。自由组合，得到最短路线方案。
所有的组合路线应该是（此处我们只需要四个点的组合）
ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC
得到的结果是这样么多（24条路线）；
n!=(n-1)!*n

A、B、C、D四个点。设定一个点为起点（我设置A为起点），不设定终点，得到最短路线方案
BCD
BDC
CBD
CDB
DCB
DBC

A为起点，BCD自由组合，则有6条路线；

现在对6个结果进行最短距离排序；根据高德的路线规划，得到一个最短路线；

然后对着一条路线进行规划，你会得到一个路线的所有途径点的集合，然后对途径地点之间的距离进行排序
，然后调整路线，进行显示就可以了。

下面开始上代码；

// 添加数据
if (start == null) {
Toast.makeText(this, "请选择起点", Toast.LENGTH_SHORT).show();
return;
}
if (throughList.size() == 0) {
Toast.makeText(this, "请添加途径点", Toast.LENGTH_SHORT).show();
return;
}
startTip = new LatLonPoint(new BigDecimal(start.getLat()).doubleValue(), new BigDecimal(start.getLon()).doubleValue());
sortPoint(throughList, startTip);

  // 组合点，得到所有可能的路线
private void sortPoint(List<Bean> allList,LatLonPoint start) {
    String s = "";
    for (int i = 0; i < allList.size(); i++) {
        s += allList.get(i).getId();
    }
    char[] result = s.toCharArray();
    routes = TSPUtil.sortPoint(result, 0);
    for (int i = 0; i < routes.size(); i++) {
        plan(allList, routes.get(i),start);
    }
}

static List<String> list = new ArrayList<>();
public static List<String> sortPoint(char result[], int k){
    String s = "";
    if(k==result.length){
        for(int i=0;i<result.length;i++){
            s += result[i];
        }
        list.add(s);
        return list;
    }
    for(int i=k;i<result.length;i++){
        //交换
        {char t = result[k];result[k] = result[i];result[i] = t;}
        //递归，下一个数去排列
        sortPoint(result,k+1);
        //再归位数据
        {char t = result[k];result[k] = result[i];result[i] = t;}
    }
    return list;
}

// 开始路线规划
private void plan(List<Bean> points,String s,LatLonPoint start) {
char[] array = s.toCharArray();
for (int i = 0; i < array.length; i++) {
through1.clear();
through2.clear();
// 得到策略后所有点的集合
for (int j = 0; j < points.size(); j++) {
if (points.get(j).getId().equals(String.valueOf(array[i]))) {
through2.add(points.get(j));
}
}
// 填充规划集合
for (int j = 0; j < through2.size(); j++) {
through1.add(new LatLonPoint(new BigDecimal(through2.get(j).getLat()).doubleValue(),new BigDecimal(through2.get(j).getLon()).doubleValue()));
}
}
AMapUtil.doRoutePlan(start,through1.get(through1.size()-1),through1,this,this);
}

// 得到最短距离，根据最短距离得到最短路线，并展示地图
@Override
public void onDriveRouteSearched(DriveRouteResult driveRouteResult, int i) {
    if (i == 1000) {
        if (driveRouteResult != null && driveRouteResult.getPaths() != null) {
            disList.add(Double.valueOf(driveRouteResult.getPaths().get(0).getTollDistance()));
            if (minDistance == 0) {
                minDistance = driveRouteResult.getPaths().get(0).getTollDistance();
            }else {
                if (minDistance > driveRouteResult.getPaths().get(0).getTollDistance()) {
                    minDistance = driveRouteResult.getPaths().get(0).getTollDistance();
                }
            }

            if (disList.size() == routes.size()) {
                for (int j = 0; j < disList.size(); j++) {
                    if (minDistance == disList.get(j)) {
                        if (throughList.size() > j && throughList.get(j) != null) {
                            minDisRoute = throughList.get(j);
                            Bundle bundle = new Bundle();
                            bundle.putString("start",GsonInstance.getInstance().toJson(start));
                            bundle.putString("end",GsonInstance.getInstance().toJson(throughList.get(0)));
                            bundle.putSerializable("list", (Serializable) throughList);
                            startActivity(ShowRouteActivity.class,bundle,true);
                            break;
                        }
                    }
                }
            }
            Log.d(TAG, "onDriveRouteSearched: 规划成果="+minDistance);
        }
    }
}

下面就不说了，上一篇都已经讲到。这是是传送阵。https://blog.csdn.net/Naide_S/article/details/80650547

后面会有下载链接。完整demo，仅供参考
https://github.com/MaDyShi/WJCMap

可下载demo运行测试。欢迎评论/讨论私信