基于分時MDP 的出租車載客預(yù)測推薦技術(shù)研究

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

（1.哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱 150001；2.哈爾濱工程大學(xué)先進(jìn)船舶通信與信息技術(shù)重點實驗室，黑龍江 哈爾濱 150001）

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

圖1 出租車載客預(yù)測和推薦框架

3)根據(jù)軌跡中的時間戳信息，統(tǒng)計每個區(qū)域各時間段的載客人數(shù)，得到區(qū)域載客人數(shù)向量，進(jìn)而建立載客人數(shù)預(yù)測模型。

4)獲取載客區(qū)域最新的載客信息，輸入訓(xùn)練好的預(yù)測模型中，模型的輸出即為預(yù)測的乘客數(shù)量。

5)將預(yù)測結(jié)果輸入推薦模型，推薦模型結(jié)合熱點間相關(guān)信息實現(xiàn)尋客推薦。

3.1 線下處理過程

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

3.1.1 數(shù)據(jù)預(yù)處理和載客人數(shù)向量挖掘

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

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

表1 局部清洗后的數(shù)據(jù)格式

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

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

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

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

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

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

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

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

3.1.2 神經(jīng)網(wǎng)絡(luò)預(yù)測模型

對于出租車載客熱點預(yù)測問題，由于大數(shù)據(jù)的復(fù)雜性，用傳統(tǒng)機器學(xué)習(xí)算法進(jìn)行預(yù)測會達(dá)到極限，而神經(jīng)網(wǎng)絡(luò)在海量數(shù)據(jù)面前能夠展示自己的潛力。另一方面，在出租車乘客預(yù)測中，載客人數(shù)具有時序性，經(jīng)典BPNN 難以表征時間序列數(shù)據(jù)的內(nèi)在聯(lián)系，神經(jīng)網(wǎng)絡(luò)中隱藏層的值只取決于當(dāng)前輸入，不同樣本間的輸入、輸出相互獨立，許多情況下不能實現(xiàn)很好的預(yù)測，因此本文結(jié)合RNN 的思想，對出租車乘客數(shù)量進(jìn)行預(yù)測。

本文出租車乘客數(shù)量的預(yù)測中，采用RNN 作為預(yù)測模型，模型輸入為歷史前d段載客人數(shù)，輸出為第d+1 段的載客人數(shù)，即循環(huán)神經(jīng)網(wǎng)絡(luò)輸入層為d維向量，輸出層為一維向量?？紤]出租車載客系統(tǒng)長期的優(yōu)化，僅得到未來最近一段時間的預(yù)測結(jié)果是不夠的，因此，本文進(jìn)一步地提出SPBR 算法對出租車系統(tǒng)進(jìn)行未來多個時間段的人數(shù)預(yù)測。

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

圖4 SPBR 算法預(yù)測模型結(jié)構(gòu)

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

3.2 線上處理過程

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

3.2.1 基于MDP 的載客推薦模型

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

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

3.2.2 分時馬爾可夫決策過程

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

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

表2 TMDP 中的轉(zhuǎn)移概率矩陣Psia

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

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

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

其中，表示在時段n中所有經(jīng)過區(qū)域sj時發(fā)生空載狀態(tài)的出租車數(shù)量，即在區(qū)域sj的時段n內(nèi)，出現(xiàn)過載客狀態(tài)為0的出租車數(shù)量；表示時段n內(nèi)在區(qū)域sj尋到客的出租車數(shù)量，即在區(qū)域sj的時段n中，載客狀態(tài)由0 跳變?yōu)?0 000 000 的出租車數(shù)量。

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

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

3.2.3 狀態(tài)轉(zhuǎn)移概率矩陣的提取

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

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

1)查找出租車在區(qū)域s中某一時間段t的軌跡點。遍歷數(shù)據(jù)集D，如果D中某條軌跡所屬區(qū)域為s，其時間戳對應(yīng)所屬時間段t，且該軌跡為空載狀態(tài)，將其標(biāo)記為(s,t)。

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

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

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

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

可見P1和P2是不同行為對應(yīng)的9 600×9 600轉(zhuǎn)移概率矩陣，最終狀態(tài)轉(zhuǎn)移概率矩陣表示為P=[P1,P2]。

3.2.4 TMDP 回報矩陣分析

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

1)載客概率矩陣Q

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

2)尋客時間矩陣E

從狀態(tài)到的平均尋客時間為

其中，當(dāng)從狀態(tài)sim不可能到達(dá)sjn時，，從而說明該情況下達(dá)到最差回報。為了避免過小引起計算的不方便，引入?yún)?shù)3 600。

3)載客人數(shù)矩陣X

Xjn是通過SPBR 預(yù)測得到的區(qū)域sj在未來第n個時段的乘客人數(shù)。TMDP 的狀態(tài)?值函數(shù)為

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

其中，l為確定輸入段和輸出段的臨界距離。當(dāng)距離小于或等于l時，Xjn由SPBR預(yù)測得到；當(dāng)距離大于l時，Xjn取訓(xùn)練集數(shù)據(jù)對應(yīng)時間段的平均值。

3.2.5 TMDP 求解過程

TMDP 的狀態(tài)?值函數(shù)可表示為

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

TMDP 求解過程從初始化策略出發(fā)，實施策略評估，改進(jìn)策略，經(jīng)過持續(xù)迭代更新，直到策略收斂。具體步驟如下。

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

2)用當(dāng)前的V(s)對策略進(jìn)行評估，計算出每一個狀態(tài)的V(s)，直到V(s)收斂。

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

