基于改進遺傳卡爾曼算法的短時路段行程時間估計

林園

上海同濟城市規(guī)劃設(shè)計研究院有限公司城市開發(fā)規(guī)劃研究院，上海 200092

0 引言

城市道路交通擁堵問題在我國城市化進程中日益嚴重,傳統(tǒng)的解決方法主要是增加道路和橋梁建設(shè)。據(jù)統(tǒng)計，車輛數(shù)量的增長速度約為道路增長速度的2～3倍[1]。因此，采用成熟的交通信息網(wǎng)絡(luò)和交通信息提取技術(shù)輔助交通管理，已成為緩解當前城市交通擁堵問題的熱門課題。

全球定位系統(tǒng)(global positioning system，GPS)在居民日常生活中得到了普遍應(yīng)用。裝載GPS設(shè)備的城市浮動車成為交通信息采集的重要節(jié)點，浮動車可獲得海量的交通數(shù)據(jù)。有關(guān)學(xué)者就如何對采集到的數(shù)據(jù)信息進行篩選和提取、發(fā)現(xiàn)數(shù)據(jù)之間的內(nèi)在聯(lián)系、利用數(shù)據(jù)建立模型、獲得動態(tài)交通信息等進行了諸多研究，當前已有研究針對特定時間段內(nèi)的車輛即時運行速度進行計算，從而估計路段行程時間。武小云[2]分別以1、2、5 min 3種間隔為單位時間窗口，對各車輛的平均速度進行統(tǒng)計分析，獲取路段的行程時間，選擇行程時間序列標準差中離散程度的最小值作為評價標準，但沒有考慮車輛在道路交叉口處的延誤，降低了對道路行程時間估計的準確度。李宇光[3]采用臨近GPS數(shù)據(jù)點間的運行速度和距離估計各車輛通過道路節(jié)點的時間，以數(shù)理統(tǒng)計分析方法推測不同道路路段的行程時間。王志建等[4]對低頻數(shù)據(jù)在道路交叉口處相鄰定位點的4種分布進行總結(jié)，依托車輛運行的速度特征估算通過交叉口的時間，該方法側(cè)重于分析交叉口對車輛運行造成的延誤，忽視了非交叉口處車輛運行速度的變化。道路交通狀態(tài)的變化通常是漸進時變的過程，利用KF算法可以較好地比較和修正車輛運行的時變特征，提高系統(tǒng)狀態(tài)的預(yù)測精度[5-9]。

為進一步優(yōu)化行程時間預(yù)測效果，本文針對數(shù)據(jù)源本身存在的精度問題，提出用高斯濾波算法優(yōu)化數(shù)據(jù)，結(jié)合城市GIS信息提出路段地圖匹配方法，利用KF算法估計預(yù)測道路行程時間。以上海市外環(huán)路為例，結(jié)合道路線圈測量數(shù)據(jù)，對路段行程時間估計結(jié)果的準確性進行分析。

1 數(shù)據(jù)格式及預(yù)處理

浮動車GPS數(shù)據(jù)是安裝在城市浮動車上的GPS設(shè)備采集的車輛定位數(shù)據(jù)。對于不同的GPS數(shù)據(jù)采集設(shè)備，采集數(shù)據(jù)格式的標準有所區(qū)別。

本文使用的浮動車GPS數(shù)據(jù)樣例如表1所示。

表1 GPS數(shù)據(jù)格式樣例

由于GPS衛(wèi)星信號在空間傳播過程中極易受到環(huán)境干擾，造成定位位置數(shù)據(jù)與實際位置有偏差，同時，浮動車GPS數(shù)據(jù)包含因漂移等問題產(chǎn)生的噪音數(shù)據(jù)，嚴重影響后續(xù)道路行程時間的預(yù)測精度。因此，采用高斯濾波器對已有數(shù)據(jù)進行除噪預(yù)處理，以減小數(shù)據(jù)偏差[10]。

對每一個點的坐標(x、y)，濾波后分別為：

圖1為高斯濾波前后GPS速度的對比。由圖1可以看出：濾波前最大速度約為50 m/s，濾波后的速度均小于10 m/s，濾除了明顯不合理的數(shù)據(jù)，得到與實際情況更符合的數(shù)據(jù)。同理，對經(jīng)緯度等數(shù)據(jù)進行高斯濾波，為下一步的算法提供較好的數(shù)據(jù)基礎(chǔ)。

