董勇剛,譚 燕

(1.湖北省交通規(guī)劃設(shè)計(jì)院股份有限公司，湖北 武漢 430064；2.湖北工業(yè)大學(xué) 土木建筑與環(huán)境學(xué)院 ，湖北 武漢 430072)

0 引 言

區(qū)域內(nèi)汽車的保有量逐漸增長，使得區(qū)域道路交通狀態(tài)日益惡化。交通運(yùn)行狀態(tài)如果較差，將會(huì)對(duì)社會(huì)發(fā)展和人們的工作、生活造成較大的影響，甚至造成巨大的經(jīng)濟(jì)損失[1-2]。因此，為了滿足人民群眾對(duì)美好生活的需求，設(shè)計(jì)有效的道路網(wǎng)規(guī)劃和車輛誘導(dǎo)措施具有重要的現(xiàn)實(shí)意義。

為提升區(qū)域交通運(yùn)輸水平、緩解交通擁堵狀態(tài)，文獻(xiàn)[3]在道路運(yùn)行監(jiān)管系統(tǒng)中設(shè)置通信數(shù)據(jù)采集設(shè)備，應(yīng)用ITS技術(shù)實(shí)現(xiàn)對(duì)區(qū)域交通中汽車數(shù)據(jù)的無縫采集與實(shí)時(shí)傳輸，建立24 h獲取數(shù)據(jù)信息的區(qū)域交通路徑規(guī)劃網(wǎng)絡(luò)。在這種系統(tǒng)的支持下，區(qū)域道路網(wǎng)規(guī)劃系統(tǒng)主要研究道路的空間變化與交通流量的神經(jīng)網(wǎng)絡(luò)測試，能夠有效協(xié)調(diào)區(qū)域道路中汽車流量，但是不能對(duì)汽車行駛方向和最優(yōu)路徑進(jìn)行引導(dǎo)。文獻(xiàn)[4]采用動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)技術(shù)，實(shí)現(xiàn)區(qū)域道路網(wǎng)紅外信標(biāo)通信，從而對(duì)擁堵路況展開調(diào)度。這種方式需要在汽車上安裝與動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)技術(shù)相匹配的語音導(dǎo)航系統(tǒng)，并需要安裝交通數(shù)據(jù)頻道的廣播設(shè)備，從而保障汽車導(dǎo)航數(shù)據(jù)的實(shí)時(shí)精準(zhǔn)性。但這種系統(tǒng)對(duì)車輛最優(yōu)路徑的規(guī)劃能力較差。

免疫遺傳算法是基于生物免疫機(jī)制提出的一種改進(jìn)遺傳算法，可對(duì)應(yīng)傳統(tǒng)遺傳算法中個(gè)體的多樣性，有利于提高遺傳算法的全局搜索能力，避免其陷入局部最優(yōu)。因此，為進(jìn)一步優(yōu)化區(qū)域道路網(wǎng)路徑誘導(dǎo)能力，本文基于免疫遺傳算法設(shè)計(jì)了新的區(qū)域道路網(wǎng)智能路徑規(guī)劃系統(tǒng)，其創(chuàng)新之處在于運(yùn)用該算法對(duì)最優(yōu)路徑不斷的進(jìn)行迭代，得出最優(yōu)解，再通過層次搜索法和限制區(qū)域搜索法對(duì)得出的最優(yōu)解，進(jìn)行區(qū)域性的固定與限制，以增強(qiáng)智能路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性。

1 系統(tǒng)設(shè)計(jì)

為了使區(qū)域道路網(wǎng)中智能路徑誘導(dǎo)系統(tǒng)隨時(shí)掌握區(qū)域道路交通狀態(tài)，本文在免疫遺傳算法的基礎(chǔ)上進(jìn)行硬件設(shè)備的開發(fā)與設(shè)計(jì)，從而完成對(duì)路徑誘導(dǎo)系統(tǒng)中的交通數(shù)據(jù)收集、處理等功能的設(shè)計(jì)。基于免疫遺傳算法的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)硬件結(jié)構(gòu)如圖1所示。

圖 1 區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)硬件結(jié)構(gòu)Fig.1 Hardware architecture of intelligent path guidance system in regional road network

