改進蟻群算法支持下的交通流量分配

陳能成，么 爽，杜文英，王 超

(武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北 武漢 430079)

交通流量分配是路網(wǎng)交通規(guī)劃的重要組成部分。災(zāi)后路網(wǎng)遭到部分損毀，原有的交通分配方案已不再適用，為開展災(zāi)后疏散與救援工作，保證災(zāi)區(qū)的正常交通運輸，災(zāi)后管理已成為國內(nèi)外的研究熱點[1-4]。

災(zāi)后救援與交通流量再分配需考慮路徑規(guī)劃問題。文獻[5]提出的蟻群算法是一種解決組合優(yōu)化問題的啟發(fā)式搜索算法，螞蟻通過信息素進行交流，在不同的節(jié)點中選擇性轉(zhuǎn)移，從而得到最優(yōu)路徑。蟻群算法在路徑規(guī)劃、車輛調(diào)度[6]、集成電路設(shè)計[7]等問題中都取得了不錯的結(jié)果，在交通分配方面同樣得到廣泛應(yīng)用[8]。文獻[9]量化路段薄弱性和重要性，計算路段關(guān)鍵度，并實現(xiàn)路網(wǎng)交通流量的重分配。文獻[10]通過分析車流經(jīng)過交叉口的延誤時間改進蟻群算法，并應(yīng)用于交通分配中。文獻[11]將蟻群系統(tǒng)與可變鄰域搜索相結(jié)合，應(yīng)用改進的蟻群算法解決車輛路徑規(guī)劃問題。

路網(wǎng)的通行能力是制約交通流量的關(guān)鍵，當(dāng)前研究多以定性為主，缺乏定量化與體系化的研究，交通分配評估通行能力時缺乏綜合性指標(biāo)分析，用于災(zāi)后交通路網(wǎng)部分損壞情況的流量分配研究較少。因此，本文提出一種基于改進蟻群算法的交通流量分配方法，以長株潭地區(qū)為例，在基本算法的基礎(chǔ)上引入道路質(zhì)量評價體系，以評價結(jié)果作為啟發(fā)式因子；同時利用路段交通流量改進信息素的更新機制，加入擾動節(jié)點，以避免陷入局部最優(yōu)解。最后以長株潭地區(qū)交通流量分配進行試驗，結(jié)果表明改進算法能較好地模擬交通流量分配情況。

1 道路質(zhì)量評價體系

影響路網(wǎng)通行能力的因素主要包括路網(wǎng)結(jié)構(gòu)和路網(wǎng)容量兩方面。路網(wǎng)結(jié)構(gòu)又分為功能結(jié)構(gòu)、等級結(jié)構(gòu)和布局結(jié)構(gòu)[12]，路網(wǎng)容量由各等級道路交通量決定。因災(zāi)后路網(wǎng)受損的特殊情況，車輛行駛路徑應(yīng)保證等級結(jié)構(gòu)合理性、功能結(jié)構(gòu)穩(wěn)定性和高可達性，因此本文提出道路質(zhì)量評價體系，利用變異系數(shù)法為路段基礎(chǔ)數(shù)據(jù)如路段等級、設(shè)計時速等指標(biāo)分配權(quán)重，綜合評價路段通行能力，評價結(jié)果即為路段質(zhì)量。

(1)

式中，Ei表示指標(biāo)Zi的變異系數(shù)；σi為規(guī)范化處理后指標(biāo)Zi的標(biāo)準(zhǔn)差；μi為規(guī)范化處理后指標(biāo)Zi的平均值。

對于權(quán)重ωi[13]，有

(2)

變異系數(shù)法是一種完全客觀的賦權(quán)方法，用于評價指標(biāo)模糊且缺少專家經(jīng)驗的情況。不同路段的質(zhì)量評價結(jié)果差異明顯，路段質(zhì)量將作為啟發(fā)式因子用于改進算法，實現(xiàn)路網(wǎng)的交通流量分配。

2 改進的蟻群算法

針對基本蟻群算法運行慢、早熟收斂、易陷入局部最優(yōu)解的問題[14]，同時考慮災(zāi)后城市間交通流量的實際情況，為提高算法的有效性，本文對基本算法進行了相應(yīng)改進。

2.1 考慮道路質(zhì)量的啟發(fā)式因子改進

基本蟻群算法中螞蟻根據(jù)信息素和啟發(fā)因子選擇下一個城市，轉(zhuǎn)移概率公式[5]為

(3)

式中，k表示當(dāng)前螞蟻編號；τij(t)表示t時刻路段ij的信息素；α表示信息素影響程度；ηij(t)表示t時刻路段ij的啟發(fā)式因子；β表示啟發(fā)式因子影響程度；allowedk表示第k只螞蟻可選擇節(jié)點的集合。

