張 薇

（蘭州交通大學 交通運輸學院，甘肅 蘭州730070）

0 引 言

城市交通路網(wǎng)可靠性是衡量道路交通系統(tǒng)性能的重要指標。目前交通網(wǎng)絡的可靠性研究主要集中在以下3個方面：連通可靠性、行程時間可靠性和容量可靠性。目前，路網(wǎng)可靠性的研究主要集中在行程時間、容量可靠性兩方面［1－4］。本文針對容量可靠性進行研究。

Chen等提出了容量可靠性概念后，接著又提出了基于靈敏度分析和Monte Carlo技術來求解可靠性的方法。Lo和Tung建立了隨機約束線性規(guī)劃模型、PUE（概率用戶平衡）模型來計算路網(wǎng)的可靠性。劉海旭、蒲云構造了雙層規(guī)劃模型來計算路網(wǎng)的可靠性。這些模型都是以線性規(guī)劃為基礎，并且被應用在實際的大規(guī)模道路交通網(wǎng)絡中時，其計算量大。文獻 ［5］從狀態(tài)空間的角度來考慮路網(wǎng)的容量可靠性問題，為路網(wǎng)可靠性的評價提供了一個新的空間。它選取網(wǎng)絡最可能狀態(tài)來確定路段及路網(wǎng)可靠性的下界和上界以得到可靠性的近似值。不難發(fā)現(xiàn)，當狀態(tài)數(shù)量增加時，可靠性的上下界趨于接近，這說明狀態(tài)數(shù)量的選取限制了可靠性的準確度。文獻 ［5］中可靠性計算結果只是估計值的原因在于其算法只選取了狀態(tài)空間中的一部份最有可能狀態(tài)作為研究基礎。本文建立了隨機流路網(wǎng)容量可靠性模型，并基于此模型提出了一種交通路網(wǎng)容量可靠性計算方法，計算可靠性時考慮路網(wǎng)的整個狀態(tài)空間，采用改進的粒子群算法對整個狀態(tài)空間進行搜索，以獲得狀態(tài)空間的所有下界點來計算路網(wǎng)的容量可靠性。

1 隨機流交通路網(wǎng)可靠性模型

1.1 隨機流交通路網(wǎng)模型定義

定義G＝ （N，E，F(xiàn)，P）是一個隨機流交通路網(wǎng)，其中N是交通路網(wǎng)節(jié)點的集合，E＝ ｛ei｜1≤i≤m｝是路段的集合，F(xiàn)＝ （fij）為m×h的容量矩陣，h為路段具有的狀態(tài)數(shù)，fij表示路段ei的第j種狀態(tài)的容量，其中fi0為路段ei的最大容量，并且fij＞fij＋1，P＝ （Pij）為m×h的概率矩陣，Pij表示路段ei的第j種狀態(tài)的概率，并且。

根據(jù)我國目前大中城市的道路服務水平劃分標準 （見表1），路段上的服務水平按照飽和度分為5個級別，由于不同的服務水平下路段的容量也會不同，并且這5個服務水平級別恰好能夠反映路段的5種容量狀態(tài)。因此可將路網(wǎng)中各路段上采集到的交通流量數(shù)據(jù)對應地劃分到5個狀態(tài)中。方法如下：設vi是第j個路段的第i個流量數(shù)據(jù)，根據(jù)飽和度，可得到對應的服務水平級別，即可知對應容量狀態(tài)。隨機流路網(wǎng)模型的參數(shù)計算如下：各狀態(tài)的容量值fjk取在該狀態(tài)下的路段容量平均值，設該路段上共有n個采集數(shù)據(jù)，劃分到第k狀態(tài)的數(shù)據(jù)個數(shù)為nk，k∈［0，4］，則第j個路段的第k狀態(tài)概率為Pjk＝，并且＝1。

表1 我國大中城市道路服務水平劃分采用值

實際的交通網(wǎng)絡中路段的容量是不確定的，完全暢通時，容量為最大值；完全阻塞時，容量為0，更多的情況下路段既不處于完全暢通狀態(tài)，也不處于完全阻塞狀態(tài)，而是介于兩者之間的某種狀態(tài)，其容量為0到最大值之間的某一個值。因此，路段的容量是隨機的，是隨著流量的改變而變化的。容量的不確定性使得路網(wǎng)的可靠性計算變得困難。本文建立的交通路網(wǎng)模型將各路段的容量以道路服務水平為依據(jù)進行狀態(tài)劃分，使得容量的不確定轉化為5種確定狀態(tài)，以解決路段容量的實測數(shù)據(jù)很難得到的問題，來研究整個路網(wǎng)的可靠性。

