基于改進粒子群算法的隨機流路網可靠性研究

張 薇

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

0 引 言

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

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

1 隨機流交通路網可靠性模型

1.1 隨機流交通路網模型定義

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

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

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

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

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

1.2 路網可靠性定義

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

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

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

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

2.1 一種改進的粒子群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟7 根據式 （1）和式 （2）更新粒子的速度和位置，控制粒子的更新速度在Vmax內；

步驟8 根據式 （4）調整粒子，使得粒子是有效狀態；

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

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

3 實例驗證分析

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

圖1 網絡結構

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

表2 隨機流路網容量及概率數據

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

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

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

圖2 算法結果比較

4 結束語

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

［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］.系統工程，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）.［冷軍強，張亞平，趙瑩萍，等.基于路段服務水平約束的路網容量可靠性分析 ［J］.交通運輸系統工程與信息，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）.［王英杰，陶世寧，程琳.交通網絡連通可靠性評價方法研究 ［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）.［郭淑霞，于雷，陳旭梅，等.路網可靠性評價指標研究綜述 ［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）.［郭繼孚，高永，溫慧敏.基于替代路徑的路網連通可靠性評價方法研究 ［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）.［翟京，冷軍強，王天逸，等.基于替代路徑的道路系統連通可靠性分析 ［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）. ［黃少榮.粒子群優化算法綜述 ［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）.［孫勇，章衛國，章萌，等.基于改進粒子群算法的飛行控制器參 數 尋 優 ［J］. 系 統 仿 真 學 報，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）.［任小波，楊忠秀.粒子群優化算法的改進 ［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）. ［代軍，李國，徐晨.一種增強型的粒子群優化算法 ［J］.計算機應用，2010，30 （5）：1293－1296.］