《車輛位置數據處理及動態出行路徑誘導技術》論文發表期刊：《信息技術》；發表周期：2020年12期

《車輛位置數據處理及動態出行路徑誘導技術》論文作者信息：張春輝(1986－) ，男，碩士，工程師，研究方向為智能交通。

　　摘要：車輛路徑誘導技術的發展，為公眾的日常出行提供了極大的便利。為了提高車輛誘導技術的誘導精度，研究對Djkstra最短路徑算法進行了改進，提出了動態最短路徑誘導技術。通過在S市路網中的仿真分析，驗證改進算法的有效性。研究結果顯示，車輛的路徑誘導結果符合實際交通狀況，且在兩個時段的預測行駛時長僅相差26.3s，這說明動態最短路徑誘導技術具有可行性，并且能夠較好地滿足公眾日常出行需要。此次研究所提出的動態最短路徑算法表現出良好的可行性和適用性，并對于提高車輛出行效率、改善城市交通堵塞等問題具有借鑒性意義。

　　關鍵詞：車輛位置：數據;出行;路徑;算法

　　Abstract: The development of vehicle route guidance technology provides great convenience for the public' s daily travel. In order to improve the guidance accuracy of vehicle guidance technology, Dijkstra shortest path algorithm is improved, dynamic shortest path guidance technology is proposed. Through the simulation analysis in S city road network, the effectiveness of the improved algorithm is verified. The research results show that the results of vehicle route guidance are in line with the actual traffic conditions, and the predicted driving time difference between the two periods is only 26. 3s, which shows that the dynamic shortest route guidance technology is feasible and can better meet the needs of public daily travel The dvnamic shortest route algorithm proposed in this study shows good feasibility and applicability, and has reference significance for improving vehicle travel efficiency and improving urban traffic congestion.

　　Key words: vehicle location; data; travel; route; algorithm

　　0 引言

　　車輛的交通信息是交通管控的基礎，它實時地反映了車輛位置的變化情況。目前被廣泛應用的交通信息采集方式有兩種，分別是路基型和車基型檢測器。路基型檢測器主要是利用電磁波、聲波、紅外光波等進行車輛信息的檢測和采集，車基型檢測器的代表是浮動車技術。但是在實際應用中，這兩種檢測技術都有其局限之處，路基檢測器的實時性和準確性較差，浮動車技術無法保證檢測精度2。隨著城市交通網的形成，車輛的路徑導航技術逐漸成為民眾出行的日常需求。在這一背景下，交通信息的準確性直接影響到路徑導航技術的有效性，對采集數據進行評價和誤差控制是車輛路徑導航的基礎1。除此之外，數據的實時動態性已經逐漸成為車輛導航技術的發展趨勢，導航路徑的行駛時間和準確率直接體現了車輛導航技術的性能。這次研究考慮到交通實時路況的影響，提出了動態最短路徑算法，以期能提高車輛動態出行路徑誘導的有效性和準確性。

　　1車輛位置數據的預處理及誤差控制

　　車輛導航技術需要以車輛的位置信息為基礎，結合數據處理技術，得到速度、交通流狀態等多層面信息。由于車輛檢測器的局限性，原始的車輛位置數據存在數據缺失、數據突變等問題。為了保證后續系統分析的有效性，在這里將原始的車輛位置數據進行預處理，并對處理后的數據進行誤差控制。

　　在車輛位置數據的預處理中，主要從三個方面提高位置數據集的質量。一方面，當車流檢測數據中存在某一時間段無車輛行駛的情況時，需要將這種情況確認為位置數據缺失，并將其從可用數據集中刪除。另一方面，當突發交通事故時，路基車輛檢測器的車輛位置數據會產生突變。這種突變數據無法體現出數據的趨勢變化，會影響車輛導航系統的道路預測效果。但是當突變數據樣本數量增加時，它可以反映出道路的擁擠程度。在車輛位置數據的預處理中，可以通過下述公式評價數據的突變性。

　　用p表示數據的突變性閾值：用D(t)表示車輛位置信息的實測數據值：n，為車輛位置信息的歷史數據數量，通過式(3)可以得到數據的歷史趨勢值D，(r)。根據式(1)-(2)可知，將實測數據與歷史趨勢值相比，若在連續兩個時間間隔后，其偏離幅度超過突變性閾值，則認定實測數據為突變性數據：若在連續兩個時間間隔后，其偏離幅度小于突變性閾值，則認為數據突變結束。

　　此外，城市交通系統龐大且復雜，交通信息難免受到各種因素的影響，進而造成車輛位置數據的錯誤。在車輛位置信息的預處理中，需要將錯誤數據識別出來，并進行修復或刪除，以免錯誤數據影響后續分析的精度。在進行錯誤數據的識別判斷時，需要先設定正確數據的范圍，當超過這個范圍時，則將實測數據視為錯誤數據。式(4)、(5)分別表示正確數據的上限和下限。其中，o(r)表示歷史位置數據的標準差。

