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

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

1 引言

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

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

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

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

2)在乘客預(yù)測方面，提出基于循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN,recurrent neural network）的分段預(yù)測（SPBR,segment prediction based on RNN）算法，通過實(shí)驗(yàn)與支持向量回歸（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)提出了基于分時(shí)馬爾可夫決策過程（TMDP,time-varying Markov decision process）的載客推薦策略，引入回報(bào)函數(shù)來衡量出租車收益，通過仿真驗(yàn)證一個(gè)時(shí)段內(nèi)TMDP 策略下出租車期望回報(bào)與歷史期望相比的優(yōu)勢。

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 線下處理過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于出租車載客熱點(diǎn)預(yù)測問題，由于大數(shù)據(jù)的復(fù)雜性，用傳統(tǒng)機(jī)器學(xué)習(xí)算法進(jìn)行預(yù)測會(huì)達(dá)到極限，而神經(jīng)網(wǎng)絡(luò)在海量數(shù)據(jù)面前能夠展示自己的潛力。另一方面，在出租車乘客預(yù)測中，載客人數(shù)具有時(shí)序性，經(jīng)典BPNN 難以表征時(shí)間序列數(shù)據(jù)的內(nèi)在聯(lián)系，神經(jīng)網(wǎng)絡(luò)中隱藏層的值只取決于當(dāng)前輸入，不同樣本間的輸入、輸出相互獨(dú)立，許多情況下不能實(shí)現(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)化，僅得到未來最近一段時(shí)間的預(yù)測結(jié)果是不夠的，因此，本文進(jìn)一步地提出SPBR 算法對出租車系統(tǒng)進(jìn)行未來多個(gè)時(shí)間段的人數(shù)預(yù)測。

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

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

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

3.2 線上處理過程

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

3.2.1 基于MDP 的載客推薦模型

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

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

3.2.2 分時(shí)馬爾可夫決策過程

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

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

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

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

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

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

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

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

其中，R(s0)表示在當(dāng)前狀態(tài)s0采取行為后達(dá)到下一狀態(tài)s1的回報(bào)，R(s1)表示在狀態(tài)s1采取行為后到達(dá)下一狀態(tài)s2的回報(bào)，依次類推。狀態(tài)、行動(dòng)、轉(zhuǎn)移概率和回報(bào)間的關(guān)系如表2 和式(5)所示，轉(zhuǎn)移概率以及回報(bào)由初始狀態(tài)和采取的行動(dòng)決定。TMDP 可以表現(xiàn)出各區(qū)域各時(shí)間段之間的關(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é)束。

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

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

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

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

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

4)求轉(zhuǎn)移概率矩陣。將s擴(kuò)展成S=[0,100]，t擴(kuò)展成T=[0,96)，得到a為等待時(shí)的概率轉(zhuǎn)移矩陣P1，a為移動(dòng)時(shí)的概率轉(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 回報(bào)矩陣分析

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

1)載客概率矩陣Q

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

2)尋客時(shí)間矩陣E

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

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

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

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

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

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

3.2.5 TMDP 求解過程

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

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

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

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

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

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

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

圖5 策略迭代過程

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

通過對出租車預(yù)測模型進(jìn)行仿真，本文進(jìn)一步對影響預(yù)測結(jié)果的因素進(jìn)行討論，并將其準(zhǔn)確性和實(shí)際要求相結(jié)合進(jìn)而確定相關(guān)參數(shù)，以達(dá)到準(zhǔn)確度與實(shí)用性的統(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è)每段時(shí)間步長Ts=15 min，用于預(yù)測的歷史時(shí)間長度e=1，令k=0，即SPBR 輸入和輸出的數(shù)據(jù)沒有時(shí)間段間隔。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í)間段的乘客數(shù)量變化趨勢。為進(jìn)一步評估算法預(yù)測效果，采用均方根誤差（RMSE,root mean square error）和平均相對誤差（MRE,mean relative error）衡量預(yù)測算法性能。

其中，pre 為算法預(yù)測結(jié)果序列，true 為實(shí)際序列，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（即時(shí)間段0～24），乘客稀疏并且偶然性較大，在SVR 中很難找到完全契合本數(shù)據(jù)集的核函數(shù)，導(dǎo)致SVR 的預(yù)測結(jié)果出現(xiàn)一定程度的偏離；基于CART 的預(yù)測結(jié)果在該時(shí)間段有著較高的擬合程度，但由于異常突發(fā)值的存在導(dǎo)致誤差擴(kuò)大；BPNN 和SPBR 在該時(shí)段可以很好地?cái)M合。

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

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

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

歷史時(shí)間長度e決定RNN 輸入層的緯度，即輸入層神經(jīng)元的個(gè)數(shù)，所以選取不同的e，RNN 的結(jié)構(gòu)會(huì)發(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 時(shí)誤差達(dá)到最小，但誤差仍大于RNN；SVR和BPNN 的RMSE 隨e的變化不明顯，但MRE出現(xiàn)較大起伏。因此，結(jié)合RMSE 和MRE 衡量各算法的預(yù)測誤差是合理的。當(dāng)e=1 時(shí)SPBR 誤差最小，因此用SPBR 進(jìn)行載客數(shù)量預(yù)測時(shí)只需要根據(jù)前一段歷史數(shù)據(jù)即可保證對下一段預(yù)測的最小誤差。

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

4.1.3 分段預(yù)測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.1 TDMP 回報(bào)矩陣分析

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

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

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

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

圖14 SPBR 預(yù)測誤差

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

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

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

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

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

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

表5 TMDP 最大期望回報(bào)矩陣

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

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

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

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

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

表6 歷史期望回報(bào)矩陣

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

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

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

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

5 結(jié)束語

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