改進蟻群算法在交通分配模型中的應(yīng)用

常玉林，汪小渟，張 鵬

(1.江蘇大學(xué) 汽車與交通工程學(xué)院，江蘇 鎮(zhèn)江 212013； 2.東南大學(xué) 城市智能交通江蘇省重點實驗室，江蘇 南京 211189)

改進蟻群算法在交通分配模型中的應(yīng)用

常玉林1,2，汪小渟1，張 鵬1

(1.江蘇大學(xué) 汽車與交通工程學(xué)院，江蘇 鎮(zhèn)江 212013； 2.東南大學(xué) 城市智能交通江蘇省重點實驗室，江蘇 南京 211189)

為了更加準確快速地搜索到最優(yōu)路徑，通過分析車流經(jīng)過信控交叉口的到達和駛離狀況，提出一種考慮交叉口信控延誤的改進蟻群算法模型.首先，用交叉口的信控延誤和路段行走時間對基本蟻群算法的信息素更新方程進行改進，建立全新的信息素更新模型;其次，通過應(yīng)用改進后蟻群算法對路網(wǎng)各路段的車流量進行分批分配，設(shè)計考慮交叉口延誤的路段增量分配流程;最后，基于java程序語言，對路網(wǎng)的流量分配進行仿真，并且和基本蟻群算法對路網(wǎng)運行質(zhì)量進行對比分析.結(jié)果表明，改進后的蟻群算法能夠降低路網(wǎng)中路段和交叉口使用率，具有良好的尋優(yōu)性，并能有效均衡路網(wǎng)流量和緩解交叉口的通行壓力.

交通分配；交叉口延誤；蟻群算法；最優(yōu)路徑

0 引言

交通分配作為四階段法最后一步以及最重要一步，通過精確計算把各個小區(qū)發(fā)生與吸引量合理地分配到實際交通路網(wǎng).蟻群算法的設(shè)計理念來源于自然界蟻群里螞蟻個體的尋食行為，是意大利學(xué)者Dorigo首先提出并且不斷改進而得到的新型優(yōu)化算法[1].與傳統(tǒng)的數(shù)學(xué)規(guī)劃原理相比，該優(yōu)化算法具有很好的穩(wěn)定性，擁有分布計算、反饋信息以及啟發(fā)式搜索的特性，并且能夠動態(tài)響應(yīng)和反饋路徑選擇過程中的外界影響.傳統(tǒng)蟻群算法的原理是通過遺留在路徑上的信息素濃度選擇最優(yōu)路徑，表現(xiàn)形式是路徑長度越短，遺留的濃度越大.以往的改進蟻群算法統(tǒng)一表現(xiàn)在信息素更新形式，重要的突破是以行走時間代替距離要素作為信息素更新要素的改進模型[2-4].文獻[5]提出改進的蟻群系統(tǒng)算法求解可裝卸貨物的車輛路徑問題，該算法通過使用多路徑搜索原則，搜索不同路徑上的客戶，增大了搜索范圍.文獻[6]從路徑轉(zhuǎn)移規(guī)則和局部搜索的改進方程出發(fā)，提出一種能加快最優(yōu)解收斂速度的改進蟻群算法，對帶容量約束的弧路徑問題進行求解.文獻[7]通過使用AS模型對30個節(jié)點的TSP問題進行研究，總結(jié)了蟻群算法最優(yōu)參數(shù)的設(shè)置方法.宋方[8]通過在狀態(tài)轉(zhuǎn)移規(guī)則中加入擾動因子，改進全局更新規(guī)則，并將信息素更新算子引入基本蟻群算法，提出一種改進蟻群算法求解城市道路權(quán)值仿真模型.

連續(xù)車流途經(jīng)交叉口時的信控延誤勢必會影響信息素的更新，最終影響交通分配的結(jié)果.因此，筆者將車輛的信控延誤加入信息素更新要素中，通過分析車流經(jīng)過信號配時交叉口的到達和駛離狀況，綜合考慮交叉口延誤時間和路段行程時間,提出了改進的、更加符合實際情況的、考慮交叉口延誤的蟻群算法模型.但是由于交叉口延誤的影響因素非常多，所以筆者在考慮交叉口延誤時也做了一定的假設(shè)與妥協(xié).

1 蟻群算法

1.1 蟻群算法的基本原理

