時空軌跡和復(fù)合收益的動態(tài)上車點(diǎn)推薦

郭羽含，劉秋月

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島125105

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

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

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

針對上述挑戰(zhàn)，本文通過對時空軌跡大數(shù)據(jù)進(jìn)行歸納與分析，提取保證可達(dá)性的潛在上車點(diǎn)，構(gòu)建最佳上車點(diǎn)的動態(tài)推薦模型。將乘客步行收益、司機(jī)駕駛收益、上車點(diǎn)路況指標(biāo)、周邊安全性等關(guān)鍵因素納入衡量標(biāo)準(zhǔn)，并以約束控制同時段同點(diǎn)的推薦量，有效解決同時段由于單點(diǎn)訂單堆積而造成的非必要等待和資源浪費(fèi)。實(shí)驗表明本文模型和推薦方法可實(shí)現(xiàn)上車點(diǎn)的有效動態(tài)分配，提升全局司機(jī)接駕效率并降低乘客等待時間，且推薦結(jié)果優(yōu)于現(xiàn)存方法。

本文的貢獻(xiàn)主要包含以下三點(diǎn)：

（1）提出了一種基于時空軌跡數(shù)據(jù)的潛在可達(dá)上車點(diǎn)提取方法；

（2）形式化定義了多維度收益指標(biāo)，并提出了一種復(fù)合收益評價模型及一種基于高差值優(yōu)先的動態(tài)推薦方法；

（3）基于真實(shí)網(wǎng)約車數(shù)據(jù)，對不同推薦策略進(jìn)行了比較，并分析了其對收益的影響。

1 問題描述與建模

1.1 基本定義

（上車點(diǎn)）對于給定點(diǎn)集={h，h=＜,,,＞表示1 個潛在上車點(diǎn)，為點(diǎn)標(biāo)識，∈N 且≤，為上車點(diǎn)集的上車點(diǎn)數(shù)，表示上車點(diǎn)的采集時間，和表示上車點(diǎn)的經(jīng)度和緯度，表示上車點(diǎn)當(dāng)前被分配人數(shù)。

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

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

1.2 數(shù)學(xué)模型

式中，?、分別為L、L的權(quán)重。

（上車點(diǎn)安全指標(biāo)） P為=的上車點(diǎn)處安全性指標(biāo)。本文對有監(jiān)控的位置進(jìn)行標(biāo)注，并將其監(jiān)控范圍進(jìn)行經(jīng)緯度標(biāo)注，從而將上車點(diǎn)是否處于監(jiān)控范圍內(nèi)作為乘客上車安全性指標(biāo)P的判別標(biāo)準(zhǔn)，1 表示該乘車點(diǎn)處于監(jiān)控覆蓋范圍內(nèi)，否則為0，即：

進(jìn)而，本問題的目標(biāo)函數(shù)可定義為：

研究所涉及的參數(shù)及變量見表1。

表1 參數(shù)及變量Table 1 Parameters and variables

2 求解算法

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

圖1 算法架構(gòu)圖Fig. 1 Algorithm architecture

2.1 潛在上車點(diǎn)提取

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

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

2.2 時空軌跡點(diǎn)匹配

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

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

圖4 點(diǎn)到線匹配Fig. 4 Point to line matching

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

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

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

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

2.3 同時段同點(diǎn)推薦量約束

將乘客集合內(nèi)的個體按照其叫車時間r進(jìn)行升序排列，即：

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

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

直至其計數(shù)值達(dá)到分配人數(shù)閾值時，該上車點(diǎn)將不作為候選上車點(diǎn)參與計算分配給乘客。即：

2.4 高差值優(yōu)先算法生成乘客推薦次序

對于同時段內(nèi)同上車點(diǎn)的乘客推薦次序問題，本文提出了高差值優(yōu)先算法。

輸入：上車點(diǎn)集合；時段乘客集合。

輸出：乘客對應(yīng)乘車點(diǎn)。

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

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

3 實(shí)驗與分析

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

3.1 實(shí)驗環(huán)境

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

表2 實(shí)驗環(huán)境Table 2 Experimental environment

表3 參數(shù)設(shè)置Table 3 Parameter setting

上述參數(shù)值綜合考慮真實(shí)應(yīng)用環(huán)境與大量實(shí)驗的最優(yōu)輸出而設(shè)定，參數(shù)敏感性分析見3.3節(jié)。

本文主要采用層次分析法來實(shí)現(xiàn)權(quán)重的分配。首先通過一致矩陣法構(gòu)造評分矩陣，從而定義一致性指標(biāo)與一致性比率，即：

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

3.2 實(shí)驗結(jié)果

PPS實(shí)驗權(quán)重設(shè)置見表4。

表4 PPS實(shí)驗權(quán)重設(shè)置Table 4 Weight setting in PPS experiment

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

圖6 乘客2推薦結(jié)果Fig. 6 Passenger 2 recommendation results

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

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

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

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

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

DPS中參數(shù)權(quán)重設(shè)置見表5。

表5 DPS實(shí)驗權(quán)重設(shè)置Table 5 Weight setting in DPS experiment

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

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

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

圖9 乘客2推薦結(jié)果Fig. 9 Passenger 2 recommendation results

如圖10 所示，乘客2 的最佳上車點(diǎn)較其他候選上車點(diǎn)有較高的司機(jī)駕駛收益和路況指標(biāo)。

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

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

本實(shí)驗從司機(jī)與乘客雙方角度出發(fā)，探究司乘雙方的收益關(guān)系及各方收益的變化趨勢，如圖12所示。

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

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

如圖13所示，在提升司機(jī)駕駛收益的占比時，乘客的步行收益持續(xù)下降，而路況指標(biāo)則持續(xù)提升。

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

如圖14所示，在提升路況指標(biāo)占比時，乘客的步行收益也會受影響而持續(xù)下降，而當(dāng)路況指標(biāo)占比小于0.25時，司機(jī)的駕駛收益呈下降趨勢，當(dāng)路況指標(biāo)占比在0.25～0.40 時，司機(jī)駕駛收益呈穩(wěn)定上升趨勢。

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

3.3 結(jié)果分析

（1）綜合收益分析

不同策略的上車點(diǎn)推薦結(jié)果對比見表6。

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

表6 上車點(diǎn)收益表Table 6 Revenue of pickup point

（2）行程時間對比

本文以人的平均步行速度60 m/min，出租車的平均行駛速度600 m/min 進(jìn)行實(shí)驗，實(shí)驗結(jié)果見表7。

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

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

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

（3）敏感度分析

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

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

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

4 結(jié)束語

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

未來研究中，仍需要進(jìn)一步探索本文提出的四項指標(biāo)對于最佳上車點(diǎn)選取的具體影響，并以動態(tài)方式?jīng)Q定該四項指標(biāo)在最佳上車點(diǎn)推薦模型中的占比。