基于分時MDP 的出租車載客預測推薦技術研究

王桐，高山，龔慧雯，孫博

（1.哈爾濱工程大學信息與通信工程學院，黑龍江 哈爾濱 150001；2.哈爾濱工程大學先進船舶通信與信息技術重點實驗室，黑龍江 哈爾濱 150001）

1 引言

出租車空載時間是影響運營收益的主要因素之一。據調查，一些大型城市的出租車空載率已經高達40%～50%[1]，造成這一現象的主要原因是出租車在尋客時具有隨機性，司機對尋客路線和尋客地點缺乏足夠的認知。雖然打車軟件使出租車司機有了明確的載客地點，但仍屬于被動尋客模式，即在收到乘客的需求訂單后才能出發，當沒有乘客需求時，出租車又會處于盲目尋客狀態。針對上述問題，需要從全局優化角度出發，為出租車提供明確的主動尋客策略。

出租車軌跡數據挖掘是智能交通領域研究的主要方向之一[2-3]。傳統的方法[4-6]利用模糊聚類定義隸屬度值，模糊地將對象劃分為多個簇，無法保證在復雜城市環境中實現高準確度的預測和推薦。結合歷史軌跡進行數據分析并用于優化出租車系統已經得到了廣泛的研究[7-8]。目前，對該問題的多數研究根據熱點信息及熱點間距離進行推薦[9-13]，而沒有考慮空載時間，不能更好地反映出租車載客情況。由于出租車之間存在競爭性，即使熱點乘客數量多，也未必容易載客，即缺少對熱點載客概率等影響因素的充分考慮[14-15]，載客熱點間轉移概率的研究缺乏實時性。因此，構建更合理的“智能”出租車推薦策略是十分必要的。

本文以北京市出租車載客為例，對出租車空載時主動尋客、載客系統乘客預測及出租車載客策略推薦展開研究，主要貢獻如下。

1)載客熱點區域聚類研究中，考慮實際出租車載客點的分布特征，結合K-means 與DBSCAN（density-based spatial clustering of applications with noise）提出KAD（K-means and DBSCAN）聚類方法，使載客點聚類更合理。

2)在乘客預測方面，提出基于循環神經網絡（RNN,recurrent neural network）的分段預測（SPBR,segment prediction based on RNN）算法，通過實驗與支持向量回歸（SVR,support vector regression）、CART（classification and regression tree）和BP 神經網絡（BPNN,back propagation neural network）等算法進行對比，以證明SPBR 算法預測的準確性以及多次分段預測的合理性。

3)提出了基于分時馬爾可夫決策過程（TMDP,time-varying Markov decision process）的載客推薦策略，引入回報函數來衡量出租車收益，通過仿真驗證一個時段內TMDP 策略下出租車期望回報與歷史期望相比的優勢。

2 相關工作

出租車載客研究主要包括對出租車的路徑選擇、載客效益、載客推薦實時性等方面。

出租車路徑選擇方面[16-17]的研究內容主要為向空載出租車司機推薦一條最短時間或最大概率載客的路線。路徑研究中主要依據司機的駕駛偏好、指定出發點、目的地和出發時間，從大量軌跡數據中實現個性化的路線推薦[18]。Ge 等[19]提出了一種LCP（longest common prefix）算法，開發了一種高效移動推薦系統，該系統能夠為司機推薦一系列可能的乘客潛在點，系統從GPS 軌跡中提取出租車位置痕跡，并將這些位置聚集成多個有代表性的小區域，這些小區域被稱為從高利潤出租車司機的軌跡中學習的提升點，但這種算法為司機推薦駕駛方向而不推薦具體路線。針對尋客途中出現的道路擁堵現象，主要有2 種不同類型的查詢最短路徑的算法[20]：Query_FiST 基于堆的Bellman-Ford 算法和Query_BeST 擴展的Bellman-Ford 算法。這2 種算法只考慮了實時交通信息，沒有考慮乘客對出租車的需求量。Rong 等[21]考慮目的地對出租車的影響，使用馬爾可夫鏈為尋客過程建模，找到空載出租車的最佳行程，但是熱點之間的不確定因素會導致推薦結果的不準確。

在出租車載客效益方面，相關研究[22-23]主要側重于出租車運營收益，這主要與乘客供求關系、交通狀況等信息有關。此外，一些研究從出租車歷史收益角度出發，在大規模歷史出租車軌跡中挖掘高效運營出租車所行駛的路線，從而提高整體利潤[24]。文獻[25-26]根據經驗豐富的司機產生的歷史出租車軌跡，設計了一種兩階段路由算法，為最終用戶計算實際速度最快的定制路由，建立智能駕駛方向系統。Yuan 等[27]從乘客角度考慮，基于出租車產生的大量GPS 軌跡檢測停車位的方法，設計了一個概率模型來描述與時間相關的出租車行為（上下車、巡航、停車），并為出租車司機和乘客提供全市范圍的推薦系統，使其盡可能迅速地載客，并最大化下一次行程的利潤。但由于乘客的隨機性、流動性過強，在實踐中效果不佳[28]。上述方法多數只考慮短期收益，而未考慮未來時間連續載客規劃。

