基于候客點規劃的空閑出租車路線推薦算法

陳冬梅，卜霄菲，黃 河，杜 揚，高國舉，孫玉娥

（1.蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006；2.沈陽師范大學 軟件學院，沈陽 110034；3.蘇州大學 軌道交通學院，江蘇 蘇州 215137）

0 概述

隨著定位技術和4G/5G 技術的發展，裝備全球定位系統（Global Position System，GPS）設備的出租車越來越多［1-3］。通過對該類設備采集得到的海量軌跡數據進行挖掘分析，可以在改善出租車服務質量方面提供更好的數據支撐，令出租車服務更加舒適、快捷，使出租車成為更多乘客的出行選擇［4］。然而，在面臨日益增長的乘客需求和出租車供給不平衡的矛盾時，如何為空閑司機規劃路線，以最短時間和最短距離接載到乘客，成為學術界關注的熱點問題［5-7］。

傳統的空閑出租車路線推薦主要有2 種方式：載客點推薦［8-10］和載客路線推薦［5-7］。載客點推薦一般是通過對歷史軌跡數據的上下車事件進行聚類從而發現乘客需求較多的載客點，當司機發出請求時，可以推薦司機前往最近的接載點。例如文獻［8］通過歷史軌跡數據檢測停車點，從而并向空閑司機推薦這些停車點以最快的時間接載到乘客。文獻［9］通過將底層道路網絡聚類成多個路段集群，根據每個集群的特征評估其尋客潛力并進行推薦。然而，該類方法忽略了前往這些載客熱點的路線并不唯一的問題，在沒有經驗知識的情況下，司機如何選擇效益最高的路線是一個難以解決的問題。

為解決接載點推薦存在的問題，近幾年的研究工作主要集中在為空閑司機推薦接載路線，原因是相比較只推薦接載點而言，直接推薦完整的路徑可以為無經驗的司機減少閑逛距離，從而減少空閑時的花費成本。其中，文獻［5］提出路段的凈利潤函數，向司機推薦潛在利潤最大的路線。文獻［6］在文獻［5］的工作基礎上提出了一個基于蒙特卡洛搜索樹思想的路線推薦方法，實現了動態的接載概率。文獻［7］提出自適應最短預期閑逛路線的推薦方法，能夠根據位置的容量和接載概率推薦路線。

目前存在的路線推薦方法主要是為空閑司機推薦一條完整的駕駛路線，直到司機接載到乘客或者遇到終點路段才停止推薦。但該方式忽略了真實路網環境下某些路段的可等待因素。例如餐飲服務集中地區、大型商場周圍、地鐵公交車站附近以及學校周邊的可停車路段，這些路段都會在特定的時間段（如車站到達、地鐵換乘、上課放學等時段）出現大量乘車需求。當司機在某時段經過這些路段時，傳統方法依然會繼續推薦行駛路線，卻沒有預判到該路段未來某段時間的乘車需求對司機決策的影響。例如當司機經過地鐵站附近的路段時，如果該地鐵站在未來1 min 剛好到站則會出現大量換乘乘客，此時司機選擇停車等待可能會更快接到乘客。相反，如果司機選擇繼續行駛，則會導致空閑出租車的閑逛距離過長，工作收益降低。相比較傳統的路線推薦方法而言，考慮路段等待因素不僅可以幫助司機更快地接載到乘客，而且可以幫助司機降低因閑逛產生的油費損耗，從而進一步減少能源消耗以及廢氣排放造成的空氣污染［11-12］。此外，通過考慮路段的可等待因素還可以幫助乘客減少因換乘產生的等待時間，在提高搭載雙方工作效率的同時，進一步緩解交通擁堵的壓力，對提高城市的流動性具有重要意義［13-14］。

本文針對當前路線推薦方法存在忽略路段可等待因素的問題，提出一種基于候客點規劃的空閑出租車路線推薦機制。通過分析出租車行駛過程產生的軌跡數據，將軌跡點和真實路段建立聯系。同時，處理出租車行走路段的歷史搭載信息，從而構建接載概率預測模型。基于已有數據，以推薦花費成本更小的路線策略為準則，提出一種考慮等待時間的路線推薦算法，并在真實的出租車軌跡數據集上驗證該算法的有效性。

