基于HMM的電動出租汽車行駛狀態(tài)預(yù)測改進(jìn)模型研究

唐 飛 劉大明 郭傅傲

(上海電力大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200092)

0 引 言

“互聯(lián)網(wǎng)+交通”模式產(chǎn)生一系列新興業(yè)態(tài)，對人們的城市交通出行方式帶來顛覆性的改變。僅2014年一年我國中心城市出租汽車載客車次總數(shù)就達(dá)到657 467萬次，運(yùn)營里程6 204 401萬公里，預(yù)計(jì)新增電動出租汽車12.1萬輛，電動出租汽車發(fā)展迅猛。相對于傳統(tǒng)化石能源，電力無法大規(guī)模儲能，電動出租汽車的入網(wǎng)，將對電網(wǎng)安全運(yùn)行和優(yōu)化調(diào)度造成困難。建立有效的電動汽車行駛狀態(tài)預(yù)測模型，為分析電動出租汽車行駛特征和充電負(fù)荷預(yù)測打下基礎(chǔ)，從而優(yōu)化電動出租汽車調(diào)度控制[1-4]。當(dāng)前可用的電動出租汽車行駛數(shù)據(jù)極少，相對而言，隨著定位技術(shù)的成熟與發(fā)展，出租汽車行業(yè)已經(jīng)累積了大量用戶位置數(shù)據(jù)。電動出租汽車屬于一類特殊的出租汽車，二者擁有相似的經(jīng)營特點(diǎn)[5]，且司機(jī)的駕駛習(xí)慣極少由于駕駛電動出租汽車而改變[6]，可以使用普通出租汽車數(shù)據(jù)對電動出租汽車進(jìn)行研究。

車輛行駛狀態(tài)具有空間和時間規(guī)律性，具有預(yù)測的可能性。文獻(xiàn)[7]通過觀察記錄252位司機(jī)40天的行程發(fā)現(xiàn)，大約60%的司機(jī)會選擇具有相同時間、位置特征的行程，即傾向于每天進(jìn)行相同的出行。文獻(xiàn)[8]通過跟蹤100 000條手機(jī)行動軌跡六個月的數(shù)據(jù)指出：人類軌跡顯示出高度的時間和空間規(guī)律性，每個個體都大概率往返于幾個高頻率坐標(biāo)位置，遵循簡單的可再現(xiàn)模式。

在行駛狀態(tài)預(yù)測模型中，馬爾可夫模型對于離散的時間與狀態(tài)具有良好的時序性，目前對于GPS軌跡數(shù)據(jù)的研究主要基于馬爾可夫模型進(jìn)行建模預(yù)測。文獻(xiàn)[9-10]通過聚類方法對GPS數(shù)據(jù)中的重要位置進(jìn)行數(shù)據(jù)挖掘，并將其合并到馬爾可夫模型中進(jìn)行目的地預(yù)測。文獻(xiàn)[11]使用連續(xù)路線模式挖掘從GPS軌跡數(shù)據(jù)中提取歷史運(yùn)動模式，從而對未來運(yùn)動模式進(jìn)行預(yù)測。文獻(xiàn)[12]通過高斯混合模型對移動對象運(yùn)動模式的概率分布進(jìn)行計(jì)算，將GPS軌跡數(shù)據(jù)劃分為不同分量，從而預(yù)測未來軌跡。文獻(xiàn)[13]將軌跡信息作為觀測狀態(tài)，實(shí)際路網(wǎng)信息作為隱狀態(tài)，建立隱馬爾可夫模型進(jìn)行汽車位置預(yù)測。

