車輛導航系統中多路徑選擇算法的研究

歐陽浩亞

(湖南省醴茶高速公路建設開發有限公司，湖南株洲 412000)

0 引言

車輛導航系統是在路網數字化地圖的基礎上，運用GPS、DR(Dead Reckoning)等定位技術進行車輛定位，為駕駛員提供路徑引導信息，使車輛避開擁擠區域，沿最佳路線到達目的地。車輛導航系統由四個子系統組成，路線選擇子系統是其核心組成部分之一，它的基本功能是在已知的路網上，按照一定的算法，為車輛駕駛員提供一條優化合理的行駛路線，引導車輛快速、安全到達目的地。

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

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

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

1 單親遺傳算法及算子設計

1.1 編碼

將問題的解編碼成為染色體是遺傳算法使用中的關鍵問題，它直接影響到解碼操、適應度計算和交叉、變異等算子的操作。設路網圖為G=(V，E)，V為節點構成的集合，E為路網上邊所構成的集合，節點由邊相連，各邊權值為dij，節點的序列為對應的路徑。

個體編碼采用自然數編碼方式，如1-2-4-13則表示從起點1到終點13的一條路徑，該路徑途徑節點2和節點4。由于起點到終點的路徑上途徑節點的個數不確定，所以個體編碼采用變長度的染色體方式。

1.2 適應度函數

該問題的數學模型為最小化問題，故可以建立適應度函數和目標函數的映射關系，使得個體越優良其適應度值越大。具體為:

其中fitki代表第i代個體k的目標函數值，fik為第i代個體k的適應度值，P為一個足夠大的常數，由于在程序測試過程中發現最差個體適應度值小于1 000，本文程序中的常數P值設置為1 500。

1.3 選擇算子

遺傳算法使用選擇算子(或稱復制算子)來實現對群體中的個體進行優勝劣汰操作:適應度高的個體被遺傳到下一代群體中的概率大;適應度低的個體，被遺傳到下一代群體的概率小。

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

1.4 變異算子

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

考慮到在路徑中有兩種可能的方式使得路徑的長度變短。首先，在某一路徑中添加一個新的節點就有可能使得路徑長度更短。假如有路徑1-2-4-13，如果在節點2和節點4之間插入節點3使得路徑變為1-2-3-4-13，而路徑1-2-3-4-13有可能比路徑1-2-4-13更短。其次，更多的時候刪除路徑中的一些節點也有可能使得路徑長度變短。如路徑1-2-4-13中刪除節點2使得路徑變為1-4-13。

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

設有路徑a-b-c-d-e-f-g-h:

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

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

2 算法流程

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

圖1 單親遺傳算法流程圖

3 算例驗證

為了驗證算法結果的正確性，本文選取湖南長沙市某區域的實際路網進行驗證，圖中的節點表示實際道路的路口，每兩個節點之間的權值代表行駛距離。該算例路網有26個節點，其具體的路網結構圖如圖2所示。

第n次 符合數 第n次 符合數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 路網結構圖

在輸入起點、終點和所要求的最短路的條數后，迭代200代，在CPU 1.66 GHz內存下運行約4 s可求出結果，結果如表1所示。

圖3 收斂效果圖

表1 路徑表

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

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

20次運行過程中，收斂效果最佳的一次的迭代過程中，每代個體最佳的10個個體的適應度平均值收斂效果如圖3所示。

通過以上計算結果和分析可以看出，本文所設計的單親遺傳算法在求解K最短路問題時能夠一次生成多條備選優化路徑供出行者根據實際情況進行路徑選擇，并且算法穩定性好，收斂速度快，求解質量高。

4 結論

車輛導航系統是交通發展的必然產物，本文主要對車輛導航系統中的路徑選擇子系統進行路徑優化算法的研究，通過設計一種性能良好的單親遺傳算法來求解K最短路問題，并運用實際的算例進行了驗證。結果表明，該算法能較好的根據出行者的實際需求生成多條路徑供出行者選擇。

此外，由于城市交通的復雜性，本文只對K最短路的算法進行了研究，很多影響交通出行的因素并沒有和路徑選擇方案結合起來進行具體的分析，實際上，還有很多問題值得進一步探討和研究。

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

2)在路線選擇子系統中嵌入影響交通出行的因子，如道路暢通度，并設定當道路暢通度達到一定的值時才考慮該行駛路徑，當每條路徑的道路暢通度的值都很小時，我們可以初步判斷該路網已接近飽和，亟需增加交通基礎設施建設來緩解交通出行問題。

［1］李成銀，江務學.VC環境下遺傳算法在網絡最短路徑優化中的設計與實現［J］.電腦開發與應用，2007，20(11):55-56.

［2］王麗星，郜 巍.多條最短路算法的優化［J］.科技情報開發與經濟，1999(2):32-33.

［3］鄒 亮，徐建閩.基于遺傳算法的動態網絡中最短路徑問題算法［J］.計算機應用，2005，25(4):742-744.

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

［5］田奇君.基于遺傳算法的最短路徑問題求解實現［J］.中國科技信息，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條最優路徑問題的遺傳算法［J］.計算機工程與應用，2006(12):100-101.