另外，連通可靠性經(jīng)常被用于如地震等自然災害發(fā)生時的特殊情況下的路網(wǎng)狀態(tài)評價，而不適用于正常的交通網(wǎng)絡中［6－11］。本文的隨機流路網(wǎng)模型恰好描述了路網(wǎng)的多種狀態(tài)及各種狀態(tài)的概率，使得最終可靠性評價結果能夠表征路網(wǎng)連通的程度，從而可以判斷路網(wǎng)的確切狀態(tài)。這樣連通可靠性的應用范圍能夠得到擴展，應用于正常交通網(wǎng)絡中可靠性的評價。

1.2 路網(wǎng)可靠性定義

路網(wǎng)容量可靠性反映的是路網(wǎng)能夠滿足一定交通需求的概率。各路段的若干狀態(tài)的隨機出現(xiàn)構成了路網(wǎng)的巨大的狀態(tài)空間Ω。令X＝ （x1，x2，…，xi，…xn）為交通路網(wǎng)G＝ （N，E，F(xiàn)，P）的狀態(tài)空間Ω中的任一狀態(tài)，同時令交通需求量為d。若某個路網(wǎng)狀態(tài)X＝ （x1，x2，…，xi，…xn）能夠滿足需求流量d，并且大于此狀態(tài)的路網(wǎng)狀態(tài)都能夠滿足需求流量d，則該狀態(tài)稱為路網(wǎng)的d－下界點。

其中，狀態(tài)X1＞X2的含義為：不存在x1i＜x2i的情況，即狀態(tài)X1中的所有路段容量都大于或等于狀態(tài)X2中的對應的路段容量。

根據(jù)可靠性原理，當需求流量為d時，節(jié)點i和j之間的可靠性為Rd（i，j）＝Pr｛X｜f（X）≥d｝＝Pr｛X｜X≥Xi，Xi為d－下界點｝，因此，可靠性的計算問題轉化為求出路網(wǎng)狀態(tài)空間中足夠d－下界點的問題。

2 基于改進粒子群算法的隨機流交通路網(wǎng)可靠性分析

2.1 一種改進的粒子群算法

粒子群優(yōu)化 （particle swarm optimization，PSO）算法是一種模擬鳥群覓食行為的演化計算算法。粒子群優(yōu)化算法提出之后引起了全世界學者的廣泛關注。由于粒子群優(yōu)化算法概念簡單，收斂速度快，涉及參數(shù)少，易于實現(xiàn)，具有很強的全局優(yōu)化能力，因而迅速得到了認可，在當前的優(yōu)化應用中受到越來越多的關注。目前粒子群優(yōu)化算法已廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制、水利、電力和經(jīng)濟等大規(guī)模組合優(yōu)化問題求解［12－15］。但是在求解問題規(guī)模龐大的交通路網(wǎng)問題時基本粒子群算法常常會陷入局部無解狀態(tài)。本文利用粒子群算法的最優(yōu)解實質是基于局部極值搜尋的這一特點，提出一種改進的能夠搜索出滿足要求的多個解的方法，應用這種改進的粒子群算法實現(xiàn)整個狀態(tài)空間中足夠d－下界點的目標搜索，從而進行有效的交通流路網(wǎng)可靠性分析。

基本PSO算法一直適用于尋找一個最優(yōu)解的問題，其實將多個粒子散布于狀態(tài)空間中，各個粒子通過自己本身的思考和其它粒子提供的信息作為指導，不斷地改變飛行速度，最終是能夠在狀態(tài)空間中找到滿足某條件的多個解的。

式中：i＝1，2…，m，d＝1，2，…，D；ω——慣性因子；c1、c2——學習因子；r1、r2—— ［0，1］之間的隨機數(shù)；α——約束因子；——所有局部無解狀態(tài)的出發(fā)點的重心。粒子既具有認知能力，又具有粒子之間的社會信息共享與相互合作。粒子的速度取決于當前最好位置和無解狀態(tài)的重心位置，通過學習后會向自己當前最好位置靠近，而遠離局部無解狀態(tài)的位置，從而盡快找到局部最優(yōu)解。