圖1中的VICS、Euro-Scout型號(hào)路徑誘導(dǎo)設(shè)備作為紅外信標(biāo)的標(biāo)識(shí)設(shè)備，需要安裝在區(qū)域道路網(wǎng)中，方便工作人員的及時(shí)管理，同時(shí)也能夠精準(zhǔn)地識(shí)別道路中的車輛信息。這2種類型的紅外信標(biāo)設(shè)備可以通過自身發(fā)射的紅外信號(hào)與車輛接收設(shè)備之間的通信時(shí)長、數(shù)據(jù)類型等信息確定系統(tǒng)數(shù)據(jù)中心對(duì)車輛運(yùn)行情況的計(jì)算[5-7]。系統(tǒng)硬件部分通過區(qū)域道路網(wǎng)誘導(dǎo)控制中心數(shù)據(jù)庫的命令，向車載路徑誘導(dǎo)系統(tǒng)發(fā)送實(shí)時(shí)交通狀態(tài)，并結(jié)合區(qū)域道路的突發(fā)事件進(jìn)行信息更改與處理，向硬件設(shè)備提供穩(wěn)定、有效的基礎(chǔ)信息。在區(qū)域交通路徑中，比較重要的交通路口需要裝配具有信息發(fā)送與信息采集功能的數(shù)據(jù)信息收集板，同時(shí)，還能夠?yàn)檐囕d單元提供相應(yīng)的道路信息文本，最終呈現(xiàn)于車載屏幕上，并按照一定類型的模糊聚類原理劃分不同道路的交通擁擠狀態(tài)，能夠提供給系統(tǒng)用戶穩(wěn)定且實(shí)時(shí)的道路擁擠狀態(tài)[8-9]。

此外，本文應(yīng)用北斗衛(wèi)星雷達(dá)和民用交通型號(hào)衛(wèi)星雷達(dá)作為全球道路網(wǎng)絡(luò)的信息覆蓋硬件設(shè)備，為用戶提供精準(zhǔn)三維數(shù)據(jù)模型與速度信息，通過差分方式將汽車的位置信息定位至1～2 m，滿足大多數(shù)普通雷達(dá)的位置精準(zhǔn)度。在衛(wèi)星雷達(dá)中裝置偽隨機(jī)噪聲碼設(shè)備，能夠?yàn)樾l(wèi)星雷達(dá)提供抗干擾信號(hào)與信息傳播通道，保證在區(qū)域道路網(wǎng)絡(luò)智能路徑規(guī)劃過程中不出現(xiàn)較大數(shù)據(jù)誤差與干擾因子[10-11]。相對(duì)于軍用雷達(dá)來講，民用交通型號(hào)衛(wèi)星雷達(dá)偏差較大，但應(yīng)用于區(qū)域交通網(wǎng)智能路徑規(guī)劃完全能夠滿足汽車的路徑行駛規(guī)范[12]。

本研究還在衛(wèi)星雷達(dá)中安裝了基點(diǎn)信息接收器，能夠反饋區(qū)域道路智能路徑誘導(dǎo)過程中的測量距離與現(xiàn)實(shí)距離之間的誤差，接收器中的終端接口再向系統(tǒng)用戶傳達(dá)經(jīng)過接收器修正過的定位系統(tǒng)動(dòng)態(tài)值。衛(wèi)星雷達(dá)的接收機(jī)作為信息誤差的修正設(shè)備，結(jié)合衛(wèi)星雷達(dá)中的數(shù)據(jù)慣性以及定位觀測量完成數(shù)據(jù)的實(shí)時(shí)修正，提升原始雷達(dá)數(shù)據(jù)的穩(wěn)定性與精準(zhǔn)性[13-15]。為對(duì)車輛的導(dǎo)航信息確定方式進(jìn)行優(yōu)化與改善，本文采用ADVANCE型號(hào)設(shè)備，通過自主通信的方式誘導(dǎo)數(shù)據(jù)定位算法與車輛流量的關(guān)聯(lián)。

2 免疫遺傳算法

