笔者最近在开发一款拼车的项目,车主发布服务时候 可能会有多个乘客购买,而每个乘客可能出发地和目的地不尽相同,这也就造成了车主接送乘客优先级的问题,到底怎么选择先接那个乘客送那个乘客才能减少出行距离呢. 地图路线规划这块用的高德地图 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 Person 和 LocationCoordinate 提供了地点经纬度信息 和乘客信息
附上笔者草图手稿
如果你正好做这方面的业务 也遇到了类似的情形,可以联系作者
好了，我是大兵布莱恩特，欢迎加入博主技术交流群，iOS 开发交流群