分析現(xiàn)有的出租汽車路徑預(yù)測相關(guān)研究工作，主要集中在出租汽車軌跡數(shù)據(jù)挖掘[14-17]、出租汽車的交通情況估計(jì)[18-20]和出租汽車運(yùn)營管理[21-23]三部分，針對電動出租汽車的研究較少。出租汽車相對于私家車有目的地隨機(jī)性大、路徑選擇多、停留時間短等特點(diǎn)，需要采用適應(yīng)出租汽車出行習(xí)慣的建模策略。文獻(xiàn)[24]使用滑動窗口模型估計(jì)軌跡未來軌跡范圍，從而獲取候選軌跡列表并建立模型進(jìn)行位置預(yù)測，能較好地表示出租汽車無序的路徑選擇，但其采用的一階馬爾可夫模型僅使用當(dāng)前位置進(jìn)行預(yù)測，對歷史軌跡利用不充分，預(yù)測精度較低。針對上述問題，本文提出使用滑動窗口的隱馬爾可夫模型電動出租汽車行駛狀態(tài)預(yù)測方法。該方法首先通過載客狀態(tài)與行駛距離對軌跡信息進(jìn)行劃分，然后建立隱馬爾可夫模型，通過適應(yīng)電動出租汽車行駛特點(diǎn)的改進(jìn)解法求解相關(guān)參數(shù)。

1 行駛狀態(tài)識別

為了對電動出租汽車行駛狀態(tài)進(jìn)行預(yù)測，需要根據(jù)出租汽車相對普通私家車的特殊行駛模式對GPS軌跡數(shù)據(jù)中包含的信息進(jìn)行提取。GPS軌跡數(shù)據(jù)一般由一系列以時間為序的點(diǎn)組成，每個點(diǎn)包含坐標(biāo)及行駛相關(guān)信息。為了利用這些信息，需要進(jìn)行出租汽車狀態(tài)識別，即從軌跡數(shù)據(jù)中識別出目的地坐標(biāo)，將整段行駛路徑劃分為若干行程。

出租汽車的行駛行為與普通私家車存在很大區(qū)別：相對于私家車，出租汽車沒有既定的目的地，其目的地通常由乘客決定，這使出租汽車一天的行程相對私家車更無序；出租汽車更多是為了接客而進(jìn)行短期停留，而不是像私家車那樣在工作場所或商場周邊停留幾小時。因此，本文做如下定義：

定義1目的地。出租汽車進(jìn)行停留或者下客的地方定義為目的地dn。

定義2行程。兩個目的地之間的行駛軌跡定義為行程ln。去往同一個地點(diǎn)通常有多條可選路線，即相同的兩個目的地之間存在多段可能的行程。

定義3行駛狀態(tài)。通過定義1與定義2中的目的地與行程將GPS軌跡劃分成k個包含目的地與路徑軌跡的行駛狀態(tài)，單個行駛狀態(tài)表示為sn={ln,dn}，1≤n≤k。

定義4載客狀態(tài)。將出租車載客狀態(tài)記作αi，載客記為1，空載記為0，有乘客上下車即記作載客狀態(tài)發(fā)生變化。

根據(jù)上述定義，為了識別出行駛狀態(tài)，使用出租汽車載客狀態(tài)與停留動作從GPS軌跡中提取出目的地dn組成目的地集合STAY。首先根據(jù)定義4中的載客狀態(tài)αi的變化進(jìn)行判斷。載客狀態(tài)能夠清楚地反映出何時出租汽車將乘客送到目的地及何時何地出租汽車接到新乘客結(jié)束空載狀態(tài)。若是判斷到αi發(fā)生改變，就將發(fā)生狀態(tài)改變的坐標(biāo)Li存入目的地集合STAY。

(1)

式中：Lng代表經(jīng)度；Lat代表緯度；R代表地球半徑，取值為6 317 km。

定義5停止持續(xù)時間。出租汽車能被判斷為在坐標(biāo)Li進(jìn)行停留的最小停留時間記作tdur，本文定義tdur=5 min。

定義6漫游距離。出租汽車能被判斷為在坐標(biāo)Li進(jìn)行停留的最大偏移距離記作漫游距離，即在tdur時間內(nèi)所有dadj的和，其計(jì)算如下：

(2)

劃分后的部分坐標(biāo)軌跡如圖1所示，其中共有四個目的地，兩個目的地之間的坐標(biāo)被劃為兩段載客行程和一段空載行程。

圖1 軌跡劃分舉例

2 預(yù)測方法

在對軌跡信息進(jìn)行處理之后，對出租汽車的旅行中的行程進(jìn)行預(yù)測，即預(yù)測出租汽車行駛的下一個狀態(tài)sn。使用隱馬爾可夫模型進(jìn)行預(yù)測，使用滑動窗口模型改進(jìn)狀態(tài)轉(zhuǎn)移概率求解，Baum-Welch算法用以求解觀察概率與初始概率分布。