a)濾波前 b)濾波后圖1 濾波前后GPS速度對比

2 路段行程時間預(yù)測模型

2.1 地圖匹配算法

地圖匹配算法是一種定位誤差修正技術(shù)，基本思路是將設(shè)備輸出的車輛定位點與城市地理信息系統(tǒng)(GIS)中的路網(wǎng)信息相匹配。當GPS浮動車在目標路段的路網(wǎng)范圍內(nèi)行駛時，將GPS定位數(shù)據(jù)、車輛運行軌跡和電子地圖主路數(shù)據(jù)綜合比較，通過合適的地圖進行算法匹配。本研究根據(jù)位置點到路段的距離以及位置點到候選路段位置角的差值選取匹配路段，將車輛匹配到最近的路段上。地圖匹配過程對GPS數(shù)據(jù)定位的誤差要求小于20 m，因此可能會有多個候選路段出現(xiàn)，從候選路段中挑選目標路段的具體規(guī)則根據(jù)選取的具體算法確定。本文從候選路段中選擇與車輛軌跡相似度較高的路段作為目標路段[11]。

GPS速度計算精度在很大程度上與路徑搜尋、位置確定有關(guān)。地圖匹配算法的任務(wù)是：選擇備選路段，并從中識別出目標路段；將位置點投影到目標路段上，以確定浮動車的實際物理位置。

1)選擇候選路段

圖2 位置點候選路段集

由于GPS設(shè)備在定位過程中通常存在定位誤差，GPS浮動車的定位坐標總是落于實際位置周邊一定范圍內(nèi)，這個范圍稱為“誤差范圍”。一般認為，20 m以內(nèi)的誤差不會對結(jié)果產(chǎn)生較大的影響[12]。關(guān)于誤差范圍的計算方法已有一些成熟的研究[13]。通常，誤差范圍假定為圓形或者矩形等形狀，為簡化計算過程，提高算法運行效率，將誤差區(qū)域假定為以位置點為圓心，誤差距離15 m為半徑r的圓形，圓形誤差區(qū)域內(nèi)的m個路段構(gòu)成初始候選路段集Lm，位置點的圓形誤差范圍與候選路段集如圖2所示。

2)候選路段篩選與比對

確定初始候選路段集后，需通過設(shè)置條件進一步選擇比對路段集。本文主要通過研究位置點到候選路段的最短距離以及兩者方向角的差值2個控制變量來確定最終路段集。

假設(shè)路段K1(K1∈m)兩端點的坐標為P1(x1，y1)，P2(x2，y2)，GPS浮動車位置點的坐標為P3(x3，y3)，如圖3所示。點P(x，y)坐標的計算公式為：

計算定位點P3至目標路段K1的距離

式中：a=R(y3)-R(y)，其中R(y3)=πy3/180，R(y)=πy/180；b=R(x3)-R(x)，其中R(x3)=πx3/180，R(x)=πx/180；Re為地球半徑。

路段篩選還需用到GPS車輛行進方向角ψ與路段指向方向角θ的差值，即α=ψ-θ，α定義為“誤差角”，如圖4所示。ψ、θ兩者同是以正北方向為0°起始角，順時針旋轉(zhuǎn)，ψ∈[0°， 360°]，θ∈[0°， 360°]。

圖3 點到直線的距離示意圖 圖4 誤差角α示意圖

θ的計算公式為：

式中：Δx=x2-x1，Δy=y2-y1。

α的計算公式為：

為保證GPS浮動車行駛方向與路段方向最大可能一致，避免位置點P3匹配到相反方向的路段上，要求α=0～45°。研究表明：當車速低于11 km/h時，GPS浮動車的θ很不穩(wěn)定，為避免刪除可靠數(shù)據(jù)，此種情況需特殊考慮。1)當瞬時車速大于11 km/h時，α=0～45°，選擇P3到路段距離最短的2個路段；2)當瞬時車速小于11 km/h時，選擇P3到道路距離最短的4個路段。

2.2 基于KF的路段行程時間估計

路段行程時間是運行車輛沿某路段從某路口行駛至下個路口所花費的時間，通常根據(jù)車輛路段行駛長度與運行速度的比值計算。由于浮動車GPS測量的瞬時速度存在誤差，取其測量平均值作為道路行程速度具有較大的不確定性。本文利用KF算法預(yù)測路段的行程時間。