載客推薦實時性是研究出租車系統的又一個重要條件，路徑動態更新可以保證推薦策略的有效性[26]。Qian 等[29]利用在線地圖實時查詢方法，定義了3 種路線評價原則，分別為priority principle、decaying principle、sharing principle，進而設計了一個符合出租車司機需求的評價函數，提出了一種路徑分配機制來保證出租車司機推薦的公平性，并根據用戶需求和實時交通狀況給出最佳路徑。Huang 等[30]制定了一種TDVRP-PF（time-dependent vehicle routing problem with path flexibility）模型，采用Route-Path近似方法在隨機交通條件下為TDVRP-PF 生成近似最優解，將道路網絡中的路徑選擇和時間選擇因素相結合，確保了推薦的實時性。Lei 等[31]提出了“虛擬車輛”的概念，通過實時客流分布為出租車提供尋客時間短并且載客概率高的出行方案。“虛擬車輛”之間可以相互通信，了解周圍司機的駕駛行為，根據動態交通信息做出決策，從而達到整體車輛的最佳通行效率，但由于使用導航軟件的司機都存在自私行為，因此可能導致更嚴重的交通擁堵。胡昊然[32]提出了一種稱為cabrec 的路線推薦系統，提取載客熱點，利用啟發式算法構造熱點樹，熱點樹以當前位置為根節點，連接所有的載客點；同時，提出了一種估計各路線權重的概率模型，并給出了一組加權循環推薦方法。但是，其僅考慮了熱點和尋客時間的影響，忽略了熱點間的關系，缺乏整體性。

針對上述問題，本文采用回報函數衡量熱點區域價值。

3 基于RNN 的載客熱點分段預測和TMDP尋客策略推薦

由于乘客具有流動性和隨機性[28]，常用算法（如支持向量機、決策樹等）很難挖掘乘客數據的內在聯系，因此降低了預測的準確性。針對這一問題，本文提出SPBR 算法對出租車行駛區域進行乘客熱點分布預測，為出租車推薦尋客策略，實現出租車載客路線的長距離規劃。

為更加準確地預測以及合理地推薦，本文設計了出租車載客預測和推薦框架，如圖1 所示。該框架分為線下處理過程和線上處理過程兩部分，具體流程如下。

1)清洗出租車歷史軌跡原始數據，刪除無效、重復信息。

2)采用聚類算法處理出租車GPS 信息中的載客點（即乘客上車點）信息，得到載客熱點區域。

圖1 出租車載客預測和推薦框架

3)根據軌跡中的時間戳信息，統計每個區域各時間段的載客人數，得到區域載客人數向量，進而建立載客人數預測模型。

4)獲取載客區域最新的載客信息，輸入訓練好的預測模型中，模型的輸出即為預測的乘客數量。

5)將預測結果輸入推薦模型，推薦模型結合熱點間相關信息實現尋客推薦。

3.1 線下處理過程

由圖1 可知，本文算法在對出租車乘客預測和推薦時，需先對數據進行線下處理，包括數據預處理、必要信息的提取以及預測模型的訓練。

3.1.1 數據預處理和載客人數向量挖掘

由于出租車原始歷史數據中存在大量冗余及無效的信息，需要對其進行清洗以減少存儲空間、加快運算速度。本文所用數據來源為北京市28 000 輛出租車在2015 年12 月產生的GPS 軌跡數據，局部清洗后的數據格式如表1 所示。最終提取的載客軌跡為323 752 條，在此基礎上分析出租車載客點軌跡的分布情況[33]，選擇合適的聚類算法。本文采用KAD 的方式對北京市出租車不同場景下的載客點聚類。

K-means 聚類時，按照載客點之間的距離來區分不同的簇。K-means 算法收斂速度快、易實現，當不同熱點區域之間有較明顯的區別時，K-means 算法有很好的聚類效果。通過K-means 聚類流程可以發現，算法需要的參數僅目標熱點數K，不受其他參數影響。但K值的確定往往比較困難，需要提前對樣本集分析來選取較好的K值。根據K-means 算法流程可知，質心的迭代更新是在初始隨機選擇質心的基礎上進行的，這就導致最終聚類結果會受初始質心的影響，所以聚類結果具有一定的不確定性。另外，K-means 算法默認將所有載客點都視為樣本，導致其對噪聲和異常點比較敏感，如果樣本中離散和隨機的載客點比較多，會對結果會產生較大的負面影響。

表1 局部清洗后的數據格式

