基于免疫遺傳優(yōu)化的實時交通路徑誘導(dǎo)方法

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

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

1 引言

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

為實現(xiàn)交通路徑的有效誘導(dǎo)，陳業(yè)華[3]等人通過構(gòu)建緊急函數(shù)，利用行駛時間感知方法，給突發(fā)事件距離內(nèi)的用戶搭配行駛路線，并推算最短路徑信息。但該方法極易產(chǎn)生局部最優(yōu)解，計算精確性有待加強(qiáng)。鄧輝[4]等人通過明確車輛行駛數(shù)據(jù)，融合交通信號配時和路徑轉(zhuǎn)向信息，獲得現(xiàn)階段路段路阻，按照每個路段的路阻信息與路網(wǎng)拓?fù)洌暨x行程時間最短的路線為誘導(dǎo)路徑。但該方法冗余參變量較多，計算時間較長。

為進(jìn)一步改善城市交通擁堵現(xiàn)象，為駕駛員提供合理、高效行駛路線，提出一種基于免疫遺傳優(yōu)化的實時交通路徑誘導(dǎo)方法。組建實時交通局部路網(wǎng)模型展現(xiàn)整個交通道路拓?fù)浣Y(jié)構(gòu)，計算最短路徑的同時，使用免疫遺傳優(yōu)化方法中的評估、選擇、交叉等過程完成高效率車輛交通路徑誘導(dǎo)，并利用仿真證明了本文方法的可靠性。

2 實時交通局部路網(wǎng)模型構(gòu)建

(1)

在途行駛車輛一般會受到道路交通流的直接影響，道路交通狀態(tài)指數(shù)就是道路的交通流形態(tài)[5]。在局部路網(wǎng)模型內(nèi)，路阻越高，交通情況越糟糕，這也會影響模型節(jié)點之間的流通情況。

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

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

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

(2)

其中

(3)

其中，aij表示兩個節(jié)點的空間相鄰關(guān)聯(lián)。λ為路阻系數(shù)。

明確出行預(yù)期速率臨界值后，得到局部路網(wǎng)的空間動態(tài)臨界矩陣是

A(λ)=[aij(λ)]

(4)

其中

(5)

城市交通路網(wǎng)內(nèi)局部交通流數(shù)量較多，更易發(fā)生交通事故，導(dǎo)致車輛沒有經(jīng)過的誘導(dǎo)路徑產(chǎn)生堵塞，因此要及時更新誘導(dǎo)路徑[6]。

為保障駕駛路徑的較強(qiáng)連通性，使用動態(tài)連通性指標(biāo)推算并判斷車輛目前方位周邊的局部路網(wǎng)，同時實現(xiàn)誘導(dǎo)路徑更新目標(biāo)。局部路網(wǎng)將誘導(dǎo)路網(wǎng)內(nèi)駕駛的車輛方位作為標(biāo)準(zhǔn)，包含周邊某些范圍，并伴隨車輛行駛過程動態(tài)變換位置，一直維持從目前節(jié)點至終點的動態(tài)連通性能。

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

節(jié)點pO、pD均位于誘導(dǎo)路徑內(nèi)，兩者之間符合〈pO，pD〉的關(guān)聯(lián)，即行駛過程中首先通過節(jié)點pO，然后路過節(jié)點pD。為便于理解，把局部誘導(dǎo)路徑內(nèi)的節(jié)點依照車輛行駛路過的先后順序?qū)嵤┚幋a，也就是局部誘導(dǎo)路徑內(nèi)的節(jié)點〈pO，…，pi，…，pD〉當(dāng)作整數(shù)1，…，i，…，q。同理，節(jié)點pO、pD間的關(guān)聯(lián)也可記作pO

圖1 初始點和其余節(jié)點之間的關(guān)聯(lián)

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

(6)

若車輛抵達(dá)節(jié)點pGet并得到當(dāng)前交通數(shù)據(jù)，則

(7)

因此節(jié)點pO要符合如下收斂公式

(8)

終點與局部路網(wǎng)范圍對出行者在局部路網(wǎng)內(nèi)挑選可能的備用路徑擁有重要作用。恰當(dāng)?shù)慕K點路徑規(guī)劃可以確保在不同水準(zhǔn)的交通堵塞狀態(tài)下，和初始點之間始終具備一條可靠的連通路徑[8]。設(shè)定一個可達(dá)臨界值U，則終點要符合式(9)的約束條件。

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

(9)

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

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

(10)

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

3 實時交通最短路徑確定

利用上述過程在掌握整體交通路況狀態(tài)下，提取出擁堵時可以緩解交通壓力的最短路徑。實時動態(tài)交通誘導(dǎo)使用滾動循環(huán)策略完成交通疏導(dǎo)任務(wù)，其最短路徑Q的數(shù)學(xué)表達(dá)形式為

(11)

其中

(12)

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

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

(13)

根據(jù)路徑長短進(jìn)行排序[10-11]，將會獲得如下結(jié)果

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

(14)

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

4 免疫遺傳優(yōu)化下交通路徑誘導(dǎo)

免疫遺傳算法是在生物免疫前提下的改進(jìn)遺傳算法，將求解問題設(shè)置成抗原，解是免疫系統(tǒng)抗體。在局部路網(wǎng)規(guī)模龐大的情況下，應(yīng)用傳統(tǒng)遺傳算法探尋最短路徑難度很高，計算時間也隨之增多[12]。代入一個單點交叉算子完成優(yōu)化控制，從全局角度操控交叉過程，拓展解的搜尋空間，防止產(chǎn)生早熟收斂并呈現(xiàn)出陷入局部最優(yōu)解的現(xiàn)象?；诿庖哌z傳優(yōu)化的實時交通路徑誘導(dǎo)方法的運算過程如下：

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

步驟2：在抗體種群內(nèi)任意生成抗體樣本，在初次操作中，抗體個數(shù)隨機(jī)產(chǎn)生，但在二次操作時，需應(yīng)用免疫機(jī)制記憶功能?？贵w擁有優(yōu)秀的適應(yīng)度，因此能有效提升收斂速率。

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

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

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

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

(15)

由此推導(dǎo)出抗體濃度計算方程

(16)

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

(17)

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

整體來說，步驟3～6是一個評估、選擇、交叉與變異的循環(huán)流程，所以要反復(fù)執(zhí)行以上步驟，直到最優(yōu)個體適應(yīng)度函數(shù)低于某個預(yù)期值或?qū)崿F(xiàn)期望的加速循環(huán)次數(shù)，然后終止算法，實現(xiàn)高精度實時交通路徑誘導(dǎo)，緩解車輛高峰期出行不便的困擾，讓車輛可以更快抵達(dá)目的地。

5 仿真研究

利用仿真評估所提方法實用性，實驗平臺為VISSIM軟件。實驗方法為本文方法及文獻(xiàn)[3]、[4]方法，將某市堵塞區(qū)域路網(wǎng)為例，路網(wǎng)內(nèi)共11個節(jié)點，如圖2所示。

圖2 路網(wǎng)拓?fù)鋱D

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

圖3 三種方法路徑誘導(dǎo)所遇車輛的對比情況

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

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

表1 實時交通路徑誘導(dǎo)對比

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

6 結(jié)論

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