基于多目標(biāo)的車(chē)輛導(dǎo)航最優(yōu)路徑規(guī)劃研究

李 勇 仝春靈*

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

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

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

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

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

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

2 研究?jī)?nèi)容、技術(shù)路線(xiàn)和創(chuàng)新點(diǎn)

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

2.1 研究?jī)?nèi)容

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

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

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

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

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

（3）是否收通行費(fèi)；

（4）路徑的復(fù)雜程度；

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

2.1.2 基于多目標(biāo)的最優(yōu)路徑規(guī)劃算法設(shè)計(jì)

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

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

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

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

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

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

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

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

2.2 技術(shù)路線(xiàn)

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

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

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

當(dāng)然，因?yàn)槠史謭D有更多的點(diǎn)和有向邊，計(jì)算最短路徑的復(fù)雜性將大大增加，這又會(huì)帶來(lái)有關(guān)計(jì)算復(fù)雜度的一個(gè)問(wèn)題，本文采用回溯和分支限界策略降低計(jì)算復(fù)雜度、提高計(jì)算效率。

2.3 創(chuàng)新點(diǎn)

2.3.1 在分析影響最優(yōu)路徑的交通因素時(shí)考慮了路線(xiàn)的復(fù)雜性，并在目標(biāo)優(yōu)化中增加了以此為標(biāo)準(zhǔn)的最短路徑計(jì)算，為新手或路盲上路提供了更好的選擇。

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

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

3 結(jié)論

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

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

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