曹 斌 洪 峰 王 凱 徐錦婷 趙立為 范 菁

(浙江工業(yè)大學計算機科學與技術學院 杭州 310023)

隨著經(jīng)濟不斷的發(fā)展，城市中私家車數(shù)量的增加，交通環(huán)境變得日益擁堵[1]，并伴隨著嚴重的環(huán)境污染問題.同時養(yǎng)車壓力居高不下，以及社交網(wǎng)絡不斷深入生活等多方面因素相互作用下，越來越多的人選擇拼車出行.參與拼車離不開拼車系統(tǒng)[2-4](軟件)，決定拼車軟件效率主要是其背后的拼車算法性能.然而目前市場上的拼車軟件的拼車算法仍存在較多不足之處，如：1)拼車方式不合理，只選取乘客周圍的司機進行匹配；2)拼車路線規(guī)劃隨意，沒有指向性，導致司機繞路距離增加；3)拼車請求不人性化，不能保證乘客的出發(fā)時間、司機的到達時間等.為此本文提出一種高效的大規(guī)模多對多拼車匹配算法Uroad來彌足現(xiàn)有算法的不足.

算法從全局角度出發(fā)，以所有司機產(chǎn)生的繞路距離總和最小為考量目標，對拼車請求中的乘客和司機進行匹配.Uroad在匹配乘客和司機的過程中，除了考慮到雙方的時間和費用條件之外，還將所有司機因為拼車產(chǎn)生的繞路距離也作為拼車過程中的考慮要素之一.司機在提出拼車申請時，除了要提供自身行程的出發(fā)位置和目的地位置之外，還可以提出自身行程開始的出發(fā)時間和要求到達自身目的地的最晚到達時間.同樣乘客在發(fā)出拼車請求時，除了需要包含行程的出發(fā)位置和目的地位置之外，還可以提出2方面的約束:1)時間約束即出發(fā)時間段，乘客可以提出一個出發(fā)時間段，表明司機可以在該時間內(nèi)前來接乘客；2)費用約束即最大拼車費用，乘客可以提出一個最大拼車費用值，表明對此次拼車服務乘客最多愿意支付的費用.Uroad則會根據(jù)自身的拼車計費模型為乘客來估算車費.除了考慮乘客自身行程距離之外，該計費模型還將因為乘客拼車而對司機產(chǎn)生的繞路距離也考慮在內(nèi).根據(jù)乘客的拼車要求，Uroad會盡可能為每一名乘客匹配一名符合雙方拼車條件的司機為其服務，最終使得所有司機因為拼車而產(chǎn)生的繞路距離之和最小.

不同于基本方法中直接計算大量最短路徑距離，Uroad在前期增加了一系列的基于時間、歐氏距離、路網(wǎng)距離的空間剪枝策略，以加快算法的整體運行速度和效率.其中拼車匹配過程共分為兩大階段：1)單乘客對多司機匹配，為每一名乘客找出所有符合其拼車要求的司機集合；2)多乘客與多司機最優(yōu)組合匹配，盡可能為每一名乘客在其司機集合中指定一名司機，使得所有司機產(chǎn)生的繞路距離最小.在第1階段中，Uroad通過連續(xù)的3種空間剪枝策略，能高效實現(xiàn)單個乘客與多司機的匹配，即基于乘客出發(fā)時間約束篩選、基于2點間歐氏距離篩選、基于路網(wǎng)真實距離篩選.第1階段匹配結果中每名乘客可以被多名司機服務，同時單個司機也可以服務多名乘客，因此Uroad在第2階段借鑒組合優(yōu)化的思想，利用Kuhn-Munkres(KM)算法[5]進行多乘客與多司機的全局最優(yōu)匹配，使最后的匹配結果產(chǎn)生的繞路路程之和最小.同時我們利用切分矩陣算法來提高這一階段的匹配速度.實驗結果顯示，算法能在2 min內(nèi)實現(xiàn)1 000名乘客在100 000名司機中找出最優(yōu)的拼車匹配組合方案，與直接計算最短路徑的基本方法相比，整體耗時縮短了40%.和現(xiàn)有算法中乘客隨機選擇司機的策略相比，加入了全局優(yōu)化策略，之后本文算法中所有司機的拼車距離總和可減少60%左右.同時實驗也顯示了各階段的剪枝技術較好的性能和較低的開銷，以及我們可以通過少量的路網(wǎng)距離計算來完成拼車匹配的優(yōu)勢.綜上，本文的貢獻主要有4個方面：

1) 定義了一種多對多拼車匹配問題，在拼車過程中加入了時間約束和費用約束，并且將所有司機繞路距離最小作為整體的拼車目標.

2) 通過3種空間剪枝技術縮小最短路徑的計算量，從而提高算法的整體效率.

3) 證明了切分矩陣算法的合理性，大幅加快了在確定乘客與司機的最優(yōu)匹配組合階段的運行速度，提高了算法整體的效率.

4) 基于真實路網(wǎng)信息，進行了大量大規(guī)模的仿真實驗，驗證了Uroad算法的有效性和高效性.

1 預備知識

本節(jié)將介紹一些預備知識，以便于更好地理解Uroad所研究的拼車場景和拼車方式，包括乘客和司機的定義、拼車中的計費模型以及拼車問題的定義.

1.1 乘客和司機

1.1.1 乘客

乘客指的是向Uroad提出拼車服務請求的人員.為了能夠獲得較好的拼車服務，Uroad要求乘客r在拼車請求中除了表明自己的出發(fā)位置Orig(r)和目的地位置Dest(r)這2個必要的位置信息之外，還需要提出一個出發(fā)時間段，即最早出發(fā)時間departureTimeMin(r)和最晚出發(fā)時間departure-TimeMax(r)，以此來確定乘客r的出發(fā)時間范圍，乘客r只在該時間范圍內(nèi)接受司機的拼車服務.同時，乘客r需要在拼車請求中提出一個最大拼車費用maxPrice(r)，以此來限定本次拼車服務的費用.在乘客設定最大拼車費用maxPrice(r)時，系統(tǒng)會根據(jù)乘客提供的出發(fā)位置Orig(r)和目的地位置Dest(r)來預估一個最低拼車費用值，以此為乘客設定拼車費用提供參考，同時也保證了司機的最低收益.乘客在根據(jù)要求向Uroad提出自己的拼車請求之后，Uroad會自動反饋乘客的拼車匹配結果，乘客只需在出發(fā)時間段內(nèi)等待相應的拼車司機來接送即可.

1.1.2 司機

司機指的是能夠提供拼車服務的通勤人員.為了能夠順利地提供拼車服務，司機d需要提供自己的出發(fā)位置Orig(d)和目的地位置Dest(d).此外，司機還需要提出一個出發(fā)時間DepartureTime(d)和一個最晚達到時間ArrivalTime(d)，分別代表司機會在時刻DepartureTime(d)從自身的出發(fā)位置出發(fā)，并且必須要在ArrivalTime(d)之前達到自己的目的地位置.

根據(jù)乘客提出的拼車要求，Uroad為每一名乘客盡可能確定一名能夠滿足雙方拼車要求的司機作為拼車對象.當司機確定了拼車匹配結果后，從司機的出發(fā)位置出發(fā)到乘客的出發(fā)位置，接上乘客之后將其送達到目的地，最后再返回司機自己的目的地位置.期間，司機獲得的車費收入，主要是根據(jù)乘客自身的行程距離和司機因為接送乘客產(chǎn)生的繞路距離這兩部分來決定的.車費的具體計算方式，將在2.2節(jié)中展開.

1.2 計費模型