策略迭代過程如圖5 所示，該過程是一個反復(fù)優(yōu)化狀態(tài)?值函數(shù)V和策略π的過程，當(dāng)V(s)和π(s)全部收斂時即可得到最優(yōu)策略π*和最優(yōu)狀態(tài)?值函數(shù)V*。

圖5 策略迭代過程

通過TMDP 求出最優(yōu)策略的矩陣形式如表3 所示。表3 為出租車在每個區(qū)域每個時間段下應(yīng)選的最優(yōu)載客策略，其中，1 代表在當(dāng)前區(qū)域等待，2 代表去其他區(qū)域?qū)た?。出租車處于空載狀態(tài)時，確定所處區(qū)域和對應(yīng)時間段，通過與表3 匹配得到最優(yōu)策略。當(dāng)推薦的最優(yōu)策略為2 時，出租車應(yīng)在當(dāng)前區(qū)域繼續(xù)等待。當(dāng)推薦的最優(yōu)策略為1 時，出租車應(yīng)主動到其他區(qū)域?qū)た汀?/p>

表3 TMDP 最優(yōu)策略矩陣形式

4 實驗結(jié)果與分析

4.1 乘客熱點區(qū)域的預(yù)測結(jié)果及誤差分析

通過對出租車預(yù)測模型進(jìn)行仿真，本文進(jìn)一步對影響預(yù)測結(jié)果的因素進(jìn)行討論，并將其準(zhǔn)確性和實際要求相結(jié)合進(jìn)而確定相關(guān)參數(shù)，以達(dá)到準(zhǔn)確度與實用性的統(tǒng)一。

4.1.1 預(yù)測結(jié)果及性能比較

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

圖6 預(yù)測結(jié)果對比

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

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

圖7 算法誤差對比

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

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

4.1.2 歷史時間長度對預(yù)測結(jié)果的影響

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

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

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

4.1.3 分段預(yù)測

基于RNN 的多次分段預(yù)測方法中，輸出層神經(jīng)元數(shù)量為1，每次預(yù)測只得到未來某一個時間段的載客人數(shù)。SPBR 通過多次預(yù)測可得到未來每個時間段的預(yù)測數(shù)據(jù)，進(jìn)而得到多段預(yù)測結(jié)果。使用回歸預(yù)測時，神經(jīng)網(wǎng)絡(luò)本身可以通過增加輸出層神經(jīng)元數(shù)量實現(xiàn)對未來的一次性多段預(yù)測，例如預(yù)測某個區(qū)域未來6 個時間段的載客人數(shù)，只需將RNN 輸出層神經(jīng)元數(shù)目設(shè)定為6 就能一次性完成預(yù)測。

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

圖9 分段預(yù)測結(jié)果對應(yīng)誤差

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

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

4.1.4 時間步長對預(yù)測結(jié)果的影響

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

圖10 多段預(yù)測結(jié)果及誤差

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

4.1.5 過擬合對預(yù)測結(jié)果的影響

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

圖11 基于SPBR 的不同時間步長的預(yù)測結(jié)果及誤差

經(jīng)過多次調(diào)參和訓(xùn)練發(fā)現(xiàn)，更新參數(shù)時隨機斷開20%的輸入神經(jīng)元連接可以實現(xiàn)有效改進(jìn)。如圖12 所示，添加Dropout 層的RNN 的擬合效果明顯優(yōu)于未添加Dropout 層的RNN。

4.2 載客推薦結(jié)果分析

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

圖12 Dropout 層對預(yù)測誤差的影響

4.2.1 TDMP 回報矩陣分析

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

圖13 訓(xùn)練集平均載客人數(shù)與測試集一天載客人數(shù)對比

對比圖13 與圖9 可知，訓(xùn)練集平均載客人數(shù)與實際誤差較大，遠(yuǎn)遠(yuǎn)不如通過SPBR 預(yù)測數(shù)據(jù)準(zhǔn)確；當(dāng)SPBR 輸入段和預(yù)測段距離增加，預(yù)測誤差大于訓(xùn)練集平均值誤差時，可用訓(xùn)練集平均值代替SPBR 預(yù)測。SPBR 預(yù)測誤差隨輸入段和預(yù)測段距離的變化如圖14 所示。

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

圖14 SPBR 預(yù)測誤差

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

4.2.2 TMDP 推薦結(jié)果分析

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

通過策略迭代求得狀態(tài)?值函數(shù)V(s)達(dá)到最大值的最優(yōu)策略函數(shù)π*(s)。

TMDP 推薦結(jié)果策略如表4 所示，si(0≤i＜100)表示出租車所在區(qū)域，Tj(0≤j＜96)表示出租車所在時間段。策略為1 表示出租車空載狀態(tài)下TMDP 建議在當(dāng)前區(qū)域等待。策略為2表示出租車空載狀態(tài)下TMDP建議去往其他區(qū)域?qū)た??；诒? 的推薦策略，每個狀態(tài)可得到的最大期望回報矩陣如表5 所示。

表4 TMDP 推薦結(jié)果策略

表5 TMDP 最大期望回報矩陣

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

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

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

可從歷史數(shù)據(jù)中求得與行為無關(guān)的狀態(tài)轉(zhuǎn)移概率矩陣P'，當(dāng)最大預(yù)測距離為6 時，對應(yīng)TMDP中折扣因子γ=0.5，定義矩陣Z為

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

表6 歷史期望回報矩陣

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

圖15 區(qū)域平均期望回報

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

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

5 結(jié)束語

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