基于概率路由的出租車共乘調(diào)度算法

蔡文廣 劉佳旭 張小欣

收稿日期：2023-06-02；修回日期：2023-08-01? 基金項(xiàng)目：遼寧省教育廳青年項(xiàng)目（LJ2019QL022）

作者簡介：蔡文廣（1998—），男，遼寧阜新人，碩士研究生，CCF會員，主要研究方向?yàn)闀r空數(shù)據(jù)管理、數(shù)據(jù)挖掘；劉佳旭（1979—），男（通信作者），遼寧葫蘆島人，講師，碩導(dǎo)，博士，主要研究方向?yàn)闀r空數(shù)據(jù)管理、群體智能、城市計算、數(shù)據(jù)挖掘等（liujiaxu@buaa.edu.cn）；張小欣（1998—），女，遼寧營口人，碩士研究生，主要研究方向?yàn)闀r空數(shù)據(jù)管理、數(shù)據(jù)挖掘.

摘? 要：針對現(xiàn)有的拼車方案大多服務(wù)在線乘客請求，而忽略了離線乘客請求，導(dǎo)致出租車資源無法得到充分利用這一問題，提出了一種基于挖掘歷史出行軌跡數(shù)據(jù)的概率路由拼車優(yōu)化算法。該算法根據(jù)乘客請求的歷史時空數(shù)據(jù)計算出區(qū)域概率轉(zhuǎn)移矩陣，并使用該矩陣優(yōu)化平臺為出租車推薦拼車路徑，提供了歷史數(shù)據(jù)和拼車問題相融合的一種解決方案，可以有效提高出租車的載客量。在保障離線乘客接載率、在線乘客忍耐度的同時，使用松弛時間的度量指標(biāo)，可以在O（n）內(nèi)對整條路徑的乘客忍耐時間進(jìn)行評估預(yù)測，并用迪杰斯特拉算法對繞行區(qū)域進(jìn)行路徑規(guī)劃，讓出租車的繞行距離最短。使用滴滴GAIA真實(shí)數(shù)據(jù)集對算法有效性進(jìn)行驗(yàn)證，結(jié)果顯示，該算法在服務(wù)請求數(shù)量上高于基準(zhǔn)算法12%。

關(guān)鍵詞：共乘；路徑規(guī)劃；K-means聚類；概率路由

中圖分類號：TP391.41??? 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）02-017-0432-06

doi：10.19734/j.issn.1001-3695.2023.06.0248

Algorithm for taxi ride-sharing scheduling based on probabilistic routing

Cai Wenguang，Liu Jiaxu，Zhang Xiaoxin

（College of Software，Liaoning Technical University，Huludao Liaoning 125105，China）

Abstract：Aiming to address the issue that current ridesharing solutions mostly focus on serving online passenger requests and overlook offline ones，leading to underutilization of taxi resources，this paper proposed a probability-based routing ridesharing optimization algorithm that relied on mining historical travel trajectory data.This algorithm calculated a regional probability transition matrix from historical spatiotemporal data of passenger requests and utilized this matrix to optimize the recommended ridesharing routes for taxis.It presented a solution that integrated historical data with the ridesharing problem，effectively increasing the taxis passenger capacity.By ensuring the offline passenger acceptance rate and online passenger tolerance，the algorithm employed a relaxed-time metric to predict and evaluate the passenger tolerance time for the entire path in O（n） time，and used the Dijkstra algorithm to plan routes through detour areas，minimizing the detour distance for taxis.This paper validated the effectiveness of the algorithm by using the real-world DiDi GAIA dataset.Experimental results demonstrate that the proposed algorithm outperforms the baseline algorithm by 12% in terms of the number of service requests served.

Key words：ride-sharing；route planning；K-means clustering；probabilistic routing

0? 引言

隨著共享經(jīng)濟(jì)的快速發(fā)展，通過共享閑置社會運(yùn)載資源，為消費(fèi)者提供服務(wù)的拼車平臺已對交通運(yùn)輸產(chǎn)生了深遠(yuǎn)的影響。為了提高出租車的空座利用率，降低乘客的出行成本，滴滴出行等平臺［1，2］提供了共享拼車的服務(wù)。當(dāng)出租車與多名乘客有相似的行程時，共乘平臺允許兩者共享一輛車，這樣可以顯著緩解城市交通擁堵，降低能源消耗，實(shí)現(xiàn)出租車和乘客的雙贏。由于出租車在城市中的便利性和實(shí)用性［3］，共乘成為一種高效的交通出行方式［4，5］。與基于私家車的拼車［6］不同，其乘車請求是靜態(tài)的，可以提前規(guī)劃拼車路線。出租車拼車更復(fù)雜，乘車請求和出租車都是高度動態(tài)的模式。更糟糕的是，有一些乘客不會明確提交他們的請求，而是在路邊呼叫出租車，在城市中沒有固定的路線運(yùn)送乘客，這種拼車方式難度很大。出租車需減少路邊乘客的等待時間，并及時服務(wù)乘車請求，同時還要更新出租車時間表和路線以保證服務(wù)質(zhì)量，導(dǎo)致出租車實(shí)時調(diào)度極具挑戰(zhàn)性。