圖1是拼車過程的一個示意圖.其中，黑點分別代表司機d的出發(fā)位置Orig(d)和目的地位置Dest(d).白點代表了乘客r的出發(fā)位置Orig(r)和目的地位置Dest(r).虛線表示司機原本的行程路線，即從司機的出發(fā)位置直接到其目的地位置的行程，記為DriverTrip(d).實線代表實際拼車過程中的行程路線，主要分為3部分：1)從司機的出發(fā)位置Orig(d)到乘客的出發(fā)位置Orig(r)，記為Pickup(d,r)；2)從乘客的出發(fā)位置Orig(r)到乘客的目的地位置Dest(r)，記為RiderTrip(r)；3)從乘客的目的地位置Dest(r)到司機的目的地位置Dest(d)，記為Return(d,r).顯然，為了給乘客r提供拼車服務，司機d在接送乘客r的過程中，相比于司機原本的行程DriverTrip(d)，勢必會產(chǎn)生一定的繞路距離，將其記為Detour(d,r).

Fig. 1 Carpooling process diagram圖1 拼車過程示意圖

以圖1為例，乘客r在獲得了司機d提供的拼車服務后，需要支付的拼車費用記為Price(d,r).拼車費用Price(d,r)主要分為2部分：一部分是RiderTrip(r)所對應的費用.這部分費用是乘客r至少需要支付的費用，只與行程RiderTrip(r)有關.另一部分費用是因為司機d接送乘客r而產(chǎn)生的繞路距離Detour(d,r)所對應的費用.因為不同的司機，對應的繞路距離不同.所以對乘客而言，這部分費用是會發(fā)生變化的.綜上所述，車費Price(d,r)表示為

Price(d,r)=RiderTrip(r)+Detour(d,r)，

(1)

其中繞路距離Detour(d,r)代表的是司機拼車實際路程(圖1中的實線)與司機原本的路程(圖1中的虛線)的距離之差.所以繞路距離Detour(d,r)表示為

Detour(d,r)=Pickup(d,r)+RiderTrip(r)+
Return(d,r)-DriverTrip(d).

(2)

根據(jù)式(1)和式(2)，拼車車費Price(d,r)可以直接表示為

Price(d,r)=Pickup(d,r)+2×RiderTrip(r)+
Return(d,r)-DriverTrip(d).

(3)

需要說明的是，式(3)中所有行程的金額，即2點之間的行程所代表的金額，都是其對應的最短路徑距離的倍數(shù).例如Pickup(d,r)代表的是從司機出發(fā)位置Orig(d)到乘客出發(fā)位置Orig(r)這段路程所代表的距離，費用即是從司機出發(fā)位置Orig(d)到乘客出發(fā)位置Orig(r)的最短路徑距離的某一個倍數(shù)值,這個倍數(shù)即實際情景中每公里定價.

1.3 問題定義

在拼車計費模型的基礎上，我們對研究的拼車問題做出了如下定義：

定義1. 給定一個司機的集合D，任一司機d∈D包含出發(fā)位置Orig(d)、目的地位置Dest(d)、出發(fā)時間DepartureTime(d)、最晚達到時間ArrivalTime(d)這4部分信息.給定一個乘客的集合R，任一乘客r∈R包含5部分信息：出發(fā)位置Orig(r)、目的地位置Dest(r)、最大拼車費用maxPrice(r)、最早出發(fā)時間departureTime-Min(r)、最晚出發(fā)時間departureTimeMax(r).feedbackTime(D,R)表示拼車匹配結果反饋給乘客與司機的時間.那么我們的目標是，為?r∈R找出一名司機d∈D能夠滿足雙方的拼車要求，即需要滿足5點要求：

1)departureTimeMin(r)≤DepartureTime(d)+Pickup(d,r)≤departureTimeMax(r)；

2)DepartureTime(d)+Pickup(d,r)+RiderTrip(r)+Return(d,r)≤ArrivalTime(d)；

3)Price(d,r)≤maxPrice(r)；

4)feedbackTime(D,R)

其中，需要注明的是，第1)2)條要求中的Pickup(d,r),RiderTrip(r),Return(d,r)雖然代表的是最短路徑距離，但是Uroad可以根據(jù)拼車時道路上的實時平均車速來轉(zhuǎn)換成對應的行駛時間.所以這里指代的是其對應的行駛時間，是對應的最短路徑距離的某一個倍數(shù)值，這個倍數(shù)是可以根據(jù)計算時的具體情況調(diào)整：

1) 表示的是司機必須要在乘客的出發(fā)時間范圍內(nèi)到達乘客的出發(fā)位置，以方便乘客能夠合理規(guī)劃自己的行程；

2) 表示的是司機在完成乘客的拼車訂單之后，還能在自己的最晚到達時間之前到達司機自身的目的地，保證了司機的行程不被耽誤；

3) 表示的是乘客支付的車費必須小于他提出的最大拼車費用；

4) 司機和乘客出發(fā)時間之前獲得拼車反饋信息，確保司機在出行時能夠明確自己的具體行程安排；

5) 表示所有司機因為拼車產(chǎn)生的繞路距離最小.

1.4 數(shù)據(jù)結構

1.4.1 司機信息列表(driver table)

司機信息列表中存儲了當前所有已經(jīng)提出拼車請求但是還沒有匹配到乘客的司機.每當一名新的司機提出了拼車服務請求之后，他就會被添加進司機信息列表中.作為司機信息列表中的一個實體，它需要包含6項屬性：

1)ID為一名司機的唯一標識；

2)Origin為司機當前的出發(fā)位置，通?？梢酝ㄟ^手機等移動設備獲??；

3)Destination為司機的目的地位置信息；

4)DriverTrip為從司機的出發(fā)位置到其目的地位置的最短路徑距離；

5)DepartureTime為出發(fā)時間；

6)ArrivalTime為最晚到達目的地的時間.當司機匹配到乘客之后，會自動將該司機從司機列表中刪除.

1.4.2 網(wǎng)格索引(grid index)

我們將地圖劃分成m×n個相同大小的正方形網(wǎng)格.根據(jù)司機的出發(fā)位置來確定其所屬的網(wǎng)格，并將司機存入該網(wǎng)格內(nèi).當要查詢某一范圍的司機時，只要確定該范圍所覆蓋的網(wǎng)格，直接獲取這些網(wǎng)格內(nèi)的所有司機并進行篩選即可.這就避免了對所有司機進行檢驗篩選，降低了查詢過程中的時間消耗.這里選擇使用網(wǎng)格索引是因為它易于實現(xiàn)和較低的更新開銷.因為在拼車場景中司機信息會被頻繁地創(chuàng)建和刪除，所以更新和構建索引的開銷會極大影響算法的效率.因此，在更新頻率較高的拼車場景中，通過建立更新和建立索引開銷較低的網(wǎng)格索引則比較合適.

1.4.3 時間索引(time index)

我們采用hashmap的數(shù)據(jù)結構來實現(xiàn)時間索引的構建.根據(jù)司機的出發(fā)時間構建一個司機出發(fā)時間索引(driver departure time index)，將出發(fā)時間點作為key值，其對應的value值是所有在出發(fā)時刻的司機所構成的司機集合.當要獲取某一出發(fā)時間的所有司機時，只要根據(jù)時間在司機出發(fā)時間索引中直接獲取該時間下的所有司機即可.相應地根據(jù)乘客的最晚出發(fā)時間來建立一個乘客的出發(fā)索引(rider departure time index)，同樣是將乘客的最晚出發(fā)時間點作為key值，所有最晚出發(fā)時間相同的乘客構成乘客集合作為value值存儲在對應位置中.通過時間索引可以快算查找對應時刻的司機和乘客，就可以降低根據(jù)時間查找司機和乘客的時間，從而提高整體算法的運行速度.

1.4.4 繞路距離記錄表(detour distance table)

為了記錄下乘客與司機之間是否能夠匹配以及匹配成功后的繞路距離等信息，我們設計并采用繞路距離記錄表來存儲匹配的繞路距離，如表1所示：

Table 1 Detour Distance Diagram表1 繞路距離記錄表

