基于多目標的車輛導航最優路徑規劃研究

李 勇 仝春靈*

(山東交通學院 信息科學與電氣工程學院，山東 濟南 250357)

車輛導航系統是一種綜合利用GIS（地理信息系統）、計算機和通信技術進行全球定位的自動導航系統。它通過自動獲取交通網絡中道路的交通狀況和車輛的地理位置，為出行者找到從所在位置到目的地最優的行駛路線，幫助出行者輕松地前往他們想要到達的地方。

1 國內外發展概況

公元2600年前中國古代發明家馬鈞發明的指南車可以看成人類歷史上最早的車輛導航系統，19世紀導航技術開始真正用于汽車行駛，20世紀60年代末，在美國公共道路管理局的呼吁和支持下開發了電子路徑引導系統ERGS(Electronic Route Guidance System)。日本和德國在20世紀70年代也開始著手這方面技術的研究，進行了許多類似車輛導航方面的項目實驗。進入80年代后，車輛導航系統等相關技術在全球范圍內得到了快速發展，GPS技術迅速應用于車載導航系統中。通過在車輛上安裝GPS接收機，可以獲得車輛的當前位置、行駛速度和方向。但是車輛的GPS定位精準度通常容易受到衛星信號狀況和道路環境地勢的影響，因而簡單的GPS定位系統仍存在定位精度低、可靠性不理想等問題[1-2]。從20世紀90年代開始，國外導航研究者們將組合定位技術應用到車輛導航系統中,使得車輛的定位精度有了極大提高[3-5]。相對而言，我國的車載導航系統起步較晚，直到1980年才逐漸形成體系。但是隨著汽車導航系統的研究工作越來越受到人們的重視，汽車導航系統相關的專業論壇不斷舉行，又加上政府和有關部門的重視，高德、百度、騰訊、谷歌、360等大型科技公司都開發出了自己的導航系統并投入正常使用。目前，北斗導航APP也已上線。盡管這些系統已被廣泛應用，但是這些系統在最優路徑選擇方面還不是很完善，把車輛導入樓頂、河溝、斷崖的事件時有發生，因而在導航的準確性和靈活性方面還需要進一步改進[6]。

車輛導航系統的核心是最優路徑規劃[7-8]。最優路徑規劃是將城市交通信息管理中心發布的實時交通信息與車輛當前的路況信息進行綜合分析，利用車載導航設備在城市交通網絡中尋找出一條滿足出行者要求的從起始點到目的地的最優路徑。最優路徑規劃在軍事和民用領域都有廣泛的應用。車輛在道路上的行駛需要路徑規劃，導彈發射軌跡和飛機飛行航線也需要路徑規劃。目前，已有多種路徑規劃算法應用于導航系統中為人們的出行提供便捷的服務[9-11]。

本文在充分分析現有路徑規劃算法的基礎上，全面考慮到車輛行駛過程中影響路徑規劃的各種因素，通過優化目前的車輛導航路徑規劃算法，使車輛導航系統能夠滿足不同用戶的特殊需求，提供給出行者更加精準、靈活且符合個人要求的最優行駛路線。

2 研究內容、技術路線和創新點

路徑規劃能幫助駕駛員在特定的交通網絡中找到符合自身要求的最優行駛路線。根據規劃目標的不同，路徑規劃可劃分為多車輛綜合路徑規劃和單車輛導航路徑規劃。其中多車輛綜合路徑規劃主要應用于車隊整體調度和交通控制，單車輛導航路徑規劃就是通常所說的車輛導航系統。根據用戶在實際應用過程中的不同要求，路徑規劃可以以行車距離、花費時間、行駛費用、經過的交叉路口或路線的復雜程度等標準進行優化。無論采用哪種標準進行優化，最優路徑規劃最終都可以歸結為在特定的交通網絡中尋找代價最小的路徑問題，即圖論中的最短路徑問題。本文以實時交通信息為基礎，研究出最優的交通路徑以滿足用戶需求。

2.1 研究內容

本文研究的主要內容有：影響最優路徑的主要交通因素分析、基于多目標的車輛導航最優路徑規劃算法設計以及最優路徑的計算和選擇。