　　有研究表明，影響車輛位置數據精度的因素主要有三個方面，分別是GPS定位誤差、GIS地圖匹配誤差、GPS/DR融合誤差0-]。表1為GPS誤差分類。根據GPS系統的信號傳輸過程，可以將GPS定位誤差分為衛星部分、信號部分、信號接收部分和其他影響。前三種情況會導致1.5m~10.0m的測量誤差，最后一種情況所導的測量i差為1.0m.

　　由于車輛位置信息匹配到GIS電子地圖中，會經過數據傳輸等一系列過程，因此GIS電子地圖存在一定程度的誤差。有研究表明，GIS地圖的比例尺與匹配誤差存在定量關系，且匹配誤差隨著比例的增加而增加-10。如表2所示，當比例尺為1：5000時，電子地圖的匹配誤差為1.0m：當比例尺為1：10000時，電子地圖的匹配誤差為2.0m：當比例尺為1：25000時，電子地圖的匹配誤差為5.0m.

　　組合定位技術是目前新興的車輛定位技術，以GPS/DR組合定位為例，這種方式使得GPS和DR的定位信息能夠相互校正補償，從而改善單一定位技術的定位精度和可靠性。但是在GPS/DR的融合過程中，存在狀態估計誤差和傳播誤差。目前的解決方案是通過引入智能算法，降低數據融合的誤差，進而得到高精度的定位數據，如利用卡爾曼濾波器修正狀態估計誤差、利用小波分析進行信號降噪等。

　　2基于改進Dijkstra算法的車輛動態路徑誘導技術

　　2.1基于行程時間短時預測的動態簡化路網模型

　　在進行城市路徑誘導研究中，需要先建立城市路網模型。傳統的路網模型由兩個部分組成，分別是表示路段的有向弧和表示道路交叉口的節點，這種路網模型又稱有向圖。隨著路網研究的深入，傳統的路網模型已經不能滿足實際工作的需要，對真實路網進行簡化得到的路網模型，更能展現實際路網中的限制信息[2-1]。由于城市每天的交通狀況呈現出潮汐性變化規律，因此車輛導航系統需要參考城市交通的動態變化規律，進行合理的路徑誘導。在這里將建立動態簡化路網模型，如圖1所示，并在此基礎上進行后續的路徑誘導研究。

　　圖1(a)為傳統的路網模型，其中A表示道路交叉口節點，B.C、D、E表示有向路段：圖1(b)為動態簡化路網模型，在這里用G表示：用V表示路網交叉點，即模型的節點：用01表示交叉口的出口道數量：用E表示路網中的有向路段集合：用T表示時間序列，AT為時段間隔：用W表示路段行程時間的權值集合。下述表達式為動態簡化路網模型的數學表達式。

　　根據城市交通規律，動態路網模型可以根據時段劃分進行構建，也可以根據行程時間短時預測進行構建。在時段間隔極小的情況下，根據時段劃分的動態路網模型可以實時更新當前的路況情況，但是這種方法無法反映出未來的交通狀態。在根據行程時間短時預測構建的路網模型中，將交通參數的短時預測考慮到動態最短路徑規劃中，這種方式的誘導精度更好。假設短時預測的路網模型考慮到未來s時段的路況變化，且S= 1，2，..，M;用，表示預測的路段行程時間：用w，表示與當前交通狀況相似的歷史行程時間數據。根據行程時間短期預測所構建的動態簡化路網模型，需要在式(6)的基礎上，增加下述的數學表達式。

　　2.2 基于Dijkstra算法的靜態最短路徑誘導技術車輛的路徑誘導技術的關鍵在于最短路徑的計算。在簡化的路網模型中，通過智能算法使得每一路段的行程時間達到最短，可以得到車輛導航的最短路徑。根據交通信息的狀態，可以將最短路徑問題分為兩種類型：靜態最短路徑和動態最短路徑。靜態最短路徑問題是在靜態的交通信息中進行最短路徑研究，動態最短路徑問題是將交通信息的參數變化考慮到最短路徑研究中。經典的最短路徑算法有Floyd算法、A*算法、分層搜索法、遺傳算法、Dijkstra算法等，其中Djkstra算法是目前應用發展最完善的算法。因此這次研究將采用Djkstra算法進行最短路徑的算法研究。Dijkstra算法從源點出發，按照路徑長度逐點增長的方式，構建一顆路徑樹。它采用的是一種貪心策略，以源點為中心向外層層擴散，從而求出源點到其它頂點的最短路徑。在這一算法中，需要引入集合S和U，集合s用于記錄已求出最短路徑的頂點和相應的最短距離，集合U用于記錄還未求出最短路徑的頂點及其到源點的距離。

　　Dijkstra 算法僅適用于邊權為非負的情況，在路網結點很多時，這種算法的搜索效率會降低，且它的搜索速度受限于地圖的存儲結構。對于動態最短路徑問題，這里將在經典Dijkstra算法的基礎上進行改進，使其能適用于真實路網狀態下的最短路徑搜索。