路徑誘導(dǎo)的作用是指應(yīng)用連接法確定出發(fā)點(diǎn)和終點(diǎn)之間的距離、道路狀態(tài)等信息，然后在區(qū)域道路網(wǎng)中確定兩點(diǎn)之間的最優(yōu)行駛路線[16-17]。

本文應(yīng)用免疫遺傳算法設(shè)計(jì)智能路徑誘導(dǎo)系統(tǒng)，確定區(qū)域道路網(wǎng)中智能路徑與遺傳算法中染色體等串位結(jié)構(gòu)之間的關(guān)聯(lián)，應(yīng)用編碼對(duì)排列運(yùn)算路徑誘導(dǎo)信息，同時(shí)，需要結(jié)合實(shí)時(shí)的道路運(yùn)行狀態(tài)信息與免疫遺傳算法中染色體等因素的算法功能，設(shè)定免疫遺傳算法中染色體的長度代表路徑規(guī)劃的初始點(diǎn)與結(jié)束點(diǎn)。染色體內(nèi)包含的子染色體是未知因素，其具有一定的延展性。因此，在設(shè)計(jì)編碼的過程中，需要將區(qū)域道路網(wǎng)中所有的路徑信息全部涵蓋。

遺傳免疫算法中的染色體具有不可重復(fù)的特點(diǎn)[18-19]。因此，當(dāng)區(qū)域道路中具有環(huán)路、立交橋等路狀時(shí)，不考慮將其道路信息添加至免疫遺傳算法中，從而減少編碼儲(chǔ)存空間。在區(qū)域道路網(wǎng)中設(shè)置n個(gè)節(jié)點(diǎn)。則道路網(wǎng)中共有n個(gè)道路的初始點(diǎn)或終點(diǎn)，計(jì)算不同點(diǎn)之間的最佳路徑時(shí)，可以對(duì)點(diǎn)與點(diǎn)之間進(jìn)行路徑個(gè)體編碼，編碼中的終點(diǎn)為基因結(jié)束位置，路徑經(jīng)過點(diǎn)位為基因串。免疫遺傳算法在系統(tǒng)中的路徑規(guī)劃步驟如下：

1) 獲取區(qū)域內(nèi)的路徑數(shù)據(jù)信息并生成基因種群結(jié)構(gòu)；

2) 模擬路徑的相關(guān)參數(shù)并設(shè)定路徑規(guī)劃中所應(yīng)用的初始值；

3) 在種群數(shù)據(jù)中尋找具有代表性的路徑運(yùn)算參數(shù)，將其作為抗原，并判斷最佳的適度計(jì)算條件；

4) 判斷適度計(jì)算條件在一定時(shí)間內(nèi)是否存在，并應(yīng)用2種搜索方法擴(kuò)大范圍搜索備用適度計(jì)算條件，通過計(jì)算抗體確定路徑最優(yōu)解的存在；

5) 通過遍歷所有的數(shù)據(jù)節(jié)點(diǎn)，將數(shù)據(jù)節(jié)點(diǎn)的重組操作，并將新產(chǎn)生的節(jié)點(diǎn)基因個(gè)體不斷代入免疫遺傳算法中循環(huán)迭代計(jì)算，并將計(jì)算結(jié)果持續(xù)性地檢索與驗(yàn)證，保障最佳路徑的有效性。

免疫遺傳算法具有變量數(shù)量大的特點(diǎn)，因此，在復(fù)雜交錯(cuò)的道路網(wǎng)中可以設(shè)定大量的數(shù)據(jù)節(jié)點(diǎn)。然而隨著區(qū)域道路網(wǎng)規(guī)模的不斷擴(kuò)大，數(shù)據(jù)節(jié)點(diǎn)的規(guī)模也不斷增大，當(dāng)基因中重復(fù)性地出現(xiàn)相同染色體時(shí)，將不能滿足免疫遺傳算法的基本適應(yīng)函數(shù)，導(dǎo)致免疫遺傳算法在路徑規(guī)劃的過程中出現(xiàn)基因種群庫超載現(xiàn)象，不能夠及時(shí)對(duì)種群基因庫限制[20-21]，進(jìn)而降低了系統(tǒng)對(duì)路徑規(guī)劃的搜索效率。為此，本文在免疫遺傳算法的基礎(chǔ)上建立種群的層次搜索方法與限制區(qū)域搜索方法，通過上述方法提升基因搜索效率。其中，層次搜索法用于實(shí)現(xiàn)圖像分層處理、道路等級(jí)劃分搜索以及關(guān)聯(lián)子圖搜索；限制區(qū)域搜索法用于實(shí)現(xiàn)限制距離與構(gòu)建模型以及提取道路子網(wǎng)數(shù)據(jù)。