K-means 算法和DBSCAN 算法對郊區載客點的聚類效果如圖2 所示。K-means 算法雖然將不同的熱點區域明顯地進行區分，但由于郊區載客點的稀疏性，一些隨機的載客點被劃分到不同熱點中，導致載客熱點區域范圍變大，但這些載客點本身不具有可分析性，會導致出租車在某個區域尋客困難而失去推薦的作用。DBSCAN 算法將某些離散點排除，只將密集的載客點聚為一類，每個區域范圍較小，提高了對區域進一步處理的準確度，因此，郊區載客點聚類適合采用DBSCAN 算法。

圖2 K-means 算法和DBSCAN 算法對郊區載客點的聚類效果

K-means 算法和DBSCAN 算法對市區載客點的聚類效果如圖3 所示。從圖3 可以看出，在市區中，載客點沿道路呈網絡狀分布，由于DBSCAN 算法按照密度可以將簇聚類為任意形狀，因此DBSCAN 算法最終形成的簇集沿道路分布而不是形成區域，而且由于道路的相互交叉，簇集之間也會以不規則的形狀相互交錯，這種形式的簇集不適合作為載客熱點區域。K-means 算法避免了上述問題，其把載客點劃分成相對均勻的若干個載客熱點區域，區域間相鄰但不發生交錯，能夠很好地對載客區域進一步處理。

圖3 K-means 算法和DBSCAN 算法對市區載客點的聚類效果

DBSCAN 算法的載客熱點之間往往相隔一定的距離，這將導致在進行出租車載客推薦時不僅需要載客熱點的相關信息，還要考慮從某個熱點到另一熱點所經路徑的有關信息（如路徑上的載客概率），這會大大增加數據處理的難度。因此，市區內載客點聚類適合采用K-means 算法。

本文采用KAD 方式對北京市出租車不同場景下載客點進行聚類。已知北京市總面積s=16 410 km2，根據相關文獻，出租車平均尋客時間z=15 min[34]，假設出租車行駛的平均行駛速度為v=30 km/h[35]，則劃分的區域半徑r=vz/60，則載客區域個數n=s/r2=93，為便于分析和計算，本文將載客區域數量設為n=100。郊區采用DBSCAN 算法，調整參數進行仿真，直到每一簇都具有較好的聚類效果，此時聚類結果為32 個熱點區域；基于K-means 算法的市區載客點聚類設定熱點數量為K=68。依次標記郊區熱點區域為0～31，市區熱點區域為32～99。

為保證時間有效性，出租車載客區域還需與每個區域不同時間段歷史載客人數相對應。根據平均尋客時間，令每段時間z=15 min，即將每個區域全天劃分成24×60/15=96 個時間段。根據GPS 軌跡所包含的時間戳，統計各個時間段內載客點的數量，對每個區域進行向量化處理構成96 維的向量。以區域i為例，每天載客人數向量為Vi={b0,b1,…,b95}，擴展到一個月（即30 天），則Vs={b0,b1,…,b2879}，得到區域i的載客人數向量數據集為

其中，m表示預測模型的輸入；n表示輸出對比；d表示用于預測的時間長度；k表示當前時間段與預測時間段的間隔數，例如，k=0 表示通過前d段數據預測第d+1 段的載客人數，k=1 表示通過前d段數據預測第d+2 段的載客人數，即輸入和輸出時間段距離為2。

3.1.2 神經網絡預測模型

對于出租車載客熱點預測問題，由于大數據的復雜性，用傳統機器學習算法進行預測會達到極限，而神經網絡在海量數據面前能夠展示自己的潛力。另一方面，在出租車乘客預測中，載客人數具有時序性，經典BPNN 難以表征時間序列數據的內在聯系，神經網絡中隱藏層的值只取決于當前輸入，不同樣本間的輸入、輸出相互獨立，許多情況下不能實現很好的預測，因此本文結合RNN 的思想，對出租車乘客數量進行預測。

本文出租車乘客數量的預測中，采用RNN 作為預測模型，模型輸入為歷史前d段載客人數，輸出為第d+1 段的載客人數，即循環神經網絡輸入層為d維向量，輸出層為一維向量。考慮出租車載客系統長期的優化，僅得到未來最近一段時間的預測結果是不夠的，因此，本文進一步地提出SPBR 算法對出租車系統進行未來多個時間段的人數預測。

各個區域乘客信息通過式(3)提取處理得到數據集Dk，k=0,1,2,…。將數據集Dk的70%作為訓練集輸入RNN，剩余的30%作為測試集。在實際訓練中對隱藏層層數、每層神經元個數以及神經元激活函數等參數不斷優化，訓練得到與k有關的K_RNN 模型。預測出租車乘客數量時，從當前每個區域數據中獲取最新d段載客人數，根據預測目標段加載對應K_RNN 模型，模型的輸出即為相應時間段的預測值，最后將所有預測值生成向量作為推薦的基礎。SPBR 算法預測模型結構如圖4 所示。

圖4 SPBR 算法預測模型結構

