经过这段时间的使用和研究，我发现点和点之间的最短路线并不是最优的。针对所有点的组合可能，
得到的最短路线才是最好的（也就是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运行测试。欢迎评论/讨论私信
网友评论