繞路距離記錄表中的行表示乘客，列表示司機每個空格的數(shù)據(jù)值代表司機與乘客進行匹配時產(chǎn)生的繞路距離.例如司機d1與乘客r1可以進行拼車匹配，匹配后的繞路距離為5 km，填在司機d1和乘客r1相交的空格中；如果司機d2與乘客r1不能匹配，則空格的值為無窮大∞.由于拼車條件的限制，并不是任意一名乘客與司機都能成功匹配，即表格中存在大量的∞.所以考慮到這一特性，我們采用稀疏矩陣的形式來實現(xiàn)繞路距離記錄表，在縮小存儲空間的同時，也能加快搜索和查找的速度.

2 Uroad查詢過程

本文算法可以分為兩大步驟執(zhí)行：1)單乘客對多司機匹配,每一名乘客找出所有既能符合乘客拼車要求又能滿足自身拼車要求的司機；2)多乘客與多司機最優(yōu)組合匹配,每一名乘客在滿足要求的司機中指定一名司機與之匹配，使得最終所有司機的拼車繞路距離之和最小.

2.1 單乘客對多司機匹配

篩選出滿足某一乘客拼車要求的司機，現(xiàn)有較為簡單的方法是:直接計算所有司機出發(fā)位置到乘客出發(fā)位置的Pickup(d,r)距離，以及乘客目的地位置到所有司機目的地位置的Return(d,r)距離.根據(jù)計算獲得的每一名乘客與所有司機匹配后各路段行程的最短距離，來篩選出所有既能符合乘客出發(fā)時間和最大拼車費用約束，又能保證自身時間約束的司機.雖然這個方法看上去十分簡單，但是它需要進行大量的路網(wǎng)距離計算.計算量非常巨大，極大影響算法的性能.這對于需要快速反饋的拼車場景來說并不可取.為了避免出現(xiàn)以上情況，我們通過運用一些空間剪枝技術來縮小需最短路徑距離計算量.Find Drivers Algorithm算法主要分為3部分:出發(fā)時間篩選(departure time pruning, DTP)、歐氏距離篩選(Euclidean pruning, EP)、最短路徑距離篩選(shortest path pruning, SP).

2.1.1 基于乘客出發(fā)時間篩選

在這一步驟中，輸入的是司機的出發(fā)時間索引和乘客的最晚出發(fā)時間索引.輸出是每一名乘客對應的所有出發(fā)時間在其最晚出發(fā)時間之前的司機集合，記為D1.這一步主要是刪去所有出發(fā)時間不符合要求的司機.

因為乘客和司機都有各自的特定出發(fā)時間，所以如果司機能夠為乘客提供拼車服務，那么司機的出發(fā)時間DepartureTime(d)必定要早于乘客的最晚出發(fā)時間departureTimeMax(r)，才有可能滿足乘客的出發(fā)時間要求.

Fig. 2 Rider departure time index and driver departure time index diagram圖2 乘客最晚出發(fā)時間索引和司機出發(fā)時間索引示意圖

為了找出所有早于乘客最晚出發(fā)時間departure-TimeMax(r)的司機，最直接的方法就是遍歷所有的司機，判斷他們的出發(fā)時間符合乘客的要求.但是這需要消耗大量的時間，所以這個方法并不可取.所以我們通過建立司機出發(fā)時間索引(driver departure time index)和乘客最晚出發(fā)時間索引(rider max departure time index)，實現(xiàn)查詢速度的提升.其中2個索引的key值按從早到晚的順序進行排序.2個索引的結構具體如圖2所示.

出發(fā)時間篩選的偽代碼如算法1所示.

算法1. 出發(fā)時間篩選算法.

輸入:司機出發(fā)時間索引ddti、乘客最晚出發(fā)時間索引rmdti；

輸出:符合雙方時間要求的司機集D1.

①DS=null;*司機集合*

②ddti.keySet()→dtArray;*從小到大進行排列*

③rmdti.keySet()→rtArray;*從小到大進行排列*

④Start=0;*在dtArray中標記第1個索引*

⑤ FOR(i=0;i

⑥r(nóng)Time=rtArray[i];

⑦ FOR(j=Start;j

dtArray[length-1];i++)

⑧ Put allddti.get(dtArray[j]) into

DS;

⑨ ENDFOR

⑩RS←rmdti.get(rTime);*乘客集合*

出發(fā)時間篩選的5個主要步驟為：

1) 按順序遍歷乘客最晚出發(fā)時間索引，先獲取出發(fā)時間最早的乘客集合和對應的時刻記為rTime(行⑥).

2) 順序遍歷司機出發(fā)時間索引并獲取合并對應的司機集合，直到出發(fā)時間與rTime相等為止(行⑦～⑨).將此時的合并后獲得的司機集合記為D1，那么D1就是出發(fā)時間篩選后時刻rTime對應的乘客集合中所有乘客的目標司機集合(行).

3) 完成時刻rTime后，繼續(xù)為乘客最晚出發(fā)時間索引中下一時刻rTime′乘客集合進行出發(fā)時間篩選.

5) 直到遍歷完乘客最晚出發(fā)時間索引位為止.

通過以上5個步驟我們只需遍歷一遍乘客最晚出發(fā)時間索引和司機出發(fā)時間索引就可完成整個出發(fā)時間篩選步驟.

例1. 以圖2為例，出發(fā)時間篩選的具體操作為:

2.1.2 基于歐氏距離篩選

在這一計算步驟中，輸入為一名乘客r的拼車請求和該乘客通過出發(fā)時間篩選后獲得的司機集合D1.輸出的是所有在歐氏距離上滿足了乘客r的拼車要求，并且也滿足自身到達時間要求的所有司機D3.

為了能夠更加清晰地說明我們的算法，我們將用圖3中的例子來配合解釋.黑色的點代表的是乘客，白色的點代表的是司機.圖3(a)中的點表示的是司機和乘客的出發(fā)位置，圖3(b)中的點表示的是他們的目的地位置.

Fig. 3 Euclidean distance screening diagram圖3 歐氏距離篩選說明圖

眾所周知，歐氏距離指2點之間的線段距離，它必定是小于或等于2點之間的路網(wǎng)距離.而且相比于計算2點之間的最短路徑距離而言，計算2點之間的歐氏距離花費的時間就要短得多.因此，在計算實際路網(wǎng)距離之前，通過歐氏距離排除一部分不可能匹配的司機，這是一種時間代價較低的剪枝方法.

歐氏距離篩選的偽代碼如算法2所示：

算法2. 歐氏距離篩選算法.

輸入:司機集合D1、1名乘客r、當前時刻Now；

輸出:司機集合D3.

① Build the grid indexgforD1;

②riderTimeMax←departureTimeMax(r)-Now;

③dmax←riderTimeMax;*dmax是一個距離*

④D1←RangeQuerry(g,orig(r),dmax);

⑤ FORd∈D1DO

⑥ ComputeEuclideanPickup(d,r);

⑦ IFDepartureTime(d)+EuclideanPickup(d,r)≤departureTimeMax(r) THEN

⑧ AdddintoD2;

⑨ EndIF

⑩ ENDFOR

RiderTrip(r)+EuclideanReturn(d,r)-DriverTrip(d)≤maxPrice(r) &&

DepartureTime(d)+EuclideanPickup(d,r)+RiderTrip(r)+EuclideanReturn(d,r)≤ArrivalTime(d) THEN

歐氏距離篩選的主要步驟為

1) 根據(jù)D1中司機的出發(fā)位置，為他們建立網(wǎng)格索引g(行①).計算從當前時刻Now起到乘客r最晚出發(fā)時間departureTimeMax(r)的時長，即departureTimeMax(r)-Now，記為riderTimeMax(行②).根據(jù)目前道路平均時速Speed和rider-TimeMax相乘計算獲得能夠滿足乘客出發(fā)時間要求的最遠距離dmax(行③).