2.1 隱馬爾可夫模型

隱馬爾可夫模型(Hidden Markov Model，HMM)最初由一些學(xué)者發(fā)表在一系列的統(tǒng)計(jì)學(xué)論文中。馬爾可夫模型在出租汽車行駛狀態(tài)預(yù)測中可以很好地表示時序位置關(guān)系，能很好地應(yīng)用于位置建模和預(yù)測；而隱狀態(tài)的加入使HMM成為一個雙重隨機(jī)過程，可以充分考慮到坐標(biāo)與現(xiàn)實(shí)道路不匹配的問題。因此，本文選擇使用HMM對出租汽車行駛狀態(tài)進(jìn)行預(yù)測。

定義7隱馬爾可夫行駛狀態(tài)預(yù)測模型。HMM是一種含有隱狀態(tài)的馬爾可夫過程，為了應(yīng)用于行駛狀態(tài)預(yù)測，模型包含五個基本要素，可表示為一個五元組λ=(S,O,A,Z,π)，其中：

(1)S表示一組狀態(tài)，且S=(s1,s2,…,sN)，N是狀態(tài)的總數(shù)，一般來說S中的是不可觀測的隱狀態(tài)。

(2)O表示一組觀察值O=(o1,o2,…,oM)，M是觀察值的總數(shù)，一般來說O中的觀測值是可以從數(shù)據(jù)中直接得到的。

(3)A={aij}是狀態(tài)轉(zhuǎn)移概率，且aij=p(sj|si)，表示從si狀態(tài)轉(zhuǎn)移到sj狀態(tài)的概率。

(4)Z={zi}是觀察概率，且zi=p(oi|si)，表示系統(tǒng)在si狀態(tài)被觀測到觀測值oi的概率。

(5)π={πi}是隱藏狀態(tài)的初始概率分布，πi表示當(dāng)時間t=1時狀態(tài)si的概率分布。

si狀態(tài)在t時間的概率分布記作pt(si)，當(dāng)t=1時p1(si)=π是si狀態(tài)的初始概率分布。sj狀態(tài)在t+1時間的概率分布可以通過下式計(jì)算得到：

(3)

為了更新概率分布，可以使用貝葉斯準(zhǔn)則[28]獲得：

(4)

(5)

式中：p(ot+1)作為歸一化因子。

為了進(jìn)行路徑預(yù)測，需要將出租汽車行駛的元素與HMM的基本元素進(jìn)行匹配。隱狀態(tài)集S由第一節(jié)中得到的s={l,d}組成，代表由一條路線l到達(dá)目的地d的狀態(tài)。因此，狀態(tài)轉(zhuǎn)移概率aij=p(sj|si)也對應(yīng)代表著出租汽車從si狀態(tài)轉(zhuǎn)移到sj狀態(tài)的概率。觀察集O對應(yīng)出租汽車的瞬時坐標(biāo)，可以直接從GPS軌跡中得到。觀察概率Z表示GPS位置與實(shí)際路網(wǎng)的匹配程度，對應(yīng)為zi=p(oi|si)，即當(dāng)出租汽車處在si狀態(tài)時被觀測到GPS坐標(biāo)為oi的概率。

2.2 狀態(tài)轉(zhuǎn)移概率計(jì)算

2.1節(jié)中完成了對HMM基本元素的定義，隱狀態(tài)集S與觀察集O都能通過軌跡數(shù)據(jù)得到，剩下的任務(wù)就是計(jì)算狀態(tài)轉(zhuǎn)移矩陣A，觀察矩陣Z以及初始狀態(tài)π。由于出租汽車單次行程距離短，目的地變化快，本文采用文獻(xiàn)[24]提到的滑動窗口模型改進(jìn)HMM狀態(tài)轉(zhuǎn)移概率計(jì)算。

定義8滑動窗口模型?；瑒哟翱谀Ｐ透鶕?jù)出租汽車實(shí)時位置建立半徑為Rd的圓形滑動窗口，通過統(tǒng)計(jì)歷史行程數(shù)據(jù)預(yù)測未來最有可能選擇的行程，從而預(yù)測出租汽車的未來位置。