根據k的不同取值，SPBR 算法能夠有效地挖掘某一時間段輸入與輸出值的內在聯系。通過多次分段預測準確獲取熱點區域未來每個時間段的載客人數，并將預測結果生成向量用于推薦。同時，對訓練集進行更新，采集區域產生的實際載客信息進行緩存，當緩存數據達到一定量時，將其加入訓練集并重新訓練K_RNN。隨著訓練數據的不斷積累，得到的乘客預測模型將具有更強的擬合能力，進而保證了數據集的有效性以及預測結果的準確性。

3.2 線上處理過程

由圖1 可知，通過線下處理，乘客數量預測可以為出租車司機提供更準確的載客參考，但考慮到載客區域之間的聯系以及出租車長期的收益，單純將所有區域的乘客預測信息推薦給司機缺乏實際依托。因此，本文擬建立一個出租車載客推薦模型，對實時數據進行線上處理。當出租車處于空載時，依據所在區域及其他各區域的相關信息（包括載客、轉移概率等信息），結合SPBR 算法預測的各區域未來可能的乘客數量，共同輸入推薦模型，以計算出更優的載客策略進行推薦。

3.2.1 基于MDP 的載客推薦模型

出租車載客推薦框架的難點在于如何構建合理的推薦模型。該模型需考慮出租車載客推薦的特點，模型輸出的載客策略相當于司機所采取的行為，并且最終載客結果只由當前所在區域及采取的行為決定。該推薦模型具有隨機性策略與回報，為序貫決策的數學模型，因此本文采用馬爾可夫決策過程（MDP,Markov decision process）為出租車司機提供合理的載客策略。

將MDP 表示為一個五元組(S,A,Psia,γ,Rsia)。MDP 方法與出租車載客推薦問題相結合，則司機在載客點的行為集合A={等待,移動到其他區域}，而出租車司機對下一載客點的選擇取決于當前所在位置，符合MDP 無后效性的性質；Psia為載客區域si∈S下司機進行動作a∈A后轉移到下一載客區域的概率矩陣；γ∈(0,1)為折扣因子；Rsia是在狀態si∈S下進行a∈A后的回報；S在MDP 中表示可能的狀態集合，此處結合出租車推薦問題表示載客區域集合，數量N=100。

3.2.2 分時馬爾可夫決策過程

MDP 中狀態轉移概率矩陣Psia是固定不變的，即載客區域之間的轉移概率固定。該假設顯然不符合出租車載客的實際情況，區域之間的轉移概率在一天之中會隨著時間的變化而改變。例如，早上的乘客偏向從生活區到工作區，而傍晚的乘客更偏向由工作區返回生活區。因此，通過傳統MDP 尋找最優載客策略缺乏合理性。為滿足區域之間的轉移概率隨時間段變化的特點，本文提出TMDP 用于推薦司機尋找最優載客策略。

TMDP 中的轉移概率矩陣Psia如表2 所示。將15 min 劃分為一個時間段，TMDP 將每個載客區域擴展為96 個時段。(0≤i≤99，0≤m≤95)表示區域i的第m個時間段的狀態，因此狀態集合S的數量擴展為N=100×96，行為a下的TMDP 轉移概率矩陣為9 600×9 600 的矩陣。

表2 TMDP 中的轉移概率矩陣Psia

TMDP 中將狀態集合由單純區域集合擴展為區域加時間段集合，狀態轉移概率矩陣Psia的復雜度隨之提高。當行為是等待時，區域不會發生變化，且出租車不可能由未來回到過去，所以在a為等待的情況下，只有當i=j且n不是m之前的時段時有意義，其余為0；在a為移動到其他區域的情況下，只有當i≠j且n不是m之前的時段時有意義，其余為0。

當時間段m=95 時，未來時段從第二天的m=0時段算起，因此，表2 是可循環的。例如可以表示在區域0 從第一天的第95 個時間段到區域0第二天的第0 個時間段的轉移概率，可以表示在區域0 從第一天的第95 個時間段到區域1 第二天的第0 個時間段的轉移概率。由于分時馬爾可夫決策過程和馬爾可夫決策過程一樣為無限步驟，即

因此，表2 的可循環性能夠很好地滿足分時馬爾可夫決策過程。在出租車系統中，出租車的收益受到各種因素干擾，所以回報函數應考慮多方面的影響。出租車的空載對其收入回報呈負面影響，而載客區域的預期載客人數及載客概率對收入呈正面影響。定義從狀態到的回報為

其中，表示在時段n中所有經過區域sj時發生空載狀態的出租車數量，即在區域sj的時段n內，出現過載客狀態為0的出租車數量；表示時段n內在區域sj尋到客的出租車數量，即在區域sj的時段n中，載客狀態由0 跳變為10 000 000 的出租車數量。

