基于免疫遺傳優化的實時交通路徑誘導方法

劉智萍，周清華，彭吉瓊，楊 真

(1.江西科技學院信息工程學院，江西 南昌 330098；2.江西科技學院，江西 南昌 330098；3.華東交通大學網絡信息中心，江西 南昌 330098)

1 引言

如今，汽車數量的迅速增多導致道路承載量受到威脅，交通事故、交通堵塞等問題較為嚴重[1]。為降低城市交通路網壓力，降低各類資源損耗，智能交通孕育而生。智能交通將計算機、通信、控制等高新技術有機融合并應用在交通指揮中，構建一種多角度、規模龐大且實時性強的交通運輸管理系統。其中交通路徑誘導為智能交通系統中的核心部分[2]，可按照不斷改變的交通現狀，快速準確地給出行者提供誘導數據，并以最快速度抵達目的地，完成網絡優化控制。

為實現交通路徑的有效誘導，陳業華[3]等人通過構建緊急函數，利用行駛時間感知方法，給突發事件距離內的用戶搭配行駛路線，并推算最短路徑信息。但該方法極易產生局部最優解，計算精確性有待加強。鄧輝[4]等人通過明確車輛行駛數據，融合交通信號配時和路徑轉向信息，獲得現階段路段路阻，按照每個路段的路阻信息與路網拓撲，挑選行程時間最短的路線為誘導路徑。但該方法冗余參變量較多，計算時間較長。

為進一步改善城市交通擁堵現象，為駕駛員提供合理、高效行駛路線，提出一種基于免疫遺傳優化的實時交通路徑誘導方法。組建實時交通局部路網模型展現整個交通道路拓撲結構，計算最短路徑的同時，使用免疫遺傳優化方法中的評估、選擇、交叉等過程完成高效率車輛交通路徑誘導，并利用仿真證明了本文方法的可靠性。

2 實時交通局部路網模型構建

(1)

在途行駛車輛一般會受到道路交通流的直接影響，道路交通狀態指數就是道路的交通流形態[5]。在局部路網模型內，路阻越高，交通情況越糟糕，這也會影響模型節點之間的流通情況。

代入一個出行預期速率臨界值λ，該臨界值定義了出行者期望實現的行駛速度均值。若某個路段的路阻高于臨界值，證明行車過程中無法處在順暢狀態，路阻接近無窮大，路段內眾多節點之間互不相通；反之，節點之間為相通狀態。

路阻矩陣D(λ)處于出行預期速率臨界值情況下，路網內鄰近的兩個節點間的真實通行代價，將其描述成

D(λ)=[dij(λ)]m×n

(2)

其中

(3)

其中，aij表示兩個節點的空間相鄰關聯。λ為路阻系數。

明確出行預期速率臨界值后，得到局部路網的空間動態臨界矩陣是

A(λ)=[aij(λ)]

(4)

其中

(5)

城市交通路網內局部交通流數量較多，更易發生交通事故，導致車輛沒有經過的誘導路徑產生堵塞，因此要及時更新誘導路徑[6]。

為保障駕駛路徑的較強連通性，使用動態連通性指標推算并判斷車輛目前方位周邊的局部路網，同時實現誘導路徑更新目標。局部路網將誘導路網內駕駛的車輛方位作為標準，包含周邊某些范圍，并伴隨車輛行駛過程動態變換位置，一直維持從目前節點至終點的動態連通性能。

局部路網最少包括誘導路徑內的兩個節點，將其定義成有向圖GLocal(PLocal，ELocal，D(λ)，pO，pD，λ)。PLocal代表局部路網節點集合，ELocal表示局部路網邊集合，pO為路徑初始點，pD為路徑結束點。

節點pO、pD均位于誘導路徑內，兩者之間符合〈pO，pD〉的關聯，即行駛過程中首先通過節點pO，然后路過節點pD。為便于理解，把局部誘導路徑內的節點依照車輛行駛路過的先后順序實施編碼，也就是局部誘導路徑內的節點〈pO，…，pi，…，pD〉當作整數1，…，i，…，q。同理，節點pO、pD間的關聯也可記作pO