目前，學(xué)者們已經(jīng)提出了很多共乘問題的算法，成果主要集中在以下優(yōu)化目標(biāo)，例如從駕駛員的角度最小化總行程［7］或最大化共乘系統(tǒng)的服務(wù)率［8］，從平臺的角度最大化平臺收益［9］等。共乘問題是NP-hard問題，需要設(shè)計近似算法為每輛出租車尋找合適的路線。Tong等人［10］優(yōu)化了共乘算法的時間復(fù)雜度，利用動態(tài)規(guī)劃的方法把一條路線上的各個事件點(diǎn)的時間戳在O（n）時間內(nèi)預(yù)計出來。當(dāng)出現(xiàn)一個新的請求，可以在O（1）時間內(nèi)計算出最優(yōu)的插入位置，時間復(fù)雜度從O（n3）降到了O（n）。Zheng等人［11］考慮拼車平臺收益問題，用貪心策略把訂單集和車輛集進(jìn)行匹配，選擇最優(yōu)的匹配對，提出一種定價機(jī)制，更好地激勵出租車和乘客參與拼車。Cheng等人［12］優(yōu)化了平臺收益目標(biāo)，提出一種動態(tài)共乘框架，用機(jī)器學(xué)習(xí)模型預(yù)測每個區(qū)域未來的乘車需求，然后用排隊(duì)論把新到來的車輛分配給需要的區(qū)域，并在調(diào)度過程中考慮平臺的最大化整體收益以及對乘客滿意度的影響。Li等人［13］考慮價格和社會關(guān)系對乘客的影響，提出一種新穎的定價方案，設(shè)計一種高效的剪枝算法，為乘客推薦前k個合適的出租車。Luo等人［14］考慮請求數(shù)量遠(yuǎn)大于出租車的數(shù)量，提出一種距離優(yōu)先和貪心策略相融合的匹配方法，從而提高了平臺整體服務(wù)率并實(shí)現(xiàn)了出租車最小繞行距離。Ma等人［15］正式定義了生成時間表的大規(guī)模實(shí)時出租車服務(wù)問題，提出單邊出租車搜索、雙邊出租車搜索算法和過濾無效候選集的時空索引相融合的方法。Na等人［16］根據(jù)出租車和乘客具有相似的路徑，提出一種高效的共享路徑百分比框架，結(jié)合二分圖的匹配篩選出權(quán)重最優(yōu)的匹配結(jié)果。Chen等人［17］在動態(tài)拼車問題中考慮時間和價格的影響，乘客可以從時間的角度選擇時間短的方案，乘客也可以從價格的角度選擇價格低的方案，并使用大量剪枝技術(shù)篩選掉不符合條件的候選集。Ma等人［18］提出一個移動云框架的出租車共享系統(tǒng)，并根據(jù)時間、容量和價格為乘客分配合適的出租車。Huang等人［19］考慮實(shí)時大規(guī)模拼車問題，提出了分支界定算法和整數(shù)規(guī)劃的方法，但是這兩種方法的時間復(fù)雜度相對較高，為此又提出了動態(tài)樹的算法，大大降低了時間復(fù)雜度。Lin等人［20］利用出行需求的數(shù)據(jù)來優(yōu)化拼車路線，把它歸結(jié)為一個滿足乘客出行延時要求和在線作出事先不知道出行情況下的決策優(yōu)化問題，提出一個兩階段動態(tài)規(guī)劃的解決方案。Yuen等人［21］提出最短路徑不是共享出行的最佳路徑的問題，把搜索空間縮小到一個有向無環(huán)圖中，用動態(tài)規(guī)劃的方法來解決，并使匹配乘客的失敗率降低40%，同時還將客戶的等待時間縮短20%。Lowalekar等人［22］認(rèn)為實(shí)時拼車平臺的關(guān)鍵是應(yīng)該把請求分成正確的組，使得系統(tǒng)的服務(wù)請求、收入和延時等目標(biāo)可以被自然優(yōu)化，通過設(shè)計一種區(qū)域路徑的方法，用在線和離線組合的方法來優(yōu)化請求組合，并從長遠(yuǎn)的角度出發(fā)，預(yù)測未來可能出現(xiàn)的乘車請求，在線生成更優(yōu)的請求組合。Liu等人［23］把離線乘客和在線乘客都作為拼車的用戶，從在線乘客的移動方向出發(fā)，能更好地為乘客尋找到更合適的車輛。共乘的眾多優(yōu)點(diǎn)，引起學(xué)術(shù)界和工業(yè)界極大的興趣。

從上述研究中可以看出，現(xiàn)有的共乘問題主要研究在線乘客，而缺少對離線乘客的關(guān)注。根據(jù)一份出租車研究報告［24］，離線乘客占據(jù)了總拼車人數(shù)的13.71%，并且有41.68%的人既喜歡離線拼車又喜歡在線拼車。為了最大化服務(wù)乘客數(shù)量，本文提出了一種基于挖掘歷史軌跡數(shù)據(jù)的概率路由算法，通過出租車日常轉(zhuǎn)移方式對道路網(wǎng)絡(luò)的頂點(diǎn)進(jìn)行聚類，得到的轉(zhuǎn)移概率矩陣可以預(yù)測未來出現(xiàn)的離線乘客。因?yàn)槁窂揭?guī)劃是NP-hard問題，本文將出租車路線中的行程事件分區(qū)，減少整個道路網(wǎng)絡(luò)的搜索空間，可以在多項(xiàng)式時間內(nèi)求解。為了尋找離線乘客，基于歷史訂單數(shù)據(jù)挖掘乘客出行需求的潛在規(guī)律，用條件概率挖掘出一條累積出現(xiàn)離線乘客概率最大的路線。