由式(5)可知，出租車的載客回報與下一載客區域的預測載客人數以及載客概率成正比，與從當前區域到下一區域的空載尋客時間成反比，考慮所有區域和所有時間段，通過式(5)得到的回報函數可以表示為矩陣R∈9600×9600。參照3.1.2 節，由于預測得到的未來多個時間段的載客人數因輸出段與輸入段距離增加導致預測誤差擴大，且出租車司機更注重較近時段的收益。因此，在TMDP 中引入折扣因子，累計回報表示為

其中，R(s0)表示在當前狀態s0采取行為后達到下一狀態s1的回報，R(s1)表示在狀態s1采取行為后到達下一狀態s2的回報，依次類推。狀態、行動、轉移概率和回報間的關系如表2 和式(5)所示，轉移概率以及回報由初始狀態和采取的行動決定。TMDP 可以表現出各區域各時間段之間的關系，因此能夠得到更加合理的載客策略推薦結果。綜上所述，TMDP 推薦模型可以表示為五元組(S∈1×9600,A∈?1×2,P∈?9600×9600×2,γ,R∈?9600×9600×2)，其中，折扣因子γ由具體情況決定。

3.2.3 狀態轉移概率矩陣的提取

構建TMDP 的模型后，需要獲取狀態轉移概率矩陣P。線下處理清洗數據后，從表1 中可知，在同一出租車ID 下，載客狀態由0 到10000000 表示出租車的空載到載客的過程，載客狀態由10000000到0 表示出租車從載客到空載的過程。針對出租車載客策略，對表1 數據進一步過濾，使每輛出租車的起始狀態都從空載開始，到載客結束。

由于熱點的劃分按照不同區域由KAD 方法聚類得到，分別用0～99 代表聚類得到的100 個載客區域，計算每條尋客軌跡的所屬區域，并將區域標號作為新的字段添加到軌跡信息中。基于TMDP 的推薦是隨時間變化的，區域間的轉移概率可根據時間步長Ts=15 min 劃分的時間段來求得。又因為TMDP 的狀態轉移概率與行為a有關，求解轉移概率矩陣（a為移動）的具體步驟如下。

1)查找出租車在區域s中某一時間段t的軌跡點。遍歷數據集D，如果D中某條軌跡所屬區域為s，其時間戳對應所屬時間段t，且該軌跡為空載狀態，將其標記為(s,t)。

2)求(s,t)在a為移動時的轉移概率。(s,t)下一條為同一出租車在載客狀態下的軌跡信息，判斷載客狀態的軌跡點所屬區域，若不屬于s，則說明該出租車在其他區域s'尋到乘客，根據時間戳求得在s'時所屬時間段t'。統計從(s,t)出發到所有其他(s',t')載到乘客的軌跡點數量，并計算概率得到執行動作a為移動時(s,t)的轉移概率p1(s,t)。具體判斷的條件為

其中，e是數據集D中的一條軌跡，e[0]是出租車編號，e[1]是時間戳，e[0]是緯度，e[3]是經度，e[4]是載客狀態，e[5]是軌跡所屬區域，e.next 是軌跡e的下一條軌跡，startTime 是一天的初始時間戳。

3)求(s,t)在a為等待時的轉移概率。如果(s,t)下一條載客狀態的軌跡點仍屬于區域s，說明該出租車接到乘客，根據時間戳求得在區域s載到乘客時所屬時間段t'。統計從(s,t)出發到所有其他(s,t')載到乘客的軌跡點數量，并計算概率得到執行動作a為等待時(s,t)的轉移概率p2(s,t)。判斷的具體條件為

4)求轉移概率矩陣。將s擴展成S=[0,100]，t擴展成T=[0,96)，得到a為等待時的概率轉移矩陣P1，a為移動時的概率轉移矩陣P2。生成和行為有關的狀態轉移概率矩陣的具體方法為

可見P1和P2是不同行為對應的9 600×9 600轉移概率矩陣，最終狀態轉移概率矩陣表示為P=[P1,P2]。

3.2.4 TMDP 回報矩陣分析

由式(5)可知，回報矩陣R需根據載客概率矩陣Q、尋客時間矩陣E及預測的載客人數矩陣X得出。

1)載客概率矩陣Q

每個區域的載客概率由歷史軌跡數據統計得到，與當前所執行的行為無關，因此載客概率矩陣不需要劃分不同行為。根據式(6)分別求出100 個區域在96 個時間段的載客概率矩陣Q∈?100×96，則回報函數矩陣表示為R∈?9600×9600，為保證數據形式的一致性，需要先將Q∈?100×96轉化為Q∈?1×9600，然后對Q∈?1×9600復制9 600 次得到Q∈?9600×9600。

2)尋客時間矩陣E

從狀態到的平均尋客時間為

其中，當從狀態sim不可能到達sjn時，，從而說明該情況下達到最差回報。為了避免過小引起計算的不方便，引入參數3 600。

3)載客人數矩陣X