隨機流交通路網(wǎng)隨著節(jié)點的增加，問題的規(guī)模解也越來越多，常規(guī)基本粒子群算法往往陷入局部無解狀態(tài)，使問題無法求解。本文提出一種改進粒子群算法，即在基本粒子群算法中加入一種轉移機制。即當某一粒子連續(xù)t次更新后仍處于一局部范圍，則重新為該粒子找到新的出發(fā)點。令xit2為粒子i從位置xit1更新后的位置，則｜xit1－xit2｜為粒子i某一次的移動距離，若｜xit1－xit2｜＜ε（ε為一較小值），表示粒子移動距離較小，如果粒子連續(xù)t次都移動較小距離，并且沒有找到目標，則認為該粒子近期在一個較小范圍內(nèi)搜索，可能陷入局部范圍找不到目標的狀況。若判斷出粒子已經(jīng)陷入局部無目標搜索，則重新設置粒子的位置進行搜索。設置方法如下：為當前所有粒子所在位置的重心，粒子i的新位置為xi＝＋α，其中α是一較大值，使得粒子在新的空地重新開始搜索，不會出現(xiàn)擁擠現(xiàn)象，能夠保證全局搜索的能力。

2.2 基于改進粒子群算法的d－下界點搜索

各路段的若干狀態(tài)的隨機出現(xiàn)構成了路網(wǎng)的巨大的狀態(tài)空間Ω。令X＝ （x1，x2，…，xi，…xn）為交通路網(wǎng)G＝ （N，E，F(xiàn)，P）的狀態(tài)空間Ω中的任一狀態(tài)，xi表示第i條路段所處的狀態(tài)號，xi∈ ［0，4］，fixi為該路段在xi狀態(tài)下的最大容量，并且當j＜j’時，fij＜fij′。在n維的目標搜索空間中，選擇m個路網(wǎng)狀態(tài)組成一個群體，從初始粒子群體開始，每個粒子根據(jù)自己的飛行經(jīng)驗和其它粒子的飛行經(jīng)驗來動態(tài)調整自己的飛行方向和距離，最終找到滿足d流量的下界點。

適應度函數(shù)為fitness（X）＝d－f（X），表示當前狀態(tài)的最大流量與目標流量的距離。其中，f（X）為X路網(wǎng)狀態(tài)下的最大流量。根據(jù)最大流最小割定理，網(wǎng)絡的最大流等于最小割的容量。在某一狀態(tài)X下，最大流f（X）＝min｛c（k）｜k為G的割｝，其中，c（k）為X狀態(tài)下k的容量。

根據(jù)本文求解問題的特點，對算法參數(shù)作以下設置：研究表明較大的慣性權重ω有利于跳出局部極小點，較小的ω有利于算法收斂。隨著迭代進行，ω按式 （3）由最大ωmax線性減小到最小ωmin，即

式中：itermax——最大進化代數(shù)，ωmax＝0.9，ωmin＝0.4［13］；群體規(guī)模m的選擇與解的個數(shù)有關，m值過小，會遺漏可行解，m值過大，則對搜索時間和空間造成浪費，一般取m值能夠滿足解的數(shù)量即可；本問題中粒子本身的思考和其它粒子提供的信息對粒子的飛行速度都有很好指導意義，可設置加速常數(shù)c1＝c2＝2；為不使粒子飛過好位置，且目標是局部最優(yōu)，所以Vmax可取值相對較小，Vmax＝2。

粒子執(zhí)行完更新操作后，需對粒子作適當調整才能保證粒子的有效性。調整如下

2.3 改進粒子群算法求解隨機流交通路網(wǎng)可靠性流程

本文提出的改進粒子群算法求解隨機流路網(wǎng)可靠性算法流程如下：

步驟1 設定各參數(shù)的值，包括群體規(guī)模m，慣性權重w，加速常數(shù)c，最大速度Vmax，最大迭代次數(shù)Gmax；

步驟2 初始化m個粒子，包括隨機位置和速度，記錄粒子的初始位置；

步驟3 計算每個粒子的適應度函數(shù)值；

