時空軌跡和復合收益的動態上車點推薦

郭羽含，劉秋月

遼寧工程技術大學 軟件學院，遼寧 葫蘆島125105

隨著移動互聯網技術的快速發展，網約車已成為人們出行的重要手段。在乘客與司機匹配后，司機需前往固定位置接駕乘客，而該位置的選擇不但影響司機的接駕效率，也對乘客的等待時間、乘客的安全性以及周邊的交通擁堵情況具有顯著影響。因此，上車點的推薦方法具有重要的研究意義。

目前國內外對于網約車的研究主要集中在時空熱度與路徑規劃等方面，推薦最佳上車點的研究較少。現存研究主要采用兩種推薦方法：（1）基于潛在上車點與乘客出發地的距離，如賀明慧將問題抽象為“二分類問題”和“排序問題”進行建模并通過聚類算法挖掘出潛在上車點，之后以乘客到上車點的步行距離及司機到上車點的接駕距離作為主要衡量標準篩選出最適合乘客的上車點；鐘穎通過司機與乘客當前位置信息，獲取在預設步行距離閾值范圍內所有候選上車點，根據設定的步行距離和乘客期待上車點的位置，及司機接駕路程和司機期待到達上車點時長，確定乘客與司機可接受范圍內的上車點，為乘客推薦最佳上車點。對于上車點的路網匹配問題，馬云飛采用點到線匹配算法，通過計算待匹配點的運動方向與各路段行駛方向的夾角，定義匹配函數，將待匹配點匹配到匹配度最高的路段。（2）基于潛在上車點的擁堵程度，如張旭東對于多個潛在上車點通過其訂單量計算該上車點的擁堵權重，將擁堵權重最小的上車點推薦給乘客；張巖通過篩選預設范圍內的多個候選上車點，統計各上車點所處路段當前的路況信息，并根據歷史訂單數據預測未來時間的路況信息，為乘客推薦綜合路況最好的上車點作為最佳上車點；張海強獲取在預設范圍內所有滿足條件的候選上車點，根據各候選上車點路況信息及司乘雙方各自前往上車點的交通方式，計算司機與乘客完成上車事件的總時間并進行升序排列，選取耗時最少的上車點作為優先推薦給乘客的最佳上車點。

現存方法仍未能較好地解決以下挑戰：（1）以聚類或理論計算得出的潛在上車點無法保證其可達性，即司機或無法通過道路抵達該位置；（2）基于單一指標推薦的上車點往往在其他指標上存在顯著弊端，未在司機收益和乘客便利性之間取得較好平衡，導致司機與乘客需進行后續溝通調整，從而降低了服務和出行效率；（3）上車點的安全性是目前網約車平臺亟待解決的問題，因此需將上車點在不同時段的安全性納入推薦的考量范圍；（4）如何避免由于同時段同上車點推薦量增加所造成的交通擁堵，即實現上車點合理有效分配，減少資源浪費。

針對上述挑戰，本文通過對時空軌跡大數據進行歸納與分析，提取保證可達性的潛在上車點，構建最佳上車點的動態推薦模型。將乘客步行收益、司機駕駛收益、上車點路況指標、周邊安全性等關鍵因素納入衡量標準，并以約束控制同時段同點的推薦量，有效解決同時段由于單點訂單堆積而造成的非必要等待和資源浪費。實驗表明本文模型和推薦方法可實現上車點的有效動態分配，提升全局司機接駕效率并降低乘客等待時間，且推薦結果優于現存方法。

本文的貢獻主要包含以下三點：

（1）提出了一種基于時空軌跡數據的潛在可達上車點提取方法；

（2）形式化定義了多維度收益指標，并提出了一種復合收益評價模型及一種基于高差值優先的動態推薦方法；

（3）基于真實網約車數據，對不同推薦策略進行了比較，并分析了其對收益的影響。

1 問題描述與建模

1.1 基本定義