1 相關工作

目前關于出租車路線推薦方法主要有2 種：向出租車司機推薦接載熱點及向出租車司機推薦完整路線。

針對第1 種推薦方式，YUAN 等［13-14］通過學習乘客的移動模式和司機接載行為的知識，建立概率模型進行停車點的推薦，使司機能以最短的時間接載到乘客。WANG 等［9］提出一 種基于排序的ELM 模型，該模型可以根據道路集群的拾取頻率來評估所有道路集群的尋客潛力并向出租車司機推薦具有最高尋客潛力的Top-k 道路集群。VERMA 等［15］基 于強化學習方法，利用蒙特卡抽樣建模經驗司機的行為，并通過司機的行為偏好捕捉乘客的需求變化，為閑逛司機推薦長期利益最大化的區域。CHEN 等［16］提出利用空閑狀態計算接載點的利潤并結合DBSCAN 聚類算法提取高利潤的乘客區域推薦給空閑司機。LI 等［17］基于司機目的點偏好這一因素提出基于目地點概率最大化的推薦算法PROMISE，為空閑司機推薦滿足目的區域的一系列接載點。LI 等［18］提出一種改進的ARIMA 方法，預測熱點區域乘客移動的時空區域，從而挖掘出乘客的移動模式。HWANG 等［19］通過建立ON-OFF 模型獲取乘客下車位置和下一位乘客上車位置之間的關系，并估計出推薦點的期望利益。然而，這些推薦方法基本都是基于位置點的推薦而非實際的完整路線，而這對司機在找到乘客之前如何減少閑逛時間十分重要。

針對第2 種推薦方式，向出租車司機推薦完整路線，QU 等［5］提出一種Cost-Effective 的路線推薦系統，該系統首先提出一個凈利潤函數（乘客收益-出租車花費）來評估每個路段的潛在收益。基于遞歸樹的思想生成尋找乘客的候選路徑，并利用凈利潤函數計算每個候選路徑的收益，并將收益最大的路徑推薦給空閑出租車司機。GARG 等［6］提出一個基于蒙特卡羅搜索樹的尋客策略，目的是令空閑司機與預期乘客之間的閑逛距離最小化。JI 等［11］將最小化空閑時間作為學習目標，提出一個自適應的深度強化學習策略，并進行路線推薦。該工作通過深度網絡融合多個實時的內外部特征，并為每個候選路徑學習一個評價分數。同時，利用強化學習策略進行學習，實時捕捉候選路徑的推薦分數，并將分數最高的路線推薦給空閑司機。QU 等［7］提出一個出租車收益的路線推薦方法即自適應最短預期閑逛路線（ASER）。該方法通過設計概率網格發現潛在的接載位置和動態的接載概率，然后利用卡爾曼濾波方法預測每個網格的接載概率和容量，并在大數據應用平臺下開發新的數據結構框架以提高推薦效率。LUO 與LV 等［20-21］基于接載乘客的概率和容量問題，也提出一種出租車路線推薦方法，為一組司機推薦最優的路線，目的是最小化平均閑逛駕駛距離。RONG 等［22-23］基于馬爾科夫決策模型為出租車司機推薦長期利潤最大化的路線。盡管當前存在的空閑出租車路線推薦工作已經解決了一些問題，但是這些方法均忽略了真實路網環境下某些路段的可等待因素，使推薦的路線因載客概率較低、行駛距離較長而花費成本變高。

2 模型構建

2.1 符號說明

定義1（節點）節點是指某2 個路段相交的點，可以表示為s=(id，lat，lon)，其中：id 是該節點的唯一標識符；lat 和lon 分別表示該節點所在的經緯度信息。

定義2（路段）1 條完整的路徑可以被多個節點s分割成多個路段序列r，其中每個路段均由2 個節點確定，即r=(sstart，send)。如果該路段不是終點路段，則與其相連的其他路段稱為它的鄰居路段，可以表示為