1? 問題定義

定義1? 道路網(wǎng)絡(luò)。道路網(wǎng)絡(luò)是由圖G=〈V，E〉的多個頂點(diǎn)和多條邊組成的無向圖，每條邊（u，v）∈E，表示從頂點(diǎn)u到頂點(diǎn)v的旅行成本，旅行成本是在旅行中的時間或者距離，其中dis（u，v）是兩個頂點(diǎn)之間最短的旅行成本。

定義2? 請求。請求R分為在線請求和離線請求，在線請求R+=〈or，dr，tr，er，Kr，arr〉，or∈V是請求的起點(diǎn)，dr∈V是請求的終點(diǎn)，tr是請求的發(fā)布時間，er是請求的截止時間，Kr是請求中乘客的數(shù)量。離線乘車請求R-只有在共享出租車偶然遇到時才能獲知，這里使用R-專門表示離線乘車請求。

定義3? 出租車。出租車由t=〈loct，St，Rt〉表示，其中l(wèi)oct表示出租車t的當(dāng)前位置，St和Rt分別是出租車t的行程事件表和共享出行的路線。

定義4? 行程事件。一個出租車的行程事件表St=〈L0，L1，L2，…，Ln〉，它是由出租車的當(dāng)前位置loct和所有請求起點(diǎn)or和目的地dr的序列組成，事件L0是出租車的當(dāng)前位置，后面的每個事件對應(yīng)于在某個位置乘客上車或下車的位置，但是對于同一個請求R來說，它的起點(diǎn)or必須出現(xiàn)在終點(diǎn)dr的前面。

定義5? 出租車的路線。根據(jù)出租車的行程事件表St生成出租車路線Rt，其指St中任意兩個連續(xù)事件的行駛路徑。對于共享同一輛出租車的請求，應(yīng)制定有效的行程事件表，以便沿著計劃的拼車路線依次接送乘客。

定義6? 分區(qū)。給定一個出租車和一個行程事件St，在St中任意兩個連續(xù)事件之間的路線對應(yīng)一個分區(qū)。初始時，如果St有n個事件，那么就形成了n個區(qū)。

定義7? 地標(biāo)。空間簇Cz的地標(biāo)頂點(diǎn)LMz∈Cz，它是由簇Cz內(nèi)頂點(diǎn)的距離屬性和概率屬性組成，選擇Rank（D，P）最大值為地標(biāo)頂點(diǎn)，具體確定地標(biāo)頂點(diǎn)LMz的公式為

Rank（D，P）=α×LMz到Cz內(nèi)所有頂點(diǎn)的距離之和累加Cz內(nèi)所有邊的和+（1-α）×LMz 到簇C 的概率和Cz 內(nèi)頂點(diǎn)的數(shù)量（1）

其中：α是平衡距離和概率的系數(shù)，默認(rèn)值為0.5。為了公平地測量這兩個因素，并將它們保持在相同的范圍內(nèi)，歸一化到［0，1］。

定義8? 最大化服務(wù)請求。給定一組乘車請求，包括在線請求和離線請求，以及道路網(wǎng)絡(luò)上的一組出租車。目標(biāo)是共享出租車在原來行駛的路線基礎(chǔ)上尋找離線請求，使得服務(wù)的乘車請求數(shù)量最大化，而總的繞行成本最小化，同時也要受到以下時空約束：容量約束，出租車載客人數(shù)任何時候都不得超過租車的容量；時間約束，在一條路線中想要接載一個離線請求，必須滿足已在車上的請求，能在最后截止時間er之前送達(dá)。

2? 框架

本文方法的主要架構(gòu)如圖1所示，從出租車狀態(tài)、乘車請求信息和歷史出租車數(shù)據(jù)以及路線圖獲取輸入，動態(tài)安排共享出租車服務(wù)在線和離線乘車請求。在出租車方面，它會不斷上傳自己的狀態(tài)（包括位置、可用座位等）并從服務(wù)器接收和更新自己的路線；在請求方面，乘客可以向服務(wù)器提交乘車請求，或者以離線方式在路邊呼叫共享出租車；通過挖掘歷史出租車數(shù)據(jù)，篩選出隱藏在道路網(wǎng)絡(luò)頂點(diǎn)中的熱門上車位置，對這些頂點(diǎn)中暗含的轉(zhuǎn)移方式進(jìn)行空間聚類。通過聚類算法、行程事件分區(qū)和概率路由算法尋找離線乘客，如果尋找到合適的路線則返回更新的路線，否則返回原有路線。

2.1? 階段1 節(jié)點(diǎn)聚類

節(jié)點(diǎn)聚類的目的是為了預(yù)測離線乘客，讓出租車有機(jī)會遇到離線請求。節(jié)點(diǎn)聚類需要從大量的歷史出租車信息中挖掘出相似的轉(zhuǎn)移方式。具體的地圖分割過程如下：