2) 通過grid index篩選出所有落在以乘客出發(fā)位置Orig(r)為圓心、以dmax為半徑的圓范圍內(nèi)的所有司機，記為D1(行④)，并記錄下乘客r出發(fā)位置Orig(r)與這些司機出發(fā)位置的歐氏距離，記為EuclideanPickup(d,r).

3) 從這些司機中篩選出在歐氏距離上滿足：

DepartureTime(d)+EuclideanPickup(d,r)≤
departureTimeMax(r).

(4)

式(4)的乘客出發(fā)時間要求的司機，組成司機集合D2(行⑤～⑩).

需要特別說明的是，在步驟3中不使用乘客的出發(fā)時間約束departureTimeMin(r)≤depar-tureTime(d)+EuclideanPickup(d,r)這一條件，是因為2點之間的路網(wǎng)距離是大于等于歐氏距離的，所以可能存在有些司機雖然在歐氏距離上不滿足乘客的這一出發(fā)時間約束，但是在路網(wǎng)距離上確實滿足.為了避免將這些司機誤刪，所以不采用departureTimeMin(r)≤DepartureTime(d)+EuclideanPickup(d,r)這一時間約束條件，但是在之后的路網(wǎng)距離篩選上，會用到乘客的最晚出發(fā)時間來作為篩選條件.

4) 計算從乘客r的目的地位置Dest(r)到集合D2中所有司機目的地位置的歐氏距離，并記為EuclideanReturn(d,r).判斷這些司機在歐氏距離上是否都滿足乘客r的拼車費用約束，即是否滿足：

EuclideanPickup(d,r)+2×RiderTrip(r)+
EuclideanReturn(d,r)-DriverTrip(d)≤
maxPrice(r)，

(5)

同時是否滿足司機自身的到達時間約束，即是否滿足：

DepartureTime(d)+EuclideanPickup(d,r)+
RiderTrip(r)+EuclideanReturn(d,r)≤
ArrivalTime(d).

(6)

將同時滿足式(5)(6)的司機保留下來，組成司機集合D3(行～).司機集合D3就是滿足歐氏距離篩選的乘客r的司機集合.

例2. 乘客r1根據(jù)出發(fā)時間篩選后，獲得的司機集合D1中的司機分布如圖3所示.進行歐氏距離篩選計算時的時刻Now=07:20，平均道路時速Speed=60 kmh，rate=1yuankm.乘客r1的departureTimeMin(r1)=7:30，departureTime-Max(r1)=7:40；RiderTrip(r1)=12 km；maxPrice(r1)=20yuan.計算可得乘客r1的riderTimeMax=20 min，則dmax=20 km.為司機集合D1中的司機建立grid index后，根據(jù)dmax篩選出司機{d1,d2,d3,d4,d6,d7,d8,d9,d10,d12,d13}是在圓范圍內(nèi)的.接著計算乘客r1的出發(fā)位置與這些司機的Euclid-eanPickup(d,r)的距離，并檢驗是否滿足式(4)乘客出發(fā)時間的要求，各司機的計算結果如表2所示：

Table 2 Euclidean Distance Screening Step 1表2 歐氏距離篩選步驟1

所以滿足式(4)的司機集合D2為{d1,d2,d3,d4,d6,d7,d9}.

接著計算司機集合D2中所有司機目的地位置與乘客r1目的地位置Dest(r)之間的Euclidean-Return(d,r)距離，并檢驗是否滿足式(5)(6)的乘客拼車費用和司機到達時間約束，計算結果如表3所示:

Table 3 Euclidean Distance Screening Step 2表3 歐氏距離篩選步驟2

同時滿足式(5)(6)的司機集合D3為{d1,d3,d4,d6,d7}，所以經(jīng)過歐氏篩選之后獲得的司機集合為D3={d1,d3,d4,d6,d7}.

2.1.3 基于路網(wǎng)距離篩選

這一步的輸入是一名乘客r的拼車和通過歐氏距離篩選的司機集合D3；輸出是通過路網(wǎng)距離篩選的司機集合D5，即所有滿足乘客拼車要求的司機組成的集合.

路網(wǎng)距離篩選和歐氏距離篩選大致相同，分別是計算乘客與司機之間的路網(wǎng)Pickup(d,r)距離和Return(d，r)距離來對司機進行篩選，主要的差別在于約束條件上有略微的調(diào)整.

路網(wǎng)距離篩選的偽代碼如算法3所示:

算法3. 路網(wǎng)距離篩選.

輸入:司機集合D3、1個乘客r；

輸出:司機集合D5.

① FORd∈D3DO

② ComputePickup(d,r);

③ IFDepartureTime(d)+Pickup(d,r)≤departureTimeMax(r) &&Pickup(d,r)+2×RiderTrip(r)+Euclidean-Return(d,r)-DriverTrip(d)≤maxPrice(r) &&departureTime(d)+Pickup(d,r)+RiderTrip(r)+EuclideanReturn(d,r)≤Arrival-Time(d) THEN

④ PutdintoD4;

⑤ ENDIF

⑥ ENDFOR

⑦ FORd∈D4DO

⑧ ComputeReturn(d,r);

⑨ IFPickup(d,r)+2×RiderTrip(r)+Return(d,r)-DriverTrip(d)≤maxPrice(r) &&DepartureTime(d)+Pickup(d,r)+RiderTrip(r)+Return(d,r)≤ArrivalTime(d) THEN

⑩ PutdintoD5;

Table;

路網(wǎng)距離篩選的主要步驟有3個：

1) 計算乘客r與D3中所有司機的Pickup(d,r)距離，并檢驗是否滿足時間約束，即：

departureTimeMin(r)≤DepartureTime(d)+
Pickup(d,r)≤departureTimeMax(r).

(7)

2) 利用路網(wǎng)距離Pickup(d,r)和歐氏距離EuclideanReturn判斷司機是否符合式(8)(9)：

Pickup(d,r)+2×RiderTrip(r)+
EuclideanReturn(d,r)-
DriverTrip(d)≤maxPrice(r)；

(8)

DepartureTime(d)+Pickup(d,r)+
RiderTrip(r)+EuclideanReturn(d,r)≤
ArrivalTime(d).

(9)

這一步是為了刪除更多不符合要求的司機，這里利用司機的到達時間約束和乘客的費用約束，通過半歐氏的方法刪除一部分不符合要求的司機.將經(jīng)過這一步篩選之后得到的司機集合記為D4，該集合中的所有司機都滿足乘客的拼車時間要求.但是由于用到了EuclideanReturn，所以并不是所有司機在乘客的費用約束和司機的到達時間約束上都滿足要求，還需進一步的篩選.

3) 計算司機集合D4中所有司機與乘客r的Return距離，并判斷是否符合乘客r的費用約束和司機的到達時間約束，即是否滿足式(10)(11)：

Pickup(d,r)+2×RiderTrip(r)+
Return(d,r)-DriverTrip(d)≤
maxPrice(r)；

(10)

DepartureTime(d)+Pickup(d,r)+
RiderTrip(r)+Return(d,r)≤
ArrivalTime(d).

(11)

將滿足式(10)(11)的司機組成集合D5，則該集合就是所求的所有滿足乘客r的拼車條件的司機集合.

最后根據(jù)式(2)計算出乘客r1與司機集合D5中所有司機的繞路距離Detour(d,r)，并將結果寫入繞路距離記錄表中.偽代碼如例3所示：

例3. 在歐氏距離篩選結果的基礎上對路網(wǎng)距離篩選進行進一步的說明計算司機集合D3中所有司機的出發(fā)位置到乘客r1出發(fā)位置的Pickup(d,r)距離，并判斷是否在路網(wǎng)距離上滿足式(7)～(9)乘客的出發(fā)時間約束，各司機的計算結果如表4所示.