定義3（路線）路線R由一系列相連的路段組成，可以表示為R={r1→r2→…→rn}，滿足對于?i，1≤i≤n，，且該路 線的起點 為R_start=，該路線的終點為R_end=

定義4（路網）1 個路網可以表示為有向圖G(V，E，D)，其中：V表示所有節點的集合{s1，s2，…，sn；E={ri→j|si(idi，lati，loni)，sj(idj，latj，lonj)∈V} }表 示所有有向路段的集合；D表示為每個路段物理距離長度的集合，可由Haversine 式（1）計算得出：

其中：φ是節點s的緯度；λ是節點s的經度；RRadius為地球半徑（6 371 km）。

定義5（軌跡）軌跡是按時間序列排序的一系列GPS 采樣點組成的集合，可以表示為Tr={p1→p2→…→pn}，其中每個采樣點表示為pi={lat，lon，time，empty，speed}記錄著采樣點的位置信息、時間戳、載客狀態、速度等信息。對于出租車的載客狀態可以由式（2）表示：

從出租車的軌跡數據中進一步挖掘出租車是否處于停車狀態，并通過該狀態標識可停車路段。對于2 個連續的GPS 采樣點pi和pi+1，利用Haversine 公式計算這2 個采樣點之間的距離與時間間隔，當距離小于預先定義的距離閾值且時間間隔大于采集間隔時，認為此時出租車的狀態為停車狀態，意味著司機經過該路段時可以選擇停留。值得注意的是，本文定義的停車路段是司機在該路段等待有需求的乘客。在現實生活中，這類場景多數會出現在周圍有車站、商場附近、居民區等的路段。

定義6（時變的接載概率）由于不同道路環境、不同天氣以及不同時段等因素的影響，對于某一路段的乘客需求在不斷變化，因此對于任意的某一路段r在時間間隔[τ1，τ2]內的搭載概率為：

2.2 問題描述

定義7當出租車司機放下乘客處于空閑狀態時，可以發出尋客請求。根據空閑司機發出請求的路段r1和請求時間t，為空閑出租車司機推薦1 個效益最大化的接載路線R*={r1，r2，…，rL}，使得空閑司機選擇這條行駛路徑接載到乘客時的閑逛距離、閑逛時間和花費成本最小，其中L表示選擇路徑的長度。

由于司機的花費成本涉及到司機在接載到乘客之前所行駛的距離和所花費的時間，因此對于每個路段的潛在花費成本可以根據式（4）得出：

其中：p(ri，[τ1，τ2])表示在該路段接載到乘客的概率；Frent是出租車司機租賃出租車的費用；Fgas是出租車行駛d(r)距離所花費的汽油費；tp(r)是出租車穿過該路段所花費的時間；tw(r)是出租車停留在該路段所花費的時間；t=tw+tp是出租車司機在該路段上花費的總時間。

對于每個路段的潛在收益可根據式（5）得出：

因此對于每個路段的凈收益可由式（6）計算得出：

由該公式可以看出影響司機收益的重要因素是在閑逛時所花費的時間和距離。因此，如果想要提高司機的收益，需要不斷減小司機在閑逛時所花費的成本，即Minimise(Cost(r，t))。

基于以上定義，對于任意推薦路線R={r1，r2，r3，…，rL}可以計算其花費成本函數為：

式（7）表示對于推薦的路徑R來說，當出租車司機在路段rL接到乘客時，所花費的成本最小。

以往的推薦算法是推薦一個連續駕駛路線，只考慮經過路段的當前接載概率，若經過該路段沒有接載到乘客，則會繼續推薦路線，導致閑逛距離變長，花費成本變高。而本文算法考慮了路段的可等待因素。當出租車司機經過靠近地鐵站、車站、學校等地方的路段時，能夠預判未來某個時刻可能發生的事件，比如由于地鐵到站而出現大量換乘乘客。本文算法推薦的具體步驟如下：1）根據歷史GPS 軌跡信息為每個路段統計出最長等待時間；2）設定司機在某路段等待的時間閾值是3 min，單位時間間隔是1 min；3）當空閑司機在r1路段發出請求時，對于r1的鄰居路段{r2，r3，r4}以及等候間隔有2 種方案選擇。這2 種方案具體如下：