其中半徑Rd=vave·Tp，vave是車輛行駛速度，Tp表示預(yù)測周期。采用城市路網(wǎng)的平均速度作為車輛行駛速度，即vave=40 km/h，用GPS軌跡數(shù)據(jù)采集周期作為預(yù)測周期Tp，對滑動窗口的半徑Rd進(jìn)行計(jì)算。

滑動窗口模型如圖2所示，表示在局部道路網(wǎng)絡(luò)使用滑動窗口進(jìn)行狀態(tài)預(yù)測。其中虛線圓圈就是一個動態(tài)窗口，l是供選擇的行程，d是行程的目的地。圈中所有的行程l都是未來的可選行程。

圖2 滑動窗口模型

為了降低模型的復(fù)雜度，本文進(jìn)行如下假設(shè)：(1) 假設(shè)出租汽車不會掉頭返回上個行駛過的路口；(2) 假設(shè)行程l與目的地d相互獨(dú)立。因此狀態(tài)轉(zhuǎn)移概率aij的計(jì)算式可以寫作p({lj,dj}|si)=p(dj|lj)·p(lj|si)，其中p(lj|si)表示在當(dāng)前狀態(tài)si選擇的下個行程是lj的概率，p(dj|lj)表示通過行程lj，駛向目的地dj的概率。為了計(jì)算p(lj|si)與p(dj|lj)，引入m1與m2兩個參數(shù)，用圖2中的道路情況舉例計(jì)算過程。首先計(jì)算p(lj|si)。定義集合{lj,di,m2}，表示當(dāng)出租汽車通過行程li到達(dá)目的地di后行駛?cè)胄谐蘬j的總次數(shù)。由此可以計(jì)算：

(6)

使用類似的方法，可以計(jì)算p(dj|lj)。定義集合{dj,lj,m1}，表示當(dāng)目的地為dj時，出租汽車經(jīng)過行程lj共m1次。由此計(jì)算：

(7)

在通過aij=p(dj|lj)·p(lj|si)計(jì)算出狀態(tài)轉(zhuǎn)移概率aij后，可以計(jì)算下一個時間段的狀態(tài)轉(zhuǎn)移概率：

(8)

用式(2)和式(3)更新pt+1(sj)：

(9)

其中：

(10)

在式(8)、式(9)和式(10)中：t是狀態(tài)si所在的時間段，t+1表示狀態(tài)轉(zhuǎn)移到下一個狀態(tài)sj的時間段；ot+1表示在t+1時間段，即處在狀態(tài)sj時的觀察值；sk表示出租汽車從si狀態(tài)向目的地dj行駛所選擇的行程lk，k=1,2,…,n，n由實(shí)際道路情況確定。例如車輛處在十字路口時，n的值為3，即可選道路有3條。

2.3 Baum-Welch算法

2.2節(jié)介紹了通過滑動窗口模型改進(jìn)HMM狀態(tài)轉(zhuǎn)移矩陣A的計(jì)算。本節(jié)將在此基礎(chǔ)上對觀察概率Z與初始狀態(tài)π進(jìn)行求解，隨后通過迭代對三個參數(shù)進(jìn)行更新。采用的方法對應(yīng)概率論中的極大似估計(jì)問題。由于HMM模型包含隱狀態(tài)，無法通過直接求導(dǎo)進(jìn)行求解，故采用Baum-Welch算法[29]進(jìn)行求解。

首先進(jìn)行初始化，隨機(jī)給觀察概率zj與初始狀態(tài)πi進(jìn)行賦值，使其滿足如下條件：

(11)

(12)

定義9前向概率。前向概率為時刻t的觀察序列為(o1,o2,…,ot)，且時刻t隱狀態(tài)為si的概率，記為：

αt(i)=p(o1,o2,…,ot,xt=si|λ)

(13)

在得到了前向概率后，便能利用式(14)-式(15)遞歸地求解前向概率和觀測序列的概率：

α1(i)=πizi(1)

(14)

(15)

定義10后向概率。后向概率為時刻t隱狀態(tài)為si且時刻t+1到T為止的觀察序列為(ot+1,ot+2,…,oT)的概率，記為：

βt(i)=1

(16)

(17)

由于后向概率的方向是相反的，最終時刻T之后的概率不作考慮，故賦值1。