應(yīng)用基因搜索方法選擇區(qū)域道路中的任意兩點(diǎn)作為種群基因的初始路徑規(guī)劃范圍，兩點(diǎn)之間進(jìn)行連接可以得到相應(yīng)的橢圓形搜索范圍，橢圓限制區(qū)域搜索范圍如圖2所示。

圖 2 橢圓限制區(qū)域搜索范圍Fig.2 Ellipse area to limited search range

圖2中，a為出發(fā)點(diǎn)，b為到達(dá)點(diǎn)，(A,B)為橢圓圓心坐標(biāo)，(xa,ya)為a點(diǎn)坐標(biāo)，(xb,yb)為b點(diǎn)坐標(biāo)。由于每一個(gè)區(qū)域的道路網(wǎng)都具有不同的特點(diǎn)，導(dǎo)致橢圓形的搜索范圍不同，應(yīng)用幾何學(xué)方法計(jì)算橢圓范圍內(nèi)的道路網(wǎng)匹配基因系數(shù)為橢圓長軸與橢圓焦距之比，進(jìn)而能夠確定橢圓的基本模型，可表示為

(1)

式中：θ為長軸與坐標(biāo)系X軸的角度。

隨著道路網(wǎng)的拓展，在橢圓形區(qū)域搜索免疫遺傳基因的算法與搜索的功能特性也隨之提升[22-23]。在應(yīng)用免疫遺傳算法規(guī)劃最佳路徑的同時(shí)，也需要考慮到用戶的實(shí)用信息，例如路徑長度、路況、道路等級(jí)、心理期待預(yù)期等，因此需要在免疫遺傳算法的基礎(chǔ)上建立函數(shù)策略，滿足算法中染色體與基因構(gòu)造過程中的環(huán)境穩(wěn)定性。

假設(shè)路徑權(quán)值為ω，通行率為g，路徑基礎(chǔ)長度為l，路徑染色體參與數(shù)為r，路況染色體比重參數(shù)為r1，道路等級(jí)為C，道路等級(jí)染色體比重為r2，可得路徑權(quán)值ω表達(dá)式為

(2)

權(quán)值ω越小，則證明通過此路徑的時(shí)間越少，時(shí)間消耗損耗越小。

綜合上述分析，設(shè)計(jì)基于免疫遺傳的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)流程如圖3所示。

圖 3 區(qū)域道路網(wǎng)智能路徑誘導(dǎo)流程Fig.3 Intelligent route guidance process of regional road network

3 實(shí)驗(yàn)研究

本文在免疫遺傳算法的基礎(chǔ)上，應(yīng)用2種數(shù)據(jù)搜索方法在限制區(qū)域內(nèi)尋找路徑的最優(yōu)解，使遺傳算法與2種搜索方法形成數(shù)據(jù)平衡狀態(tài)，更有利于免疫遺傳算法信息的深度積累與最優(yōu)路徑空間的解鎖。

將免疫遺傳算法應(yīng)用到實(shí)際系統(tǒng)中，通過節(jié)點(diǎn)與節(jié)點(diǎn)之間的路徑規(guī)劃驗(yàn)證本文系統(tǒng)的有效性。設(shè)定在實(shí)驗(yàn)道路區(qū)域內(nèi)具有11個(gè)路徑出發(fā)點(diǎn)與終點(diǎn)(a—b點(diǎn)，將a設(shè)為起點(diǎn)，將b設(shè)為終點(diǎn))。在考慮用戶心理變化的情況下要保障權(quán)重值不能大于高峰值，根據(jù)生活常識(shí)需要在早晚高峰時(shí)期進(jìn)行目標(biāo)的最快路徑搜索，此時(shí)的路徑規(guī)劃過程需要具有更短的路徑規(guī)劃時(shí)間，為用戶行駛方向的改變爭取時(shí)間。