步驟4 對每個粒子Xi，將其適應值與其經(jīng)歷的最好位置Pi的適應值作比較，如果較好，則將Xi作為當前的最好位置Pi；

步驟5 判斷粒子是否滿足流量d的要求，若滿足，記為d－下界點；

步驟6 對非d－下界點，根據(jù)轉移機制判斷粒子是否陷入局部無解狀態(tài)，若是，重新設置粒子位置；

步驟7 根據(jù)式 （1）和式 （2）更新粒子的速度和位置，控制粒子的更新速度在Vmax內(nèi)；

步驟8 根據(jù)式 （4）調整粒子，使得粒子是有效狀態(tài)；

步驟9 轉步驟3，直到各粒子都找到d－下界點為止；

步驟10 計算可靠性Rd（i，j）＝Pr｛X｜X≥Xi，Xi為d－下界點｝。

3 實例驗證分析

圖1為某城市某一路段抽象出來的交通網(wǎng)絡拓撲結構圖，其中包括6個節(jié)點和7條路段，這里以節(jié)點 （2→5）為OD對進行可靠性分析。假設在一天中的車流高峰期8：00－20：00之間連續(xù)對7個路段的車流量數(shù)據(jù)進行采集，每一小時為一個時間段，在12個時間段上共采集到12組數(shù)據(jù)，連續(xù)采集7天，求出平均值作為各路段一天中車流高峰期間的車流數(shù)據(jù)。

圖1 網(wǎng)絡結構

本試驗隨機產(chǎn)生7個路段的12組車流量數(shù)據(jù)作為基礎數(shù)據(jù)，路段上的各狀態(tài)對應的容量均為 ｛300，250，200，150，100｝，對該路網(wǎng)建立隨機流路網(wǎng)模型，經(jīng)計算得到表2所示的路網(wǎng)各路段容量及其概率數(shù)據(jù)。

表2 隨機流路網(wǎng)容量及概率數(shù)據(jù)

應用本文提出的改進粒子群算法搜索得到不同需求量下OD對 （2→5）的d－下界點如表3所示。

為了驗證本文提出的改進粒子群算法對交通流路網(wǎng)可靠性分析的正確性，首先應用本文提出的方法計算不同需求量下OD對 （2→5）的可靠性，然后采用傳統(tǒng)蒙特卡羅方法進行計算，將兩種不同方法計算結果進行比較，見圖2，從圖2可見清楚地看出本文提出的改進粒子群算法的計算結果與傳統(tǒng)蒙特卡羅方法計算基本一致，從而說明了本文提出的改進算法是準確有效的。

表3 不同需求量下的d－下界點

圖2 算法結果比較

4 結束語

根據(jù)城市交通路網(wǎng)容量的隨機性特征，本文建立了隨機流交通路網(wǎng)可靠性模型；提出的路網(wǎng)可靠性的算法以整個狀態(tài)空間為背景搜索出所有的下界點狀態(tài)，避免狀態(tài)數(shù)量的限制影響到可靠性計算的準確度；搜索過程提出的改進粒子群算法能夠尋找到多個可行解，并且在算法中引入轉移機制的搜索方案，避免了粒子出現(xiàn)局部無解現(xiàn)象，能夠在整個狀態(tài)空間中找到足夠的d－下界點。本文提出的算法為城市交通路網(wǎng)的可靠性評價提供了一個新的途徑，可以幫助路網(wǎng)管理者對路網(wǎng)能力進行判斷，并對路網(wǎng)的規(guī)劃有一定指導意義。

［1］Armando M，Leite da Silva，Reinaldo A G，et al.Generating capacity reliability evaluation based on Monte Carlo simulation and cross－entropy methods ［J］.IEEE Transactions on Power Systems，2010，25 （1）：129－136.

［2］Loustau Pierre，Morency Catherine，Trépanier Martin，et al.Travel time reliability on a highway network：Estimations using floating car data ［J］.Transportation Letters，2010，2 （1）：27－37.

［3］Sumalee A，Kurauchi F.Network capacity reliability analysis considering traffic regulation after a major disaster ［J］.Networks and Spatial Economics，2006，6 （3）：205－219.

［4］ Hesham Rakha，Ihab El－Shawarby， Mazen Arafeh.Trip travel－time reliability：Issues and proposed solutions ［J］.Journal of Intelligent Transportation Systems，2010，14 （4）：232－250.