蟻群算法根據(jù)的原理是：螞蟻在尋找食物的過程當中，會相互協(xié)同工作，這中間起著關(guān)鍵作用的是螞蟻自身分泌的一種激素——信息素[8-9].螞蟻在尋找路徑時，總是傾向于選擇信息素濃度大的路徑作為下一個行進方向，即信息素遺留越多、濃度越大的路徑越容易被選中，被選中的路徑又會增加其濃度，這就是所謂的正反饋機制.這種機制的一個好處就是螞蟻對整個路徑上的全部信息素的反饋要求降低，僅僅通過局部信息素的信息反饋就可以找出最短路徑.整個蟻群的行為也會隨外界環(huán)境的改變而改變，當有阻礙物出現(xiàn)在螞蟻的行動路徑上時，螞蟻會快速地做出改變，并且重新找到另一條在當前環(huán)境下的最優(yōu)路徑.

1.2 基本模型

以經(jīng)典TSP(旅行商問題)作為例子，來闡述蟻群算法的相關(guān)模型.旅行商問題的實質(zhì)是：已知所有目標地點的總數(shù)為n，并且已知任意兩個目標城市之間的距離[10-11].旅行商以任選一點作為起點出發(fā)，要求確定一條最短路徑，并且這條最短路徑只經(jīng)過每個旅行地一次.

在最初t=0時刻，各條路的信息素濃度都為常數(shù)，設(shè)為τij(t0)=C，式中τij(t0)表示t0時刻路段(i，j)上的信息素濃度，C為常數(shù).

在進行路徑選擇時，m只螞蟻根據(jù)每條路徑上留有的信息素濃度和自己的判斷決定轉(zhuǎn)移方向，在t時刻螞蟻的轉(zhuǎn)移概率

(1)

式中：ηij為能見度因數(shù)，以兩點之間的距離作為變量，距離越大ηij越??；α為路徑上的信息素總量對螞蟻行為的影響程度；β為路徑長度對螞蟻行為的影響程度；allowedk={C-tabuk}，表示除掉禁忌列表剩下的城市，即可以被選擇的城市集合.人工螞蟻具有真實螞蟻不具備的特點，在進行選擇時會增加一個禁忌列表.所有在本次循環(huán)中被選擇過的城市都會被記錄到禁忌列表里，避免被反復(fù)選擇，禁忌列表里的城市會在循環(huán)結(jié)束后被釋放，在下一次循環(huán)開始時，螞蟻又能夠從所有城市中進行選擇.

經(jīng)過n個時刻，當m只螞蟻遍歷完所有城市后，各條路徑上的信息素根據(jù)下式進行調(diào)整：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1).

(2)

(3)

式中：Q為每只螞蟻在這次循環(huán)中釋放的信息素量，是常數(shù)；Lk表示螞蟻k在此次循環(huán)中經(jīng)過的所有路段加起來組成的路徑長度.

2 改進蟻群算法

筆者在傳統(tǒng)蟻群算法模型的基礎(chǔ)上，再加上交叉口延誤，建立考慮交叉口延誤的蟻群算法模型.引入交叉口延誤的蟻群算法模型信息素更新方程為：

(5)

式中：Q為信息素常數(shù)；T為路段總花費時間，是路段行走時間和車輛在交叉口的信控延誤之和，即T=tij(qij)+dij(qij).

信息素更新改進模型如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1).

(6)

(7)

其中信息素更新方程為：

(8)

(9)

dij=dij1+dij2；

(10)

(11)

(12)

式中：dij(qij)為城市i和j之間最短路徑上交叉口處在流量qij時的延誤時間；k=0.5；I=1.

3 基于改進的蟻群算法增量分配模型

(1)初始化.螞蟻個數(shù)m;最大循環(huán)次數(shù)NC;循環(huán)次數(shù)n=1;τij=C(C為邊(i，j)上的信息素量初始值)，Q;Δτij=0、α、β等.取出起點g和終點h以及相應(yīng)的需求分配交通量.

(2)將總共m(m=n×m0)只人工螞蟻放置在起點g上，采用分批分配方法以m0(m0=PA)只螞蟻為一批，分配批次n=1.

(3)分批分配.讓第一批人工螞蟻隨機選擇路徑，并保證每只螞蟻完成一次循環(huán)選擇，計算各路段螞蟻數(shù)并更新總行駛時間tij和路段上的信息素軌跡τij.

(5)計算目標函數(shù)值，找出各OD點對之間的最優(yōu)解，計算各路段qij(t)和tij(t).

(6)n=n+1，若m只人工螞蟻全部循環(huán)一次結(jié)束，轉(zhuǎn)至(7)，否則轉(zhuǎn)至(4).

