車輛導(dǎo)航系統(tǒng)中多路徑選擇算法的研究

歐陽(yáng)浩亞

(湖南省醴茶高速公路建設(shè)開(kāi)發(fā)有限公司，湖南株洲 412000)

0 引言

車輛導(dǎo)航系統(tǒng)是在路網(wǎng)數(shù)字化地圖的基礎(chǔ)上，運(yùn)用GPS、DR(Dead Reckoning)等定位技術(shù)進(jìn)行車輛定位，為駕駛員提供路徑引導(dǎo)信息，使車輛避開(kāi)擁擠區(qū)域，沿最佳路線到達(dá)目的地。車輛導(dǎo)航系統(tǒng)由四個(gè)子系統(tǒng)組成，路線選擇子系統(tǒng)是其核心組成部分之一，它的基本功能是在已知的路網(wǎng)上，按照一定的算法，為車輛駕駛員提供一條優(yōu)化合理的行駛路線，引導(dǎo)車輛快速、安全到達(dá)目的地。

近年來(lái)，隨著經(jīng)濟(jì)的快速發(fā)展，城市的車流量越來(lái)越大，城市交通狀況日漸復(fù)雜化，交通擁堵現(xiàn)象日趨嚴(yán)重。為了緩解交通壓力，國(guó)家相關(guān)部門提出大力投資交通基礎(chǔ)設(shè)施建設(shè)，單行線、路口禁止轉(zhuǎn)向等交通管制措施也被廣泛的采用，但是，機(jī)動(dòng)車的增長(zhǎng)速度遠(yuǎn)遠(yuǎn)超過(guò)道路基礎(chǔ)設(shè)施的建設(shè)速度，各種交通管制措施同時(shí)增加了出行的復(fù)雜性，于是，交通壓力越來(lái)越繁重。而且，汽車在遇上交通擁堵的情況下，廢氣的排放量是平時(shí)的好幾倍，燃油量也遠(yuǎn)遠(yuǎn)高于正常速度行駛的汽車，針對(duì)以上形勢(shì)，如何引導(dǎo)出行者根據(jù)自己的需求選擇最優(yōu)的路線，使其能夠盡量避免擁堵，避免違規(guī)駕駛，安全、順利、便捷的到達(dá)目的地是我們迫切需要解決的問(wèn)題。對(duì)于交通管理者來(lái)說(shuō)，出行者合理的路徑選擇可以使交通流盡量合理地分配在整個(gè)路網(wǎng)上，達(dá)到在現(xiàn)有的道路基礎(chǔ)設(shè)施中實(shí)現(xiàn)“路暢其行，貨暢其流”的優(yōu)化效果。因此，車輛導(dǎo)航系統(tǒng)中的路徑選擇子系統(tǒng)就應(yīng)運(yùn)而生了，并且擁有巨大的應(yīng)用前景和市場(chǎng)前景。

目前，大多數(shù)的路徑選擇子系統(tǒng)都能根據(jù)一定的目標(biāo)與約束條件(如出行距離)，在出行者指定的起訖點(diǎn)尋找一條最短行駛路徑，但由于車輛行進(jìn)中交通狀態(tài)通常不穩(wěn)定，出行者路徑選擇心里的復(fù)雜性，往往單一的僅考慮出行距離的行駛路線不能適應(yīng)交通流分配的需要和出行者的心理需要。例如出行距離最短的路線上交通十分擁堵、出行者考慮必須通過(guò)某條路等。因此，一個(gè)先進(jìn)、有效的路徑選擇子系統(tǒng)不能只為用戶提供單一的路線優(yōu)化方案，還應(yīng)提供次優(yōu)、次次優(yōu)、...、K優(yōu)等一系列合理的備選路徑方案供出行者根據(jù)實(shí)際情況進(jìn)行選擇。