（上車點）對于給定點集={h，h=＜,,,＞表示1 個潛在上車點，為點標識，∈N 且≤，為上車點集的上車點數，表示上車點的采集時間，和表示上車點的經度和緯度，表示上車點當前被分配人數。

（乘客）乘客集={r}表示當前所有乘客集合，r=＜,,,,,＞表示1 位乘客個體，為乘客標識，∈N 且≤，為乘客集的乘客數，表示乘客叫車時間，和表示乘客叫車位置的經度和緯度，和表示乘客目的地位置的經度和緯度。

（司機）司機集={d}表示當前所有車主集合，d=＜,,＞表示乘客r所對應的司機標識，為車主標識，∈N 且≤，為司機集的車主數，和表示司機當前所在位置的經度和緯度。

1.2 數學模型

式中，?、分別為L、L的權重。

（上車點安全指標） P為=的上車點處安全性指標。本文對有監控的位置進行標注，并將其監控范圍進行經緯度標注，從而將上車點是否處于監控范圍內作為乘客上車安全性指標P的判別標準，1 表示該乘車點處于監控覆蓋范圍內，否則為0，即：

進而，本問題的目標函數可定義為：

研究所涉及的參數及變量見表1。

表1 參數及變量Table 1 Parameters and variables

2 求解算法

對于本文提出的動態上車點推薦模型，包括潛在上車點提取、時空軌跡點匹配、同時段同點推薦量約束及高差值優先算法生成乘客推薦次序等具體步驟，其算法架構如圖1所示。

圖1 算法架構圖Fig. 1 Algorithm architecture

2.1 潛在上車點提取

圖2 載客事件圖Fig. 2 Passenger incident diagram

圖3 DBSCAN算法示意圖Fig. 3 Schematic diagram of DBSCAN algorithm

2.2 時空軌跡點匹配

采用點到線匹配算法將潛在上車點與路網上的路段進行匹配。算法以誤差閾值為半徑，以待匹配點為圓心進行搜索，獲得誤差范圍內的候選點集合與待匹配路段集合。計算待匹配點運動角度與候選路段行駛方向的夾角，從而定義匹配度函數如下：

其中，λ和λ為權重；為待匹配點運動角度與路段行駛方向夾角的倒數；為待匹配點到候選路段的垂直距離。如圖4 所示，以待匹配點為圓心，誤差為半徑搜索到的候選點集為{1,2,3,5,6,7,8}，待匹配路段集為{,,,}，由點分別向、、、作垂線，依據點的運動角度與各路段的行駛方向，計算各路段的匹配度，將點歸于匹配度最高的路段。

圖4 點到線匹配Fig. 4 Point to line matching

將匹配完路段的軌跡點作為待校正軌跡點，將所屬為同一出租車下的待校正軌跡點歸為一個集合F，即：

其中，F為出租車=的所有待校正軌跡點集合，,,…,f為按時間順序排列的待校正軌跡點。

依次校正集合F中的待校正軌跡點，校正方法為：以待校正軌跡點f為中心，選取點f前后相鄰的軌跡點f與f，如果在相鄰點集[f,f,f]中至少存在兩個相鄰點匹配的路段相同，則認為軌跡點f路段匹配正確；如果點f與f、f的匹配路段不同，則將待校正軌跡點f的匹配路段校正為f與f所匹配的路段。

再分別計算點與匹配路段中候選點距離，將距離最小的點作為路網中的潛在上車點。

2.3 同時段同點推薦量約束

將乘客集合內的個體按照其叫車時間r進行升序排列，即：

以固定時間間隔將集合)中的乘客劃分為不同時段的子集，即：

式（11）表示時段集合，式（12）表示在各時段內所采集的乘客集合。

直至其計數值達到分配人數閾值時，該上車點將不作為候選上車點參與計算分配給乘客。即：

2.4 高差值優先算法生成乘客推薦次序

對于同時段內同上車點的乘客推薦次序問題，本文提出了高差值優先算法。

輸入：上車點集合；時段乘客集合。

輸出：乘客對應乘車點。

其具體推薦流程如圖5所示。

圖5 控制訂單量流程圖Fig. 5 Flow chart of order quantity control

3 實驗與分析

本實驗分別從乘客與司機角度出發，提供兩種優先級策略，分別為乘客優先策略（passenger priority strategy，PPS）和司機優先策略（driver priority strategy，DPS）。探究兩策略優劣并與步行距離推薦策略（walking distance recommendation strategy，WDRS）及路況推薦策略（road condition recommendation strategy，RCRS）對收益以及出行時間的影響進行綜合比較。

3.1 實驗環境

本文所用到的數據集是上海市出租車單日24 h GPS 數據集，數據采集頻率為每次10～80 s。實驗部分采用Python語言，實驗環境、實驗參數分別見表2、表3。

表2 實驗環境Table 2 Experimental environment

表3 參數設置Table 3 Parameter setting

上述參數值綜合考慮真實應用環境與大量實驗的最優輸出而設定，參數敏感性分析見3.3節。

本文主要采用層次分析法來實現權重的分配。首先通過一致矩陣法構造評分矩陣，從而定義一致性指標與一致性比率，即：

其中，()為矩陣的最大特征值，為矩陣的維數，為矩陣的一致性標準，當＜0.1 時，則判定矩陣具有滿意的一致性，則可以對矩陣采用規范列平均法得到所求權重分配。表3 中的?、、λ、λ及表4 與表5 中的權重分配都采用該方法得出。

3.2 實驗結果

PPS實驗權重設置見表4。

表4 PPS實驗權重設置Table 4 Weight setting in PPS experiment

乘客2 的推薦結果如圖6 所示，乘客2 最佳上車點與其他候選上車點收益對比如圖7所示，多乘客同時段叫車的推薦結果如圖8所示。

圖6 乘客2推薦結果Fig. 6 Passenger 2 recommendation results

如圖6 所示，方形點位置為乘客2 叫車位置，綜合考慮所有候選上車點的乘客步行收益、司機駕駛收益、上車點路況指標以及上車點附近安全性等關鍵因素。由于離乘客2 較近的候選上車點的路況指標及安全性較差，綜合推薦星形點位置為乘客2的最佳上車點位置。