(7)滿足條件，即n=NC，結(jié)果無退化行為，即在本次循環(huán)中得到的最優(yōu)解等于N個循環(huán)之前的解，則循環(huán)結(jié)束并輸出結(jié)果，否則轉(zhuǎn)至(2).

4 案例分析

4.1 初始計算

圖1 選用道路網(wǎng)絡(luò)結(jié)構(gòu)圖

基于下述路網(wǎng)的OD分配量，對其進行數(shù)據(jù)篩選獲得符合實際路網(wǎng)的交通OD表，并借助互聯(lián)網(wǎng)地圖及AutoCAD同比例縮放功能，以交叉口7為坐標原點，求得各個交叉口的相對坐標點.根據(jù)各交叉口間距、車輛行駛速度、初始行駛時間、每個交叉口的信號周期、信號綠信比、交叉口通行能力，計算得到各轉(zhuǎn)向車道上車輛的延誤時間和交叉口的延誤時間.

4.2 程序仿真

采用java語言，在基本蟻群算法程序基礎(chǔ)上，編入交叉口延誤數(shù)據(jù)，并用MyEclips軟件實現(xiàn)改進蟻群算法的功能.

對基本蟻群算法選擇概率函數(shù)的各參數(shù)進行初始值設(shè)置：α=2，β=4，ρ=0.5，最大迭代次數(shù)200次，信息素Q=100，螞蟻數(shù)30.設(shè)置信息素更新方程的路段行駛阻抗函數(shù)參數(shù)：α=1，β=4.在程序內(nèi)輸入交叉口坐標數(shù)據(jù)表、OD矩陣表、初始行駛時間表、延誤對比表，運行程序得到各路段分配結(jié)果，如圖2所示.

圖2 蟻群算法改進前后的流量對比圖

試驗結(jié)果表明，采用改進蟻群算法分配路段交通流量，各路段的平均流量為411.4 pcu/h，方差為2 190.7；采用基本蟻群算法對各路段流量進行分配，各路段平均流量為485.2 pcu/h，方差達到3 096.4.在改進蟻群算法下，車次總延誤時間為642 446.17 s，基本蟻群算法車次總延誤時間為772 387.09 s.比較可得，改進算法比基本算法車均延誤減少55.649 s.

基本蟻群算法并沒有考慮交叉口的延誤，實際情況中交叉口延誤影響較大，所以筆者用基本蟻群算法，再運用公式計算對應(yīng)流量下的延誤時間，以兩者時間之和作為基本蟻群算法的車輛行駛時間.通過對上萬輛車的實測數(shù)據(jù)篩選結(jié)果，得出車輛實際行駛的時間,如表1所示.

沒考慮交叉口延誤的影響時，路段行駛時間是主要因素，而考慮交叉口延誤之后，交叉口延誤就成為了影響車輛行駛時間的主要因素.總車次上，改進蟻群算法同樣小于基本蟻群算法.而總車次反映的是車均經(jīng)過交叉口數(shù)的大小，這也反映了改進蟻群算法在路徑尋優(yōu)時更加具有方向性.本次的實例應(yīng)用，主要的是緩解常武路路段上的擁堵情況，如表2所示.

表1 車均行駛時間對比表

表2 常武路交叉口使用率對比表

通過對改進蟻群模型、基本蟻群模型和實測數(shù)據(jù)的分析可知，雖然基本蟻群算法也能夠緩解交叉口通行壓力，使交叉口使用率從109.44%下降到97.90%，但是改進蟻群模型在緩解交叉口使用率，從而緩解交叉口擁堵方面能夠比基本蟻群算法效果更好，在基本蟻群算法的基礎(chǔ)上，再下降8.11個百分點至89.79%.

5 結(jié)論

在基本蟻群算法的基礎(chǔ)上，通過將交叉口延誤時間和行駛時間之和引入信息素更新方程中，即用車輛在交叉口的延誤時間和在路段的行駛時間之和替代路段長度對信息素進行更新.試驗表明，改進后的蟻群算法相比基本蟻群算法在路徑選擇時更具方向性，并且能夠更好地做到均衡分配，能夠?qū)④嚵鞅M可能地分配到整個路網(wǎng)上，使得整體流量限制在了一個比較小的區(qū)間內(nèi)，減輕OD點量大的路段上的負擔.

[1] MULLEN R J, MONEKOSSO D, BARMAN S, et al. A review of ant algorithms[J]. Expert system with applications,2009,36(6):9608-9617.