啟發(fā)式因子ηij反映螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點j的啟發(fā)程度，一般情況下為該路段長度的倒數(shù)。本文引入道路質(zhì)量評價體系，其結(jié)果F有ηij=F，反映路段通行能力，由路段行政等級、設(shè)計時速、車道數(shù)量、年平均日交通量4個指標(biāo)衡量。路徑為起終點間被選擇路段的有序集合，路徑質(zhì)量即為路段質(zhì)量之和，路徑質(zhì)量越好，通行能力越強，該條路徑越易被選擇。

2.2 避免陷入局部最優(yōu)解

蟻群算法中信息素τij反映走過的路段長度，n時刻后更新[5]如下

(4)

式中，ρ表示信息素蒸發(fā)參數(shù)；Δτij表示路段ij的信息素增量；Lk表示螞蟻k走過的路段長度；N為常數(shù)。

針對基本蟻群算法易陷入局部最優(yōu)解的問題，設(shè)置監(jiān)控閾值num，當(dāng)路段ij被選擇次數(shù)超過num時，引入隨機節(jié)點c，同時改進原路段ij信息素更新機制。在保證信息素的影響下將搜索范圍擴至全局，這樣的擾動增強了算法的隨機搜索，在一定程度上避免了局部發(fā)生停滯的問題。

3 改進的蟻群算法用于交通流量分配

基于改進蟻群算法的交通流量分配方法流程如圖1所示。

(1)數(shù)據(jù)預(yù)處理：以市縣區(qū)為單位劃分節(jié)點，確定節(jié)點數(shù)目N，根據(jù)道路質(zhì)量評價體系求得路段質(zhì)量F。

(2)設(shè)置參數(shù)：由交通需求總量確定螞蟻數(shù)目M、循環(huán)次數(shù)C，使交通總量等于M×C，確定轉(zhuǎn)移公式中的α、β、ρ；信息素τij初始為路段ij長度的倒數(shù)；起點區(qū)域為FIRST，終點區(qū)域FINAL。

(3)選擇路徑：令n=1，M只螞蟻從FIRST出發(fā)，根據(jù)式(4)選擇下一節(jié)點。引入?yún)?shù)q0，q0決定了螞蟻轉(zhuǎn)移時選擇已有經(jīng)驗還是選擇探索新路徑。選擇下一個節(jié)點時，產(chǎn)生隨機數(shù)q，q≤q0時選擇allowedk中轉(zhuǎn)移概率最大的節(jié)點；q>q0時采用輪盤賭法，計算不同路段的概率累積量，轉(zhuǎn)移的方向即為q所在概率區(qū)間的節(jié)點

(5)

判斷路段ij被選擇次數(shù)是否達到監(jiān)控閾值num，未超過則按式(4)更新該路段的信息素τij；若超過num則開發(fā)新路段，引入隨機節(jié)點c，此時轉(zhuǎn)移概率為

(6)

新路段ic信息素按式(4)更新，原路段ij信息素更新為

(7)

(4)分配流量：迭代處理時保證每只螞蟻都能找到FINAL，使交通量完全分配到路網(wǎng)中，記錄所有可通行路徑和路徑被選擇的重復(fù)次數(shù)。

(5)判斷n是否與C相等，不等則n=n+1。更新每次循環(huán)中最優(yōu)路徑的信息素，信息素的全局更新公式為

(8)

式中，Lbest表示本次循環(huán)全局最優(yōu)路徑的長度。全局更新方法擴大了最優(yōu)解與普通解間的信息素差異，加快了算法收斂。隨后將M只螞蟻重置于FIRST，重復(fù)步驟(3)—(5)，直至滿足終止條件。

(6)完成交通總量的全部分配，輸出所有可通行路徑、路徑重復(fù)次數(shù)和路段的交通流量，得到路網(wǎng)交通流量分配圖。

4 試驗結(jié)果與分析

本文以長株潭地區(qū)23個市縣區(qū)為例，路網(wǎng)分布如圖2所示。將151個收費站按地理位置所屬市縣區(qū)進行劃分，建立收費站與路段的關(guān)聯(lián)關(guān)系。

4.1 試驗結(jié)果

參數(shù)初始化：N=151，M=151，C=20，α=1，β=1，ρ=0.1，本文1只螞蟻記為1個交通量。輸入路段長度和路段質(zhì)量，起點區(qū)域為攸縣，終點區(qū)域為岳麓區(qū)，如圖3所示。

運行算法，得到起點終點區(qū)域間所有可通行路徑、全局最優(yōu)路徑和各路段的流量，全局最優(yōu)路徑如圖4箭頭所示。