　　2.3 基于改進Dijkstra算法的動態最短路徑誘導技術

　　在動態的路網中，每一個路段的行程時間都是動態變化的。由于交通規則等節點屬性的限制，使得行程時間具有可預測性。車輛進入路段的時刻決定了這一路段的行程時間，但只有在搜索過程中才能確定車輛進入路段的時刻。假設AT為一個時段的長度，用1表示不同時刻：用k表示行程中的不同路段，且路段是時刻具有連續性：當車輛經過路段k時，時間范圍為r4]：用7，表示車輛經過整個路段的用時。圖3為動態行程時間的計算模型。其中，橫坐標表示時間，縱坐標表示速度，橫、縱坐標的區域面積為在7，時段內的行駛距離。因此，這一模型的唯一約束條件為陰影部分面積等于1分析圖3的計算模型，可以得到下述方程。其中，x表示車輛到達路段 時的時段起點序號：T.表示路段k在時段(X，+i-1)的行程時間。

　　根據上述的路段行程時間權值公式，結合實時的交通信息計算出路段權值T，以此對Dijkstra算法進行改進。在改進算法中，需要根據路段行程時間預測表更新權值，以此實現最短路徑搜索的動態化。

　　3基于動態最短路徑誘導算法的仿真

　　分析

　　為了驗證改進Dijkstra算法在路徑誘導上的有效性，在這里選取s市的真實路網進行仿真實驗，實驗路段的簡化路網模型如圖4所示。在實驗中，采用1：20的比例尺對路段長度進行縮放，將車輛位置數據加載到Mapx 5.0平臺，采用Visual C++6.0進行改進Dijkstra算法的編譯工作。

　　圖4為S市實驗路網的簡化模型，根據路網結構可以發現，以A點為起始點，以J點為目的地，路網中共有15個交叉口。在實驗開始前對各個交叉口的主要路口進行編號，例如，交叉口A有三個主要路口，分別是A1，A2、A3。將各個交叉口的交通規則作為路網簡化模型的節點屬性，進行仿真實驗。根據圖4的簡化路網模型，建立路網節點鄰接表，如表3所示。

　　考慮到城市交通的潮汐性變化規律，分別選取了工作日的高峰期和平峰期兩個時段進行實驗，并設置實驗的周期長度為15min，時段間隔為180s，路段的行程時間來源于對10輛汽車行駛實測數據的平均值，并假設第一時段的起始時刻為系統接受響應的時刻。表4為高峰時段和平峰時段的路網動態行程時間，由于篇幅限制，這里僅展示部分數據統計結果。

　　根據改進Djkstra算法搜索動態行程時間最短路徑，表5為仿真實驗的統計結果。通過統計結果可以發現，在改進Dijkstra算法的路徑誘導中，平峰時段和高峰時段的最短路徑誘導結果是不同的：在平峰時段車輛經過6個路網節點，在高峰時段車輛經過10個路網節點：平峰時段的誘導路徑行駛時間為274.4s，高峰時段的誘導路徑行駛時間為300.7s.

　　結合實際的交通狀態進行分析，在平峰時段，起點和目的地之間的道路處于暢通狀態，因此最短路徑處于主干道上：在高峰時段，主干道的交通擁擠，此時需要避開擁擠路段，選擇車流量較少的路段。

　　在改進Dijkstra算法下，車輛在平峰時段和高峰時段的路徑誘導時長僅相差26.3s，這說明動態最短路徑誘導技術具有可行性，路徑誘導結果符合實際交通狀況，可以滿足實際出行的需要。

　　4結束語

　　傳統的路徑誘導技術是根據當前車輛位置數據進行路徑誘導，這種方式無法應對突發交通事故的影響。為了提高路徑誘導技術的靈活性和實用性，這次研究在經典的Dijkstra最短路徑算法基礎上，考慮到路段行程時間權值的動態變化，以此提出了車輛的動態最短路徑誘導算法。此外，為了提高路徑誘導的精度，這里提出對車輛位置數據進行預處理和誤差控制。通過對s市的實驗路網進行仿真分析得出，這次研究所提出的動態路徑誘導算法具有良好的適用性，希望此次研究能在車輛路徑誘導的研究和應用中提供一些參考。此外，這次研究尚且存在不足之處，如未能將算法的誘導結果與實際行駛結果進行對比，這將在以后的研究中作出改進。

　　參考文獻：

　　[1]丁宏飛，秦政，劉博，等，基于AFSVR的城市快速路多源交通信息融研t機1程與用，2017，53(5)：266-270.

　　[2]辛燕，馮霞，李婷婷.VANET中位置相關的輕量級Sybil攻擊檢測方法[1].通信學報，2017，38(4)：110-119

　　[3]李祎承，胡釗政，胡月志，等·基于GPS與圖像融合的智能車輛高精度定位算法[].交通運輸系統工程與信息，2017，17(3)：112-119.