方案1在請求路段等待1～3 min，接到乘客；

方案2在請求路段等待1～3 min 后，選擇前往下一個路段。

對于某個司機在某一路段的選擇可由式（8）表示：

其表達含義是選擇最小花費的行駛路段以及等待時間時的方案。因此，對于所有行駛時間小于Tmin，駕駛路段不超過L的候選路徑R={R1，R2，…，Rn}，本文的目標是選擇1 個花費成本最小的候選路徑R*，滿足：

3 算法設計

如圖1 所示，基于候客點規劃的空閑出租車路線推薦方法主要分為3 個步驟：1）進行數據預處理，利用最短路徑匹配算法將GPS 軌跡匹配到真實的路網環境中，并依據連續2 個GPS 點之間的距離和時間屬性識別可停車路段，將停車時間超過5 min 的路段標記出來；2）根據每個路段發生接載事件的特征，利用改進的多層感知機有效地預測不同天、不同時段以及不同天氣情況下的接載概率；3）根據每個路段的接載概率，設計考慮等待時間的最小成本優化路徑算法，從而進行有效的路線推薦，實現效益最大化。

圖1 出租車路線推薦框架Fig.1 Framework of taxi route recommendation

3.1 路段匹配算法

在實際的數據采集過程中，由于設備的精度誤差、路網障礙物、信號強弱因素的影響，GPS 設備采集到的軌跡點往往散落在道路周圍而無法匹配到具體的路段上。本文首要解決的問題是為軌跡數據匹配具體的路段，并根據狀態位的表示為每個路段統計載客次數和空載次數，具體的算法描述及操作過程如下：

算法1路段匹配

結合實例（如圖2）對路段匹配算法1 進行分析。對于待處理軌跡點p2，首先根據路網數據為其劃分1 個緩沖區buffe，如圖2（a）所示。該緩沖區由當前點p2為中心點，radius 作為半徑進行劃分。接著找到與該緩沖區相交的所有路段作為p2的候選路段candiSeg（算法1 第5 行）。然后對候選路段candiSeg進行判斷：情況1，如果候選路段為空則返回null，匹配失敗；情況2，如果只包含一個候選路段則直接返回該路段作為匹配路段（如算法1 第6～9 行所示）；情況3，如果存在多個候選路段，如圖2（a）所示，candiSeg={r1，r2，r3}，則繼續進行判斷。遍歷所有候選路段candiSeg，通過最短距離函數finddis 計算出與p2點距離最近的所有路段NearSeg 并判斷：情況1，若只包含1 個最近路段則直接返回該路段作為匹配路段（如算法1 第10～14 行所示）；情況2，若存在多個最近路段，如圖2（b）所示，nearSeg=｛r1，r2｝，則繼續利用最小角度函數findangle 計算與行駛方向夾角最小的路段作為匹配路段（如算法1 第15～17 行所示），如圖2（c）所示。最后，返回最佳匹配路段Machsegment=r1，如圖2（d）所示。

圖2 道路匹配實例Fig.2 Example of road matching

3.2 基于歷史數據的接載概率預測

在路線推薦問題中，有效預測不同路段的接載概率非常重要。由于不同位置、不同時段、不同天氣等因素的影響，潛在的接載概率不斷發生變化。以不同地區為例，圖3 分別表示了上海市虹橋機場和上海市南京步行街在不同時刻發生接載事件的情況，從圖3（a）可以看出，在上午04：00—08：00 時，有較多乘客選擇前往機場，并在機場下車。同一時段也可以發現，從機場選擇搭載出租車出行的需求比較少，導致在該時段有大量出租車空閑。因此，即使是機場這樣的接載熱點，此時的接載概率也非常低。而在晚上20：00 以后情況則剛好相反，該時段內大量乘客到達機場并選擇前往市區，接載概率變高，可以將該地區推薦給空閑司機。