a）地理聚類。首先利用K-means算法根據(jù)道路網(wǎng)絡(luò)中頂點(diǎn)的地理位置將其分成k個空間簇。初始化階段將所有頂點(diǎn)進(jìn)行聚類，空間簇中的頂點(diǎn)在地理上是接近的。在后面的過程中，按比例對在步驟c）中導(dǎo)出的每個轉(zhuǎn)移簇進(jìn)行聚類。給出大小為n的轉(zhuǎn)移簇，其頂點(diǎn)被分組到nkN+12」空間簇內(nèi)，其中N是V中的頂點(diǎn)總數(shù)。

b）轉(zhuǎn)移概率的計算。基于步驟a）中獲得的k個空間簇，計算每個頂點(diǎn)vi的轉(zhuǎn)移概率。每一項(xiàng)Bi，j（i=1，2，…，N和j=1，2，…，K）是在頂點(diǎn)vi到第j個空間簇內(nèi)的轉(zhuǎn)移概率，這可以利用歷史出租車數(shù)據(jù)來計算。

c）轉(zhuǎn)移聚類。把矢量Bi看作頂點(diǎn)vi的移動特征，并使用K-means聚類算法根據(jù)所有頂點(diǎn)的轉(zhuǎn)移概率矢量，將所有頂點(diǎn)分組為kt個轉(zhuǎn)移簇，其中kt

2.2? 階段2? 路線分區(qū)

路線分區(qū)是為了重新規(guī)劃路徑以遇到離線乘客，基于路線分區(qū)的關(guān)鍵是可以對行程事件進(jìn)行分區(qū)并劃分為n（行程事件的數(shù)量）個不相交的集合，并且獨(dú)立地處理它們的目標(biāo)函數(shù)OBJ（St）。路線分區(qū)基于繞道的概念，繞道表示插入新位置后與原始路徑的行程時間相比增加的行程時間。當(dāng)引入松弛時間，出租車在從一個事件行駛到另一個事件的區(qū)間中，對路線進(jìn)行重新規(guī)劃，讓出租車更有機(jī)會遇到離線乘客，使服務(wù)請求數(shù)量達(dá)到最大化。當(dāng)給定一條行程路線時，可以將其劃分為n個分區(qū)，如圖3所示。

分區(qū)1是出租車當(dāng)前位置到事件L1的行駛區(qū)間，分區(qū)2是事件L1到事件L2的行駛區(qū)間。結(jié)合圖3和松弛時間式（2）可以計算出每個事件的松弛時間，在所有事件的松弛時間集合中選擇最小的松弛時間來約束下一階段檢查截止時間的約束：將slk［i］定義為在事件Li之后滿足截止時間約束的繞行的最大忍耐時間（松弛時間），有

slk［i］=min{slk［i+1］，ddl［i+1］-arr［i+1］}（2）

其中：arr［i］表示出租車到達(dá)事件Li的時間；ddl［i］表示在不違反最后截止時間約束的情況下出租車到達(dá)Li的最晚時間。具體而言，ddl［i］可計算為

ddl［i］=er-dis（or，dr）如果Li是起點(diǎn)

er如果Li是終點(diǎn)（3）

將arr［i］表示為出租車到達(dá)Li的時間，有

arr［i］=arr［i-1］+dis（Li-1，Li）（4）

計算完每個事件的松弛時間，選擇最小的松弛時間規(guī)劃搜索離線乘客范圍的概率路由算法，雖然出現(xiàn)離線乘客的頂點(diǎn)非常多，但是不能無限制地去遍歷，這是非常耗時的。把最小的松弛時間分配到具有最高概率遇到離線乘客的分區(qū)Pmax中，Pmax是由當(dāng)前事件頂點(diǎn)到下一事件頂點(diǎn)簇的轉(zhuǎn)移概率值決定的。當(dāng)松弛時間小于閾值，直接結(jié)束循環(huán)（據(jù)圖4最長邊長在0～500 m的概率占絕大部分，出租車在街區(qū)中繞行500 m大約需要1 min，沒有必要松弛，所以閾值選擇1 min）返回原有的路線。目標(biāo)是要選擇最大的：

OBJ（Rt）=max{分區(qū)i 的概率|i∈（1，n）}（5）

2.3? 階段3? 尋找離線乘客

本階段假設(shè)在不同時間、不同路段之間的離線請求是可以預(yù)測的，路線規(guī)劃通常又是出租車調(diào)度的效率瓶頸。為了設(shè)計出滿足以上兩階段要求的路徑規(guī)劃算法，提出了基于歷史數(shù)據(jù)的預(yù)測結(jié)果進(jìn)行分區(qū)過濾的Dijkstra最短路徑算法，以優(yōu)化概率路由算法。給定一個行程事件表St，通過階段2得到的分區(qū)，對事件（Lz，Lz+1）∈St重新規(guī)劃路線，即減少路線的搜索空間并返回一條在松弛時間約束內(nèi)的可行路徑。假設(shè)出租車在事件（Lz，Lz+1）∈St可能路線被表示為Rt=（Lz，LM1，LM2，…，LMn，Lz+1），其中Lz是分區(qū)z+1的起點(diǎn)，Lz+1是分區(qū)z+1的終點(diǎn)，從事件Lz到Lz+1經(jīng)歷了n個簇，其中LMi分別是簇i的地標(biāo)頂點(diǎn)。