短時路段行程時間預(yù)測可以根據(jù)前幾個時段的路段行程時間和時間估計誤差確定。為了及時響應(yīng)路段狀況的變化，短時預(yù)測以 1 min 為時間間隔，即以路段上第kmin 的路段行程時間預(yù)測第(k+1)分鐘的路段行程時間[14]。

用k，k-1，…，k-n+1時刻的路段行程時間預(yù)測k+1時刻的路段行程時間，模型為：

T(k+1)=H0(k)T(k)+H1(k)T(k-1)+…+Hn-1(k)T(k-n+1)+ω(k)，

(1)

式中：Tk為k時刻的路段行程時間的狀態(tài)向量，Tk=[ktk]T，其中k為時刻，tk為k時刻的路段行程時間；H0(k)，H1(k)，…，Hn-1(k)為參數(shù)矩陣；ω(k)為測量噪聲，假設(shè)其是均值為零的白噪聲，用R(k)表示它的協(xié)方差矩陣[15]。

轉(zhuǎn)換式(1)，將其以狀態(tài)空間形式表達，同時狀態(tài)空間里的點集以時變參數(shù)表示，從而更有利于利用卡爾曼濾波理論對狀態(tài)變量進行預(yù)測估計。則KF的系統(tǒng)狀態(tài)方程和觀測方程為：

式中：y(k)為觀測向量，是濾波的輸入；x(k)、x(k-1)分別為k、k-1時刻的狀態(tài)向量；Φ(k,k-1)為狀態(tài)轉(zhuǎn)移矩陣；A(k)為轉(zhuǎn)換矩陣，用于將k時刻狀態(tài)變量映射到測量值所在空間中；u(k-1)為均值為零的高斯白噪聲，其協(xié)方差矩陣為Q(k-1)。

至此，狀態(tài)空間表示由原時間序列模型重新構(gòu)建轉(zhuǎn)換[16]，根據(jù)KF算法，其遞推方程表達式為：

(2)

1)算法初始化

令k=k0，確定k0時刻的初始值x(k0)和P(k0)。

2)預(yù)測過程

狀態(tài)預(yù)測

(3)

協(xié)方差預(yù)測

P(k|k-1)=Φ(k|k-1)P(k-1)ΦT(k|k-1)+Q(k-1)。

(4)

3)計算卡爾曼增益

4)估計過程

狀態(tài)值更新

協(xié)方差更新

P(k)=[I-K(k)A(k)]P(k|k-1)。

(5)

5)循環(huán)條件

令k=k+1，重復(fù)步驟2)～5)，估計下一個時刻結(jié)果。

6)沒有新的觀測值時，跳出循環(huán)。

2.3 基于遺傳算法的卡爾曼參數(shù)優(yōu)化

圖5 基于GA的KF參數(shù)優(yōu)化

KF算法中的觀測噪聲協(xié)方差和測量噪聲協(xié)方差是影響KF預(yù)測效果的重要參數(shù)。由于這2個參數(shù)難以直接測量，本文選用GA對這2個參數(shù)的初始值Q和R進行聯(lián)合優(yōu)化，以達到更加理想的預(yù)測效果。該優(yōu)化流程除使用浮動車GPS數(shù)據(jù)外，還加入同時段的道路線圈采集的數(shù)據(jù)，作為車輛運行狀態(tài)的真實數(shù)據(jù)。

GA是借鑒自然遺傳選擇的隨機搜索最優(yōu)化算法，根據(jù)自主確定的適應(yīng)度函數(shù)，經(jīng)歷遺傳中的選擇、交叉和變異對參數(shù)個體進行篩選，從而達到更優(yōu)的參數(shù)組合[23-26]，優(yōu)化流程如圖5所示。

優(yōu)化步驟如下：

1)設(shè)置待優(yōu)化參數(shù)Q、R的取值范圍為[0，1],且精確到4位小數(shù)。對2個參數(shù)進行二進制編碼，確定染色體編碼長度為30，隨機生成初始種群。

