雜草算法在城市交通用戶平衡問題中的應用

曾慶山，劉 巍

(鄭州大學 電氣工程學院，河南 鄭州450001)

雜草算法在城市交通用戶平衡問題中的應用

曾慶山，劉 巍

(鄭州大學 電氣工程學院，河南 鄭州450001)

根據(jù)城市交通中用戶平衡狀態(tài)的演化特征，提出了一種求解用戶平衡問題的新方法.該方法通過逐步添加最短路徑以保證所有阻抗最小路徑均被使用，并通過改進入侵雜草算法(IWO)來分配各路徑上的流量，以實現(xiàn)交通網(wǎng)絡上的用戶平衡.通過求解單個復雜交通網(wǎng)絡上的用戶平衡問題，驗證了該方法的有效性.在求解多個復雜交通網(wǎng)絡上的用戶平衡問題上，與連續(xù)平均法(MSA)進行對比，表明該新算法能更好地解決城市交通網(wǎng)絡用戶平衡問題.

城市交通；演化特征；用戶平衡；雜草入侵算法；連續(xù)平均法

0 引言

交通分配問題是交通管理與交通規(guī)劃中的重要問題.交通用戶平衡狀態(tài)是基于Wardrop第一出行原則(UE)的網(wǎng)絡流狀態(tài)[1].在該原則下，交通起訖點(ORIGIN-DESTINATION，O-D)間的所有出行者都試圖尋找最短路徑出行，并最終達到平衡狀態(tài)，在該狀態(tài)下，任一O-D對間的所有出行者的出行時間均相等且最短.

由于在城市交通網(wǎng)絡中，各O-D對間的出行者只能沿著特定的路徑出行，且各路徑流量之間、路徑流量與路徑阻抗之間需滿足特定的關系，使得難以直接將智能算法應用于求解城市交通用戶平衡問題.筆者根據(jù)用戶平衡狀態(tài)的演化過程中出行者間的非合作博弈行為，提出一基于入侵雜草智能算法實現(xiàn)用戶平衡的方法，并將該算法與連續(xù)平均法進行對比.

1 用戶平衡配流模型

在用戶平衡配模型中，每個出行者都力圖使自己的出行時間最小，而不考慮對其他出行者的影響，其實質(zhì)是博弈論中的納什均衡[2].

Wardrop平衡配流原則描述如下：在起止點間所有可供選擇的路徑中，使用者所利用的各條路徑上的出行費用全都相等，且不大于未被利用路徑上的出行費用.

Beckmann采用下式描述Wardrop平衡狀態(tài)

(1)

通常用路段走行時間表示路段阻抗，采用美國公路局開發(fā)的BPR函數(shù)

(2)

式中：tij(0)為路段(i,j)上流量為零時車輛自由形式所需的時間；eij為路段(i,j)單位時間內(nèi)可通過的最大車輛數(shù)；α,β為模型參數(shù)，一般的α=0.15,β=4；Qij為路段(i,j)上的車流量.

求解用戶平衡配流模型的方法很多，一般用Frank-Wolfe方法或者連續(xù)平均法[3-4].連續(xù)平均法是Frank-Wolfe方法的變種算法，在實際應用中，具有廣泛的應用性.

2 智能算法求解用戶平衡問題

在城市交通網(wǎng)絡中，由于出行者出行路徑受限，出行者下一出行路段必須與當前所在路段直接相連，路徑阻抗隨著路徑流量變化等多種條件限制，使得應用智能算法求解用戶平衡問題的研究成果并不多，且計算量往往過大.

文獻[5]應用螞蟻算法求解用戶平衡問題，通過將O-D對間的螞蟻以一定方式行動，尋找較優(yōu)路徑并實現(xiàn)流量分配，以達到用戶平衡狀態(tài).但在復雜的交通網(wǎng)絡中，因可選路徑往往較多，故需要在每個O-D對間均配置大量的螞蟻，其計算量是極為龐大的.同時在該方法中，螞蟻的出行行為受路段阻抗影響較多，使得螞蟻有可能錯過較優(yōu)路徑，而不能達到真正的用戶平衡狀態(tài).