為了在路線分區(qū)階段尋找到適合本次行程的路線，本階段基于分區(qū)過濾和轉(zhuǎn)移概率矩陣的概率路由算法組成，它支持出租車有機(jī)會遇到合適的離線乘客。如果R-是在松弛時間內(nèi)找到乘客，并且滿足時空約束，則認(rèn)為該請求R-被認(rèn)為是合適的。從理論上講，應(yīng)該在可行的松弛時間內(nèi)計算所有分區(qū)的所有頂點(diǎn)上合適請求的概率，并計算一條累積最大概率的路線來搭載離線乘客。然而這在計算上是十分復(fù)雜的，已經(jīng)被證明是NP完全問題［16］，假設(shè)離線乘客的出行需求遵循時間相關(guān)的統(tǒng)計模式。在時間戳t和事件Lz處，存在概率P（Lz|t）的行駛要求，共享服務(wù)以條件概率P（Lz+1，Lz|t）到達(dá)節(jié)點(diǎn)z+1。進(jìn)一步假設(shè)乘客到達(dá)在不同節(jié)點(diǎn)和不同時間戳是獨(dú)立的。因此，該路線的概率可以計算為

P（Rt）∑P（Lz+1，Lz|t）（6）

s.t.→t≤min{slack［1］，…，slack［n］}+dis（Lz，Lz+1）（7）

圖5（a）描述了道網(wǎng)聚類后空間特征的一個示例，共分為四個簇，v1、v3、v6和v8分別是空間簇1、空間簇2、空間簇3和空間簇4的地標(biāo)頂點(diǎn)，每個簇都包含兩個頂點(diǎn)，虛線代表空間簇與空間簇的邊界。圖5（b）描述了圖5（a）中各個頂點(diǎn)在歷史出租車數(shù)據(jù)中的轉(zhuǎn)移概率，其中每個子簇Gu包含一個頂點(diǎn)子集Vu和一個邊集Eu，每個頂點(diǎn)集又包含一組map集合。例如在子圖G1中有兩個頂點(diǎn)v1和v2，v1中的key就是其他簇的索引，value是v1到其他各簇的轉(zhuǎn)移概率，并且使得∑k-1j=1Pij=1，Pij是頂點(diǎn)vi到簇j的轉(zhuǎn)移概率。為了避免大量的計算，在多個分區(qū)中只選擇一個分區(qū)，在這個分區(qū)規(guī)劃出一條高概率遇到離線乘客的路徑，主要步驟如下：

a）概率路由過程。給定一條出租車路線，根據(jù)階段2得到的分區(qū)，選擇用迪杰斯特拉算法遍歷從源行程事件到目標(biāo)行程事件由地標(biāo)頂點(diǎn)映射的簇，在這些簇集內(nèi)再次枚舉從源行程事件到目標(biāo)行程事件的累積轉(zhuǎn)移概率和最大路徑。同時滿足已經(jīng)在出租車上乘客的最后截至日期的約束，它是行程事件（Lz，Lz+1）之間具有最大概率遇到合適離線乘客的路線。如果在此過程中找不到有效的路線，則將返回出租車上原有的路線St。由于概率路由比普通路由的計算時間要長，出租車僅在有足夠的空閑容量且松弛時間充足時才調(diào)用它，否則返回原有路線。盡管在規(guī)劃中遇到離線乘客的路線可能會帶來輕微的延遲，但它可能會為出租車和離線乘客帶來各自的收益。

如算法1，第1行為初始化出租車路線分區(qū)的集合、松弛時間集合和嘗試遍歷尋找離線乘客的次數(shù)。第3～10行表示如果出租車的容量小于0，直接退出循環(huán)，否則對出租車的行程路線進(jìn)行分區(qū)，根據(jù)式（2）計算每個事件的松弛時間，在松弛時間內(nèi)選擇出現(xiàn)離線乘客概率最大的分區(qū)。第11～19行表示在選出的分區(qū)重新對出租車路線進(jìn)行規(guī)劃，利用地標(biāo)頂點(diǎn)篩選出要遍歷的簇，過濾掉不符合條件的簇，再利用每個簇內(nèi)頂點(diǎn)的轉(zhuǎn)移概率值，規(guī)劃一條累積最大概率權(quán)重的路徑，其中最短路徑需要用迪杰斯特拉來尋找。如果找到有效路線，則將返回更新的路線USt，重復(fù)這兩個步驟，如果找不到有效路線或超過了嘗試的次數(shù)，則返回原有的路線St。

算法1? PR-share算法

輸入：A taxi with route St。

輸出：A taxi with updated route USt。

1initialize P=、slack［］、attempt=0