圖1 初始點和其余節點之間的關聯

推算初始點po可為出行者更新路徑供應較為充分的時間完成決策反應，對局部路網計算、路徑更新等因素也具備較大影響[7]。

(6)

若車輛抵達節點pGet并得到當前交通數據，則

(7)

因此節點pO要符合如下收斂公式

(8)

終點與局部路網范圍對出行者在局部路網內挑選可能的備用路徑擁有重要作用。恰當的終點路徑規劃可以確保在不同水準的交通堵塞狀態下，和初始點之間始終具備一條可靠的連通路徑[8]。設定一個可達臨界值U，則終點要符合式(9)的約束條件。

Φ(L，M，pD，λ)≥U

(9)

局部路網范圍可直接決定了出行者挑選備用路徑的面積。若范圍較廣，備用路徑通常個數很多，在備用路徑滿足固定個數情況下，出行者就能找到最適合自己的連通路徑。但局部路網范圍廣帶來的直接問題為路徑冗余率過高，增加了人們的出行成本，給交通行駛帶來一定壓力[9]。

此外，通常擁有若干個符合式(9)需求的局部路網，但不同路徑的路阻各不相等，可達路阻越低的路網連通性能越優秀。所以最優局部路網的范圍要滿足下列約束公式

(10)

總結以上內容，按照交通堵塞臨界值與路阻函數，推算D(λ)值，并計算出起點pO，按照式(9)獲得終點pD，然后通過式(10)明確集合P與E的值，求出最優的局部路網，保證后續算法中能獲得更加完整的備用路徑，增強交通路徑誘導可靠性。

3 實時交通最短路徑確定

利用上述過程在掌握整體交通路況狀態下，提取出擁堵時可以緩解交通壓力的最短路徑。實時動態交通誘導使用滾動循環策略完成交通疏導任務，其最短路徑Q的數學表達形式為

(11)

其中

(12)

符合式(11)和收斂條件式(12)的解即為從出行初始點至終點的最短路徑。在實時交通路徑誘導的有向圖模型內，前K條最短路徑問題可以定義成：假設vi、vj是有向圖G中固定的兩個頂點，r是vi、vj間的一條路徑，長度是z(r)。通過vi、vj間的全部互不相等的路徑構成的集合R(G，vi，vj)為G內vi與vj之間的路徑集合，得到

R(G，vi，vj)={r}

(13)

根據路徑長短進行排序[10-11]，將會獲得如下結果

r1，r2，…，rQ|z(r1)≤z(r2)≤…≤z(rQ)

(14)

至此將r1當作有向圖內vi與vj之間的第一最短路徑，z(r1)表示長度，以此類推，rQ是有向圖內vi與vj之間的第Q個最短路徑，z(rQ)表示路徑長度。

4 免疫遺傳優化下交通路徑誘導

免疫遺傳算法是在生物免疫前提下的改進遺傳算法，將求解問題設置成抗原，解是免疫系統抗體。在局部路網規模龐大的情況下，應用傳統遺傳算法探尋最短路徑難度很高，計算時間也隨之增多[12]。代入一個單點交叉算子完成優化控制，從全局角度操控交叉過程，拓展解的搜尋空間，防止產生早熟收斂并呈現出陷入局部最優解的現象。基于免疫遺傳優化的實時交通路徑誘導方法的運算過程如下：

步驟1：從抗原種群內任意調選一個抗原個體，同時設置有關的參變量。待優化目標函數與各類收斂條件是免疫遺傳算法中的抗原，設定群體模式、交叉概率、變異概率三個目標項，群體模式M的值越高，搜尋區域面積越大，但各代的遺傳流程耗時就會變多，反之M越低遺傳操作時間越少，搜尋空間面積越小。

步驟2：在抗體種群內任意生成抗體樣本，在初次操作中，抗體個數隨機產生，但在二次操作時，需應用免疫機制記憶功能。抗體擁有優秀的適應度，因此能有效提升收斂速率。