對(duì)于車輛導(dǎo)航系統(tǒng)中的路徑選擇算法，目前國(guó)內(nèi)外已有一定的研究，一般情況下，路網(wǎng)節(jié)點(diǎn)較多的時(shí)候都需要用啟發(fā)式算法來(lái)求解，在路徑選擇的遺傳算法研究方面，文獻(xiàn)［1～5］都進(jìn)行了研究。David Eppstein［6］給出了一個(gè)新的簡(jiǎn)單路徑的有效算法，M.H.Macgregor［7］考慮在通信網(wǎng)絡(luò)中 K 最短路徑問(wèn)題。文獻(xiàn)［8］作者提出了任意兩點(diǎn)間K條最優(yōu)路徑問(wèn)題的遺傳算法。該方法采用節(jié)點(diǎn)的自然路徑作為染色體編碼，根據(jù)路徑節(jié)點(diǎn)的連接實(shí)施染色體的交叉操作，將節(jié)點(diǎn)路徑塊作為染色體的變異基因塊實(shí)施變異操作。為探索不同遺傳算法在K最短路上的求解性能，為出行者更合理、有效的選擇行駛路線，本文設(shè)計(jì)了單親遺傳算法來(lái)求解K最短路問(wèn)題。

1 單親遺傳算法及算子設(shè)計(jì)

1.1 編碼

將問(wèn)題的解編碼成為染色體是遺傳算法使用中的關(guān)鍵問(wèn)題，它直接影響到解碼操、適應(yīng)度計(jì)算和交叉、變異等算子的操作。設(shè)路網(wǎng)圖為G=(V，E)，V為節(jié)點(diǎn)構(gòu)成的集合，E為路網(wǎng)上邊所構(gòu)成的集合，節(jié)點(diǎn)由邊相連，各邊權(quán)值為dij，節(jié)點(diǎn)的序列為對(duì)應(yīng)的路徑。

個(gè)體編碼采用自然數(shù)編碼方式，如1-2-4-13則表示從起點(diǎn)1到終點(diǎn)13的一條路徑，該路徑途徑節(jié)點(diǎn)2和節(jié)點(diǎn)4。由于起點(diǎn)到終點(diǎn)的路徑上途徑節(jié)點(diǎn)的個(gè)數(shù)不確定，所以個(gè)體編碼采用變長(zhǎng)度的染色體方式。

1.2 適應(yīng)度函數(shù)

該問(wèn)題的數(shù)學(xué)模型為最小化問(wèn)題，故可以建立適應(yīng)度函數(shù)和目標(biāo)函數(shù)的映射關(guān)系，使得個(gè)體越優(yōu)良其適應(yīng)度值越大。具體為:

其中fitki代表第i代個(gè)體k的目標(biāo)函數(shù)值，fik為第i代個(gè)體k的適應(yīng)度值，P為一個(gè)足夠大的常數(shù)，由于在程序測(cè)試過(guò)程中發(fā)現(xiàn)最差個(gè)體適應(yīng)度值小于1 000，本文程序中的常數(shù)P值設(shè)置為1 500。

1.3 選擇算子

遺傳算法使用選擇算子(或稱復(fù)制算子)來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作:適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大;適應(yīng)度低的個(gè)體，被遺傳到下一代群體的概率小。

在本研究中我們用隨機(jī)生成方法產(chǎn)生初始種群，然后按適應(yīng)度比例方法(輪盤賭選擇)從父代中每次挑選兩個(gè)個(gè)體，以相應(yīng)的概率參加下面的變異操作。但是考慮到變異操作會(huì)使得父代個(gè)體優(yōu)良基因不能很好遺傳到下一代，本文在采取輪盤賭選擇的基礎(chǔ)上，增加了最佳個(gè)體保留策略。也就是在交叉完成之后，將父代個(gè)體中的最優(yōu)個(gè)體直接復(fù)制到下一代種群中。

1.4 變異算子

變異操作是為了在運(yùn)算過(guò)程中能改變某些成員的值，以避免失去一些有用的基因，防止某些成員的值處于不變的狀態(tài)，是一種防止算法早熟的措施。