2while（true）{

3? if remaining capacity of taxi < 0

4??? break；

5? else{

6??? for Li∈St do {

7??? Construction partition P=P∪Pi∈（Li，Li+1）

8??? Calculate slack［i］ According to formula 2

9??? }

10? Select P* = max OBJ（Rt）

11? while（true）{

12??? Select the maximum weighted path Rt from Lz to Lz+1 with Landmarks in clusters

13??? Find the shortest path Rt using the Dijkstra algorithm on USt

14??? attempt=attempt+1

15??? if Rt is valid

16??? ??return USt

17??? if attempt>5

18????? return St

19??? }

20? }

21}

b）時間復(fù)雜度。為了服務(wù)請求，需要檢查出租車中的所有行程事件，然后選擇合理繞行成本的路線，概率路由的算法時間復(fù)雜度為O（mNDP/K），其中m是行程事件的個數(shù)，N/K是平均每個簇中頂點(diǎn)的個數(shù)，D是查詢轉(zhuǎn)移概率矩陣的次數(shù)，P是所選擇簇的數(shù)量。因?yàn)槿魏蝺蓚€頂點(diǎn)之間的最短路徑可以預(yù)先計算和緩存，所以最短路徑查詢與以前的研究一樣可以在O（1）時間計算出。

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

3.1? 實(shí)驗(yàn)數(shù)據(jù)

本文使用滴滴GAIA計劃公開發(fā)布的真實(shí)世界數(shù)據(jù)集［25］進(jìn)行實(shí)驗(yàn)評估，該數(shù)據(jù)集包含成都市2016年11月18日上午10：00～11：00的數(shù)據(jù)。實(shí)驗(yàn)中的時間段是非上下班高峰期，大多數(shù)出租車的在線乘車請求不足，有足夠的空余容量，可以啟用概率路由算法。數(shù)據(jù)集中每個元組都由上車的經(jīng)度/緯度、下車的經(jīng)度/緯度和發(fā)布時間組成29 534個出租車請求。使用開源的OpenStreetMap［26］導(dǎo)出成都市的道路網(wǎng)絡(luò)，并將道路網(wǎng)絡(luò)表示為一個由214 440個頂點(diǎn)和466 330條邊組成的無向圖G（V，E）。表1總結(jié)了請求的數(shù)量以及導(dǎo)論網(wǎng)絡(luò)中頂點(diǎn)和邊的數(shù)量。

3.2? 實(shí)驗(yàn)方法

為了模擬一個典型的共享出行應(yīng)用程序，應(yīng)遵循已有工作實(shí)驗(yàn)［27］中的設(shè)置，采用相同的請求集、頂點(diǎn)集和邊集，改變實(shí)驗(yàn)的參數(shù)，例如，使用2k、5k等不同數(shù)量的出租車和其他的默認(rèn)參數(shù)進(jìn)行評估。轉(zhuǎn)移概率是通過某一個頂點(diǎn)附近的若干個歷史訂單數(shù)量來近似計算這一頂點(diǎn)的轉(zhuǎn)移概率，當(dāng)歷史訂單規(guī)模越大，預(yù)測得會更準(zhǔn)確，本文將每個請求的起點(diǎn)和終點(diǎn)預(yù)先映射到道路網(wǎng)絡(luò)中最近的頂點(diǎn)。出租車的初始位置是從道路網(wǎng)絡(luò)頂點(diǎn)中隨機(jī)選擇的，當(dāng)它服務(wù)請求時，會按照計劃的路線行駛到目的地。為了模擬離線乘車請求，隨機(jī)將5 000個在線請求的起點(diǎn)、目的地和發(fā)布時間對出租車不可見，測試出租車能否完成離線請求的任務(wù)。本文采用服務(wù)請求的數(shù)量和響應(yīng)時間指標(biāo)來評估算法的性能，表2列舉了實(shí)驗(yàn)的主要參數(shù)，默認(rèn)參數(shù)值以粗體標(biāo)記，例如：發(fā)布時間為tr的請求的默認(rèn)截止時間為tr+10 min。所有實(shí)驗(yàn)均在Intel Core i7（2.80 GHz）和16 GB RAM的服務(wù)器上進(jìn)行，所有算法均在Ubuntu環(huán)境下使用 C++來實(shí)現(xiàn)。在相同的實(shí)驗(yàn)設(shè)置下，用Python生成10次不同位置的出租車初始數(shù)據(jù)，并報告同一設(shè)置下的平均結(jié)果。

3.3? 實(shí)驗(yàn)結(jié)果與分析

將本文方法與No-Sharing、T-Share［15］、mT-Share［23］、NDP［7］進(jìn)行比較。No-Sharing是用一對一的方式來服務(wù)乘客，將乘車請求分配給搜索范圍γ內(nèi)最近的空出租車。T-Share 是最先進(jìn)的方法之一，使用空間網(wǎng)格對所有出租車和請求進(jìn)行索引跟蹤，從請求起點(diǎn)和請求終點(diǎn)的γ范圍內(nèi)雙邊搜索候選出租車，如果找到有效的候選者，它將立即返回。mT-Share首先在請求的搜索范圍γ內(nèi)選擇候選出租車列表，在出租車列表的基礎(chǔ)上又用出租車向量和請求向量的夾角余弦值判斷是否服務(wù)新請求，向量的起點(diǎn)是出租車（請求）的起點(diǎn)，向量的終點(diǎn)是出租車（請求）的終點(diǎn)。NDP把出租車和請求的匹配問題轉(zhuǎn)換為請求的插入問題，在滿足最小化繞行成本的前提下，結(jié)合動態(tài)規(guī)劃和最大流算法，在一個分區(qū)框架中讓新請求選擇最適合的插入位置。