為突出說明本文系統(tǒng)在最優(yōu)路徑誘導(dǎo)方面的作用，實(shí)驗(yàn)環(huán)境不便的前提下，進(jìn)行對(duì)比實(shí)驗(yàn)，設(shè)置對(duì)照組，對(duì)比系統(tǒng)分別為文獻(xiàn)[3]和文獻(xiàn)[4]，實(shí)驗(yàn)結(jié)果的評(píng)價(jià)以路徑作為評(píng)價(jià)指標(biāo)，路徑越短，說明系統(tǒng)的路徑規(guī)劃性能越好。實(shí)驗(yàn)結(jié)果如圖4所示。

(a) 本文系統(tǒng)

(b) 文獻(xiàn)[3]系統(tǒng)

(c) 文獻(xiàn)[4]系統(tǒng)圖 4 最佳路徑對(duì)比實(shí)驗(yàn)結(jié)果Fig.4 Experiment results of the best path comparison

從圖4可以看出，本研究通過免疫遺傳算法對(duì)區(qū)域道路節(jié)點(diǎn)的不斷操作與數(shù)據(jù)適應(yīng)搜索，最終規(guī)劃的路徑為a—c—b，文獻(xiàn)[3]系統(tǒng)規(guī)劃的路徑為a—g—d—e—b，文獻(xiàn)[4]系統(tǒng)規(guī)劃的路徑為a—h—i—k—b，其中本文系統(tǒng)規(guī)劃的路徑除起點(diǎn)和終點(diǎn)外，只經(jīng)過1個(gè)節(jié)點(diǎn)c，文獻(xiàn)的系統(tǒng)除起點(diǎn)和終點(diǎn)外，均經(jīng)過3個(gè)節(jié)點(diǎn)，與本文系統(tǒng)相比，路徑的節(jié)點(diǎn)數(shù)量超出本文2個(gè)，路徑的長度超過本文系統(tǒng)規(guī)劃的路徑。因此，本文系統(tǒng)規(guī)劃的路徑更合理，有效提高了路徑的規(guī)劃能力，實(shí)現(xiàn)車輛路徑最優(yōu)誘導(dǎo)。測試不同系統(tǒng)進(jìn)行網(wǎng)智能路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性，得到對(duì)比結(jié)果見表1。

表 1 路徑誘導(dǎo)系統(tǒng)穩(wěn)定性測試Tab.1 Stability test of path induction system

從表1可以看出，當(dāng)?shù)螖?shù)達(dá)到400次時(shí)，本文系統(tǒng)的穩(wěn)定性達(dá)到0.997，近乎為1，文獻(xiàn)[3]系統(tǒng)的穩(wěn)定性為0.913，文獻(xiàn)[4]系統(tǒng)的穩(wěn)定性為0.901，分別低于本文0.084和0.096，其他迭代次數(shù)時(shí)的穩(wěn)定性也均低于本文系統(tǒng)。由此可見，本文系統(tǒng)的路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性效果得到了提升。

4 結(jié) 語

本文根據(jù)區(qū)域交通的特點(diǎn)對(duì)基于免疫遺傳算法的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)展開研究與設(shè)計(jì)，采用經(jīng)典的免疫遺傳算法獲取區(qū)域道路網(wǎng)中可能存在的路徑最優(yōu)解，再應(yīng)用層次搜索法和限制區(qū)域搜索法對(duì)免疫遺傳算法的最優(yōu)解進(jìn)行區(qū)域性的限制與穩(wěn)固，從而增強(qiáng)了路徑誘導(dǎo)的智能程度與高效性。

然而由于研究時(shí)間的限制，本文系統(tǒng)還存在一定的不足，如路徑規(guī)劃過程耗時(shí)偏多。因此，在接下來的研究中，將考慮從提高誘導(dǎo)路徑規(guī)劃時(shí)效性的角度進(jìn)一步提高本文系統(tǒng)的應(yīng)用優(yōu)勢。