笔者最近在开发一款拼车的项目,车主发布服务时候 可能会有多个乘客购买,而每个乘客可能出发地和目的地不尽相同,这也就造成了车主接送乘客优先级的问题,到底怎么选择先接那个乘客送那个乘客才能减少出行距离呢.
地图路线规划这块用的高德地图 API, 使用起来很简单 可以设置起点 终点 ,沿途经过点(最多16个途经点),就可以在地图上将所有点绘制成一条线路,如果不考虑每个点之间的距离,那么简单设置下 会看的地图上规划线路错综复杂,而且何有可能会有绕弯路甚至是重复的路线,就造成车主无法知道应该先去接送那个乘客,甚至可能多走冤枉路,当然对路况比较熟开车不用导航地图的老司机可以略过.
简而言之就是给你几个点 ,找出最短路径的问题,思路就是 先用车主的起点 跟3个乘客(假定只有3个乘客)的起点进行比较,得到最短的那个线路,然后可以先接这个比较近的乘客B,接下来用这个乘客的起点 跟 剩余两个乘客 A C 的起点,已经乘客B 自己的终点进行比较,得出应该将乘客 B 送到目的地再去接乘客 A C 还是先去接乘客 A, C 其中的一个 .如此反复没确定一个点 就可以以这个点对余下的点测距,直到最后一个点没有比较的时候,才会停止比较,然后将排序(按路线距离)的途径点数组 wayPoint 给高德地图 API, 这样高德地图SDK 会绘制出一条距离比较短的路线,按照这个路线可以方便的知道 应该先去接那个乘客 先送那个乘客到目的地.
以下是代码部分 并没有多少难度 参考了选择排序的一些思路,并做了一些优化(在比较次数不变情况下,减少对数组集合的删除添加操作)减少算法时间复杂度
```
//阿里巴巴 -> 120.026208,30.279212 萧山国际机场 120.43242,30.234697
Person *owner = PersonMake(@"车主",LocationCoordinateMake(30.279212,120.026208), LocationCoordinateMake(30.234697,120.43242));
//西溪北苑 -> 120.035535,30.287874 杭州东站 120.213116,30.290998
Person *passer1 = PersonMake(@"乘客", LocationCoordinateMake(30.287874,120.035535), LocationCoordinateMake(30.290998,120.213116));
// 杭州西溪银泰 120.075097,30.293039 -> 杭州火车站 120.182839,30.243403
Person *passer2 = PersonMake(@"乘客", LocationCoordinateMake(30.293039,120.075097), LocationCoordinateMake(30.243403,120.182839));
//杭州中医院 120.15436,30.269383 -> 萧山汽车站 120.280418,30.165468
Person *passer3 = PersonMake(@"乘客", LocationCoordinateMake(30.269383,120.15436), LocationCoordinateMake(30.165468,120.280418));
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
dict[passer1.startPt.hashType] = passer1.endPt;
dict[passer2.startPt.hashType] = passer2.endPt;
dict[passer3.startPt.hashType] = passer3.endPt;
NSMutableArray *points = [NSMutableArray array];
[points addObject:passer1.startPt];
[points addObject:passer2.startPt];
[points addObject:passer3.startPt];
NSMutableArray *shortestPath = [NSMutableArray array];
[shortestPath addObject:owner.startPt];
CFAbsoluteTime startTime =CFAbsoluteTimeGetCurrent();
///规划路径找出最短路径
while (points.count > 0) {
double minDistance = MAXFLOAT;
NSInteger count = points.count;
__weak LocationCoordinate *deleteCoordinate;
for (NSInteger i = 0; i<count; i++) {
LocationCoordinate *coordinate = [points objectAtIndex:i];
double distance = getDistance([shortestPath lastObject],coordinate);
///比较2个点的经纬度之间的距离
if (distance < minDistance) {
minDistance = distance;
deleteCoordinate = coordinate;
continue;
}
}
///在比较次数不变情况下 减少了对points 和 shortestPath 的修改操作
///将最路径最短的一个点放到 shortestPath 并将它对应终点取出来 再进行下一次毕竟
if (deleteCoordinate) {
[shortestPath addObject:deleteCoordinate];
[points removeObject:deleteCoordinate];
LocationCoordinate *endPt = [dict objectForKey:deleteCoordinate.hashType];
if (endPt) {
[points addObject:endPt];
}
}
}
///往高德地图 规划线路 navi.wayPoints 添加途径点数据
// NSMutableArray *wayPoints = [NSMutableArray array];
///起点不用加到wayPoints 里边 只需要将所有用户起点 终点 排序
for (int i = 1; i<shortestPath.count; i++) {
LocationCoordinate *coord = [shortestPath objectAtIndex:i];
NSLog(@"%@",coord);
// AMapGeoPoint *pt = [AMapGeoPoint locationWithLatitude:coord.latitude longitude:coord.longitude];
// [wayPoints addObject:pt];
}
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
NSLog(@"Linked in %f ms", linkTime *1000.0);
```
Person 和 LocationCoordinate 提供了地点经纬度信息 和乘客信息
附上笔者草图手稿
如果你正好做这方面的业务 也遇到了类似的情形,可以联系作者
联系QQ : 1060545231