Xjn是通過SPBR 預測得到的區域sj在未來第n個時段的乘客人數。TMDP 的狀態?值函數為

隨著SPBR 輸入時間段和輸出時間段距離的增加，預測未來無限個時間段的載客人數誤差會越來越大，考慮到出租車司機對近期收入的注重，因此沒有必要預測距離當前過遠的時間段。適用于TMDP 的Xjn為

其中，l為確定輸入段和輸出段的臨界距離。當距離小于或等于l時，Xjn由SPBR預測得到；當距離大于l時，Xjn取訓練集數據對應時間段的平均值。

3.2.5 TMDP 求解過程

TMDP 的狀態?值函數可表示為

TMDP 的目的是求解最大期望回報，即最優狀態?值函數V*(s)，從而得到最優策略π*(s)，最終將最優策略推薦給出租車司機。本文采用策略迭代算法求解TMDP，策略迭代算法如算法1 所示。

TMDP 求解過程從初始化策略出發，實施策略評估，改進策略，經過持續迭代更新，直到策略收斂。具體步驟如下。

1)初始化所有狀態的V(s)以及π(s)（初始化為隨機策略）。

2)用當前的V(s)對策略進行評估，計算出每一個狀態的V(s)，直到V(s)收斂。

3)用步驟2)得到的當前策略評估函數V(s)進行改進，在每個狀態s時，對每個可能的動作a，計算采取這個動作后到達下一狀態的期望，選取期望價值函數最大的動作來更新策略π(s)，然后再次循環步驟2)和步驟3)，直到V(s)和π(s)全部收斂。

策略迭代過程如圖5 所示，該過程是一個反復優化狀態?值函數V和策略π的過程，當V(s)和π(s)全部收斂時即可得到最優策略π*和最優狀態?值函數V*。

圖5 策略迭代過程

通過TMDP 求出最優策略的矩陣形式如表3 所示。表3 為出租車在每個區域每個時間段下應選的最優載客策略，其中，1 代表在當前區域等待，2 代表去其他區域尋客。出租車處于空載狀態時，確定所處區域和對應時間段，通過與表3 匹配得到最優策略。當推薦的最優策略為2 時，出租車應在當前區域繼續等待。當推薦的最優策略為1 時，出租車應主動到其他區域尋客。

表3 TMDP 最優策略矩陣形式

4 實驗結果與分析

4.1 乘客熱點區域的預測結果及誤差分析

通過對出租車預測模型進行仿真，本文進一步對影響預測結果的因素進行討論，并將其準確性和實際要求相結合進而確定相關參數，以達到準確度與實用性的統一。

4.1.1 預測結果及性能比較

在預測模型中基于RNN 對出租車歷史載客數據進行分段訓練和預測，將載客數據集的70%（21天）用于神經網絡的訓練，剩余30%（9 天）作為測試，設每段時間步長Ts=15 min，用于預測的歷史時間長度e=1，令k=0，即SPBR 輸入和輸出的數據沒有時間段間隔。SVR、CART 和BPNN 作為比較算法。利用相同數據集分別訓練SVR、CART、BPNN 和SPBR 模型并進行預測，結果如圖6 所示。

圖6 預測結果對比

從圖6 可以看出，SPBR 整體預測性能較好，能夠準確還原每一時間段的乘客數量變化趨勢。為進一步評估算法預測效果，采用均方根誤差（RMSE,root mean square error）和平均相對誤差（MRE,mean relative error）衡量預測算法性能。

其中，pre 為算法預測結果序列，true 為實際序列，m為序列長度。SVR、CART、BPNN 和SPBR 預測結果誤差對比如圖7 所示，相較于SVR、CART、BPNN，SPBR 的RMSE 分別降低了67.6%、71.1%、64.5%，MRE 分別降低了59.1%、58.3%、6.0%。

圖7 算法誤差對比

結合圖6 和圖7，在00:00～06:00（即時間段0～24），乘客稀疏并且偶然性較大，在SVR 中很難找到完全契合本數據集的核函數，導致SVR 的預測結果出現一定程度的偏離；基于CART 的預測結果在該時間段有著較高的擬合程度，但由于異常突發值的存在導致誤差擴大；BPNN 和SPBR 在該時段可以很好地擬合。

6:00 之后的時間段，SVR、CART 和BPNN 的預測結果比真實數據的波動平緩，但只能在大致趨勢上還原，尚缺乏局部準確性。SPBR 由于其強大的自組織能力以及針對時間序列的遞歸性，可以捕捉到前后數據間的關系，對全天數據可以很好地擬合。

4.1.2 歷史時間長度對預測結果的影響

本節對e的最佳取值進一步討論。歷史數據中，各時間段的載客人數有潛在的聯系，因此歷史時間長度的選取對預測結果有著不可忽略的影響。