2.1.1 影響最優路徑選擇的交通因素分析

影響最優路徑選擇的交通因素主要包括：

（1）經過的交叉路口數量及交叉路口紅綠燈的等待時間；

（2）單行線和禁止轉彎情況；

（3）是否收通行費；

（4）路徑的復雜程度；

（5）上下班高峰期和節假日車輛出行量。

2.1.2 基于多目標的最優路徑規劃算法設計

基于多目標的最優路徑規劃算法分為以下4步：

（1）基于交通道路狀況實時信息建立路況交通網絡；

（2）對各種影響最優路徑的因素進行量化討論，使之轉化為節點和邊的權重；

（3）根據優化目標，設計最優路徑規劃算法；

（4）對（3）進行復雜性分析，并不斷改進最優路徑規劃算法，設法降低算法的時間復雜度。

2.1.3 最優路徑的計算和選擇

（1）根據2.1.2 設計的多目標最優路徑規劃算法，求不同優化目標下的最優路徑；

（2）對所求的最優路徑進行模擬分析，并根據結果逐步優化路徑的選擇，求得最佳路徑。

2.2 技術路線

最短路徑是加權有向圖中從一個頂點到另一頂點的權值總和最小的路徑。如果將路徑規劃中的優化目標量轉化為車輛行駛成本，則最優路徑規劃問題可以轉化為在特定交通網絡中尋找總行駛成本最小的路徑問題。常用的求解最短路徑的算法有蠻力算法、Dijkstra算法、Floyd算法和動態規劃算法。在深入分析各種算法的效率和適用范圍的基礎上，結合車輛導航的多目標優化的要求，本文選擇Dijkstra算法來求最優路徑。但是由于不同的駕駛員對路徑的要求不一樣，本文在應用Dijkstra算法求最短路徑時不僅根據不同的優化目標分別求出滿足出行者要求的最短路徑，而且對Dijkstra算法進行擴展：除了傳統的對有向邊進行賦值(權重)外，還對交通網絡圖的節點根據交叉路口紅綠燈的等待時間進行賦值調整，即：把節點擴展為路徑，將交通網絡圖轉化為其剖分圖，然后計算該剖分圖的單源最短路徑。圖1、2，顯示了某個交通網絡圖及其剖分圖。

圖1 交通網絡圖

圖2 交通網絡圖的剖分圖

當然，因為剖分圖有更多的點和有向邊，計算最短路徑的復雜性將大大增加，這又會帶來有關計算復雜度的一個問題，本文采用回溯和分支限界策略降低計算復雜度、提高計算效率。

2.3 創新點

2.3.1 在分析影響最優路徑的交通因素時考慮了路線的復雜性，并在目標優化中增加了以此為標準的最短路徑計算，為新手或路盲上路提供了更好的選擇。

2.3.2 將路口紅綠燈的等待時間轉換為交通網絡中節點的權值，從而把求交通網絡圖的最短路徑轉化為求其剖分圖的最短路徑，擴展了傳統的Dijkstra最短路徑算法。

2.3.3 在求交通網絡圖的剖分圖的最短路徑的過程中，為了降低復雜度、提高計算效率，使用了回溯和分支限界策略。

3 結論

本文通過全面分析影響最優路徑的各種交通因素，按照用戶的不同需求，進行合理量化賦值；而且根據不同的優化目標擴展傳統的Dijkstra最短路徑算法，從而為導航系統提供更加靈活、準確的最優行駛路線。同時，應用回溯和分支限界技術降低了最優路徑規劃算法的復雜度，加快了系統響應時間，提高了導航速度。本文中研究的最優路徑規劃算法應用到導航系統后，可以減少車輛在道路上的停留時間，提高出行效率；還可以合理避開交通擁堵，降低事故發生率。具體地說：

(1)在以距離、時間和費用為優化目標的最優路徑規劃中，使用本文提出的最優路徑規劃算法，車輛的行駛距離、時間或費用可以降低(或減少)5%-10%。

(2)在以線路的簡單性為目標的最優路徑規劃中，使用本文提出的最優路徑規劃算法，新手或路盲的導航使用滿意率可以提高12%-15%,事故發生率可以降低8%-10%。