讨论/算法和数据结构/计算穿过地图上所有GPS点的最短路径(两点之前直线距离),起点确定,终点不确定,如何实现?/
计算穿过地图上所有GPS点的最短路径(两点之前直线距离),起点确定,终点不确定,如何实现?

需求

有一组经纬度坐标点,第一个点为起点,从起点开始把所有的点穿起来,求一条最短路径,地图上两点之间不考虑其他因素,直接求直线距离。

数据

名称 经纬度
北京南站 116.376873,39.866559
双贝子坟路7号院(南1门) 116.332394,39.898635
北京三环专家公寓 116.311013,39.911748
方恒万泽中心(南门) 116.297107,39.866553
停车场(天作国际3号楼南) 116.324064,39.959275
双贝子坟路7号院(南门) 116.332746,39.898688
北京铁道大厦 116.324782,39.900426

输出

站点之间的顺序: 北京南站 -> 方恒万泽中心(南门) -> 双贝子坟路7号院(南门) -> 双贝子坟路7号院(南1门) -> 北京铁道大厦 -> 北京三环专家公寓 -> 停车场(天作国际3号楼南)

求两点之前距离的方法

public static int getDistance(double oLongitude, double oLatitude, double dLongitude, double dLatitude) {
	double radLat1 = rad(oLatitude);
	double radLat2 = rad(dLatitude);
	double a = radLat1 - radLat2;
	double b = rad(oLongitude) - rad(dLongitude);
	double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) +
			Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
	s = s * 6378137;
	s = new BigDecimal(s).setScale(3, BigDecimal.ROUND_HALF_UP).doubleValue();
	return new BigDecimal(Math.ceil(s)).setScale(0, BigDecimal.ROUND_HALF_UP).intValue();
}
private static double rad(double d) {
	return d * Math.PI / 180.0;
}

哪位大神有帮忙看一下如何用算法实现,万分感谢!

展开讨论
刘彦民发起于 2019-12-30
最近编辑于 2019-12-30

在github上找到解决方法了,有一个开源项目jsprit,说的是车辆路径优化问题,跟我实际遇到的很类似,适合大量点求较优解的。他是基于启发式算法实现的。碰到类似问题的可以研究一下,github地址: https://github.com/graphhopper/jsprit

展开全部 6 讨论