文獻[6]應用粒子群算法求解隨機用戶平衡問題，其將所有O-D對間的所有路徑流量構成一個解，而后采用粒子群算法求得滿足適應度函數(shù)最小的粒子，其解的維度與O-D對數(shù)及O-D對間的路徑數(shù)成正比.隨著網(wǎng)絡規(guī)模的增大，其解的維度成幾何數(shù)的增大，且每次迭代均需求得所有粒子對應的目標函數(shù)值，計算量極為龐大.

導致上述兩種方法計算量過大的原因主要在于O-D對間路徑的選擇上.為解決該問題，通過模擬用戶平衡狀態(tài)的演化過程，在O-D對間逐步添加出行路徑，并通過智能算法分配各路徑間的流量，最終實現(xiàn)用戶平衡狀態(tài).

3 入侵雜草算法求解用戶平衡問題

3.1 入侵雜草算法

入侵雜草算法是Mehrabian和Lucas于2006年提出一種智能優(yōu)化算法[7].具有結構簡單、參數(shù)少、易于理解和編程的特點.目前，入侵雜草算法已被應用于天線陣列設計問題[8]、神經(jīng)網(wǎng)絡優(yōu)化[9]等多個領域.

在雜草入侵算法中，用雜草表示所求問題的可行解，雜草按適應度值的大小分配其產(chǎn)生的種子數(shù)目，種子按照一定的規(guī)則在父代雜草附近的空間內(nèi)擴散，發(fā)育成雜草.當種群中的雜草數(shù)目達到預先設定的最大值時，雜草便在種群內(nèi)產(chǎn)生競爭，找到適應度最高的雜草，即最優(yōu)解.

步驟(1)初始化.在搜索空間按均勻分布的方式產(chǎn)生N個初始解.

步驟(2)繁殖子代.每個雜草按適應度大小產(chǎn)生子代，子代數(shù)目按下式計算

(3)

式中：f,fmax,fmin分別對應父代雜草適應度、種群最大適應度和最小適應度值；smax,smin分別表示每個雜草所能產(chǎn)生的最大和最小種子數(shù).

步驟(3)空間分布.每個父代雜草產(chǎn)生的種子按平均值為0，標準差為σ的正態(tài)分布，分布到父代雜草周圍，σ按如下公式計算

(4)

式中：iter和itermax分別為當前迭代次數(shù)和最大迭代次數(shù)；σinit,σfinal分別為標準差的初始值和最終值；n為非線性調(diào)和因子，一般取n=3.

步驟(4)競爭淘汰.若雜草數(shù)量達到種群規(guī)模上限P_MAX，則取適應度較高的前P_MAX個個體，返回步驟(2)，進行下一次迭代.

3.2 求解用戶平衡問題中的具體步驟

在用入侵雜草算法求解用戶平衡問題時，目標是將每個O-D對間的路徑阻抗相等且最小，而非尋找某個使得目標函數(shù)最小的解，故需對入侵雜草算法進行修改.

將一個O-D對視為一個雜草群體，O-D對間的每條已用路徑視為一個父代，路徑阻抗的相反數(shù)視為該父代的適應度，即路徑阻抗越高，父代適應度越低.每個父代按式(3)產(chǎn)生子代，且子代分布在父代對應的路徑上，數(shù)目按下式計算

(5)

(6)

式中：ωmin和ωmax分別為ω的最小值和最大值；iter和itermax分別為當前迭代次數(shù)和最大迭代次數(shù).

路徑流量按下式計算

(7)

式(3)保證阻抗較小的路徑，即適應度較高的父代能夠產(chǎn)生較多的子代，式(5)、(7)通過累加雜草的方式，實現(xiàn)路徑上流量的平滑轉(zhuǎn)移，并保證雜草數(shù)量較多的路徑能夠獲得較多的交通流量，隨著迭代次數(shù)增加，總雜草數(shù)目增多，每次迭代轉(zhuǎn)移的流量逐步減少，求解精度逐步提高.

采用競爭淘汰機制刪除已存在的不適合出行的路徑.當O-D對間的最大阻抗路徑滿足以下條件時，刪除該路徑.