考慮到在路徑中有兩種可能的方式使得路徑的長(zhǎng)度變短。首先，在某一路徑中添加一個(gè)新的節(jié)點(diǎn)就有可能使得路徑長(zhǎng)度更短。假如有路徑1-2-4-13，如果在節(jié)點(diǎn)2和節(jié)點(diǎn)4之間插入節(jié)點(diǎn)3使得路徑變?yōu)?-2-3-4-13，而路徑1-2-3-4-13有可能比路徑1-2-4-13更短。其次，更多的時(shí)候刪除路徑中的一些節(jié)點(diǎn)也有可能使得路徑長(zhǎng)度變短。如路徑1-2-4-13中刪除節(jié)點(diǎn)2使得路徑變?yōu)?-4-13。

基于這樣兩種思路，本文設(shè)置了兩個(gè)變異算子。

設(shè)有路徑a-b-c-d-e-f-g-h:

1)變異算子1:在初始路徑中隨機(jī)生成要插入的節(jié)點(diǎn)的位置，如為c，判斷是否有節(jié)點(diǎn)和節(jié)點(diǎn)c以及節(jié)點(diǎn)d都相鄰，若存在這類節(jié)點(diǎn)(如符合要求的節(jié)點(diǎn)為j，k)，則隨機(jī)選擇一個(gè)這類節(jié)點(diǎn)(如為j)插入到c和d之間，形成新的路徑a-b-c-j-d-e-f-g-h。

2)變異算子2:在初始路徑中隨機(jī)生成要?jiǎng)h除的節(jié)點(diǎn)的位置，如為c，順序地從路徑最后的節(jié)點(diǎn)h到c之間查找是否存在節(jié)點(diǎn)f(從最后的節(jié)點(diǎn)開(kāi)始刪除是基于更多節(jié)點(diǎn)的刪除能帶來(lái)路徑長(zhǎng)度更大的節(jié)省)，使得c和該節(jié)點(diǎn)相鄰，若存在，則刪除c和該位置節(jié)點(diǎn)之間的所有節(jié)點(diǎn)，形成新的路徑a-b-c-f-g-h。

2 算法流程

單親遺傳算法流程如圖1所示。

圖1 單親遺傳算法流程圖

3 算例驗(yàn)證

為了驗(yàn)證算法結(jié)果的正確性，本文選取湖南長(zhǎng)沙市某區(qū)域的實(shí)際路網(wǎng)進(jìn)行驗(yàn)證，圖中的節(jié)點(diǎn)表示實(shí)際道路的路口，每?jī)蓚€(gè)節(jié)點(diǎn)之間的權(quán)值代表行駛距離。該算例路網(wǎng)有26個(gè)節(jié)點(diǎn)，其具體的路網(wǎng)結(jié)構(gòu)圖如圖2所示。

第n次 符合數(shù) 第n次 符合數(shù)1 10 11 10 2 9 12 10 3 9 13 9 4 10 14 10 5 9 15 9 6 10 16 10 7 10 17 10 8 9 18 9 9 10 19 10 10 10 20 10

圖2 路網(wǎng)結(jié)構(gòu)圖

在輸入起點(diǎn)、終點(diǎn)和所要求的最短路的條數(shù)后，迭代200代，在CPU 1.66 GHz內(nèi)存下運(yùn)行約4 s可求出結(jié)果，結(jié)果如表1所示。

圖3 收斂效果圖

表1 路徑表

用該程序連續(xù)運(yùn)行20次，求解起點(diǎn)為1，終點(diǎn)為26的10條最短路徑。為了檢驗(yàn)本算法的效果，本文主要考慮兩個(gè)方面。一是連續(xù)運(yùn)行20次所得到的10條最短路與實(shí)際10條最短路相比符合的條數(shù);二是20次運(yùn)行中收斂效果最佳的一次迭代過(guò)程中每代個(gè)體中最佳的10個(gè)個(gè)體的適應(yīng)度的平均值。

20次運(yùn)行中，每次得到的十條最短路和實(shí)際的10條最短路相比符合的條數(shù)如表2所示。