圖6為改變出租車數(shù)量的影響結(jié)果。所有算法的服務(wù)數(shù)量隨著出租車數(shù)量的增加而增加，在服務(wù)數(shù)量方面，PR-Share優(yōu)于T-Share和No-Sharing，因?yàn)樗鼉?yōu)化了拼車路線，可以返回更多的請求-出租車匹配對，與mT-Share和NDP相比，PR-Share略差一些。例如，在3 000輛出租車的情況下，所服務(wù)的No-Sharing、T-Share、NDP、mT-Share和PR-Share請求數(shù)量分別為6 521、7 841、10 032、10 619和8 934。與 T-Share和No-Sharing算法相比，PR-Share分別多提供了12%和27%的乘車請求，這是由于概率路由可以服務(wù)更多的離線乘客，而其他算法忽略了這一點(diǎn)。

通過改變簇數(shù)κ并保持其他參數(shù)為默認(rèn)值來進(jìn)行實(shí)驗(yàn)，圖7為T-Share、mT-Share、NDP和PR-Share對服務(wù)請求數(shù)量的影響。T-Share、mT-Share和NDP通過改變網(wǎng)格的大小可以近似地和PR-Share中簇的大小在功能上實(shí)現(xiàn)相同的作用，起初增加網(wǎng)格和簇的數(shù)量可以讓服務(wù)請求的數(shù)量增加，然而隨著增加數(shù)量的變多，服務(wù)請求的數(shù)量也開始減少。例如，κ=150，這是因?yàn)樘』蜻^大的κ將導(dǎo)致增加和減少候選簇的集合，進(jìn)而影響算法的性能。以PR-Share為例，當(dāng)κ從100變化到150時，服務(wù)請求的數(shù)量增加了6%，服務(wù)請求的數(shù)量從6 123增加到6 547，然而當(dāng)簇數(shù)增多，總的服務(wù)請求也慢慢變少。

圖8為改變截止時間的結(jié)果，通過改變截止時間，出租車的搜索范圍也會變化，隨著截止時間的增大，算法的服務(wù)數(shù)量都有所增加。原因在于較長的截止時間允許搜索更多的請求，但是較長的截止時間會影響乘客的滿意度。雖然增加了服務(wù)請求的數(shù)量，但是犧牲了乘客的忍耐性，等待時間變長導(dǎo)致增長速度緩慢。在截止時間為10 min，PR-Share比T-Share算法提高了14%。

圖9顯示響應(yīng)時間隨著可用出租車的數(shù)量增加而增加。很明顯，No-Sharing總是可以在1 ms內(nèi)處理請求，因?yàn)樗环?wù)一個請求。PR-Share比mT-Share和T-Share需要更長的時間來響應(yīng)請求，而NDP是最慢的一個。這是因?yàn)樵跊Q策階段，NDP計算每個候選出租車的繞行下界是非常耗時的，一般來說，本文算法在100～280 ms就可以響應(yīng)乘車請求，并且在響應(yīng)時間上優(yōu)于NDP 3～9倍。

圖10顯示在2 000輛出租車、150個簇集、容量為4和截止時間10 min情況下服務(wù)請求數(shù)量的結(jié)果，被服務(wù)請求的總數(shù)量由在線請求的數(shù)量和離線請求的數(shù)量組成。雖然PR-Share服務(wù)請求的總體數(shù)量沒有NDP和mT-Share多，但是在離線請求數(shù)量上分別比mT-Share、NDP和T-Share多17%、29%和33%。

4? 結(jié)束語

為解決現(xiàn)有共乘方案僅對在線乘客服務(wù)而缺少對離線乘客服務(wù)的局限性，針對現(xiàn)有求解離線乘客的方法并不能很好地與預(yù)測方法相匹配的問題，本文提出了一種挖掘歷史出租車數(shù)據(jù)的概率路由算法。a）利用頂點(diǎn)附近的歷史訂單數(shù)據(jù)中潛在轉(zhuǎn)移方式聚類，生成的概率轉(zhuǎn)移矩陣預(yù)測離線請求；b）對出租車路線中的行程事件進(jìn)行分區(qū)，選擇出現(xiàn)離線乘客概率最高的分區(qū)，用概率轉(zhuǎn)移矩陣在該分區(qū)重新規(guī)劃路線。同時使用松弛時間，縮小尋找離線乘客的范圍，提高了算法的靈活適應(yīng)能力。通過在真實(shí)數(shù)據(jù)集上進(jìn)行比較，驗(yàn)證了該方法不僅能有效地匹配離線乘客、增加服務(wù)請求的數(shù)量，還能進(jìn)一步提高平臺和出租車的收益。但是實(shí)驗(yàn)中的個別離線乘客很難被服務(wù)，未來將側(cè)重于對這些離線請求的位置進(jìn)行算法優(yōu)化。

參考文獻(xiàn)：

［1］Didichuxing［EB/OL］.https：//www.didiglobal.com/.

［2］Uberpool［EB/OL］.https：//www.uber.com/.

