李 勇 仝春靈*
(山東交通學院 信息科學與電氣工程學院,山東 濟南 250357)
車輛導航系統(tǒng)是一種綜合利用GIS(地理信息系統(tǒng))、計算機和通信技術(shù)進行全球定位的自動導航系統(tǒng)。它通過自動獲取交通網(wǎng)絡中道路的交通狀況和車輛的地理位置,為出行者找到從所在位置到目的地最優(yōu)的行駛路線,幫助出行者輕松地前往他們想要到達的地方。
公元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ā)布的實時交通信息與車輛當前的路況信息進行綜合分析,利用車載導航設(shè)備在城市交通網(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)行駛路線。
路徑規(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)的交通路徑以滿足用戶需求。
本文研究的主要內(nèi)容有:影響最優(yōu)路徑的主要交通因素分析、基于多目標的車輛導航最優(yōu)路徑規(guī)劃算法設(shè)計以及最優(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ī)劃算法設(shè)計
基于多目標的最優(yōu)路徑規(guī)劃算法分為以下4步:
(1)基于交通道路狀況實時信息建立路況交通網(wǎng)絡;
(2)對各種影響最優(yōu)路徑的因素進行量化討論,使之轉(zhuǎn)化為節(jié)點和邊的權(quán)重;
(3)根據(jù)優(yōu)化目標,設(shè)計最優(yōu)路徑規(guī)劃算法;
(4)對(3)進行復雜性分析,并不斷改進最優(yōu)路徑規(guī)劃算法,設(shè)法降低算法的時間復雜度。
2.1.3 最優(yōu)路徑的計算和選擇
(1)根據(jù)2.1.2 設(shè)計的多目標最優(yōu)路徑規(guī)劃算法,求不同優(yōu)化目標下的最優(yōu)路徑;
(2)對所求的最優(yōu)路徑進行模擬分析,并根據(jù)結(jié)果逐步優(yōu)化路徑的選擇,求得最佳路徑。
最短路徑是加權(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.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)絡圖的剖分圖的最短路徑的過程中,為了降低復雜度、提高計算效率,使用了回溯和分支限界策略。
本文通過全面分析影響最優(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%。