歷史時間長度e決定RNN 輸入層的緯度，即輸入層神經元的個數，所以選取不同的e，RNN 的結構會發生改變并需要重新訓練。令e=1,2,3,4,5,6。設k=0，處理數據得到數據集Dke。Dke的70%用于訓練RNN，30%用于測試，圖8 為測試集不同e下的平均誤差比較。根據圖8，對于SVR 和CART，當e=2 時誤差達到最小，但誤差仍大于RNN；SVR和BPNN 的RMSE 隨e的變化不明顯，但MRE出現較大起伏。因此，結合RMSE 和MRE 衡量各算法的預測誤差是合理的。當e=1 時SPBR 誤差最小，因此用SPBR 進行載客數量預測時只需要根據前一段歷史數據即可保證對下一段預測的最小誤差。

圖8 測試集不同e 下的平均誤差比較

4.1.3 分段預測

基于RNN 的多次分段預測方法中，輸出層神經元數量為1，每次預測只得到未來某一個時間段的載客人數。SPBR 通過多次預測可得到未來每個時間段的預測數據，進而得到多段預測結果。使用回歸預測時，神經網絡本身可以通過增加輸出層神經元數量實現對未來的一次性多段預測，例如預測某個區域未來6 個時間段的載客人數，只需將RNN 輸出層神經元數目設定為6 就能一次性完成預測。

將Dk的70%作為訓練集，30%作為測試集，令k=0,1,2，e=1，即利用某個區域歷史時間段的載客人數分別預測未來最近3 個時間段的載客人數，RNN 輸入和輸出層神經元個數都為1，分別訓練得到與k有關的K_RNN 模型，9 天數據的平均預測結果作為測試集，對應誤差如圖9 所示。隨著RNN輸入時間段和輸出時間段距離的增加，SPBR 模型預測誤差變大。

圖9 分段預測結果對應誤差

作為對比算法，多段預測的數據集設置方式選用與分段預測相同，令歷史長度e=1，k=2，即一次性預測時間段數為3，得到的每個時間段平均預測結果及誤差如圖10 所示。

對比圖9 與圖10 的預測結果可知，多段預測能一次性得到未來多段的結果，且3 個時間段的預測誤差很接近。但由于訓練時要兼顧多段預測的準確度，導致不能充分學習每段輸出與輸入之間的關系，因此預測誤差整體偏大。SPBR 通過單獨訓練每段數據能夠最大限度地擬合。同時在實際情況中司機更注重的是近期收入，因此要保證第一段預測的準確性，SPBR 對每個時間段分別預測滿足了這一要求。通過比較發現，即使輸入段與輸出段的距離增大后SPBR 預測結果的誤差也隨之增大，但相同時間間隔下仍比一次性多段預測更準確。

4.1.4 時間步長對預測結果的影響

前文分析中，時間劃分默認為15 min/段，但實際中選取時間步長對預測結果的影響需要進一步討論。令時間步長Ts分別為10 min/段、15 min/段、20 min/段、30 min/段，用于預測的歷史時間長度e=1，預測目標是下一段的載客人數。

圖10 多段預測結果及誤差

基于SPBR 的不同時間步長的預測結果及誤差如圖 11 所示。當時間步長Ts=10 min 時，RMSE=9.46，達到最小，但此時MRE=0.133，遠遠大于其他情況。這是因為當Ts較小時，每段步長所對應的累計載客人數同樣較少，導致即使預測偏差較大也會因為基數小而使RMSE 較小。綜合RMSE和MRE 可知，步長Ts=15 min 最合適。

4.1.5 過擬合對預測結果的影響

由于訓練數據包含抽樣誤差，在訓練時神經網絡將訓練集中獨有的特征視為整個數據集的共有特征，由此產生的過擬合是神經網絡中的常見問題，即在訓練時誤差不斷下降但測試集誤差卻上升。為避免過擬合，在網絡中添加了Dropout 層，其原理是模型每次更新參數時隨機斷開一定百分比的輸入神經元連接。

圖11 基于SPBR 的不同時間步長的預測結果及誤差

經過多次調參和訓練發現，更新參數時隨機斷開20%的輸入神經元連接可以實現有效改進。如圖12 所示，添加Dropout 層的RNN 的擬合效果明顯優于未添加Dropout 層的RNN。

4.2 載客推薦結果分析

本文采用TMDP 算法實現基于SPBR 預測結果的出租車司機載客策略推薦。假設當前時刻為t0，歷史長度e=1，時間步長為15 min/段，因此獲取t0時刻前15 min 各載客區域的上車人數作為SPBR 預測模型的輸入，預測結果中未來多段的乘客人數作為TMDP 的推薦基礎。

圖12 Dropout 層對預測誤差的影響

4.2.1 TDMP 回報矩陣分析

本節實驗分析TMDP 回報矩陣中載客人數矩陣的X臨界距離l。訓練集21 天的載客人數求平均值與測試集一天載客人數的對比結果，如圖13所示。