Table 4 Road Network Distance Screening Step 1表4 路網(wǎng)距離篩選步驟1

所以滿足式(7)～(9)的司機集合D4為{d1,d3,d6,d7}.

接著計算司機集合D4中所有司機目的地位置分別與乘客r1目的地位置Dest(r)之間的Return(d,r)距離，并檢驗是否滿足式(10)(11)的乘客拼車費用和司機到達時間約束，各司機的計算結果如表5所示.

同時滿足式(10)(11)的司機集合D為{d1,d3}，所以經(jīng)過路網(wǎng)距離篩選之后獲得的司機集合D5={d1,d3}，即D5為所有滿足乘客r1拼車要求的司機集合.然后將乘客r1的匹配結果填寫入繞路距離記錄表Detour Distance Table中.

Table 5 Road Network Distance Screening Step 2表5 路網(wǎng)距離篩選步驟2

對每一名乘客都按照以上的步驟進行一次歐氏距離篩選和路網(wǎng)距離篩選，為其找出對應的符合拼車要求的所有司機集合，并將結果填入繞路距離記錄表中.最后補全整張繞路距離記錄表的內(nèi)容.

2.2 多乘客與多司機最優(yōu)組合匹配

在為每一名乘客找出對應的符合拼車要求的司機集合之后，為了達到所有司機拼車繞路距離最小的目標，Uroad會盡可能為每一名乘客在其司機集合中選派一名司機組成拼車匹配組合，使得所有司機最后產(chǎn)生的繞路距離最少.

但是在實際情況中，每一名乘客對應符合要求的司機會有m名，那么n名乘客與司機的匹配組合方案就會有m×n種情況.同時，每一名司機對應能夠提供服務的乘客也有數(shù)十名，這會使得乘客之間出現(xiàn)爭奪司機資源的情況.而當乘客和司機數(shù)量達到數(shù)百甚至數(shù)萬名時，要將每一名乘客與其中一名司機匹配起來的組合方案就會有數(shù)萬種.要在這數(shù)萬種可能情況中找出一種所有司機繞路距離最少的匹配組合方案，就非常具有挑戰(zhàn)性.

像這類從多種具有可能性的組合中挑選出一種最優(yōu)的組合方案的問題，稱為“組合優(yōu)化”問題或者是“指派問題”.針對這類問題，Kuhn[5]提出了一種經(jīng)典的解決方案——KM算法，可以獲得組合優(yōu)化中的最優(yōu)匹配方案.之后經(jīng)過Edmonds等人[6]不斷的研究，將KM算法針對n×n矩陣的運行時間復雜度簡化到O(n3)，使得算法的性能得到大幅度的提升.其中，n代表匹配組合矩陣的大小.

但是在面對大規(guī)模乘客與司機的拼車匹配場景中，同一時間需要進行優(yōu)化組合的乘客和司機數(shù)量將達到數(shù)千甚至數(shù)萬名.即使是時間復雜度為O(n3)的KM算法，也需要消耗大量的時間進行計算，所以直接簡單地運用KM算法并不適合.

針對上述問題，我們提出一種基于KM算法的改進方案，稱之為拆分矩陣算法(split matrix algorithm， SM).通過將完整的KM矩陣拆分成多個子矩陣，再對子矩陣進行KM算法操作獲取最優(yōu)匹配組合方案.這一方法通過縮小矩陣規(guī)模來達到加快速度的目的.

在拼車場景中符合每名乘客拼車要求的司機只有少數(shù)，所以整個繞路距離記錄表會十分稀疏.如表6所示，我們可以直觀地看到，乘客r1,r2,r3只能夠與司機d1，d2，d3進行拼車匹配組合，而乘客r4,r5只能夠與司機d4，d5進行拼車匹配組合.根據(jù)KM優(yōu)化算法，我們將繞路距離記錄表拆分成如表7、表8中的2個繞路距離子矩陣，即將所有相互有匹配關聯(lián)可能的乘客和司機拆分到同一個繞路距離子矩陣中.拆分之后再采用KM算法來計算獲得乘客與司機的拼車匹配組合結果.在這一例子中，復雜度從表6的O(53)降低到了表7、表8中的O(33)+O(23).通過上述方式，算法的復雜度大為降低.

Table 6 Detour Distance Diagram表6 繞路距離記錄表

Table 7 Detour Sub-Matrix1 Diagram表7 繞路距離子矩陣1

Table 8 Detour Sub-Matrix2 Diagram表8 繞路距離子矩陣2

在SM算法中的輸入是乘客與司機的繞路距離記錄表Detour Distance Table，輸出是一組由繞路距離子矩陣Detour Sub-Matrix構成的矩陣列表List.SM算法具體實現(xiàn)如算法4所示：

算法4. 拆分矩陣.

輸入:繞路距離表；

輸出:矩陣列表.

① FOR every riderrin Recording Table DO

② Getrandr’s candidate driversD;

③ IFrhas been checked

④ CONTINUE;

⑤ ELSE

⑦ Create a new MatrixM;

⑧ Addrand all drivers inDintoM;

⑨ FOR every driverdinMDO

⑩ Getdandd’s candidate ridersR;

按照從上到下的順序遍歷繞路距離記錄表Detour Distance Table中的每一個乘客r，有3種操作情況：

1) 若乘客r已經(jīng)被檢查過，將直接檢查Detour Distance Table中的下一個乘客.

2) 若乘客r還未被檢查過，則將新建一個Detour Sub-Matrix，并將r和r關聯(lián)的司機集合D5加入到子矩陣中，并遍歷集合D5中的每個司機d.

3) 找出d能夠服務的所有乘客集合R(即Detour Distance Table中d所在列中繞路距離值不為∞的乘客).對于R中的每個乘客r′，則乘客r′可能有2種情況：

① 如果r′已經(jīng)在Detour Sub-Matrix中，將直接檢查R中的下一個乘客，直到所有乘客都檢查完畢.

i) 若d′已經(jīng)在Detour Sub-Matrix中，將對應的Detour(d′,r′)填入Detour Sub-Matrix后檢查D′中的下一個司機，直到所有司機都檢查完畢.

ii) 若d′不在Detour Sub-Matrix中，將d′加入到Detour Sub-Matrix中，并跳轉(zhuǎn)到步驟3).

將Detour Sub-Matrix存入到List中，并跳轉(zhuǎn)到步驟1).

定理1. 通過算法4獲得的匹配組合方案與單純KM算法獲得的匹配組合方案相同.

證明. 假設2種方案獲得的匹配組合方案不同，即至少存在1名乘客匹配后的繞路不同.有3種情況：

1) 只有1名乘客匹配后的繞路不同，即2種方案僅有1名乘客匹配了不同的司機導致繞路距離不同.但是由于2種方案都是通過KM算法來選擇繞路距離最小的司機，不可能存在有2個最小繞路距離值的情況，所以假設不成立.

2) 有多名乘客互相交換了司機，導致2種方案總繞路距離不同，但是這些乘客匹配的司機集合是不變的.相同的乘客集合與相同的司機集合通過KM算法僅有一種最小繞路距離的方案，不可能出現(xiàn)2種最小值，所以假設不成立.

3) 情況1)和情況2)的結合，同樣原理，假設不成立.

綜上，假設不成立，即過SM+KM算法獲得的匹配組合方案與單純KM算法獲得的匹配組合方案相同.

證畢.

例4. 以表6中的Detour Distance Table為例，對其進行SM算法的過程為:

1) 遍歷Detour Distance Table中的第1名乘客r1.因為r1還沒有被檢查過，所以建立一個新的Detour Sub-Matrix1，將乘客r1以及其對應的關聯(lián)司機集合D5={d1,d2,d3}加入到Detour Sub-Matrix1中.此時矩陣Detour Sub-Matrix1如表9所示：

