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

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

1 引言

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

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

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

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

(1)

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

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

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

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

(2)

其中

(3)

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

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

A(λ)=[aij(λ)]

(4)

其中

(5)

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

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

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

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

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

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

(6)

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

(7)

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

(8)

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

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

(9)

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

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

(10)

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

3 實(shí)時(shí)交通最短路徑確定

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

(11)

其中

(12)

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

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

(13)

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

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

(14)

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

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

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

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

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

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

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

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

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

(15)

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

(16)

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

(17)

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

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

5 仿真研究

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

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

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

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

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

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

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

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

6 結(jié)論

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