經(jīng)過(guò)這段時(shí)間的使用和研究，我發(fā)現(xiàn)點(diǎn)和點(diǎn)之間的最短路線并不是最優(yōu)的。針對(duì)所有點(diǎn)的組合可能，
得到的最短路線才是最好的（也就是TSP方法），然后再結(jié)合點(diǎn)對(duì)點(diǎn)之間的距離進(jìn)行比較，得到的才是相對(duì)最優(yōu)方案。

舉例：A、B、C、D四個(gè)點(diǎn)。自由組合，得到最短路線方案。
所有的組合路線應(yīng)該是（此處我們只需要四個(gè)點(diǎn)的組合）
ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC
得到的結(jié)果是這樣么多（24條路線）；
n!=(n-1)!*n

A、B、C、D四個(gè)點(diǎn)。設(shè)定一個(gè)點(diǎn)為起點(diǎn)（我設(shè)置A為起點(diǎn)），不設(shè)定終點(diǎn)，得到最短路線方案
BCD
BDC
CBD
CDB
DCB
DBC

A為起點(diǎn)，BCD自由組合，則有6條路線；

現(xiàn)在對(duì)6個(gè)結(jié)果進(jìn)行最短距離排序；根據(jù)高德的路線規(guī)劃，得到一個(gè)最短路線；

然后對(duì)著一條路線進(jìn)行規(guī)劃，你會(huì)得到一個(gè)路線的所有途徑點(diǎn)的集合，然后對(duì)途徑地點(diǎn)之間的距離進(jìn)行排序
，然后調(diào)整路線，進(jìn)行顯示就可以了。

下面開(kāi)始上代碼；

// 添加數(shù)據(jù)
if (start == null) {
Toast.makeText(this, "請(qǐng)選擇起點(diǎn)", Toast.LENGTH_SHORT).show();
return;
}
if (throughList.size() == 0) {
Toast.makeText(this, "請(qǐng)?zhí)砑油緩近c(diǎn)", Toast.LENGTH_SHORT).show();
return;
}
startTip = new LatLonPoint(new BigDecimal(start.getLat()).doubleValue(), new BigDecimal(start.getLon()).doubleValue());
sortPoint(throughList, startTip);

  // 組合點(diǎn)，得到所有可能的路線
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;}
        //遞歸，下一個(gè)數(shù)去排列
        sortPoint(result,k+1);
        //再歸位數(shù)據(jù)
        {char t = result[k];result[k] = result[i];result[i] = t;}
    }
    return list;
}

// 開(kāi)始路線規(guī)劃
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();
// 得到策略后所有點(diǎn)的集合
for (int j = 0; j < points.size(); j++) {
if (points.get(j).getId().equals(String.valueOf(array[i]))) {
through2.add(points.get(j));
}
}
// 填充規(guī)劃集合
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);
}

// 得到最短距離，根據(jù)最短距離得到最短路線，并展示地圖
@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: 規(guī)劃成果="+minDistance);
        }
    }
}

下面就不說(shuō)了，上一篇都已經(jīng)講到。這是是傳送陣。https://blog.csdn.net/Naide_S/article/details/80650547

后面會(huì)有下載鏈接。完整demo，僅供參考
https://github.com/MaDyShi/WJCMap

可下載demo運(yùn)行測(cè)試。歡迎評(píng)論/討論私信