筆者最近在開發一款拼車的項目,車主釋出服務時候 可能會有多個乘客購買,而每個乘客可能出發地和目的地不盡相同,這也就造成了車主接送乘客優先級的問題,到底怎麼選擇先接那個乘客送那個乘客才能減少出行距離呢.
地圖路線規劃這塊用的高德地圖 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