步驟3：運算出抗體、抗原的親密度及濃度。依次算出抗原與抗體、抗體和抗體之間的親密度，抗原與抗體之間的親密度擁有Euclidean距離、Manhattan距離、Hamming距離等多個表達模式。

步驟4：更新記憶細胞。把和抗原親密度水平較高的抗體引入記憶細胞，記憶細胞個數擁有一定局限性，在記憶細胞內使用全新引入的抗體替代與自身親密度最高的原始抗體。

步驟5：抗體的促進與約束。免疫系統功能是利用遍布于身體各個部分的免疫細胞共同工作完成的。免疫細胞內含吞噬和淋巴兩種細胞類型。淋巴細胞內包含B、T不同作用的細胞。B細胞可以生成抗體，進行特異體液免疫，T細胞能完成特異細胞免疫及免疫調整。把抗原、B細胞與抗體看作優化問題的函數、解xi和求解適應度函數f(xi)。

N個抗體組成一個非空免疫系統集合X，將抗體f(xi)在集合X中的距離描述成

(15)

由此推導出抗體濃度計算方程

(16)

在式(16)基礎上，設計一個抗體濃度概率選擇解析式

(17)

步驟6：更新群體規模。變異操作與交叉操作的過程與遺傳算法大致相等，任意擇取兩個抗體。依照預先安排的變異概率實施變異，然后兩兩之間互相交叉，和更新之后的記憶細胞抗體變成全新的種群。

整體來說，步驟3～6是一個評估、選擇、交叉與變異的循環流程，所以要反復執行以上步驟，直到最優個體適應度函數低于某個預期值或實現期望的加速循環次數，然后終止算法，實現高精度實時交通路徑誘導，緩解車輛高峰期出行不便的困擾，讓車輛可以更快抵達目的地。

5 仿真研究

利用仿真評估所提方法實用性，實驗平臺為VISSIM軟件。實驗方法為本文方法及文獻[3]、[4]方法，將某市堵塞區域路網為例，路網內共11個節點，如圖2所示。

圖2 路網拓撲圖

以路段標號1-10為例，預測時間是晚高峰17：00～19：00，以7天為一個周期，計算三種路徑誘導方法下所經路線的車輛個數情況，遇到的車輛個數越少，證明實時交通路徑誘導可靠性越高，行駛更加暢通。實驗選用文獻[3]方法和文獻[4]方法作為實驗對照組，與所提方法的實驗結果進行對比。三種方法對比結果如圖3所示。

圖3 三種方法路徑誘導所遇車輛的對比情況

由圖3可知，兩個文獻方法誘導路徑策略下的道路車輛個數遠遠大于本文方法，而本文方法誘導路徑道路上的車輛個數最少，最貼合日常駕車出行的交通誘導需求。這是因為本文方法通過構建實時交通局部路網模型，并利用節點間的動態連通性得到交通路徑全局狀況，由此獲得高精度的交通量誘導路線。

對比三種方法在不更改出行時間狀況下，計算誘導路徑的最佳路徑分配結果，將預測交通量當作數據輸入，對路網采取仿真。三種方法下的實時交通路徑誘導情況如表1所示。

表1 實時交通路徑誘導對比

根據表1所得實驗結果可知，相比于兩個文獻方法，本文方法下的停車次數、通行時間均值、排隊延遲及排隊長度均有大幅度縮減，誘導后的路網車輛通行速率得到改善，擁堵情況也得到不同程度的緩解。本文方法在路徑擇取方面更加符合出行者的心理需求，并維持優秀的路網均衡，在全局上呈現出更優質的誘導成效，可以起到不同路面駕駛情況下的交通疏導作用。

6 結論

針對日益嚴峻的交通道路擁擠問題，提出基于免疫遺傳優化的實時交通路徑誘導方法。本文方法計算方便快捷，路徑規劃精度較高，通過與傳統方法的仿真對比，證明了所提方法的適用性與可靠性，給駕駛員提供實時交通數據的最短路徑，降低車輛停留時間，完善城市交通安全。