1、摘要： 2關鍵詞： 2abstract 2Key words: 2弓I言 31、車輛定位導航系統動態路徑規劃研究現狀 32動態路徑規劃方案設計 43、基于車載導航的多用戶動態路徑規劃 53.1靜態路徑規劃算法的選擇 53.2 城市交通路網的劃分 73.3 動態路徑規劃的多用戶導航策略 83.3.1 多用戶動態路徑規劃分析 83.3.2 動態路徑規劃的多用戶導航策略 84、應用分析 115、結束語 12致謝 12參考文獻 13城市線路高效導航策略的研究摘要：伴隨著快速發展的經濟，城市交通擁擠現象愈演愈烈，已逐步成為制約城市經濟發展的嚴重問題。目前，隨著社會的發展，人們已經意識到智能交通系統是解決

2、交通擁擠的最佳辦法，而車輛導航系統作為智能交通系 統重要組成部分之一，又是其中的關鍵。本文圍繞城市線路高效導航的策略進行論述，介紹了車輛定位導航系 統動態路徑規劃研究現狀、動態路徑規劃方案設計、基于車載導航的多用戶動態路徑規劃最后是全文總結。本文基于多用戶導航動態路徑規劃的特點，闡明了多用戶導航動態路徑規劃的方法，即通過適當算法構造 出導航路徑表并進行周期性更新，當車輛決定出發前，用戶都可以通過這張表的相關信息來決定駕駛的最佳路 徑，且可在一定時間間隔后重新該表，以決定新駕駛路徑來實現動態路徑規劃。該方法通過計算上一時間周期 內的道路檢測器實測值并將結果以表的形式存儲，供出行者查閱。當用戶數增

3、加后，可降低總體開銷，提高車 輛導航的速度和效率來滿足多用戶導航的需求。關鍵詞：導航策略；Dijkstra 算法；動態路徑規劃；多用戶abstractWith the rapid developme nt of the economy, the urba n traffic jam has become more and more inten se, and has become a serious problem that con stra ins the econo mic developme nt of the city. At prese nt, with the developme

4、nt of the society, people have realized the in tellige nt tran sportati on system is the best way to solve the traffic con gestio n, and vehicle n avigati on system as an importa nt part of in tellige nt tran sportatio n system, is the key. This paper around the city line efficie ntly, the essay dis

5、cusses the strategies of n avigati on, vehicle n avigati on and positi oning system are in troduced and dyn amic path pla nning research prese nt situatio n, dyn amic path pla nning scheme desig n, based on the n avigati on of the multi-user dyn amic path pla nning is the full text summarized at las

6、t.In this paper, based on the characteristics of user n avigati on dyn amic path pla nning, n avigati on illu min ates the multi-user dyn amic path pla nning method, n amely through appropriate algorithm con structs the n avigati on path table and periodically updated, whe n the vehicle decided befo

7、re departure, users can through this list of releva nt in formatio n to determ ine the best path for driv ing, and the table aga in, after a certa in time in terval to determ ine the new drivi ng paths to realize dyn amic path pla nning. The method calculates the measured value of the road detector

8、in the time period and stores the results in the form of a table. When the nu mber of users in creases, the overall overhead can be reduced, in creas ing the speed and efficie ncy of vehicle n avigati on to meet the n eeds of multi-user n avigati on.Key words: n avigati on strategy; Dijkstra algorit

9、hm; Dyn amic path pla nning; Many users引言隨著人們生活水平的提高，汽車已從奢侈交通工具變成了普通交通工具，汽車保有量逐年增 長，汽車已走進千家萬戶，這就給城市交通帶來極大的壓力。而智能交通誘導系統，可隨時向出 行者和管理者發布動態交通信息、報告路況動態，幫助出行者制定出行計劃和駕車線路，已成為 提高城市交通效率、有效緩解道路交通壓力的有效手段之一；作為誘導系統中及其重要的組成部 分之一，車載導航系統在其中起重要作用。作為車載導航系統核心技術，路徑規劃的算法直接影 響導航的效果，好的規劃可幫助出行者在出行前或出行中規劃最佳路徑。路徑規劃有靜態路徑規劃和動態

10、路徑規劃兩種兩種路徑形式。其中，靜態路徑規劃中求解最 短路徑的算法一般為，把各路段交通路阻視作固定不變的值代入相應的路徑規劃。目前，市場中 導航系統基本基于此算法而推出的。近年來，隨著車流量的增大，交通事故和交通堵塞頻發，顯 而易見，靜態路徑規劃法已不適應當前實際情況，需進行新課題的研究。基于此，本文進行了適 合大規模多用戶導航的交通路阻，隨時間變化網絡的最短路徑問題，即動態路徑規劃策略的研 究。1、車輛定位導航系統動態路徑規劃研究現狀使起訖點間的交通阻抗最小是路徑規劃所依據的基本原則。作為一個廣義的概念，交通阻抗 可根據實際中差異性要求而采用設定不同的阻抗標準，如最少時間、最短距離、最低收費