如圖7所示，乘客2的最佳上車點較其他候選上車點有最高的司機駕駛收益和上車點綜合收益，但該上車點的路況指標明顯低于其他候選上車點水平，且在步行收益方面也較低于某些其他候選點。

圖7 乘客2收益對比Fig. 7 Revenue comparison of passenger 2

如圖8所示，推薦給乘客的上車位置都距離乘客較近，當多乘客同時叫車時，除考慮所有備選上車點的各項收益外，還要約束控制同時段同一上車點的推薦次數，實現上車點有序、有效地分配。

圖8 多乘客推薦結果Fig. 8 Multi-passenger recommendation results

DPS中參數權重設置見表5。

表5 DPS實驗權重設置Table 5 Weight setting in DPS experiment

乘客2 的推薦結果如圖9 所示，乘客2 最佳上車點與其他候選上車點收益對比如圖10 所示，多乘客同時段叫車的推薦結果如圖11所示。

圖11 多乘客推薦結果Fig. 11 Multi-passenger recommendation results

如圖9 所示，由于離乘客2 較近的點安全性、路況等指標較差，綜合考慮，推薦擁有較高路況指標且安全性較高的星形點位置為乘客2 的最佳上車點位置。

圖9 乘客2推薦結果Fig. 9 Passenger 2 recommendation results

如圖10 所示，乘客2 的最佳上車點較其他候選上車點有較高的司機駕駛收益和路況指標。

圖10 乘客2收益對比Fig. 10 Revenue comparison of passenger 2

如圖11 所示，推薦給各乘客的最佳上車點都擁有較高的路況指標，且安全性較高。當多乘客叫同時段車時，除考慮各收益外，還要約束控制同時段同一上車點的推薦次數，實現上車點有序、有效地分配。

本實驗從司機與乘客雙方角度出發，探究司乘雙方的收益關系及各方收益的變化趨勢，如圖12所示。

圖12 司乘收益分析圖1Fig. 12 Driver and passenger income analysis figure 1

如圖12所示，在提升乘客步行收益占比時，路況指標下降明顯，且當步行收益占比在0至0.3時，司機的駕駛收益大幅下降。

如圖13所示，在提升司機駕駛收益的占比時，乘客的步行收益持續下降，而路況指標則持續提升。

圖13 司乘收益分析圖2Fig. 13 Driver and passenger income analysis figure 2

如圖14所示，在提升路況指標占比時，乘客的步行收益也會受影響而持續下降，而當路況指標占比小于0.25時，司機的駕駛收益呈下降趨勢，當路況指標占比在0.25～0.40 時，司機駕駛收益呈穩定上升趨勢。

圖14 司乘收益分析圖3Fig. 14 Driver and passenger income analysis figure 3

3.3 結果分析

（1）綜合收益分析

不同策略的上車點推薦結果對比見表6。

由表6可知，在乘客步行收益方面，WDRS具有一定優勢，RCRS則效果較差，與WDRS相差1.53；在司機駕駛收益方面，PPS 優于其他，RCRS明顯低于其他水平；在路況指標方面，RCRS表現出明顯優勢，與效果最差的WDRS相差0.07；在綜合收益方面，PPS比平均綜合收益最低的RCRS高1.74。

表6 上車點收益表Table 6 Revenue of pickup point

（2）行程時間對比

本文以人的平均步行速度60 m/min，出租車的平均行駛速度600 m/min 進行實驗，實驗結果見表7。

由表7 與圖15 實驗結果可知，在乘客步行時間方面，WDRS的時間明顯少于其他方案；司機接駕時間方面，PPS 與WDRS時間略短，RCRS接駕時間較長；路程時間方面四種策略表現相當。行程總時間方面，PPS、DPS、WDRS時間相差不大，但RCRS時間較長。

圖15 時間對比圖Fig. 15 Time comparison chart

表7 行程時間表Table 7 Travel schedule min

（3）敏感度分析

本文通過對步行收益、駕駛收益、路況指標、安全性指標在目標函數中的占比，分析各指標對復合收益的影響，實驗結果如圖16所示。

如圖16 所示，隨著步行收益與路況指標占比增加，復合收益水平會明顯降低；隨著司機駕駛收益與安全性指標占比增加，復合收益水平會有大幅度提高。

圖16 敏感度分析Fig. 16 Sensitivity analysis

4 結束語

本文通過對時空軌跡大數據進行歸納與分析，挖掘出乘客歷史上車點，綜合考慮乘客步行收益、司機駕駛收益、上車點路況指標、周邊安全性等關鍵因素，建立上車點的復合收益評價，構建最佳上車點的動態推薦模型。并提出一種高差值優先算法，解決同上車點乘客的推薦次序問題，實驗證明本文算法可以使上車點實現高效有序的分配，且PPS與DPS推薦策略在綜合收益方面明顯好于WDRS與RCRS推薦策略。在時間方面，PPS的接駕時間與路程時間最短，WDRS的步行時間最短。行程總時間方面，PPS、DPS、WDRS時間相差不大，但RCRS時間較長。

未來研究中，仍需要進一步探索本文提出的四項指標對于最佳上車點選取的具體影響，并以動態方式決定該四項指標在最佳上車點推薦模型中的占比。