使用求得的α與β對中間變量進(jìn)行計(jì)算：

(18)

然后使用求得的中間變量γ求解觀察概率Z：

(19)

πi=γ1(i)

(20)

式(19)中的I(ot=ok)僅當(dāng)時刻t的觀察值為ok時才取值為1，否則為0。使用aij、zj與πi的更新值執(zhí)行上述過程進(jìn)行迭代，將最終收斂的結(jié)果作為求得的狀態(tài)轉(zhuǎn)移概率A、觀察概率Z與初始狀態(tài)π。

3 實(shí) 驗(yàn)

本文實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i5-7300HQ CPU @ 2.50 GHz，內(nèi)存8 GB。實(shí)驗(yàn)程序用Python編寫，在Windows 10系統(tǒng)下運(yùn)行。

實(shí)驗(yàn)采用的GPS軌跡數(shù)據(jù)來自香港科技大學(xué)計(jì)算機(jī)科學(xué)與工程系的手機(jī)軌跡研究項(xiàng)目[25]，包含在2007年2月23日上海4 316輛出租汽車一天的軌跡數(shù)據(jù)。該數(shù)據(jù)集包含了超過600萬個坐標(biāo)點(diǎn)，軌跡的總距離達(dá)到160多萬公里。每輛車的數(shù)據(jù)都由m個軌跡點(diǎn)構(gòu)成，單個軌跡點(diǎn)的結(jié)構(gòu)為(ID,ti,Li,vi,θi，αi)，1≤i≤m。

每個軌跡點(diǎn)有七個字段，其中第一個字段是出租汽車的標(biāo)識ID；第二個字段ti是該軌跡點(diǎn)的時間戳，記錄軌跡點(diǎn)時間間隔為1分鐘；第三和第四個字段Li=(Lngi,Lati)為坐標(biāo)點(diǎn)，Lngi為經(jīng)度，Lati為緯度；第五個字段vi是此時出租汽車的瞬時速度；第六個字段θi是從北方順時針方向以2度為單位的角度，例如“157”表示出租汽車瞬時速度在順時針方向上與北方成314度；最后一個字段αi表示載客狀態(tài)。

根據(jù)數(shù)據(jù)中的經(jīng)緯度極限，設(shè)定研究區(qū)域經(jīng)度范圍從121.075 00到121.975 00，緯度范圍從30.690 00到31.790 00。為了簡化預(yù)測過程，將研究區(qū)域劃分成900×1 100個單元格，其中每個單元格是0.001×0.001的區(qū)域。將同一單元格中的所有坐標(biāo)記作同一位置。

本文使用相對準(zhǔn)確度RA來對預(yù)測性能進(jìn)行評估，定義如下：

(21)

(22)

式中：Eave是距離平均誤差；Lpre與Lact分別是預(yù)測坐標(biāo)與實(shí)際坐標(biāo)；n是測試樣本數(shù)量；Rd是圓形滑動窗口的半徑。

定義11市中心行程。根據(jù)上海內(nèi)環(huán)高架將經(jīng)度121.414 0～121.576 0、緯度31.205 0～31.282 0的區(qū)域定義為市中心區(qū)域，所有軌跡點(diǎn)都在這個范圍內(nèi)的行程記作市中心行程。

在驗(yàn)證模型準(zhǔn)確性的過程中，為了簡化驗(yàn)證過程，隨機(jī)從所有行程中抽取十段載客行程、十段空載行程、五段市中心的載客行程、五段市中心的空載行程來作為測試樣本。圖3顯示了載客行程、空載行程與市中心行程的預(yù)測結(jié)果。分析柱狀圖得出結(jié)論：(1) 對于行程預(yù)測的準(zhǔn)確度遠(yuǎn)小于對于出租汽車目的地的預(yù)測；(2) 在市中心行程預(yù)測準(zhǔn)確率普遍更低；(3) 空載行程的預(yù)測準(zhǔn)確率略高于載客行程。

圖3 坐標(biāo)預(yù)測結(jié)果