Table 9 Detour Sub-Matrix1 Diagram表9 繞路距離子矩陣1

2) 遍歷D5中的第1個司機d1，找到其能夠服務的所有乘客集合R={r1,r2,r3}，并檢驗R中的第1名乘客r1.因為r1已經(jīng)檢查過了，所以直接跳過r1檢查r2.

Table 10 Detour Sub-Matrix1 Diagram表10 繞路距離子矩陣1

Table 11 Detour Sub-Matrix1 Diagram表11 繞路距離子矩陣1

遍歷完成司機集合D5中的第1個司機d1之后，接著遍歷司機d2，找到其能夠服務的所有乘客集合R′={r1,r2,r3}.順序檢查乘客r1,r2,r3，發(fā)現(xiàn)都已經(jīng)檢查過.

4) 遍歷司機d3，找到其能夠服務的所有乘客集合R″={r1,r2,r3}.順序檢查乘客r1,r2,r3，發(fā)現(xiàn)也都已經(jīng)檢查過.最后將構成的Detour Sub-Matrix1加入List.

5) 在檢查Detour Distance Table中的第2，3名乘客r2,r3，發(fā)現(xiàn)已經(jīng)檢查過了.直接跳過檢查后一名乘客r4，發(fā)現(xiàn)還沒有被檢查過，所以建立一個新的Detour Sub-Matrix2，將乘客r4以及其對應的關聯(lián)司機集合D5={d4,d5}加入到Detour Sub-Matrix2中.此時矩陣Detour Sub-Matrix2如表12所示：

Table 12 Detour Sub-Matrix2 diagram表12 繞路距離子矩陣2

6) 遍歷D5中的第1個司機d4，找到其能夠服務的所有乘客集合R={r4,r5}，并檢驗R中的第1名乘客r4.因為r4已經(jīng)檢查過了，所以直接跳過r4檢查r5.

Table 13 Detour Sub-Matrix2 diagram表13 繞路距離子矩陣2

遍歷完成司機集合D5中的第1個司機d4之后，接著遍歷司機d3，找到其能夠服務的所有乘客集合R″={r4,r5}.順序檢查乘客r4,r5，發(fā)現(xiàn)也都已經(jīng)檢查過.最后將構成的Detour Sub-Matrix2加入Matrix List.

7) 檢查Detour Distance Table中的最后乘客r5，發(fā)現(xiàn)已經(jīng)檢查過了，結束完成整個SM算法.

3 實驗與分析

本節(jié)將通過2部分實驗來檢驗分析Uroad的拼車匹配算法的性能.1)與多個基準算法進行比較，分析Find Drivers算法(算法1～4)在各個階段中的性能;2)分析在KM算法處理之前采用SM算法優(yōu)化處理的性能比較.

實驗用到的路網(wǎng)數(shù)據(jù)來自于洛杉磯市(City of Los Angeles)路網(wǎng)[7]：總共包含193 948個節(jié)點和530 977條邊.實驗中用到的司機與乘客數(shù)據(jù)是采用Brinkhoff生成器[8]在洛杉磯市路網(wǎng)上生成的，總共產(chǎn)生了1 000個乘客的請求和100 000名司機.這里不使用出租車軌跡數(shù)據(jù)的主要原因是出租車司機是沒有出發(fā)位置和目的地位置設定的，并不適用于我們研究的問題，所以采用的是模擬數(shù)據(jù).

所有實驗中都假設路網(wǎng)的平均速度為60 km/h，拼車費率為1 yuan/km.實驗中，模擬拼車匹配計算的時間為7:00，司機的出發(fā)時間為7:00—9:00之間的一個隨機時間，乘客的出發(fā)時間段為7:00—9:00之間的一個隨機時間段.實驗中用到的網(wǎng)格索引結構，其每個網(wǎng)格的邊長為經(jīng)度(或緯度)0.01°所對應的路網(wǎng)距離，即邊長約為1km.實驗中計算實際路網(wǎng)距離是基于Dijkstra算法[9]實現(xiàn)的.

所有實驗均在Dell工作站中完成，處理器為Intel?Xeon?CPU E3-1220 v3@3.10 GHz，內(nèi)存為4 GB，系統(tǒng)為Windows 10專業(yè)版.

3.1 單乘客對多司機匹配環(huán)節(jié)

實驗對比了3個算法的性能和特點，除了Uroad中包含的本文提出的方法(DTP+EP+SP)外，另有2種基準算法與其比較，以便于查看分析每一個計算步驟的性能：

1) SP(最短路徑距離篩選).對所有司機直接進行Dijkstra算法，計算司機與乘客出發(fā)位置之間的距離和目的地位置之間的距離，并通過拼車約束條件篩選出符合要求的司機集合.

2) DTP+SP(出發(fā)時間篩選+最短路徑距離篩選).先對所有乘客和司機進行出發(fā)時間篩選，縮小乘客的候選司機集合；然后進行最短路徑計算，并通過拼車約束條件篩選出符合要求的司機集合.

3) DTP+EP+SP(出發(fā)時間篩選+歐氏距離篩選+最短路徑距離篩選).即本文提出的方法.

3.1.1 整體性能比較

本節(jié)通過改變匹配司機規(guī)模數(shù)量、乘客拼車費用、司機到達時間等，考察比較3種算法的總體計算時間.

1) 匹配司機規(guī)模數(shù)量對性能的影響

如圖4所示，固定乘客數(shù)量1 000人，乘客拼車費用為1.2×RiderTrip(r)即乘客RiderTrip對應費用的1.2yuan/km，司機的到達時間為DepartureTime(d)+1.3×DriverTrip(d)，即其出發(fā)時間加上DriverTrip對應時間的1.3倍.設置司機數(shù)量N=20 000～100 000人.圖4中橫坐標為司機數(shù)量，縱坐標為所有乘客總體的匹配時間.

Fig. 4 Different driver’s quantity圖4 不同司機數(shù)量

從圖4可見，DTP+EP+SP是3個算法中效率最高的算法.在相同數(shù)量的司機規(guī)模下，DTP+EP+SP表現(xiàn)最為有益.同時，隨著司機數(shù)量的增加，DTP+EP+SP增加的時間也更少，增加的時間比例最低.這是因為，DTP+EP+SP在計算最短路徑之前，從出發(fā)時間和歐氏距離2個方向?qū)λ緳C進行了篩選，使得參與最短路徑計算的司機數(shù)量大幅減少，從而提高了效率.同時，當司機數(shù)量大于8萬時，DTP+SP算法時間的增加速率有明顯的提升趨勢.這也說明，當司機數(shù)量過大時，DTP階段的優(yōu)化也會出現(xiàn)一定的瓶頸階段.

2) 乘客拼車費用和司機到達時間對性能的影響

如圖5所示，固定乘客數(shù)量為1 000人，匹配司機的規(guī)模數(shù)量為100 000人，司機的到達時間為DepartureTime(d)+1.5×DriverTrip(d).設置乘客拼車費用約束為P=1.1×RiderTrip(r)～1.5×RiderTrip(r).圖5中橫坐標為乘客拼車費用約束，縱坐標為所有乘客總體的匹配時間.

Fig. 5 Different passengers carpooling costs constraints圖5 不同乘客拼車費用約束

如圖6所示，固定乘客數(shù)量為1 000人，匹配司機的規(guī)模數(shù)量為100 000人，乘客拼車費用為1.2×RiderTrip(r).設置司機到達時間約束為T=DepartureTime(d)+1.1×DriverTrip(d)～DepartureTime(d)+1.5×DriverTrip(d).圖6中橫坐標為司機到達時間約束，縱坐標為所有乘客總體的匹配時間.

Fig. 6 Different driver arrival time constraints圖6 不同司機達到時間約束