圖3 不同地區不同時段接載需求變化Fig.3 Changes in pick-up demand over time in different regions

如圖3（b）所示，對于商業區來說，供需不平衡主要發生在08：00—12：00，此時前往該地區的乘客較多，離開的人數比較少，可以看出在白天前往商業區的需求比較大，而晚上情況相反，更多的乘客選擇從步行街離開，并前往不同的地方。因此，為有效學習這些因素對接載概率的影響，本文構建了一種基于多指標輸入的多層感知機模型（Multi-Layer Perceptron Model，MLP）進行接載概率的預測。

針對接載概率預測問題，大多數研究認為接載概率的變化往往與時間序列呈現緊密的關系，并利用傳統的多層感知機方法，將單一的時間序列作為輸入數據，設計滯后步長并進行接載概率的預測。然而通過前文的實例分析可以發現，影響路段接載概率的因素十分復雜（比如天氣、高平峰時段等）。這些復雜的因素與路段的接載概率呈現非線性相關，僅通過自身的時間序列進行建模無法捕捉到真正的變化規律。因此，為提高預測精度，本文將提取多個相關因素如日期屬性、天氣、高平峰時段、時間間隔、接載數量和空載數量作為模型的輸入，然后通過建立一個實時的接載概率預測模型，進行預測與分析。

為合理預測不同路段的接載概率，本文首先對空閑出租車在路段的行駛條件做出相應的假設。假設1：空閑出租車在巡航路段均為單向行駛，不會存在倒車；假設2：空閑出租車不會在同一路段震蕩行駛（走走停停）。基于上述假設條件，本文對所選取的因素進行量化處理。比如：日期屬性（1 代表工作日、2 代表周末、0 代表國家法定節假日）；天氣（-1代表雨天、1 代表晴天、0 代表多云）；高平峰（07：00—10：00 用1 表示、17：00—20：00 用2表示、其余時段用0 表示）；時間間隔（以1min 為間隔劃分工作時間段05：00—23：00 共1 140 個間隔）、接載數量（每個間隔內載客次數）、空載數量（每個間隔內空載次數）。將量化后的特征作為模型的輸入，模型的輸出即為預測不同路段的接載概率。對于感知機模型來說，不同的神經元個數以及不同的激活函數影響著訓練模型的復雜程度。本文選取上海市淮海中路這一路段，提取出該路段在30 天內發生接載事件的特征數據，并以其80%的數據作為訓練數據，剩余20%作為測試數據。經過多次訓練發現，當訓練的網絡層數選擇3 層，神經元的個數選擇256，激活函數選擇ReLU 時效果最佳。該模型的預測結果如圖4 所示，從圖中可以看出預測值和真實值的分布較為一致，驗證了預測模型的穩定性。

圖4 預測結果對比Fig.4 Comparison of forecast results

為進一步驗證基于多指標輸入的多層感知機模型的性能，本文利用只考慮時間序列的感知機模型作為對比，并使用MAE、MAPE、R2作為指標對預測效果進行評估，結果如表1 所示。由表1 可知，改進后的多層感知機在MAE、MAPE、R2指標上分別提高了0.5%、13%和16%。

表1 預測精度Table 1 Prediction accuracy

3.3 考慮等待時間的路線推薦算法

在3.1 節、3.2 節中對路段數據的處理使每個路段不僅包含了節點的經緯度信息，還包含了歷史的接載情況、穿行該路段的距離以及時間。依據這些信息可以利用式（4）和式（8）計算出每個路段的花費成本，然后根據推薦算法推薦效益最好的路線。

算法2考慮等待時間的路線推薦