對產(chǎn)生的三個結(jié)論進(jìn)行分析：對于結(jié)論(1)，行程預(yù)測不準(zhǔn)確的主要原因是同一目的地多條可選路徑的存在。這同時也解釋了結(jié)論(2)，市中心道路更密集，可選道路也更多，也就造成了更低的預(yù)測準(zhǔn)確率。本文選取了測試行程中RA值最低的一段繪制軌跡圖如圖4(b)所示，對比預(yù)測較準(zhǔn)確的圖4(a)而言，除了由于區(qū)域劃分產(chǎn)生的誤差外，圖4(b)選擇了與實(shí)際情況有相同目的地的另一條行程，這導(dǎo)致了RA值出現(xiàn)大量偏差。對于結(jié)論(3)，可能是出租汽車在沒有載客時，司機(jī)更少進(jìn)行高速行駛，行程的路程也相對更短。本文對出租汽車軌跡數(shù)據(jù)中的θi也就是角度變化進(jìn)行比較后發(fā)現(xiàn)在空載時，出租汽車的行駛角度θi變化率更低，即空載時出租汽車更少進(jìn)行急轉(zhuǎn)彎，這可能也是出現(xiàn)空載預(yù)測更準(zhǔn)確的原因。

(a)

(b)圖4 行駛路線

另外，還對出租汽車預(yù)測軌跡的行駛里程Dmov進(jìn)行了計(jì)算：

(23)

本文從所有行程中抽取了十段行程進(jìn)行了行駛里程計(jì)算，并與預(yù)測結(jié)果進(jìn)行了比對，結(jié)果如表1所示。

表1 預(yù)測結(jié)果

通過表1，不難發(fā)現(xiàn)HMM對行程的行駛里程計(jì)算相當(dāng)準(zhǔn)確，達(dá)到了84.59%。表中幾個空載行程誤差較大，且多是預(yù)測路程大于實(shí)際路程，原因可能是空載時，行駛速度緩慢，660 m的滑動窗口距離過大造成的。較高的目的地預(yù)測精度與行駛里程預(yù)測精度證明了本文所提出的基于HMM預(yù)測方法的可靠性。

表2對幾種常用位置預(yù)測模型進(jìn)行了準(zhǔn)確性比較，可以看出一階二階馬爾可夫模型在出租汽車位置預(yù)測方面準(zhǔn)確率并不理想；相對于普通隱馬爾可夫模型，加入滑動窗口的改進(jìn)模型對行程坐標(biāo)的預(yù)測沒有明顯提升，但在目的地坐標(biāo)預(yù)測與行駛里程預(yù)測方面準(zhǔn)確率均有提升。這是因?yàn)榛瑒哟翱谀Ｐ偷募尤胧鼓Ｐ湍軐Ξ?dāng)前位置附近的目的地進(jìn)行選擇，更契合出租車的行駛特點(diǎn)。

表2 預(yù)測結(jié)果對比 %

4 結(jié) 語

面向GPS軌跡數(shù)據(jù)，首先，通過載客狀態(tài)與停留檢測算法對軌跡進(jìn)行狀態(tài)分析；其次，為了契合出租汽車行駛的特點(diǎn)，將行程路徑與目的地作為隱狀態(tài)建立HMM；然后，使用滑動窗口模型對HMM的狀態(tài)轉(zhuǎn)移概率進(jìn)行求解，使用Baum-Welch算法對觀察概率與初始狀態(tài)概率進(jìn)行求解。實(shí)驗(yàn)表明，滑動窗口模型能很好地契合出租汽車行駛路徑選擇特點(diǎn)，本文建立的HMM在非市中心地區(qū)與出租汽車空載時有較高的準(zhǔn)確率。該方法對出租汽車行程的目的地及行駛里程的預(yù)測準(zhǔn)確度高，能較好應(yīng)用于充電負(fù)荷預(yù)測。

由于本文未考慮同一目的地相似路徑的選擇問題，導(dǎo)致在路網(wǎng)情況相對更復(fù)雜的市中心區(qū)域行程預(yù)測誤差較大。未來將會把幾個可能影響相似路徑選擇的問題列入考慮：不同的駕駛員存在不同的路線選擇習(xí)慣與路線長度衡量標(biāo)準(zhǔn)，這些特征應(yīng)該會影響路徑選擇；交通的擁擠、道路的修繕等情況會對出租汽車的路徑選擇產(chǎn)生影響。未來工作將針對這些特征建立更復(fù)雜的模型用于預(yù)測。