基于概率路由的出租車共乘調度算法

蔡文廣 劉佳旭 張小欣

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

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

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

關鍵詞：共乘；路徑規劃；K-means聚類；概率路由

中圖分類號：TP391.41??? 文獻標志碼：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? 引言

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

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

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

1? 問題定義

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

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

定義3? 出租車。出租車由t=〈loct，St，Rt〉表示，其中loct表示出租車t的當前位置，St和Rt分別是出租車t的行程事件表和共享出行的路線。

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

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

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

定義7? 地標?？臻g簇Cz的地標頂點LMz∈Cz，它是由簇Cz內頂點的距離屬性和概率屬性組成，選擇Rank（D，P）最大值為地標頂點，具體確定地標頂點LMz的公式為

Rank（D，P）=α×LMz到Cz內所有頂點的距離之和累加Cz內所有邊的和+（1-α）×LMz 到簇C 的概率和Cz 內頂點的數量（1）

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

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

2? 框架

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

2.1? 階段1 節點聚類

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

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

b）轉移概率的計算?；诓襟Ea）中獲得的k個空間簇，計算每個頂點vi的轉移概率。每一項Bi，j（i=1，2，…，N和j=1，2，…，K）是在頂點vi到第j個空間簇內的轉移概率，這可以利用歷史出租車數據來計算。

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

2.2? 階段2? 路線分區

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

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

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

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

ddl［i］=er-dis（or，dr）如果Li是起點

er如果Li是終點（3）

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

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

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

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

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

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

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

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

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

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

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

如算法1，第1行為初始化出租車路線分區的集合、松弛時間集合和嘗試遍歷尋找離線乘客的次數。第3～10行表示如果出租車的容量小于0，直接退出循環，否則對出租車的行程路線進行分區，根據式（2）計算每個事件的松弛時間，在松弛時間內選擇出現離線乘客概率最大的分區。第11～19行表示在選出的分區重新對出租車路線進行規劃，利用地標頂點篩選出要遍歷的簇，過濾掉不符合條件的簇，再利用每個簇內頂點的轉移概率值，規劃一條累積最大概率權重的路徑，其中最短路徑需要用迪杰斯特拉來尋找。如果找到有效路線，則將返回更新的路線USt，重復這兩個步驟，如果找不到有效路線或超過了嘗試的次數，則返回原有的路線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）時間復雜度。為了服務請求，需要檢查出租車中的所有行程事件，然后選擇合理繞行成本的路線，概率路由的算法時間復雜度為O（mNDP/K），其中m是行程事件的個數，N/K是平均每個簇中頂點的個數，D是查詢轉移概率矩陣的次數，P是所選擇簇的數量。因為任何兩個頂點之間的最短路徑可以預先計算和緩存，所以最短路徑查詢與以前的研究一樣可以在O（1）時間計算出。

3? 實驗分析

3.1? 實驗數據

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

3.2? 實驗方法

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

3.3? 實驗結果與分析

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

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

通過改變簇數κ并保持其他參數為默認值來進行實驗，圖7為T-Share、mT-Share、NDP和PR-Share對服務請求數量的影響。T-Share、mT-Share和NDP通過改變網格的大小可以近似地和PR-Share中簇的大小在功能上實現相同的作用，起初增加網格和簇的數量可以讓服務請求的數量增加，然而隨著增加數量的變多，服務請求的數量也開始減少。例如，κ=150，這是因為太小或過大的κ將導致增加和減少候選簇的集合，進而影響算法的性能。以PR-Share為例，當κ從100變化到150時，服務請求的數量增加了6%，服務請求的數量從6 123增加到6 547，然而當簇數增多，總的服務請求也慢慢變少。

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

圖9顯示響應時間隨著可用出租車的數量增加而增加。很明顯，No-Sharing總是可以在1 ms內處理請求，因為它只服務一個請求。PR-Share比mT-Share和T-Share需要更長的時間來響應請求，而NDP是最慢的一個。這是因為在決策階段，NDP計算每個候選出租車的繞行下界是非常耗時的，一般來說，本文算法在100～280 ms就可以響應乘車請求，并且在響應時間上優于NDP 3～9倍。

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

4? 結束語

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

參考文獻：

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

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

［3］徐毅，童詠昕，李未.大規模拼車算法研究進展［J］.計算機研究與發展，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，Francis 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.