11、等。而 時間、距離、收費等信息都可以路段屬性存儲于地圖中。并可將道路網絡中兩點之間的最優路徑 的計算轉化為圖論中求解帶全有向圖的最短路徑問題的解決。由于網絡特性、問題的特征等的復雜性，最短路徑算法也表現的多種多樣。按結節數目和特 征，最短路徑問題可以分為單對結點間最短路徑、所有結點間最短路徑、K則最短路徑、實時最 短路徑和指定必經結點的最短路徑這 5種類型。按網絡特征又可分為稠密網絡和稀疏網絡、有向 網絡和無向網絡等。按路徑搜索通用技術又可分為組合技術和代數技術。組合技術主要指大部分 最短路徑算法核心部分的標號算法。按照不同的結點處理，標號算法又可分為標號設定和標號改 正兩大體系。下圖為最短路

12、徑算法在導航系統中的應用分類，內容解釋如下：圖1 導航用最短路徑算法分類尋求算法分為實時自適應尋路和非實時尋路。其中實時尋路是指導航過程中，隨時對不斷變化 的交通信息進行實時更新而對最佳路徑重新計算修正，這就需要多次計算，主要依賴獲得實時交 通信息的頻率和所尋最優路徑的長度等因素。而非實時尋路是指，只在起始時刻進行一次尋路算 法計算，且在導航的整個過程中始終利用該結果，并不對實時交通信息進行修正和更新。2動態路徑規劃方案設計作為實現車輛導航系統其他功能的前提條件，路徑規劃是幫助駕駛員在出行前和行駛中規劃行 駛路線的過程。縱觀其發展史，路徑規劃研究，已先后經歷了靜態路徑規劃和動態路徑規劃兩個 過

13、程。靜態路徑規劃，是利用歷史數據或只利用地理信息系統信息進行規劃，同時把路段權重看做 是一個確定量，從而轉化為確定性的靜態最短路徑問題。這方面國內外已有很多學者對此做過深 入研究，并有很多成熟算法可以利用。但在實際操作中又有很多實際問題，一是記錄路網信息的 電子地圖數據庫數據龐大，不便于收集；二是受限于成本和車載環境，負責計算路徑規劃功能的 車載系統無法收集全部信息，這就導致車載導航系統處理能力和系統存儲資源有限，這就成為最 短路徑算法直接應用于車載導航系統面臨的一道難題。而動態路徑規劃與之不同，該路徑規劃因 為將路段權重看作是一個與時間相關的隨機變量，所以即轉變為隨機性最短路徑問題。在現實交

14、 通網絡中，路段權重不僅與單一變量有關，而且還與諸多不確定性因數有關，如路況、交通流 量、交通事故等等。這就體現了動態路徑規劃的優勢，該方法增加實時交通信息，使得出行者根 據車載導航系統提供的根據實時交通狀況更新而修改的行車路線形式。從整個交通路網來講，動 態路徑根據城市交通路網交通流量的動態特征，基于實際交通情況對車輛進行引導，有效地疏通 擁擠交通，是緩解交通壓力的有效措施；從出行者來講，它可以根據起終點實時更新路況，引導 出行者走出一條節約時間和金錢、安全舒適的道路。路徑規劃按導航對象可以分為多車輛路徑規劃和單個車輛路徑規劃，前者是針對整個道路網 絡，對道路上的所有車輛進行規劃，使所有車輛

15、總的行駛成本最小，改善交通；后者是對出行者 個體進行規劃，并使行駛成本達到最小。3、基于車載導航的多用戶動態路徑規劃動態路徑規劃主要考慮在時變交通網絡中尋找最短路徑問題。利用路段交通流的歷史數據，來 預測未來時段的交通流，將預測數據代入靜態路徑規劃算法來求出最短路徑是目前的主要研究方 向。該算法目的為通過把預測值代入靜態路徑規劃算法，達到動態路徑規劃。但完全依賴于預測 數據無法完全保證其準確性，是該方法的不足之處。本文通過嘗試將周期性路段實測數據帶入靜態路徑規劃算法，以實現模擬動態規劃的效果，該 方法更接近實際情況，且計算量較小，易于實現。3.1靜態路徑規劃算法的選擇經典的靜態路徑規劃算法有