(8)

即若O-D對間的某條路徑通過極小流量時，該路徑阻抗仍大于其它路徑阻抗，則認為該路徑無意義，刪除該路徑.

(9)

步驟(4)判斷是否達到用戶平衡狀態(tài).若對任意r，s，存在findPathrs=1，balancers=1,則其滿足式(1)平衡狀態(tài)，結束迭代.否則，轉(zhuǎn)向步驟5.

步驟(5)刪除路徑.若O-D對r-s間的路徑總數(shù)Pathrs_numn>1，則按式(8)刪除無意義路徑.

3.3 算例

通過對圖1所示雙層城市交通網(wǎng)絡進行用戶平衡配流，驗證算法的有效性.

圖1 雙層城市交通網(wǎng)絡Fig.1 The double layered traffic network

圖1中，上層為居民出行網(wǎng)絡，其為一個含有5個節(jié)點，10條邊的網(wǎng)絡，每條邊對應一個O-D對，共有10個O-D對，令每個O-D間的流量均為3，且居民只能沿道路網(wǎng)絡出行.

下層為城市道路網(wǎng)絡，其為一個5×5的網(wǎng)格，共有25個節(jié)點，40條邊，每個節(jié)點對應一個交叉路口，每條邊對應一個路段，令路段的通行能力均為5，車輛平均自由走行時間為1.

采用下式來判斷交通網(wǎng)絡接近平衡狀態(tài)的程度

(10)

(11)

顯然，σrs越小，O-D對r-s間各已選路徑阻抗越為接近;σ越小，交通網(wǎng)絡越接近用戶平衡狀態(tài).

采用入侵雜草算法對圖1所示網(wǎng)絡進行用戶平衡配流，取smax=100，smin=0，ωmax=1，ωmin=0.8，εf=0.02，εT=0.005，N=100.經(jīng)過61次迭代后，滿足平衡條件.

采用Beckmann等學者提出的滿足Wardrop準則的數(shù)學規(guī)劃模型驗證算法有效性，模型為

(12)

(13)

(14)

(15)

將Z(Q)作為目標函數(shù)，繪制每次迭代過程中的函數(shù)值，如圖2所示.通過計算發(fā)現(xiàn)，所有O-D中，阻抗均方差最大為0.002 2，均方差平均值為σ=0.000 6.即已被使用的路徑阻抗均大致相等，即滿足了Wardrop平衡配流原則.

圖2 Z(Q)函數(shù)值Fig.2 The value of Z(Q)

4 入侵雜草算法與連續(xù)平均法對比

考慮到城市道路交通網(wǎng)絡具有無標度性和流量集中性[10-11]，在10×10網(wǎng)格上隨機產(chǎn)生含有10個節(jié)點的小型無標度網(wǎng)絡，分別采用入侵雜草算法和連續(xù)平均法對其進行用戶平衡配流，比較兩者的運行時間和計算精度.兩種算法中，迭代次數(shù)對目標函數(shù)值下降量的邊際貢獻均是不斷減少的，當?shù)螖?shù)達到一定值后，目標函數(shù)值基本保持不變，令兩種算法均迭代100次.

令各路段通行能力e=5，各路段上車輛平均自由走行時間t為1～1.2單位時間內(nèi)的隨機數(shù)，分別令各O-D對間的車流量f為1和3，對5個無標度出行網(wǎng)絡進行用戶平衡配流，將Z(Q)和σ作為目標函數(shù)值，計算結果如表1所示.

由表1可以看出，入侵雜草算法運行時間略高于連續(xù)平均法.當O-D對間車流量f=1和f=3時，經(jīng)過100次迭代后，入侵雜草算法在4個網(wǎng)絡中的Z(Q)值小于連續(xù)平均法，而σ值在5個網(wǎng)絡中均遠小于連續(xù)平均法，即O-D對間的各路徑阻抗更為接近，證明了新算法的有效性.

表1 兩種算法對比Tab.1 The comparison of two algorithm

5 結論