20次運(yùn)行過(guò)程中，收斂效果最佳的一次的迭代過(guò)程中，每代個(gè)體最佳的10個(gè)個(gè)體的適應(yīng)度平均值收斂效果如圖3所示。

通過(guò)以上計(jì)算結(jié)果和分析可以看出，本文所設(shè)計(jì)的單親遺傳算法在求解K最短路問(wèn)題時(shí)能夠一次生成多條備選優(yōu)化路徑供出行者根據(jù)實(shí)際情況進(jìn)行路徑選擇，并且算法穩(wěn)定性好，收斂速度快，求解質(zhì)量高。

4 結(jié)論

車輛導(dǎo)航系統(tǒng)是交通發(fā)展的必然產(chǎn)物，本文主要對(duì)車輛導(dǎo)航系統(tǒng)中的路徑選擇子系統(tǒng)進(jìn)行路徑優(yōu)化算法的研究，通過(guò)設(shè)計(jì)一種性能良好的單親遺傳算法來(lái)求解K最短路問(wèn)題，并運(yùn)用實(shí)際的算例進(jìn)行了驗(yàn)證。結(jié)果表明，該算法能較好的根據(jù)出行者的實(shí)際需求生成多條路徑供出行者選擇。

此外，由于城市交通的復(fù)雜性，本文只對(duì)K最短路的算法進(jìn)行了研究，很多影響交通出行的因素并沒(méi)有和路徑選擇方案結(jié)合起來(lái)進(jìn)行具體的分析，實(shí)際上，還有很多問(wèn)題值得進(jìn)一步探討和研究。

1)出行者根據(jù)自己的客觀需求選擇行使路線是比較單一的選擇方案，但是，在交通實(shí)時(shí)信息不斷變化的情況下，如何把車輛導(dǎo)航系統(tǒng)中獲取的關(guān)于道路的流量、速度與密度的關(guān)系等實(shí)時(shí)信息和K最短路結(jié)合起來(lái)進(jìn)行路徑選擇的決策，仍待進(jìn)一步研究。

2)在路線選擇子系統(tǒng)中嵌入影響交通出行的因子，如道路暢通度，并設(shè)定當(dāng)?shù)缆窌惩ǘ冗_(dá)到一定的值時(shí)才考慮該行駛路徑，當(dāng)每條路徑的道路暢通度的值都很小時(shí)，我們可以初步判斷該路網(wǎng)已接近飽和，亟需增加交通基礎(chǔ)設(shè)施建設(shè)來(lái)緩解交通出行問(wèn)題。

［1］李成銀，江務(wù)學(xué).VC環(huán)境下遺傳算法在網(wǎng)絡(luò)最短路徑優(yōu)化中的設(shè)計(jì)與實(shí)現(xiàn)［J］.電腦開(kāi)發(fā)與應(yīng)用，2007，20(11):55-56.

［2］王麗星，郜 巍.多條最短路算法的優(yōu)化［J］.科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì)，1999(2):32-33.

［3］鄒 亮，徐建閩.基于遺傳算法的動(dòng)態(tài)網(wǎng)絡(luò)中最短路徑問(wèn)題算法［J］.計(jì)算機(jī)應(yīng)用，2005，25(4):742-744.

［4］劉汝正.基于遺傳算法的最短路徑的計(jì)算［J］.微計(jì)算機(jī)信息，2007，24(5):214-215.

［5］田奇君.基于遺傳算法的最短路徑問(wèn)題求解實(shí)現(xiàn)［J］.中國(guó)科技信息，2005(10):33.

［6］John Hershberger，Matthew Maxely，Subhash Suriz.Finding the K shortest simple paths:A new algorithm and its implementation［Z］.ALENEX Baltimore，2003.

［7］Macgegor M H，Grover WD.Optimized k-shortest-paths algorithm for facility restoration［J］.Software Practice and Experience，1994，24(9):823-828.

［8］馬 炫.求解k條最優(yōu)路徑問(wèn)題的遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006(12):100-101.