Uroad:一種高效的大規(guī)模多對多拼車匹配算法

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

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310023)

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

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

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

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

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

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

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

1 預(yù)備知識

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

1.1 乘客和司機(jī)

1.1.1 乘客

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

1.1.2 司機(jī)

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

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

1.2 計(jì)費(fèi)模型

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

1.3 問題定義

在拼車計(jì)費(fèi)模型的基礎(chǔ)上，我們對研究的拼車問題做出了如下定義：

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

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ù)拼車時道路上的實(shí)時平均車速來轉(zhuǎn)換成對應(yīng)的行駛時間.所以這里指代的是其對應(yīng)的行駛時間，是對應(yīng)的最短路徑距離的某一個倍數(shù)值，這個倍數(shù)是可以根據(jù)計(jì)算時的具體情況調(diào)整：

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

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

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

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

5) 表示所有司機(jī)因?yàn)槠窜嚠a(chǎn)生的繞路距離最小.

1.4 數(shù)據(jù)結(jié)構(gòu)

1.4.1 司機(jī)信息列表(driver table)

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

1)ID為一名司機(jī)的唯一標(biāo)識；

2)Origin為司機(jī)當(dāng)前的出發(fā)位置，通常可以通過手機(jī)等移動設(shè)備獲?。?/p>

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

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

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

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

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

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

1.4.3 時間索引(time index)

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

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

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

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

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

2 Uroad查詢過程

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

2.1 單乘客對多司機(jī)匹配

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

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

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

因?yàn)槌丝秃退緳C(jī)都有各自的特定出發(fā)時間，所以如果司機(jī)能夠?yàn)槌丝吞峁┢窜嚪?wù)，那么司機(jī)的出發(fā)時間DepartureTime(d)必定要早于乘客的最晚出發(fā)時間departureTimeMax(r)，才有可能滿足乘客的出發(fā)時間要求.

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

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

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

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

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

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

①DS=null;*司機(jī)集合*

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

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

④Start=0;*在dtArray中標(biāo)記第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ā)時間最早的乘客集合和對應(yīng)的時刻記為rTime(行⑥).

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

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

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

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

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

2.1.2 基于歐氏距離篩選

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

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

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

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

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

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

輸入:司機(jī)集合D1、1名乘客r、當(dāng)前時刻N(yùn)ow；

輸出:司機(jī)集合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中司機(jī)的出發(fā)位置，為他們建立網(wǎng)格索引g(行①).計(jì)算從當(dāng)前時刻N(yùn)ow起到乘客r最晚出發(fā)時間departureTimeMax(r)的時長，即departureTimeMax(r)-Now，記為riderTimeMax(行②).根據(jù)目前道路平均時速Speed和rider-TimeMax相乘計(jì)算獲得能夠滿足乘客出發(fā)時間要求的最遠(yuǎn)距離dmax(行③).

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

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

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

(4)

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

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

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

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

(5)

同時是否滿足司機(jī)自身的到達(dá)時間約束，即是否滿足：

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

輸入:司機(jī)集合D3、1個乘客r；

輸出:司機(jī)集合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) 計(jì)算乘客r與D3中所有司機(jī)的Pickup(d,r)距離，并檢驗(yàn)是否滿足時間約束，即：

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

(7)

2) 利用路網(wǎng)距離Pickup(d,r)和歐氏距離EuclideanReturn判斷司機(jī)是否符合式(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ī)，這里利用司機(jī)的到達(dá)時間約束和乘客的費(fèi)用約束，通過半歐氏的方法刪除一部分不符合要求的司機(jī).將經(jīng)過這一步篩選之后得到的司機(jī)集合記為D4，該集合中的所有司機(jī)都滿足乘客的拼車時間要求.但是由于用到了EuclideanReturn，所以并不是所有司機(jī)在乘客的費(fèi)用約束和司機(jī)的到達(dá)時間約束上都滿足要求，還需進(jìn)一步的篩選.

3) 計(jì)算司機(jī)集合D4中所有司機(jī)與乘客r的Return距離，并判斷是否符合乘客r的費(fèi)用約束和司機(jī)的到達(dá)時間約束，即是否滿足式(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)的司機(jī)組成集合D5，則該集合就是所求的所有滿足乘客r的拼車條件的司機(jī)集合.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在SM算法中的輸入是乘客與司機(jī)的繞路距離記錄表Detour Distance Table，輸出是一組由繞路距離子矩陣Detour Sub-Matrix構(gòu)成的矩陣列表List.SM算法具體實(shí)現(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關(guān)聯(lián)的司機(jī)集合D5加入到子矩陣中，并遍歷集合D5中的每個司機(jī)d.

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

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

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

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

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

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

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

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

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

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

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

證畢.

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

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

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

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

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

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

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

4) 遍歷司機(jī)d3，找到其能夠服務(wù)的所有乘客集合R″={r1,r2,r3}.順序檢查乘客r1,r2,r3，發(fā)現(xiàn)也都已經(jīng)檢查過.最后將構(gòu)成的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以及其對應(yīng)的關(guān)聯(lián)司機(jī)集合D5={d4,d5}加入到Detour Sub-Matrix2中.此時矩陣Detour Sub-Matrix2如表12所示：

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

3.1.1 整體性能比較

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

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

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

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

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

2) 乘客拼車費(fèi)用和司機(jī)到達(dá)時間對性能的影響

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

Fig. 5 Different passengers carpooling costs constraints圖5 不同乘客拼車費(fèi)用約束

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

Fig. 6 Different driver arrival time constraints圖6 不同司機(jī)達(dá)到時間約束

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

3.1.2 各階段性能分析

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

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

Fig. 7 Time consuming in each step圖7 各階段運(yùn)行時間

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

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

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

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

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

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

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

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

3.2 SM算法

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

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

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

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

3.2.1 改變乘客數(shù)量

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

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

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

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

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

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

3.2.2 改變司機(jī)數(shù)量

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

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

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

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

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

4 相關(guān)工作

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

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

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

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

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

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

5 總結(jié)與展望

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

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

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

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