拼车多乘客线路规划

笔者最近在开发一款拼车的项目,车主发布服务时候 可能会有多个乘客购买,而每个乘客可能出发地和目的地不尽相同,这也就造成了车主接送乘客优先级的问题,到底怎么选择先接那个乘客送那个乘客才能减少出行距离呢.
地图路线规划这块用的高德地图 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 提供了地点经纬度信息 和乘客信息

image.png image.png

附上笔者草图手稿

QQ20180613-0.png

如果你正好做这方面的业务 也遇到了类似的情形,可以联系作者

联系QQ : 1060545231