[2] ATTIRATANASUNTHRON N, FAKCHAROENPHOL J. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J]. Information processing letters,2008,105(3):88-92.

[3] 吳斌,史忠植. 一種基于蟻群算法的TSP問題分段求解算法[J].計算機學(xué)報,2001,24(12):1328-1333.

[4] 林泉,許倫輝,唐德華. 改進蟻群算法在動態(tài)交通分配中的應(yīng)用研究[J].科學(xué)技術(shù)與工程,2009,9(18):5410-5414.

[5] GAJPAL Y, ABAD P L. An ant colony system(ACS) for vehicle routing problem with simultaneous delivery and pickup[J]. Computers and operations research, 2009,36(12): 3215～3223.

[6] LUIS S, JOAO C R, JOHN R C. An improved ant colony optimization based algorithm for the capacitated arc routing problem[J]. Transportation research part B: methodological, 2010,44(2):246～266.

[7] 詹士昌,徐婕,吳俊. 蟻群算法中有關(guān)算法參數(shù)的最選擇[J]. 科技通報,2003,19(5):381～386.

[8] 宋方,汪鐳. 改進蟻群算法在智能交通中的應(yīng)用[J]. 數(shù)學(xué)的實踐與認識, 2013,43(3):66-72.

[9] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社,2007.

[10]溫惠英,徐建閩. 基于改進型蟻群算法的車輛導(dǎo)航路徑規(guī)劃研究[J]. 公路交通科技,2009,26(1):125-129.

[11]SOLNON C. Combining two pheromone structures for solving the car sequencing problem with ant colony optimization[J]. European journal of operational research, 2008,191(3):1043-1055.

[12]DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE transaction on systems man and cybernetics part B,1996, 26(1):29-41.

[13]HUTCHINSON T P. Delay at a fixed time traffic signal-II:numerical comparisons of some theoretical Expressions[J]. Transportation science,1972,6(3):286-305.

[14]吳兵,李曄.交通管理與控制[M].北京:人民交通出版社, 2013.

[15]MISRA S, OOMMEN B J. An efficient dynamic algorithm for maintaining all-pairs shortest paths in stochastic networks[J]. IEEE transactions on computers,2006,55(6): 686-702.

[16]靳凱文, 李春葆, 秦前清. 基于蟻群算法的最短路徑搜索方法研究[J]. 公路交通科技, 2006,23(3):128-130,134.

[17]唐亮,靖可,何杰. 網(wǎng)絡(luò)化制造模式下基于改進蟻群算法的供應(yīng)鏈調(diào)度優(yōu)化研究[J]. 系統(tǒng)工程理論與實踐, 2014,34(5):1267-1275.

Modified Ant Colony Algorithm and Its Application on Traffic Assignment Model

CHANG Yulin1,2, WANG Xiaoting1, ZHANG Peng1

(1.School of Automotive and Traffic Engineering, Jiangsu University, Zhenjiang 212013, China;2.Jiangsu Key Laboratory of Urban ITS, Southeast University, Nanjing 211189, China)

In order to more quickly and accurately search for the optimal path, an improved ant colony algorithm was established through analyzing the process of car arriving and departure in the signalized intersection. First of all, a new pheromone update model was put forward by improving properly the pheromone update function in traditional ant colony algorithm, which used signal control delay in the intersection and the travel time of vehicles in the road section as pheromone update operators. Then, road section incremental allocation process considering intersection delays, which was through partial distributing traffic flow in the network, was designed based on improved ant colony algorithm.Finally, flow distribution in the road network was simulated based on computer language, and the network running quality was compared with traditional ant colony algorithm. The experimental results showed that the improved ant colony algorithm, which could reduce road section and intersection using rate, was of good optimization ability, and could effectively balance the network traffic and alleviate the pressure of intersections.

traffic assignment; intersection delay; ant algorithm; optimal path

2016-05-01；

2016-09-02

江蘇省高校自然科學(xué)基金資助項目(13KJB580003)；江蘇省城市智能交通重點實驗室開放研究經(jīng)費資助項目(JTKF2014004)；江蘇大學(xué)高級專業(yè)人才科研啟動基金資助項目(12JDG056)

常玉林(1963— )，男，江蘇大學(xué)教授，博士，主要從事交通運輸規(guī)劃與系統(tǒng)優(yōu)化技術(shù)研究，E-mail:ylchang@ujs.edu.cn.

1671-6833(2017)02-0041-04

U491.1+23

A

10.13705/j.issn.1671-6833.2017.02.010