［3］徐毅，童詠昕，李未.大規(guī)模拼車算法研究進(jìn)展［J］.計算機(jī)研究與發(fā)展，2020，57（1）：32-52.（Xu Yi，Tong Yongxin，Li Wei.Research progress on large-scale carpooling algorithms［J］.Journal of Computer Research and Development，2020，57（1）：32-52.）

［4］Zhang Shanfeng，Ma Qiang，Zhang Yanyong.QA-Share：towards efficient QoS-aware dispatching approach for urban taxi-sharing［C］//Proc of the 12th Annual IEEE International Conference on Sensing，Communication，and Networking.Piscataway，NJ：IEEE Press，2015：533-541.

［5］Zhang Wei，Shemshadi A，Sheng Quan.A user-oriented taxi ride-sharing system with large-scale urban GPS sensor data［J］.IEEE Trans on Big Data，2021，7（2）：327-340.

［6］He Wen，Wang Kai，Li Deyi.Intelligent carpool routing for urban ridesharing by mining GPS trajectories［J］.IEEE Trans on Intelligent Transportation Systems，2014，15（5）：2286-2296.

［7］Xu Yi，Tong Yongxin，Shi Yexuan.An efficient insertion operator in dynamic ride-sharing services［J］.IEEE Trans on Knowledge and Data Engineering，2022，34（8）：3583-3596.

［8］Lyu Jingwei，Hao Jiannan，Yao Shuzhen.A two-sided stable matching method in ridesharing［C］//Proc of the 8th IEEE International Conference on Cloud Computing and Intelligent Systems.Piscataway，NJ：IEEE Press，2022：671-675.

［9］Elmer R，Gerard R C，F(xiàn)rancis E.A game theory-based pricing technique for ridesharing pairings［C］//Proc of the 1st International Conference on Advanced Innovations in Smart Cities.Piscataway，NJ：IEEE Press，2023：1-5.

［10］Tong Yongxin，Zeng Yuxiang，Zhou Zimu.A unified approach to route planning for shared mobility［J］.Proceedings of the VLDB Endowment，2018，11（11）：1633-1646.

［11］Zheng Libin，Chen Lei，Ye Jieping.Order dispatch in price-aware ride-sharing［J］.Proceedings of the VLDB Endowment，2018，11（8）：853-865.

［12］Cheng Peng，Jin Jiabao，Chen Lei.A queueing theoretic framework for vehicle dispatching in dynamic car-hailing［C］//Proc of the 35th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2019：2177-2189.

［13］Li Yafei，Wan Ji，Chen Rui.Top-k vehicle matching in social ride-sharing：a price-aware approach［J］.IEEE Trans on Knowledge and Data Engineering，2019，33（3）：1251-1263.

［14］Luo Hui，Bao Zhifeng，Choudhury M.Dynamic ride-sharing in peak travel periods［J］.IEEE Trans on Knowledge and Data Enginee-ring，2021，33（7）：2888-2902.

［15］Ma Shuo，Zheng Yu，Wolfson O.T-Share：a large-scale dynamic taxi ride-sharing service［C］//Proc of IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2013：410-421.

［16］Na Ta，Li Guoliang，Zhao Tianyu.An efficient ride-sharing framework for maximizing shared route［J］.IEEE Trans on Knowledge & Data Engineering，2018，30（2）：219-233.

［17］Chen Lu，Zhong Qilu，Xiao Xiaokui.Price-and-time-aware dynamic ride-sharing［C］//Proc of the 34th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2018：1061-1072.

［18］Ma Shuo，Zheng Yu，Wolfson O.Real-Time city-scale taxi ride-sharing［J］.IEEE Trans on Knowledge & Data Engineering，2015，27（7）：1782-1795.

［19］Huang Yan，Jin Ruoming，Bastani F.Large scale real-time ride-sharing with service guarantee on road networks［J］.Proceedings of the VLDB Endowment，2013，7（14）：2017-2028.

［20］Lin Qiulin，Lei Deng，Sun Jingzhou.Optimal demand aware ride-sharing routing［C］//Proc of IEEE INFOCOM -IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2018：2699-2707.

［21］Yuen C，Singh A，Goyal S.Beyond shortest paths：route recommendations for ride-sharing［C］//Proc of World Wide Web Conference.New York：ACM Press，2019：2258-2269.

［22］Lowalekar M，Varakantham P，Jaillet P.Zone path construction based approaches for effective real-time ride-sharing［J］.Journal of Artificial Intelligence Research，2021，70：119-167.

［23］Liu Zhidan，Gong Zengyang，Li Jiangzhou.mT-Share：a mobility aware dynamic taxi ride-sharing system［J］.IEEE Internet of Things Journal，2022，9（1）：182-198.

［24］Taxi research report［EB/OL］.http：//www.transformcn.com/Topics/.

［25］Gaia［EB/OL］.https：//outreach.didichuxing.com/research/opendata/.

［26］OpenStreetMap［EB/OL］.http：//www.openstreetmap.org/.

［27］Asghari M，Deng Dingxiong，Shahabi C.Price-aware real-time ride-sharing at scale：an auction-based approach［C］//Proc of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York：ACM Press，2016：1-10.