算法2 描述了考慮等待時間的最小成本推薦方法的偽代碼。該算法首先從空閑司機的請求中獲取司機所在的當前路段r和當前時間t，并根據所在路段位置和時間信息得到一系列的鄰居路段c_rneighbor和當前路段的接載概率p（如算法2 第1～5 行所示）。然后，基于圖搜索算法中的廣度優先搜索算法策略對當前路段的每個選擇（等待時間間隔，路段選擇），并計算其潛在的花費成本（如算法2 第6 行所示），選擇花費成本最小的方案（等待間隔，路段）作為當前的選擇（如算法2 第7～12 行所示）。該過程被不斷重復直到推薦的路段長度超過L或者推薦的搜索總時間超過T時，則停止推薦并得出最小成本的推薦路線。

為解釋、驗證本文提出的算法，下面將通過一個具體實例進行說明。如圖5 所示，假設每個路段的行駛時間為30 s，路段的等待間隔為2 min，行駛距離為120 m，其單位時間的租賃費為0.1，汽油費為0.01。當司機在r4路段在上午08：15 發出尋客請求時，由于直接穿行r4和r5路段的花費最小，因此直接到達s6節點時間為上午08：16。此時對于傳統推薦算法而言，如果在r5路段未接到乘客，則會繼續選擇下一個行駛路段。假設選擇的行駛路段為r3，此時的花費成本為4.2。而根據式（8）可知，本文推薦的算法在該路段節點選擇等待2 min 接載到乘客所花費的成本最小，為1.2。原因是該路段在上午08：18時刻會有公交車到站，出現大量換乘乘客，乘客需求增加，導致該路段的接載概率提高，使得空閑司機更容易接載到乘客。

圖5 考慮等待時間的路線推薦案例Fig.5 Route recommendation case considering waiting time

4 實驗結果與分析

4.1 實驗數據及實驗環境

出租車數據：本文所采用的實驗數據來自上海10 694 名出租車司機在2015 年4 月1 日—2015 年4 月30 日生成的軌跡數據，其中每條數據的采集頻率是10 s，采集內容包含司機編號、位置、時間、速度、狀態等，詳細信息如表2 所示。

表2 上海市出租車GPS 軌跡數據示例Table 2 Example of GPS trajectories data taxis in Shanghai

從OpenStreetMap 中獲取上海市真實道路網絡的所有信息，其中包含465 735 個節點和197 758 個路段，并且在處理數據的過程中為每個路段標記其穿行時間、穿行距離和歷史接載數據。

本文實驗采用的性能評估和分析代碼是用python語言編寫，并在Intel?CoreTMi5-8250 CPU@1.60 GHz，8 GB內存64 位Windows10 系統上運行。

4.2 對比算法

為評估本文所提算法，采用以下4 種算法作為對比，進一步驗證該算法的有效性。

1）MNP 算法。為空閑司機推薦完整路線，通過凈利潤函數計算每個路段的潛在效益，并分別利用暴力法和遞歸策略篩選出最佳的推薦路線［5］。

2）InExperience 算法。利用歷史軌跡數據計算每個司機的歷史收入，把收入最低的前10%的司機作為無經驗司機，并選擇其空閑時所行駛的路線作為對比。

3）Random 算法。采用隨機方式為每種決策編號，并通過隨機函數選擇路線。

4）WTR 算法。本文提出的基于候客點規劃的空閑出租車路線推薦算法。

4.3 對比指標

本文選擇提升性能比rimprove作為實驗的性能指標，其含義為相比較其他算法所提升的百分比。當獲得一個司機請求時，從不同算法推薦路線所需要的花費成本、閑逛時間和閑逛距離3 個方面進行性能驗證，計算式如式（10）～式（12）所示：

式（10）表示本文推薦的算法WTR 與對比算法相比，在花費成本這一指標上所改善的性能百分比。式（11）表示本文推薦的WTR 算法相比較對比算法，在閑逛時間這一指標上所改善的性能百分比。式（12）表示本文推薦的WTR 算法相比較對比算法，在閑逛距離這一指標上所改善的性能百分比。

4.4 實驗結果