可以看到圖5和圖6差別不大.隨著乘客費用的增加或者司機到達時間的增加，DTP+SP和SP幾乎沒有明顯的時間變化，這是因為2個算法在最短路徑之前的篩選過程中沒有運用到乘客費用和司機到達時間這2個約束條件，導致每次SP階段的司機數(shù)量沒有明顯的差異.而DTP+EP+SP隨著乘客費用約束的增加和司機到達時間的增加而略有上升.這是由于約束條件的放寬，使得在歐氏距離篩選過程中排除的司機數(shù)量略有減少，在最短路徑計算階段的計算量略有上升.

3.1.2 各階段性能分析

本節(jié)主要分析DTP+EP+SP在各個階段的性能表現(xiàn)，包括各個階段耗時和占總時間的比例.DTP+EP+SP的3個階段分別為：1)DTP，出發(fā)時間篩選；2)EP，歐氏距離篩選；3)SP，路網(wǎng)距離篩選.

實驗中，固定乘客數(shù)量1 000人，乘客拼車費用為1.2×RiderTrip(r)即乘客RiderTrip對應費用的1.2 yuan/km，司機的到達時間為DepartureTime(d)+ 1.3×DriverTrip(d)，即其出發(fā)時間加上DriverTrip對應時間的1.3倍.設置司機數(shù)量N=20 000～100 000人.圖7中橫坐標為司機數(shù)量，縱坐標為所有乘客總體的匹配時間.圖8中橫坐標為司機數(shù)量，縱坐標為各個階段運行時間所占整體的比例.圖9中橫坐標為司機數(shù)量，縱坐標為各個階段刪除司機數(shù)量所占整體的比例.

Fig. 7 Time consuming in each step圖7 各階段運行時間

Fig. 8 Ratio of running time in each step圖8 各階段運行時間比例

Fig. 9 Proportion of drivers removed at each stage圖9 各階段排除司機數(shù)量比例

從圖7、圖8中都可以看到，DTP階段無論是用時還是所占比例都是最少的，幾乎可以忽略.但是從圖9中可以看到，雖然用時少，但是篩選排除的司機數(shù)量占整體35%左右，DTP的篩選效果還是十分明顯的.

從圖7、圖8中都可以看到，EP階段消耗的時間和所占比例相對較少，主要是因為在EP階段中沒有最短路徑距離計算，只進行了歐氏距離計算，計算代價比較小，所以用時相對而言比較少.但是隨著司機數(shù)量的增長，EP階段用時比例逐步上升.這是因為在EP階段刪除了大量的不可匹配的司機，即使司機數(shù)量增加了，通過EP階段篩選的司機并沒有明顯的增加，所以EP階段耗時比例會有所上升.從圖9也可以明顯看出，在篩選司機數(shù)量過程中，EP階段負責了大部分司機的篩選.

從圖7、圖8中都可以看到，SP階段是耗時最多的，占了絕大多數(shù)的運行時間比例.但是從圖9中可以看出，實際進入SP階段的司機數(shù)量其實只有少數(shù),這直接說明了最短路徑計算十分耗時.這也是我們在最短路徑計算之前設計各種剪枝技術，以減少最短路徑計算量的原因.

同時我們針對小規(guī)模數(shù)據(jù)量對于本文算法的性能測試.從圖10可以看出，在規(guī)模較小的情況下，固定司機人數(shù)之后，算法的整體運行時間隨著乘客人數(shù)的增加有明顯的增長.這表明算法的耗時主要與最短路徑距離篩選相關.從圖11可以看出，在較小規(guī)模的情況下，算法的整體運行時間隨著司機數(shù)量的增加而緩慢增加，最終趨于穩(wěn)定.這表明本算法的剪枝技術十分有效.

Fig. 10 The impact of small-scale riders on the running time of each stage圖10 小規(guī)模乘客對各階段運行時間的影響

Fig. 11 The impact of small-scale drivers on the running time of each stage圖11 小規(guī)模司機對各階段運行時間的影響

3.2 SM算法

實驗對比了隨機匹配算法、KM算法、SM+KM算法之間的性能，主要通過改變司機和乘客數(shù)量來考察比較3種算法的運行時間和繞路距離總和.

1) 隨機匹配算法.通過乘客ID順序，為每一名乘客隨機匹配一名符合要求的司機.

2) KM算法.對Detour Distance Table直接采用KM找出最優(yōu)拼車匹配組合.

3) SM+KM算法.先對Detour Distance Table采用SM將其拆分成多個小矩陣，并對小矩陣采用KM，找出最優(yōu)拼車匹配組合.

3.2.1 改變乘客數(shù)量

如圖12所示，固定司機數(shù)量100 000，乘客拼車費用1.2×RiderTrip(r)，司機的到達時DepartureTime(d)+1.3×DriverTrip(d).設置乘客數(shù)量N=100～1 000.

Fig. 12 Impact of the quantity of riders on running time and detour distance圖12 乘客數(shù)量對運行時間和繞路距離的影響

圖12中橫坐標為乘客數(shù)量，圖12(a)縱坐標為運行時間，圖12(b)縱坐標為繞路距離.

根據(jù)圖12(a)可以發(fā)現(xiàn)，在乘客數(shù)量300以內(nèi)，KM與其他2種算法時間相差不大；而在乘客300以上(即Detour Distance Table中乘客數(shù)量增加)時，KM的運行時間出現(xiàn)指數(shù)型增長.而SM+KM和隨機匹配的運行時間始終平穩(wěn)變化不大,并且在實際數(shù)據(jù)上，SM+KM和隨機匹配的運行時間都在1 s以內(nèi).

圖12(b)可以發(fā)現(xiàn)，KM和SM+KM兩種算法的繞路距離是一樣的，這也驗證了定理1的正確性.同時，隨機匹配算法的繞路距離則始終都比其他2種算法要高出很多.KM和SM+KM兩者的繞路距離總和基本保持在隨機匹配算法的40%.這說明加入全局優(yōu)化策略之后，SM+KM算法能夠在保證時間不增加的情況下，使得所有司機的總體繞路距離減少60%左右，這也體現(xiàn)了本文全局優(yōu)化策略的有效性.

綜上所述，在司機數(shù)量相同、改變乘客數(shù)量的情況下，SM+KM算法在運行時間和繞路距離中的總體表現(xiàn)均優(yōu)于其他2種算法.

3.2.2 改變司機數(shù)量

如圖13，固定乘客數(shù)量1 000，乘客拼車費用1.2×RiderTrip(r)，司機的到達時間departureTime(d)+1.3×DriverTrip(d).設置司機數(shù)量N=10 000～100 000.圖13(a)(b)中橫坐標為司機數(shù)量，圖13(a)縱坐標為運行時間，圖13(b)縱坐標為繞路距離.

Fig. 13 Impact of the quantity of drivers on running time and detour distance圖13 司機數(shù)量對運行時間和繞路距離的影響

根據(jù)圖13(a)可以發(fā)現(xiàn)，無論司機的數(shù)量如何增長(即Detour Distance Table中司機數(shù)量增加)，SM+KM和隨機匹配始終能表現(xiàn)優(yōu)異，計算10 000名司機與計算100 000名司機的運行時間相差不大，均在1 s以內(nèi)，但是KM則相差十分巨大.結合圖12(a)可以發(fā)現(xiàn)，KM對司機和乘客規(guī)模的改變都十分敏感，無論是增加司機數(shù)量還是增加乘客數(shù)量，都會使得KM的計算時間顯著增加.這是因為KM本身較高的時間復雜度所決定的.這里體現(xiàn)了SM+KM的一個特點：無論Detour Distance Table中司機和乘客的數(shù)量有多少，通過SM分解矩陣之后，能夠使得進入KM中的子矩陣控制在小規(guī)模內(nèi)(乘客與司機數(shù)量約300以內(nèi))，以此降低了整體算法的運行時間.