2)初始化KF算法參數(shù)構(gòu)成的種群。由于GA求解的是極大值，而通過KF算法預(yù)測值與道路線圈測量值的誤差(絕對值)越小越好，因此取誤差的倒數(shù)作為GA的適應(yīng)度，然后確定種群大小、迭代次數(shù)、交叉概率和變異率等GA參數(shù)，通過“選擇-交叉-變異”等遺傳選擇過程，獲取最優(yōu)參數(shù)組合Sopt=(Q,R)，其中Q為優(yōu)化后的初始觀測噪聲協(xié)方差，R為優(yōu)化后的初始測量噪聲協(xié)方差。

3)利用Sopt=(Q,R)訓(xùn)練道路行程時間預(yù)測的KF模型，見式(2)。

4)利用訓(xùn)練好的KF模型對浮動車GPS數(shù)據(jù)進行處理識別，評估模型整體性能。

3 實例分析

本文采用上海外環(huán)路2016年8月上傳的浮動車GPS數(shù)據(jù)，共1400萬條。浮動車GPS采集頻率為1 Hz。本文將道路線圈設(shè)備采集的信息作為路段行程時間的真實數(shù)據(jù)[27]。

利用高斯濾波算法和地圖匹配算法對浮動車GPS數(shù)據(jù)進行處理，采用Matlab軟件建立GA-KF模型并進行訓(xùn)練。參數(shù)設(shè)置：最大遺傳代數(shù)為60，種群數(shù)量為30，交叉概率為0.9，變異概率為0.05，以模型預(yù)測值與線圈測量值誤差(絕對值)的倒數(shù)作為適應(yīng)度函數(shù)。通過GA對參數(shù)進行優(yōu)化，確定初始觀測噪聲協(xié)方差Q=0.563 8，測量噪聲協(xié)方差R=0.381 6。最后利用GA優(yōu)化后的KF模型進行各個路段行程時間預(yù)測。

圖6為對應(yīng)時刻下路段行程時間預(yù)測的部分結(jié)果。由圖6可以看出：GA參數(shù)優(yōu)化后的KF算法比原始KF算法的預(yù)測誤差更小，平均提高約7.69 s。

圖6 路段行程時間預(yù)測結(jié)果

圖7為對應(yīng)時刻下路段行程時間實際測量結(jié)果與GA-KF預(yù)測結(jié)果的相對誤差。由圖7可知：預(yù)測誤差均在0.5 min內(nèi)，平均值為0.148 min，預(yù)測效果較好。

圖7 路段行程時間預(yù)測相對誤差

圖8 上海外環(huán)路段行程車速分布

根據(jù)預(yù)測得到的路段行程時間，結(jié)合GIS中的路段長度，可以得到路段交通流參數(shù)中的速度分布，如圖8所示，可據(jù)此開發(fā)城市道路擁堵情況監(jiān)測平臺。圖8中:綠色表示當前該路段的車輛行駛速度大于70 km/h，黃色表示路段車輛行駛速度為45～70 km/h，紅色表示路段車輛行駛速度小于45 km/h。由圖8可以看出：16:00—19:00上海外環(huán)路普遍呈現(xiàn)紅黃色，表明該時間段內(nèi)道路處于較為擁堵狀態(tài)，而早高峰8:00—10:00外環(huán)路呈現(xiàn)黃綠色，表明該時間段內(nèi)道路相對暢通，即早高峰擁堵并不明顯。

4 結(jié)語

本文利用浮動車GPS數(shù)據(jù)，建立基于遺傳算法優(yōu)化的卡爾曼濾波模型，與傳統(tǒng)卡爾曼濾波器相比，能有效提高預(yù)測精度，道路行程時間預(yù)測誤差小于0.5 min，能夠滿足實際交通管理的需要。

浮動車數(shù)據(jù)采集系統(tǒng)得到的數(shù)據(jù)能較為均勻地覆蓋目標道路，較好地補充了當前一些已有固定設(shè)備數(shù)據(jù)采集的缺陷。高速公路上的檢測器種類眾多，除了GPS浮動車之外還有感應(yīng)線圈、視頻檢測、收費站檢測、雷達檢測等。未來工作將融合多源道路監(jiān)測數(shù)據(jù)，以提高道路行程時間預(yù)測的效果和時空覆蓋率，構(gòu)建上海市道路狀態(tài)監(jiān)測發(fā)布平臺，為交通管理部門的政策制定提供參考。