本文首先在上海市淮海中路附近（經度121.457 0°至121.486 8°，緯度31.219 8°至31.230 9°）隨機生成規模大小分別為10 個、100 個、1 000 個空閑司機請求數據。然后，對每個司機的請求位置和時間分別利用本文提出的WTR 算法和對比算法進行相應的路線推薦。其中，路段限制參數L和時間限制參數T分別是5 km 和10 min。最后，根據式（10）～式（12）做出相應的計算，對比實驗結果如圖6 所示。

圖6（a）表示空閑司機的推薦數量與推薦路線花費成本之間的實驗結果，從圖中可以看出本文考慮等待時間因素的推薦算法與算法MNP、InExperence、Random相比均有所提升。其中，當推薦次數為10 時，WTR 算法的花費成本相比較MNP、InExperience、Random 分別減少了44.6%、53.2%、49.45%。當推薦次數為100 時，分別減少了42.3%、51.5%、45.2%；當推薦次數等于1 000 時，分別減少了35.7%、40.1%、41%。對于整體的趨勢而言，隨著推薦次數的增加，推薦性能的百分比下降，這是因為隨著空閑司機的增多，可接載的乘客數量變得越來越少，這對于所有的推薦方法來說都將很難找到乘客，因此推薦成本的差距會變得越來越小。

圖6（b）表示空閑司機的推薦數量與推薦路線閑逛時間之間的實驗結果，從圖中可以看出本文考慮等待時間因素的推薦算法與算法MNP、InExperence 和Random 相比均有所提升。其中當推薦次數為10 時，WTR 算法的閑逛時間與算法MNP、InExperience、Random 相比分別減少了21.2%、33.3%、29.7%；當推薦次數為100 時，分別減少了18.3%、28.5%、12.2%；當推薦次數等于1 000時，分別減少了13.3%、12.2%、12.7%。隨著推薦次數的增加，閑逛時間的提升百分比不斷下降。這是因為隨著乘客需求的減少，任何一種推薦方法都難以接載到乘客，其閑逛時間的差距也會逐漸減小。

圖6 實驗結果對比Fig.6 Comparison of experimental results

圖6（c）表示空閑司機的推薦數量與推薦路線閑逛距離之間的實驗結果，從圖中可以看出本文提出的推薦算法WRT 與算法MNP、InExperence、Random 相比均有所提升。其中，當推薦次數為10 時，WTR 算法的閑逛距離與算法MNP，InExperience、Random 相比分別減少了41.7%、53%、48%；當推薦次數為100 時，分別減少了43.6%、57.3%、46.4%；當推薦次數為1 000 時，分別減少了46.4%、58.2%、76.1%。對于花費成本和閑逛時間的變化趨勢，閑逛距離隨著推薦次數的增加呈上升趨勢，原因是本文算法考慮了等待時間因素，當推薦次數逐漸增加而乘客需求不斷減少時，任何一種推薦方法都難以接到乘客。不同于MNP、InExperience、Random算法，本文所提算法在這種情況下更多選擇了停留等待的決策來減少行駛距離所帶來的成本。

由以上分析可以得出，本文所提基于候客點規劃的空閑出租車路線推薦算法通過考慮某些路段的等待因素，可以讓空閑司機更快地接載到乘客，從而減少司機的閑逛時間和閑逛距離，提高出租車的運輸效率。

5 結束語

現有的空閑司機路線推薦算法在考慮真實路網環境時忽略了路段可等待因素，導致所推薦的路線花費成本較高。為此，本文提出一種基于候客點規劃的空閑出租車路線推薦算法。通過處理出租車軌跡數據及統計每個路段的歷史接載信息，將軌跡點與真實路段進行匹配，并利用改進的多層感知機對出租車的接載概率進行建模。此外，在考慮路段可等待因素的基礎上設計一種路線推薦算法。在真實的上海出租車軌跡數據集上的實驗結果表明，相較于MNP、InExperence、Random 等算法，本文所提算法在花費成本、巡航時間以及巡航距離方面均有明顯減少。下一步將通過研究司機的目的地偏好，在本文工作基礎上為空閑司機設計個性化的推薦機制。