圖13 訓練集平均載客人數與測試集一天載客人數對比

對比圖13 與圖9 可知，訓練集平均載客人數與實際誤差較大，遠遠不如通過SPBR 預測數據準確；當SPBR 輸入段和預測段距離增加，預測誤差大于訓練集平均值誤差時，可用訓練集平均值代替SPBR 預測。SPBR 預測誤差隨輸入段和預測段距離的變化如圖14 所示。

當預測距離大于6 時，基于SPBR 預測的RMSE和MRE 都大于測試集平均值的誤差。式(13)的具體形式可寫為

圖14 SPBR 預測誤差

載客人數矩陣X∈100×96，為了保證數據形式的一致性，與載客概率矩陣相同，將X∈100×96轉化成X∈9600×9600，可求得回報矩陣R=XQG，即矩陣對應位置元素相乘。

4.2.2 TMDP 推薦結果分析

當預測距離大于6 時，SPBR 預測的誤差大于歷史平均誤差，所以在TMDP 推薦時，折扣因子要盡可能減少預測距離大于6 的階段所占比重。根據MDP 原理，當預測距離為7 時的回報項為γ6R(s)，因為0.56=0.015≈0，所以令折扣因子γ=0.5。獲取TMDP 的五元組(S,A,Psia,γ,Rsia)各個參數。

通過策略迭代求得狀態?值函數V(s)達到最大值的最優策略函數π*(s)。

TMDP 推薦結果策略如表4 所示，si(0≤i＜100)表示出租車所在區域，Tj(0≤j＜96)表示出租車所在時間段。策略為1 表示出租車空載狀態下TMDP 建議在當前區域等待。策略為2表示出租車空載狀態下TMDP建議去往其他區域尋客。基于表4 的推薦策略，每個狀態可得到的最大期望回報矩陣如表5 所示。

表4 TMDP 推薦結果策略

表5 TMDP 最大期望回報矩陣

每個區域每個時間段都有對應的最大期望回報，但有些區域的期望回報普遍較大。例如，經過推薦，s2和s99各時間段的回報都要高于其他區域。因為每個載客區域由載客點聚類得到，區域s2和s99的聚類中心點分別為(116.42224,39.89670)和(3991071,11645097)。

載客熱點s2在北京站附近，s99在中國國際貿易中心附近，這些區域客流量大，出租車處于空載狀態時只需選擇在當前區域等待就會得到最大的期望回報。該例在一定程度上證明了TMDP 推薦符合實際情況。

采用歷史平均回報作為對比，分析TMDP 推薦的效果，令判斷條件為

可從歷史數據中求得與行為無關的狀態轉移概率矩陣P'，當最大預測距離為6 時，對應TMDP中折扣因子γ=0.5，定義矩陣Z為

其中，R為回報矩陣；Z∈?9600×9600，其每一行代表從相應狀態出發經過6 次轉移分別到9 600 個狀態產生的期望回報。將Z的每行所有元素相加得到Z′∈?9600×1，表示從每個狀態出發總的期望回報，為了方便對比，將Z'轉換為歷史期望回報矩陣H，如表6 所示。

表6 歷史期望回報矩陣

為了整體分析TMDP 的推薦結果，分別求表5和表6 中每列的平均值，得到TMDP 所有區域平均期望回報∈?96×1和歷史所有區域平均期望回報∈?96×1，和的對比如圖15 所示。

圖15 區域平均期望回報

在每個時間段，基于TMDP 推薦的載客策略平均期望回報普遍大于歷史平均期望回報。由式(22)計算，結果表明基于TMDP 推薦的平均一個時間段（15 min）的回報增長率為35.9%。

綜上所述，通過TMDP 推薦的載客策略，出租車在15 min 內的預期回報相比原來平均增長了35.9%，所以TMDP 能夠使司機收入得到大幅提升。由于TMDP 推薦是基于歷史載客數據，因此TMDP推薦的實質是將挖掘出的歷史乘客信息與出租車行為進行有效分析，實現對出租車的合理調度，有助于降低出租車空載時間、提高出租車司機收入、緩解交通擁堵等。

5 結束語

本文的研究內容包括預測和推薦兩部分。針對乘客預測，本文提出了SPBR 算法，在傳統出租車載客預測算法的基礎上考慮了數據的時間序列性，將循環神經網絡運用到載客預測中。通過仿真分析，與SVR 算法、CART 算法和BPNN 算法進行對比，驗證了SPBR 算法預測的準確性；通過與一次性多段預測比較驗證了多次分段預測的合理性。針對載客推薦，與以往只考慮即時收益不同，本文研究了如何對出租車載客進行長遠規劃從而最大化期望回報，結合馬爾可夫決策過程和出租車推薦系統的特點，提出了分時馬爾可夫決策過程實現推薦。仿真結果表明，采用推薦策略的出租車期望回報相比歷史期望回報在一個時間段內提升了35.9%。