16、Dijkstra 算法、Floyd算法、Lee算法、蟻群算法等。Dijkstra 算法是網絡拓撲中兩結點間的最短路徑搜索中公認的最經典算法。其特點是思想簡單、搜索質量穩定、搜索效率高。且其基本思想被多種常見算法采用(如啟發式搜索算法一A*算法)。本文運用Dijkstra 算法，來研究多用戶導航動態路徑規劃問題。Dijkstra 算法思路簡單，基本思路為從起點開始，對當前結點的所有子結點的權重進行更新，并選用權重最小者對當前結點更新，直到遍歷目標結點為止。當采用有向圖G(E，V)表示有向交通路網時，E表示路網的結點集合，V表示路網中邊的集 合。各條邊的交通路阻用權值表示，Dijkstra 算法如

17、下：初始化，將所有結點的權重都標注為無窮大；將起始結點的權重標為0，并作為當前結點w;檢查當前結點的子結點V，對每一個子結點用公式(1)計算新權重，當新權重小于舊權重時，對 權重進行更新：D ( v ) =D ( w) +D (w，v)(1)式中，D (v)為子結點v的權重；D (w)為當前結點w的權重；D (w, v)為結點w到v 的權重。按權重大小，對所有結點進行排序，當前結點選用權重最小的結點；重復3、4步驟，直到當前結點為目標結點為止；再從目標結點反溯，至起始結點并得到最短路徑。搜索過程中， 應設置兩個表，即待展開結點集合(OPEN和已展開結點集合(CLOSE)。OPEN表保存了所有已

18、 生成，卻未考察的結點；CLOSED表中記錄已訪問過的結點。算法中有根據結點權重重排OPEN表，即在每一次搜索中只考慮 OPEN表中狀態最好的結點。3.2城市交通路網的劃分在城市中，多數出行者從道路出行便利角度考慮，優先選擇主干道，其次為次干道。因此，我們可根據交通流密集程度，把城市路網分為若干級區域 具體交通網絡劃分，可對整個區域交通網絡，按照邊的等級不同，進行整體劃分。將分層好的整 體區域，利用區域樹對各個結點進行索引。首先對交通網絡中的點劃分等級，主要依據所定的邊的等級。原則是與該點連接的所有邊中 最大等級的邊的等級作為該點的等級。根據上述方法對區域具體劃分過程如下：首先取出一點，并指定

19、其區域號。按照規則，加入所有與之相關聯的點，分配相同區域號； 再對其他點，同法進行分配。分配結束的標志為每一個點均具有有區域號，分配結束后，將相同區域號的點存放在一起， 通過區域號建立區域層次樹。通過建立區域層次樹，可以減少查詢過程中點的遍歷。例如，在 1： 7： 2區域中一點作為起點，在1 : 3： 2區域中一點左右為終點。我們可通過三級道路在 1 : 7： 2的區域中不斷查找，直到找到二級道路，通過二級道路進入區域1： 7,再通過一級道路進入區域1,而后用降序進入區域1： 3,再通過二級道路進入區域1： 3： 2。下圖所示：1:3:11:1:2 133 1:7:11:73圖2區域層次樹3.

20、3動態路徑規劃的多用戶導航策略 331多用戶動態路徑規劃分析實際交通路網的動態路徑規劃有以下幾個特點：1. 實際的道路網絡錯綜復雜，結點數巨大，如果直接使用Dijkstra 算法，龐大的結點數目會使計算時間成倍增長，計算量會變得非常大，導致路徑查詢速度減慢。2. 作為時變網絡，交通路網自然不宜采用靜態路徑規劃方法。導航系統要求算法計算時間必須短，且能跟得上駕駛員的行駛速度，這樣才能保證及時給出導航建議，且計算必須準確。3. 道路交通流量的連續性，在一定時間間隔內相鄰時間的交通流量值可視為相同。目前，系統的路徑誘導優化多以單用戶車輛的路徑優化為主要目標。對多用戶導航動態 路徑規劃研究，至今不多。

21、當然，如果僅僅是簡單按照多次運行單用戶路徑誘導算法，來實現多 用戶導航，這必然會導致路徑誘導的速度和效率下降，因為，僅僅是多次運行單用戶路徑誘導的 計算量就達到增加。因此，這就需要我們針對多用戶導航的特點，研究和設計一種適合的動態路徑策略。通過上述分析，結合多用戶導航動態路徑規劃的特點，作者提出了一種易于實現的多用戶導 航動態路徑規劃方法。該方法主要通過相應算法，構造導航路徑表并進行周期性更新，保證任何 車輛出發前，都可查詢這張表，來決定駕駛的最佳路徑。同時，也可在一定時間間隔后，重新查 詢該表，以決定新的駕駛最佳路徑，實現動態路徑規劃。該方法通過計算上一時間周期內的道路 檢測器實測值并將結果

22、以表的形式存儲，供出行者查閱。當用戶數增加后，可降低總體開銷，提 高車輛導航的速度和效率來滿足多用戶導航的需求。3.3.2動態路徑規劃的多用戶導航策略Dijkstra 算法,實現動態路徑規劃的多用戶導航的一個關鍵技術是構造導航路徑表。采用 將各路段檢測器的檢測結果計算而得的交通路阻值代入，求得任意兩點最短路徑，將結果填入路徑表，路徑表的結構如下表所示：表1導航路徑表結構字段名稱字段類型字段寬度字段說明Start字符型100起始結點名稱Goal字符型100目的結點名稱Path字符型100兩結點間最短路徑用戶查詢的最佳路徑線路，在該表中均有記錄。如，一個新用戶查詢的起始點和終點之間的 路段，在同一

23、個時間更新周期內與其他用戶規劃過的路徑重疊時，那么，該用戶即可直接使用已 規劃好的最優路徑；但是，如果更新顯示，該段路況發生較大變化，例如發生擁堵現象，此時就 應考慮重新規劃最優路徑。我們將道路檢測器動態數據采樣周期定義為TO,那么，導航路徑表的更新周期列為 TO的倍數，如2T0或4T0；因為一般情況下，駕駛員比較討厭導航路線的頻繁更換，且并不嚴格要 求路徑最短，同時，對預測交通流要求也低，因此，我們可以每運行一定的時間（例如30分鐘后）再查詢導航路徑表，來確定最佳路徑。這樣設計的依據是，在判斷周期內，基于駕駛員對繞 路程度的容忍度，即使在該時間段路段流量發生了變化，且原規劃路線已不是最短路徑

24、時，駕駛 員仍不希望頻繁繞路，因此，駕駛員往往不會選擇更換路線；但是，如果判斷周期內，出現嚴重 擁擠等情況發生，駕駛員往往無法忍受而往往選擇改變導航線路；這就體現了在一定時間間隔后 重新規劃路徑的好處，這可以適應道路交通的變化，做出最適決定。該策略符合駕駛者實際行車 規律，充分考慮實際情況，在一定程度上避免過于頻繁的更換駕駛線路。車輛導航系統開始前準備步驟：1完成路網加載，采用劃分等級區域法，確定起點及終點的區域；2將采集的數據一次性代入Dijkstra 算法，計算出基于行程時間最短或費用成本最少的最佳路徑，導航路徑表如表1所示；3 2T0或3T0的時間周期性更新導航路徑表；導航系統初始化結束

25、后，可進行動態路徑規劃的多用戶導航，該導航策略如下圖所示，具體 步驟為：圖3動態路徑規劃的多用戶導航策略1 用戶選擇出發點和目的點；2在數據庫中查詢導航路徑表，直接取用全部或部分最優路徑決定駕駛的路徑;3按照推薦的最優路徑的下一路段行駛;4判斷是否偏離規劃的路徑，若是，返回第2步驟重新規劃最優路徑；若否，進入下一步驟；5每隔一定時間，判斷駕駛員是否需要更換線路，若是，返回第2步驟，重新規劃最優路徑；若否，進入下一步驟；6當重新進入一路段時，判斷其是否為目的地路段，若是，則結束；若否，再次進入第5步驟，直至到達目的地為止。4、應用分析圖4某城市交通網絡圖參考上圖所示的某城市各路段實時數據，結合電

26、子地圖，進行車輛動態路徑規劃的多用戶導 航實驗。該實驗采用作者提出的多用戶導航動態路徑規劃策略，同時，利用動態數據庫存放導航 路徑表數據。結合實際路況信息，利用前后的路徑導航效率和時間，多次對在更新周期內已存數 據進行了比較；盡管，在每個時間周期，系統都需重新計算最短路徑，但是，一旦計算結束，該 計算結果，駕駛者都可以通過查詢路徑表迅速找到答案，且不受區域和路段的限制，并且，當用戶數增加時，查表使用相同路徑或已有用戶查詢的路徑可使用戶快速獲取最佳路徑，避免了實時 計算所導致的導航速度慢等問題，既節省了導航計算的存儲空間，同時也避免了大量重復運算,又提高了路徑規劃的運算效率和速度。5、結束語本文對動態路徑的多用戶導航問題展開研究，提出了一種動態路徑多用戶導航策略，并結合 某城市實際交通路網對