張 薇
(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院,甘肅 蘭州730070)
城市交通路網(wǎng)可靠性是衡量道路交通系統(tǒng)性能的重要指標(biāo)。目前交通網(wǎng)絡(luò)的可靠性研究主要集中在以下3個(gè)方面:連通可靠性、行程時(shí)間可靠性和容量可靠性。目前,路網(wǎng)可靠性的研究主要集中在行程時(shí)間、容量可靠性兩方面[1-4]。本文針對(duì)容量可靠性進(jìn)行研究。
Chen等提出了容量可靠性概念后,接著又提出了基于靈敏度分析和Monte Carlo技術(shù)來(lái)求解可靠性的方法。Lo和Tung建立了隨機(jī)約束線性規(guī)劃模型、PUE(概率用戶平衡)模型來(lái)計(jì)算路網(wǎng)的可靠性。劉海旭、蒲云構(gòu)造了雙層規(guī)劃模型來(lái)計(jì)算路網(wǎng)的可靠性。這些模型都是以線性規(guī)劃為基礎(chǔ),并且被應(yīng)用在實(shí)際的大規(guī)模道路交通網(wǎng)絡(luò)中時(shí),其計(jì)算量大。文獻(xiàn) [5]從狀態(tài)空間的角度來(lái)考慮路網(wǎng)的容量可靠性問(wèn)題,為路網(wǎng)可靠性的評(píng)價(jià)提供了一個(gè)新的空間。它選取網(wǎng)絡(luò)最可能狀態(tài)來(lái)確定路段及路網(wǎng)可靠性的下界和上界以得到可靠性的近似值。不難發(fā)現(xiàn),當(dāng)狀態(tài)數(shù)量增加時(shí),可靠性的上下界趨于接近,這說(shuō)明狀態(tài)數(shù)量的選取限制了可靠性的準(zhǔn)確度。文獻(xiàn) [5]中可靠性計(jì)算結(jié)果只是估計(jì)值的原因在于其算法只選取了狀態(tài)空間中的一部份最有可能狀態(tài)作為研究基礎(chǔ)。本文建立了隨機(jī)流路網(wǎng)容量可靠性模型,并基于此模型提出了一種交通路網(wǎng)容量可靠性計(jì)算方法,計(jì)算可靠性時(shí)考慮路網(wǎng)的整個(gè)狀態(tài)空間,采用改進(jìn)的粒子群算法對(duì)整個(gè)狀態(tài)空間進(jìn)行搜索,以獲得狀態(tài)空間的所有下界點(diǎn)來(lái)計(jì)算路網(wǎng)的容量可靠性。
定義G= (N,E,F(xiàn),P)是一個(gè)隨機(jī)流交通路網(wǎng),其中N是交通路網(wǎng)節(jié)點(diǎn)的集合,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ù)我國(guó)目前大中城市的道路服務(wù)水平劃分標(biāo)準(zhǔn) (見(jiàn)表1),路段上的服務(wù)水平按照飽和度分為5個(gè)級(jí)別,由于不同的服務(wù)水平下路段的容量也會(huì)不同,并且這5個(gè)服務(wù)水平級(jí)別恰好能夠反映路段的5種容量狀態(tài)。因此可將路網(wǎng)中各路段上采集到的交通流量數(shù)據(jù)對(duì)應(yīng)地劃分到5個(gè)狀態(tài)中。方法如下:設(shè)vi是第j個(gè)路段的第i個(gè)流量數(shù)據(jù),根據(jù)飽和度,可得到對(duì)應(yīng)的服務(wù)水平級(jí)別,即可知對(duì)應(yīng)容量狀態(tài)。隨機(jī)流路網(wǎng)模型的參數(shù)計(jì)算如下:各狀態(tài)的容量值fjk取在該狀態(tài)下的路段容量平均值,設(shè)該路段上共有n個(gè)采集數(shù)據(jù),劃分到第k狀態(tài)的數(shù)據(jù)個(gè)數(shù)為nk,k∈[0,4],則第j個(gè)路段的第k狀態(tài)概率為Pjk=,并且=1。
表1 我國(guó)大中城市道路服務(wù)水平劃分采用值
實(shí)際的交通網(wǎng)絡(luò)中路段的容量是不確定的,完全暢通時(shí),容量為最大值;完全阻塞時(shí),容量為0,更多的情況下路段既不處于完全暢通狀態(tài),也不處于完全阻塞狀態(tài),而是介于兩者之間的某種狀態(tài),其容量為0到最大值之間的某一個(gè)值。因此,路段的容量是隨機(jī)的,是隨著流量的改變而變化的。容量的不確定性使得路網(wǎng)的可靠性計(jì)算變得困難。本文建立的交通路網(wǎng)模型將各路段的容量以道路服務(wù)水平為依據(jù)進(jìn)行狀態(tài)劃分,使得容量的不確定轉(zhuǎn)化為5種確定狀態(tài),以解決路段容量的實(shí)測(cè)數(shù)據(jù)很難得到的問(wèn)題,來(lái)研究整個(gè)路網(wǎng)的可靠性。
另外,連通可靠性經(jīng)常被用于如地震等自然災(zāi)害發(fā)生時(shí)的特殊情況下的路網(wǎng)狀態(tài)評(píng)價(jià),而不適用于正常的交通網(wǎng)絡(luò)中[6-11]。本文的隨機(jī)流路網(wǎng)模型恰好描述了路網(wǎng)的多種狀態(tài)及各種狀態(tài)的概率,使得最終可靠性評(píng)價(jià)結(jié)果能夠表征路網(wǎng)連通的程度,從而可以判斷路網(wǎng)的確切狀態(tài)。這樣連通可靠性的應(yīng)用范圍能夠得到擴(kuò)展,應(yīng)用于正常交通網(wǎng)絡(luò)中可靠性的評(píng)價(jià)。
路網(wǎng)容量可靠性反映的是路網(wǎng)能夠滿足一定交通需求的概率。各路段的若干狀態(tài)的隨機(jī)出現(xiàn)構(gòu)成了路網(wǎng)的巨大的狀態(tài)空間Ω。令X= (x1,x2,…,xi,…xn)為交通路網(wǎng)G= (N,E,F(xiàn),P)的狀態(tài)空間Ω中的任一狀態(tài),同時(shí)令交通需求量為d。若某個(gè)路網(wǎng)狀態(tài)X= (x1,x2,…,xi,…xn)能夠滿足需求流量d,并且大于此狀態(tài)的路網(wǎng)狀態(tài)都能夠滿足需求流量d,則該狀態(tài)稱為路網(wǎng)的d-下界點(diǎn)。
其中,狀態(tài)X1>X2的含義為:不存在x1i<x2i的情況,即狀態(tài)X1中的所有路段容量都大于或等于狀態(tài)X2中的對(duì)應(yīng)的路段容量。
根據(jù)可靠性原理,當(dāng)需求流量為d時(shí),節(jié)點(diǎn)i和j之間的可靠性為Rd(i,j)=Pr{X|f(X)≥d}=Pr{X|X≥Xi,Xi為d-下界點(diǎn)},因此,可靠性的計(jì)算問(wèn)題轉(zhuǎn)化為求出路網(wǎng)狀態(tài)空間中足夠d-下界點(diǎn)的問(wèn)題。
粒子群優(yōu)化 (particle swarm optimization,PSO)算法是一種模擬鳥(niǎo)群覓食行為的演化計(jì)算算法。粒子群優(yōu)化算法提出之后引起了全世界學(xué)者的廣泛關(guān)注。由于粒子群優(yōu)化算法概念簡(jiǎn)單,收斂速度快,涉及參數(shù)少,易于實(shí)現(xiàn),具有很強(qiáng)的全局優(yōu)化能力,因而迅速得到了認(rèn)可,在當(dāng)前的優(yōu)化應(yīng)用中受到越來(lái)越多的關(guān)注。目前粒子群優(yōu)化算法已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制、水利、電力和經(jīng)濟(jì)等大規(guī)模組合優(yōu)化問(wèn)題求解[12-15]。但是在求解問(wèn)題規(guī)模龐大的交通路網(wǎng)問(wèn)題時(shí)基本粒子群算法常常會(huì)陷入局部無(wú)解狀態(tài)。本文利用粒子群算法的最優(yōu)解實(shí)質(zhì)是基于局部極值搜尋的這一特點(diǎn),提出一種改進(jìn)的能夠搜索出滿足要求的多個(gè)解的方法,應(yīng)用這種改進(jìn)的粒子群算法實(shí)現(xiàn)整個(gè)狀態(tài)空間中足夠d-下界點(diǎn)的目標(biāo)搜索,從而進(jìn)行有效的交通流路網(wǎng)可靠性分析。
基本PSO算法一直適用于尋找一個(gè)最優(yōu)解的問(wèn)題,其實(shí)將多個(gè)粒子散布于狀態(tài)空間中,各個(gè)粒子通過(guò)自己本身的思考和其它粒子提供的信息作為指導(dǎo),不斷地改變飛行速度,最終是能夠在狀態(tài)空間中找到滿足某條件的多個(gè)解的。
式中:i=1,2…,m,d=1,2,…,D;ω——慣性因子;c1、c2——學(xué)習(xí)因子;r1、r2—— [0,1]之間的隨機(jī)數(shù);α——約束因子;——所有局部無(wú)解狀態(tài)的出發(fā)點(diǎn)的重心。粒子既具有認(rèn)知能力,又具有粒子之間的社會(huì)信息共享與相互合作。粒子的速度取決于當(dāng)前最好位置和無(wú)解狀態(tài)的重心位置,通過(guò)學(xué)習(xí)后會(huì)向自己當(dāng)前最好位置靠近,而遠(yuǎn)離局部無(wú)解狀態(tài)的位置,從而盡快找到局部最優(yōu)解。
隨機(jī)流交通路網(wǎng)隨著節(jié)點(diǎn)的增加,問(wèn)題的規(guī)模解也越來(lái)越多,常規(guī)基本粒子群算法往往陷入局部無(wú)解狀態(tài),使問(wèn)題無(wú)法求解。本文提出一種改進(jìn)粒子群算法,即在基本粒子群算法中加入一種轉(zhuǎn)移機(jī)制。即當(dāng)某一粒子連續(xù)t次更新后仍處于一局部范圍,則重新為該粒子找到新的出發(fā)點(diǎn)。令xit2為粒子i從位置xit1更新后的位置,則|xit1-xit2|為粒子i某一次的移動(dòng)距離,若|xit1-xit2|<ε(ε為一較小值),表示粒子移動(dòng)距離較小,如果粒子連續(xù)t次都移動(dòng)較小距離,并且沒(méi)有找到目標(biāo),則認(rèn)為該粒子近期在一個(gè)較小范圍內(nèi)搜索,可能陷入局部范圍找不到目標(biāo)的狀況。若判斷出粒子已經(jīng)陷入局部無(wú)目標(biāo)搜索,則重新設(shè)置粒子的位置進(jìn)行搜索。設(shè)置方法如下:為當(dāng)前所有粒子所在位置的重心,粒子i的新位置為xi=+α,其中α是一較大值,使得粒子在新的空地重新開(kāi)始搜索,不會(huì)出現(xiàn)擁擠現(xiàn)象,能夠保證全局搜索的能力。
各路段的若干狀態(tài)的隨機(jī)出現(xiàn)構(gòu)成了路網(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)號(hào),xi∈ [0,4],fixi為該路段在xi狀態(tài)下的最大容量,并且當(dāng)j<j’時(shí),fij<fij′。在n維的目標(biāo)搜索空間中,選擇m個(gè)路網(wǎng)狀態(tài)組成一個(gè)群體,從初始粒子群體開(kāi)始,每個(gè)粒子根據(jù)自己的飛行經(jīng)驗(yàn)和其它粒子的飛行經(jīng)驗(yàn)來(lái)動(dòng)態(tài)調(diào)整自己的飛行方向和距離,最終找到滿足d流量的下界點(diǎn)。
適應(yīng)度函數(shù)為fitness(X)=d-f(X),表示當(dāng)前狀態(tài)的最大流量與目標(biāo)流量的距離。其中,f(X)為X路網(wǎng)狀態(tài)下的最大流量。根據(jù)最大流最小割定理,網(wǎng)絡(luò)的最大流等于最小割的容量。在某一狀態(tài)X下,最大流f(X)=min{c(k)|k為G的割},其中,c(k)為X狀態(tài)下k的容量。
根據(jù)本文求解問(wèn)題的特點(diǎn),對(duì)算法參數(shù)作以下設(shè)置:研究表明較大的慣性權(quán)重ω有利于跳出局部極小點(diǎn),較小的ω有利于算法收斂。隨著迭代進(jìn)行,ω按式 (3)由最大ωmax線性減小到最小ωmin,即
式中:itermax——最大進(jìn)化代數(shù),ωmax=0.9,ωmin=0.4[13];群體規(guī)模m的選擇與解的個(gè)數(shù)有關(guān),m值過(guò)小,會(huì)遺漏可行解,m值過(guò)大,則對(duì)搜索時(shí)間和空間造成浪費(fèi),一般取m值能夠滿足解的數(shù)量即可;本問(wèn)題中粒子本身的思考和其它粒子提供的信息對(duì)粒子的飛行速度都有很好指導(dǎo)意義,可設(shè)置加速常數(shù)c1=c2=2;為不使粒子飛過(guò)好位置,且目標(biāo)是局部最優(yōu),所以Vmax可取值相對(duì)較小,Vmax=2。
粒子執(zhí)行完更新操作后,需對(duì)粒子作適當(dāng)調(diào)整才能保證粒子的有效性。調(diào)整如下
本文提出的改進(jìn)粒子群算法求解隨機(jī)流路網(wǎng)可靠性算法流程如下:
步驟1 設(shè)定各參數(shù)的值,包括群體規(guī)模m,慣性權(quán)重w,加速常數(shù)c,最大速度Vmax,最大迭代次數(shù)Gmax;
步驟2 初始化m個(gè)粒子,包括隨機(jī)位置和速度,記錄粒子的初始位置;
步驟3 計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值;
步驟4 對(duì)每個(gè)粒子X(jué)i,將其適應(yīng)值與其經(jīng)歷的最好位置Pi的適應(yīng)值作比較,如果較好,則將Xi作為當(dāng)前的最好位置Pi;
步驟5 判斷粒子是否滿足流量d的要求,若滿足,記為d-下界點(diǎn);
步驟6 對(duì)非d-下界點(diǎn),根據(jù)轉(zhuǎn)移機(jī)制判斷粒子是否陷入局部無(wú)解狀態(tài),若是,重新設(shè)置粒子位置;
步驟7 根據(jù)式 (1)和式 (2)更新粒子的速度和位置,控制粒子的更新速度在Vmax內(nèi);
步驟8 根據(jù)式 (4)調(diào)整粒子,使得粒子是有效狀態(tài);
步驟9 轉(zhuǎn)步驟3,直到各粒子都找到d-下界點(diǎn)為止;
步驟10 計(jì)算可靠性Rd(i,j)=Pr{X|X≥Xi,Xi為d-下界點(diǎn)}。
圖1為某城市某一路段抽象出來(lái)的交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖,其中包括6個(gè)節(jié)點(diǎn)和7條路段,這里以節(jié)點(diǎn) (2→5)為OD對(duì)進(jìn)行可靠性分析。假設(shè)在一天中的車流高峰期8:00-20:00之間連續(xù)對(duì)7個(gè)路段的車流量數(shù)據(jù)進(jìn)行采集,每一小時(shí)為一個(gè)時(shí)間段,在12個(gè)時(shí)間段上共采集到12組數(shù)據(jù),連續(xù)采集7天,求出平均值作為各路段一天中車流高峰期間的車流數(shù)據(jù)。
圖1 網(wǎng)絡(luò)結(jié)構(gòu)
本試驗(yàn)隨機(jī)產(chǎn)生7個(gè)路段的12組車流量數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù),路段上的各狀態(tài)對(duì)應(yīng)的容量均為 {300,250,200,150,100},對(duì)該路網(wǎng)建立隨機(jī)流路網(wǎng)模型,經(jīng)計(jì)算得到表2所示的路網(wǎng)各路段容量及其概率數(shù)據(jù)。
表2 隨機(jī)流路網(wǎng)容量及概率數(shù)據(jù)
應(yīng)用本文提出的改進(jìn)粒子群算法搜索得到不同需求量下OD對(duì) (2→5)的d-下界點(diǎn)如表3所示。
為了驗(yàn)證本文提出的改進(jìn)粒子群算法對(duì)交通流路網(wǎng)可靠性分析的正確性,首先應(yīng)用本文提出的方法計(jì)算不同需求量下OD對(duì) (2→5)的可靠性,然后采用傳統(tǒng)蒙特卡羅方法進(jìn)行計(jì)算,將兩種不同方法計(jì)算結(jié)果進(jìn)行比較,見(jiàn)圖2,從圖2可見(jiàn)清楚地看出本文提出的改進(jìn)粒子群算法的計(jì)算結(jié)果與傳統(tǒng)蒙特卡羅方法計(jì)算基本一致,從而說(shuō)明了本文提出的改進(jìn)算法是準(zhǔn)確有效的。
表3 不同需求量下的d-下界點(diǎn)
圖2 算法結(jié)果比較
根據(jù)城市交通路網(wǎng)容量的隨機(jī)性特征,本文建立了隨機(jī)流交通路網(wǎng)可靠性模型;提出的路網(wǎng)可靠性的算法以整個(gè)狀態(tài)空間為背景搜索出所有的下界點(diǎn)狀態(tài),避免狀態(tài)數(shù)量的限制影響到可靠性計(jì)算的準(zhǔn)確度;搜索過(guò)程提出的改進(jìn)粒子群算法能夠?qū)ふ业蕉鄠€(gè)可行解,并且在算法中引入轉(zhuǎn)移機(jī)制的搜索方案,避免了粒子出現(xiàn)局部無(wú)解現(xiàn)象,能夠在整個(gè)狀態(tài)空間中找到足夠的d-下界點(diǎn)。本文提出的算法為城市交通路網(wǎng)的可靠性評(píng)價(jià)提供了一個(gè)新的途徑,可以幫助路網(wǎng)管理者對(duì)路網(wǎng)能力進(jìn)行判斷,并對(duì)路網(wǎng)的規(guī)劃有一定指導(dǎo)意義。
[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). [況愛(ài)武,黃中祥.隨機(jī)供求下的道路服務(wù)水平可靠性 [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).[冷軍強(qiáng),張亞平,趙瑩萍,等.基于路段服務(wù)水平約束的路網(wǎng)容量可靠性分析 [J].交通運(yùn)輸系統(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)絡(luò)連通可靠性評(píng)價(jià)方法研究 [J].交通運(yùn)輸工程與信息學(xué)報(bào),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)可靠性評(píng)價(jià)指標(biāo)研究綜述 [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)連通可靠性評(píng)價(jià)方法研究 [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).[翟京,冷軍強(qiáng),王天逸,等.基于替代路徑的道路系統(tǒng)連通可靠性分析 [J].昆明理工大學(xué)學(xué)報(bào) (理工版),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].計(jì)算機(jī)工程與設(shè)計(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)國(guó),章萌,等.基于改進(jìn)粒子群算法的飛行控制器參 數(shù) 尋 優(yōu) [J]. 系 統(tǒng) 仿 真 學(xué) 報(bào),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ìn) [J].計(jì)算機(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). [代軍,李國(guó),徐晨.一種增強(qiáng)型的粒子群優(yōu)化算法 [J].計(jì)算機(jī)應(yīng)用,2010,30 (5):1293-1296.]