由于貨車、客車等各種機動車所占空間不同，運輸能力相差懸殊，路網(wǎng)能容納的交通量隨機動車種類不同而變化，因此需要將不同車型交通量統(tǒng)一為標(biāo)準(zhǔn)車型交通量。《城市道路工程設(shè)計規(guī)范》(CJJ 37—2012)明確了不同車型在以小客車為標(biāo)準(zhǔn)車型時的換算系數(shù)[15]。將各種車型交通量換算成小客車當(dāng)量從而確定交通需求總量，算法結(jié)束后各路段分配的交通量可通過換算系數(shù)得到不同車型流量。各路段交通流量分配如圖5所示，箭頭方向表示車輛行駛方向，路段上的數(shù)字即為該路段分配得到的交通量。

4.2 結(jié)果分析

結(jié)果包含兩區(qū)域間所有可通行路徑和每條路徑的重復(fù)次數(shù)，重復(fù)次數(shù)反映了不同路徑被選擇的概率。重復(fù)次數(shù)最大的路徑通行能力最好，可以成為災(zāi)后救援的首選路徑。

起點區(qū)域為攸縣，終點區(qū)域為岳麓區(qū)時，不同蟻群算法選擇出的全局最優(yōu)路徑及各自重復(fù)次數(shù)、路徑流量見表1。

表1 不同算法全局最優(yōu)路徑流量對比

根據(jù)路段質(zhì)量得知，基本算法的全局最優(yōu)路徑質(zhì)量為22.738，改進算法的全局最優(yōu)路徑質(zhì)量為31.879，說明后者的通行能力更好，能承載更大的交通流量。表中“重復(fù)次數(shù)”和“路徑流量”的數(shù)據(jù)也驗證了改進算法的路徑優(yōu)于改進前。精英蟻群算法也是對基本算法的改進，算法效率有較大提高。但從表中可知，精英算法選出的全局最優(yōu)路徑和改進算法一致，但路徑流量太大，早熟收斂，不符合流量分配要求。因此本文改進算法在路徑選擇上更合理。

改進算法提高了結(jié)果的有效性。所有可通行路徑中最優(yōu)與次優(yōu)路徑見表2。兩條路徑的前9個節(jié)點相同，第10個節(jié)點發(fā)生分歧。路段30—38與路段30—71質(zhì)量相近，但路段30—38長度遠小于30—71。更多的螞蟻綜合考慮路段質(zhì)量和路段長度兩方面因素，因此第10個節(jié)點選擇了38為后繼節(jié)點。通過計算得到最優(yōu)路徑的質(zhì)量大于次優(yōu)路徑，表2路徑流量對比也證實了最優(yōu)路徑的可靠性，因此算法選擇的最優(yōu)路徑可以成為災(zāi)后救援的首選。分析表明，改進算法通過質(zhì)量差異有效區(qū)分了不同的可通行路徑，路徑質(zhì)量不同承載的流量也不同。

表2 改進蟻群算法結(jié)果路徑對比

改進算法能較好地應(yīng)對災(zāi)后路網(wǎng)損毀的情況。假設(shè)圖6中圓圈部分災(zāi)后損毀，可通行路徑數(shù)目減少，受災(zāi)前兩區(qū)域間共111條可通行路徑，受災(zāi)后有88條可通行路徑，災(zāi)后的全局最優(yōu)路徑變?yōu)闉?zāi)前選擇出的次優(yōu)路徑，如圖6箭頭所示路徑。包含節(jié)點16的路徑受災(zāi)后不能通行，這些路徑的流量按概率轉(zhuǎn)移到其他路徑上，災(zāi)后流量分配如圖7所示。

路段16—50和路段16—78災(zāi)后不能通行，兩條路段位于岳麓區(qū)和雨湖區(qū)，部分相關(guān)路段災(zāi)前災(zāi)后交通流量變化見表3。分析得到，改進算法考慮路段通行能力，將不能通行路段的流量分配到其他路段上，通行能力較強的路段承擔(dān)流量較多，體現(xiàn)了算法處理災(zāi)后流量分配問題的適用性和合理性。

表3 岳麓區(qū)和雨湖區(qū)的部分路段災(zāi)前災(zāi)后流量變化

5 結(jié) 語

本文通過對路網(wǎng)通行能力的分析，提出了一種基于改進蟻群算法的交通流量分配方法，利用路段行政等級、車道數(shù)量、設(shè)計時速、路段年平均日交通量4個指標(biāo)建立了道路質(zhì)量評價體系，改進了啟發(fā)式因子和信息素更新機制，提高了算法的有效性，算法結(jié)果能為救援工作和災(zāi)后路網(wǎng)交通運輸分配決策提供建議和支持。但本文未考慮隨時間推移流量增加對路網(wǎng)的影響，同時由于增加了“道路質(zhì)量”這一因素，算法效率有待提高，后續(xù)會進一步研究時間因素對交通分配的影響及算法效率提高的問題。