根據(jù)圖13(b)可以發(fā)現(xiàn)，KM和SM+KM的繞路距離是在同樣條件下隨機匹配繞路距離的50%～65%之間.同時，隨著司機數(shù)量的增加，KM和SM+KM的繞路距離會隨之有略微的減少.這是因為隨著司機數(shù)量的增加，乘客可以匹配的司機數(shù)量增加，乘客對應的最優(yōu)司機的繞路距離也降低了，所以整體的繞路距離會減少.但是隨機匹配的繞路距離沒有明顯的趨勢變化，基本維持在3 300左右.這是因為雖然每一名乘客的候選司機數(shù)量增加了，但是由于隨機匹配是隨機分配司機的策略，所以在總體繞路距離中并不會有明顯的趨勢變化.

綜上所述，在乘客數(shù)量相同、改變司機數(shù)量的情況下，SM+KM算法在運行時間和繞路距離的總體變現(xiàn)均優(yōu)于其他2種算法.并且無論Detour Distance Table中司機和乘客的數(shù)量有多少，SM+KM的運行時間都控制在1 s以內(nèi).

4 相關工作

與本文有關的現(xiàn)有工作主要分為3部分：1)拼車匹配方法;2)全局優(yōu)化;3)拼車計費模型.本文的相關工作也將從這3方面展開.

拼車匹配方式主要分為4類[10]，其中一名司機接送一名乘客和一名司機接送多名乘客為主這兩類方式為大家所接受.

Cao等人[1]提出了一種針對私家車拼車的算法SHAREK.他們的目的是在大量的司機中，為乘客找出符合其拼車要求的一系列滿足Skyline要求的司機.主要是利用歐氏距離設計了一些剪枝和篩選技術來降低最短路徑的計算時間，從而提高整體拼車匹配算法的運行效率.Zhang等人[11]提出了一種多用戶路徑規(guī)劃問題，并提出了相應的解決方案.他們的目的是為乘客和司機設計規(guī)劃一條共同行駛的路徑，使他們從各自出發(fā)位置出發(fā)在某一點匯合之后共同行駛一段距離，再前往到達各自目的地位置.同時，在這一條路徑中，司機和乘客的共同行駛距離能夠達到最長.但是和Uroad相比，這2個算法都沒有考慮到司機出發(fā)時間限制這一因素，同時也沒有從整體出發(fā)考慮全局最優(yōu)化的拼車結果，所以和Uroad相比是不同的，并不能直接用于解決本文問題.

Ota等人[12]主要解決的問題是為乘客匹配一輛出租車，要求這輛出租車在接上新乘客之后產(chǎn)生的繞路最少.他們的解決方案是通過為拼車匹配中2點之間的最短路徑構建索引的方式，來加快拼車匹配過程中最短路徑的查詢速度以提高整體效率.微軟Zheng等人[13]提出了針對出租車拼車設計實現(xiàn)的T-Share系統(tǒng)，為了幫助乘客找到最佳的出租車，以大規(guī)模的出租車軌跡數(shù)據(jù)為依據(jù)來預測出租車司機的未來位置，并以預測結果作為匹配的主要依據(jù).Huang等人[14]提出了一種基于分支界定的動態(tài)樹生成方法來實現(xiàn)拼車過程中的快速匹配.出租車下一步所有可能的匹配方案以樹的分支來表示，并通過各項約束條件來進行分支路徑的篩選.他們將上海市某一天所有出租車的行程構造成對應的路徑樹，并模擬生成新到來的拼車請求，以此來檢驗拼車匹配所需要的完成時間.但是這項工作主要針對的是出租車的拼車場景，實驗中用到的都是已知的出租車歷史軌跡數(shù)據(jù)，和Uroad解決的司機也有出發(fā)位置目的地位置的問題設定具有本質(zhì)上的區(qū)別.

針對全局優(yōu)化，主要的相關工作有：Armant 等人[15]通過實驗對比了MIP模型和CP模型在解決最大化拼車參與人數(shù)問題上的表現(xiàn).實驗結果表明，雖然MIP模型比較復雜，但是在性能上要優(yōu)于CP模型.Alonsomora等人[16]提出了一種量化拼車中乘客等待時間、拼車延遲時間等參數(shù)的數(shù)學模型.并通過貪心算法來分配拼車資源，使得最后得到的分配方案能夠達到最優(yōu)的效果，以此來獲得最優(yōu)解.Maciejewski等人[17]提出了一種啟發(fā)式出租車分配方案，為的是能夠在減少乘客的平均等車時間的同時，提高出租車的載客率.實驗結果表明在模擬器中，他們的分配方法比傳統(tǒng)的“為乘客就近分配出租車”的方案表現(xiàn)更好.雖然這3項工作都是以全局優(yōu)化為目標，但是他們的優(yōu)化目標分別是最大化拼車參與人數(shù)、優(yōu)化拼車等待和延遲時間、提高出租車的載客率，和Uroad追求的最小化所有司機繞路距離并不相同.

在拼車計費模型方面，Gopalakrishnan等人[18]提出了一種主要用于多人拼車的計費模型.他們在論文中指出，由于是多名乘客共同拼車，所以新加入拼車行列的乘客勢必會對車上已有乘客造成一定影響.所以，新加入的乘客應該對車上已有乘客給予一定的費用作為對其造成行程延遲的補償.Ma等人[19]針對多人共乘出租車的拼車模式提出了相應的計費模型.在他們的計費模型中，乘客的車費主要是根據(jù)其加入拼車行列中之后，對司機原有行程產(chǎn)生的繞路距離來決定的.針對車上已有乘客，根據(jù)與新乘客共乘的時間，將新乘客的一部分車費作為補償支付給車上已有乘客.和Uroad不同的是，他們主要針對的是多人拼車場景提出的計費模型，而Uroad主要針對的是一名司機接送一名乘客的拼車場景，所以這些拼車計費模型并不適用.

5 總結與展望

本文提出了一種高效的大規(guī)模順風車拼車匹配算法Uroad.司機可在拼車之前表明自己的出發(fā)時間和最晚到達時間.乘客也可在拼車請求中注明自身的出發(fā)時間段和愿意支付的最大拼車費用.除了乘客本身的行程之外，Uroad在計費模型中將乘客造成的繞路距離也考慮在內(nèi)，使得拼車計費模型更加合理.Uroad通過出發(fā)時間篩選、歐氏距離篩選和路網(wǎng)距離篩選3部分操作，為每一名乘客匹配1名符合雙方拼車要求的司機，使得最后所有司機產(chǎn)生的繞路距離最小.實驗結果顯示，在大規(guī)模情況下，平均只需要不到2 min，Uroad就能為1 000名乘客在100 000名司機中找出最優(yōu)的拼車匹配組合方案，比直接計算最短路徑縮短了40%的時間.在小規(guī)模情況下，平均只需要不到3.5 s，就能完成50名乘客在5 000名司機中找到最優(yōu)拼車匹配方案，說明本文算法在不同場景中均有優(yōu)異的性能.

雖然本文提出了高效的多對多拼車算法，但是在算法的公平性方面在未來還需要進行進一步的研究，主要包括2方面：

1) 本文所提算法是從所有司機繞路距離總和最小的全局最優(yōu)目標從發(fā)，并不能保證每一位乘客所承擔費用最小的局部最優(yōu)結果，僅僅是對產(chǎn)生的拼車費用滿足乘客拼車約束，所以未來可能需要進入競價機制等方案，優(yōu)化拼車定價模型；

2) 雖然本文算法能保證匹配結果中司機和乘客的繞路距離最短，但并未對路徑進行具體規(guī)劃，這可能導致多個拼車服務中同時包含同一段路徑，從而引起該路段發(fā)生擁堵現(xiàn)象，進而影響到實際的拼車耗時.因此在未來的工作中，我們也需要結合路徑的具體規(guī)劃和道路資源競爭情況對算法進行優(yōu)化.