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

林園

上海同濟城市規劃設計研究院有限公司城市開發規劃研究院，上海 200092

0 引言

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

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

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

1 數據格式及預處理

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

本文使用的浮動車GPS數據樣例如表1所示。

表1 GPS數據格式樣例

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

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

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

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

2 路段行程時間預測模型

2.1 地圖匹配算法

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

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

1)選擇候選路段

圖2 位置點候選路段集

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

2)候選路段篩選與比對

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

假設路段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°起始角，順時針旋轉，ψ∈[0°， 360°]，θ∈[0°， 360°]。

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

θ的計算公式為：

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

α的計算公式為：

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

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

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

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

用k，k-1，…，k-n+1時刻的路段行程時間預測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時刻的路段行程時間的狀態向量，Tk=[ktk]T，其中k為時刻，tk為k時刻的路段行程時間；H0(k)，H1(k)，…，Hn-1(k)為參數矩陣；ω(k)為測量噪聲，假設其是均值為零的白噪聲，用R(k)表示它的協方差矩陣[15]。

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

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

至此，狀態空間表示由原時間序列模型重新構建轉換[16]，根據KF算法，其遞推方程表達式為：

(2)

1)算法初始化

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

2)預測過程

狀態預測

(3)

協方差預測

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

(4)

3)計算卡爾曼增益

4)估計過程

狀態值更新

協方差更新

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

(5)

5)循環條件

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

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

2.3 基于遺傳算法的卡爾曼參數優化

圖5 基于GA的KF參數優化

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

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

優化步驟如下：

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

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

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

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

3 實例分析

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

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

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

圖6 路段行程時間預測結果

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

圖7 路段行程時間預測相對誤差

圖8 上海外環路段行程車速分布

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

4 結語

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

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