基于城市交通網(wǎng)絡中，用戶平衡狀態(tài)的演化過程，提出一種采用雜草算法求解用戶平衡問題的方法.通過在每次迭代過程中計算并添加最短路徑，保證所有較優(yōu)路徑均能被使用，同時通過模擬雜草繁殖競爭的過程實現(xiàn)交通流量的分配，最終達到Wardrop原則下的用戶平衡狀態(tài).

分別通過求解一個雙層城市交通網(wǎng)絡上的用戶平衡問題以及與連續(xù)平均法在多個交通網(wǎng)絡上進行對比，證明了新算法的有效性.

因雜草算法在每次迭代過程中，需采用一定規(guī)則分配各路徑流量，故計算時間略長于連續(xù)平均法.相對于連續(xù)平均法，智能算法求解出各路徑間的路徑阻抗更加接近，即更為接近用戶平衡狀態(tài).

[1] WARDROP J G. Some theoretical aspects of road tra-ffic research[J]. Proceedings of the Institute of Civil Engineers,Part II,1952，1-2:325- 378.

[2] MACKO M, LARSON K, STESKAL L. Braess’s paradox for flows over time[J]. Theory Of Computing Systems, 2013;53(1):86-106.

[3] 吳建軍，高自友，孫會君,等.城市交通系統(tǒng)復雜性[M].北京:科學出版社，2011.

[4] 吳先宇,袁振洲,李艷紅,等. 用戶平衡算法中目標函數(shù)值與迭代次數(shù)關系研究[J]. 交通與計算機,2007,25(6):8-12.

[5] 杜波,邵春福. 基于螞蟻算法的用戶平衡分配方法研究[J]. 物流技術,2009,28(12):155-157.

[6] 度巍,王先甲,黃崇超. 求解隨機用戶平衡問題的粒子群演化算法[J]. 武漢理工大學學報:交通科學與工程版,2010,34(3):616-619.

[7] MEHRABIAN A R, LUCAS C. A novel numerical optimization algorithm inspired from weed colonization[J]. Ecological Informatics, 2006,1(4):355-366.

[8] ROY G, DAS S, CHAKRABORTY P, et al. Design of non-uniform circular antenna arrays using a modified invasive weed optimization algorithm[J]. IEEE Transactions On Antennas & Propagation, 2011,59(1):110-118.

[9] 彭斌,胡常安,趙榮珍. 基于混合雜草算法的神經(jīng)網(wǎng)絡優(yōu)化策略[J]. 振動測試與診斷,2013,33(4):634-639.

[10]PORTA S, CRUCITTI P, LATORA V. The network analysis of urban streets: a dual approach[J]. Physica A, 2006, 369(2):853-866.

[11]JIANG B. A topological pattern of urban street networks: universality and peculiarity[J]. Physica A, 2007, 384(2):647-655.

Application of Invasive Weed Optimization Algorithm to the User Equilibrium Problem of the Urban Traffic

ZENG Qing-shan, LIU Wei

(School of Electrical Engineering, Zhengzhou University, Zhengzhou 450001, China)

Based on the evolutionary character of user equilibrium of the urban traffic, a new method which can solve the user equilibrium problem is presented. This method ensures all paths which have the minimum resistance are used by adding the shortest path step by step, and realize the user equilibrium of the urban traffic by distributing the flow of paths based on improved invasive weed optimization algorithm(IWO). The effectiveness is verified by solving the user equilibrium problems of one complex urban traffic network. It proves that the new algorithm can get better solution of the user equilibrium problem after comparing it with the method of successive algorithm(MSA) in solving the user equilibrium problems of some complex urban traffic networks.

urban traffic; evolutionary character; user equilibrium; invasive weed optimization algorithm; method of successive algorithm

2014-08-07；

2014-11-10

河南省基礎與前沿技術研究計劃資助項目(132300410420)

曾慶山(1963-)，男，湖北武漢人，鄭州大學教授，博士,主要研究方向為智能控制理論、復雜系統(tǒng)的建模與控制、分數(shù)階微分控制等，E-mail： qszeng@126.com.

1671-6833(2015)01-0010-05

TP399

A

10.3969/j.issn.1671-6833.2015.01.003