［5］KUANG Aiwu，HUANG Zhongxiang.On the service reliability in stochastic supply and demand ［J］.Systems Engineering，2007，25 （6）：25－29 （in Chinese）. ［況愛武，黃中祥.隨機供求下的道路服務水平可靠性 ［J］.系統(tǒng)工程，2007，25（6）：25－29.］

［6］David Watling.Modelling and evaluation of reliability impacts in road networks：Concepts and methods for traffic assignment models ［C］.Leiden，Netherlands：European Transport and Conference，2008.

［7］LENG Junqiang，ZHANG Yaping，ZHAO Yingping，et al.Assessment of road network capacity reliability based on the constraints of link LOS ［J］.Journal of Transportation Systems Engineering and Information，2009，9 （5）：148－152 （in Chinese）.［冷軍強，張亞平，趙瑩萍，等.基于路段服務水平約束的路網(wǎng)容量可靠性分析 ［J］.交通運輸系統(tǒng)工程與信息，2009，9 （5）：148－152.］

［8］WANG Yingjie，TAO Shining，CHENG Lin.Research on the estimating connectivity reliability of transport networks ［J］.Journal of Transportation Engineering and Information，2008，6 （2）：102－106 （in Chinese）.［王英杰，陶世寧，程琳.交通網(wǎng)絡連通可靠性評價方法研究 ［J］.交通運輸工程與信息學報，2008，6 （2）：102－106.］

［9］GUO Shuxia，YU Lei，CHEN Xumei，et al.A review of assessment measures on road network reliability ［J］.Urban Transport of China，2008，6 （5）：64－68 （in Chinese）.［郭淑霞，于雷，陳旭梅，等.路網(wǎng)可靠性評價指標研究綜述 ［J］.城市交通，2008，6 （5）：64－68.］

［10］GUO Jifu，GAO Yong，WEN Huimin.Assessment methodo－logy of connect reliability based on substituted route ［J］.Journal of Highway and Transportation Research and Development，2007，24（7）：91－94 （in Chinese）.［郭繼孚，高永，溫慧敏.基于替代路徑的路網(wǎng)連通可靠性評價方法研究 ［J］.公路交通科技，2007，24 （7）：91－94.］

［11］ZHAI Jing，LENG Junqiang，WANG Tianyi，et al.Reliability analysis of road network system based on substituted route ［J］.Journal of Kunming University of Science and Technology （Science and Technology），2010，35 （4）：57－60（in Chinese）.［翟京，冷軍強，王天逸，等.基于替代路徑的道路系統(tǒng)連通可靠性分析 ［J］.昆明理工大學學報 （理工版），2010，35 （4）：57－60.］

［12］HUANG Shaorong.Survey of particle swarm optimization algorithm ［J］.Computer Engineering and Design，2009，30 （8）：1977－1980 （in Chinese）. ［黃少榮.粒子群優(yōu)化算法綜述 ［J］.計算機工程與設計，2009，30 （8）：1977－1980.］

［13］SUN Yong，ZHANG Weiguo，ZHANG Meng，et al.Optimization of flight controller parameters based on chaotic PSO algorithm of adaptive parameter strategy ［J］.Journal of System Simulation，2010，22 （5）：1222－1225 （in Chinese）.［孫勇，章衛(wèi)國，章萌，等.基于改進粒子群算法的飛行控制器參 數(shù) 尋 優(yōu) ［J］. 系 統(tǒng) 仿 真 學 報，2010，22 （5）：1222－1225.］

［14］REN Xiaobo，YANG Zhongxiu.Improvement of particle swarm optimization algorithm ［J］.Computer Engineering，2010，36 （7）：205－207 （in Chinese）.［任小波，楊忠秀.粒子群優(yōu)化算法的改進 ［J］.計算機工程，2010，36 （7）：205－207.］

［15］DAI Jun，LI Guo，XU Chen.Enhanced particle swarm optimization algorithm ［J］.Journal of Computer Applications，2010，30 （5）：1293－1296 （in Chinese）. ［代軍，李國，徐晨.一種增強型的粒子群優(yōu)化算法 ［J］.計算機應用，2010，30 （5）：1293－1296.］