李 勇 仝春靈*

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

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

1 國內(nèi)外發(fā)展概況

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

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

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

2 研究內(nèi)容、技術(shù)路線和創(chuàng)新點

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

2.1 研究內(nèi)容

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

2.1.1 影響最優(yōu)路徑選擇的交通因素分析

影響最優(yōu)路徑選擇的交通因素主要包括：

（1）經(jīng)過的交叉路口數(shù)量及交叉路口紅綠燈的等待時間；

（2）單行線和禁止轉(zhuǎn)彎情況；

（3）是否收通行費；

（4）路徑的復雜程度；

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

2.1.2 基于多目標的最優(yōu)路徑規(guī)劃算法設計

基于多目標的最優(yōu)路徑規(guī)劃算法分為以下4步：

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

（2）對各種影響最優(yōu)路徑的因素進行量化討論，使之轉(zhuǎn)化為節(jié)點和邊的權(quán)重；

（3）根據(jù)優(yōu)化目標，設計最優(yōu)路徑規(guī)劃算法；

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

2.1.3 最優(yōu)路徑的計算和選擇

（1）根據(jù)2.1.2 設計的多目標最優(yōu)路徑規(guī)劃算法，求不同優(yōu)化目標下的最優(yōu)路徑；

（2）對所求的最優(yōu)路徑進行模擬分析，并根據(jù)結(jié)果逐步優(yōu)化路徑的選擇，求得最佳路徑。

2.2 技術(shù)路線

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

圖1 交通網(wǎng)絡圖

圖2 交通網(wǎng)絡圖的剖分圖

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

2.3 創(chuàng)新點

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

2.3.2 將路口紅綠燈的等待時間轉(zhuǎn)換為交通網(wǎng)絡中節(jié)點的權(quán)值，從而把求交通網(wǎng)絡圖的最短路徑轉(zhuǎn)化為求其剖分圖的最短路徑，擴展了傳統(tǒng)的Dijkstra最短路徑算法。

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

3 結(jié)論

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

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

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