戢曉峰,覃文文
(1.昆明理工大學(xué) 交通工程學(xué)院,昆明650500;2.長沙理工大學(xué) 公路工程省部共建教育部重點實驗室,長沙410004;3.吉林大學(xué) 汽車仿真與控制國家重點實驗室,長春130025)
考慮局部排隊延誤的VMS選址雙層規(guī)劃模型
戢曉峰*1,2,3,覃文文1
(1.昆明理工大學(xué) 交通工程學(xué)院,昆明650500;2.長沙理工大學(xué) 公路工程省部共建教育部重點實驗室,長沙410004;3.吉林大學(xué) 汽車仿真與控制國家重點實驗室,長春130025)
用Monte Carlo模擬技術(shù)刻畫路網(wǎng)狀態(tài)的隨機性,優(yōu)先考慮在交通網(wǎng)絡(luò)瓶頸路段設(shè)置可變信息板待選點,建立多目標(biāo)優(yōu)化可變信息板選址雙層規(guī)劃模型.上層模型為基于不確定風(fēng)險決策最小和誘導(dǎo)效益最大的雙目標(biāo)規(guī)劃模型,下層模型為考慮局部網(wǎng)絡(luò)有排隊延遲現(xiàn)象的隨機用戶平衡模型.采用增廣Lagrange對偶算法與相繼平均算法組合求解下層模型,采用非劣排序遺傳算法-II求解整個雙層規(guī)劃模型.算例結(jié)果表明,在可變信息板資金預(yù)算約束下,非劣排序遺傳算法-II能夠有效求解可變信息板選址的多目標(biāo)優(yōu)化問題,得到6組Pareto解.研究結(jié)果可為城市道路網(wǎng)可變信息板誘導(dǎo)配置的優(yōu)化和建設(shè)提供決策支持.
智能交通;VMS選址;雙層規(guī)劃;交通誘導(dǎo);非劣排序遺傳算法-II;增廣Lagrange對偶算法
可變信息板(Variable Message Signs,VMS)作為一種有效的群體式誘導(dǎo)信息發(fā)布系統(tǒng),其布局和信息發(fā)布對出行質(zhì)量起著關(guān)鍵性的影響[1].VMS信息發(fā)布對出行者路徑選擇行為的影響仍然是國內(nèi)外學(xué)者廣泛關(guān)注的問題[2-4],但對于VMS選址問題的相關(guān)研究并不多見.后者研究對象大多限于高速公路或快速路的VMS布局優(yōu)化,較少考慮交通系統(tǒng)對VMS選址建模的不確定性影響.Chiu和Huynh[5]假定所有出行者擁有完全信息,能預(yù)期其他出行者路徑選擇行為,建立了上層為最大化信息發(fā)布收益的VMS最優(yōu)布點,下層為用戶動態(tài)最優(yōu)交通分配模型.該模型涉及多個VMS候選方案的評估,計算量過大,難以應(yīng)用于大規(guī)模城市路網(wǎng).隨后,Chiu和Huynh[6]進一步考慮了隨機事故與ATIS共存情況下的動態(tài)VMS最優(yōu)選址問題,發(fā)現(xiàn)同時部署VMS與ATIS,比相繼安裝兩個系統(tǒng)效益更好.
綜上分析,VMS選址方案是在一個不確定性的路網(wǎng)環(huán)境中進行VMS的最佳布局,而這種不確定性主要體現(xiàn)在:
(1)交通需求的不確定性,即用戶出行的隨機性;
(2)道路交通狀態(tài)的不確定性,如路段突發(fā)交通事故等;
(3)認(rèn)知不確定性,即VMS信息發(fā)布的不完全和出行者對信息的認(rèn)知偏差,導(dǎo)致出行者做出違背信息誘導(dǎo)的路徑選擇行為.
本文引入信息熵的概念,以誘導(dǎo)交通流與VMS影響區(qū)域產(chǎn)生的信息量作為誘導(dǎo)效益最大化的衡量指標(biāo),使用行程時間的期望和標(biāo)準(zhǔn)差量化不確定決策中的風(fēng)險,建立VMS選址模型.
考慮由VMS有效影響路段組成的局部路網(wǎng),在路段能力約束下,一個有效的VMS選址方案應(yīng)該盡可能地消除瓶頸路段上由于溢流而產(chǎn)生的排隊現(xiàn)象.因此,本文利用路段費用的變化來反映VMS的誘導(dǎo)作用,即路段費用由行程時間和排隊延誤組成,出行者偏向選擇旅行費用較小的路徑出行.本文為降低模型整體規(guī)模的計算復(fù)雜度,在算例網(wǎng)絡(luò)中利用UE配流確定瓶頸路段,以此得到VMS候選點集合,并界定每個VMS的有效影響路段.
考慮交通網(wǎng)絡(luò)G=(N,A),N為所有節(jié)點的集合;A為所有路段的集合;為所有VMS有效影響路段的集合;W為所有起訖點(OD)集合,w∈W;Kw為OD對w的所有路徑集合,k∈Kw;Ω為OD需求隨機抽樣形成的不確定情景集合,并假設(shè)OD需求是滿足給定概率分布的隨機變量;ω為Ω集合中的任一需求情景實現(xiàn);qω為ω情景下的OD需求量;pω為ω情景發(fā)生概率;Λ為路段交通狀態(tài)不確定交通情景集合;λ為Λ集合中的任一交通情景實現(xiàn);pλ為λ情景發(fā)生概率為ω情景下的路段α所需的行程時間,假設(shè)其只與該路段上的流量和實際通行能力有關(guān);為ω情景下的OD對w之間路徑k的阻抗;為ω情景下的路徑路段流量關(guān)系的布爾變量,若路段a在OD對w之間路徑k上,其值為1,否則為0;為ω情景下的OD對w之間路徑k的流量;Cα為路段α的通行能力.
由于路段的交通狀態(tài)具有不確定性與實時性,本文利用信息熵衡量VMS有效影響路段上交通情景產(chǎn)生的信息量.信息量越大,越需設(shè)置VMS消除路段交通狀態(tài)的不確定性.
3.1 VMS的誘導(dǎo)效益值估計
定義VMS的誘導(dǎo)效益為VMS的誘導(dǎo)交通流與VMS消除有效影響路段產(chǎn)生的信息熵的乘積,計算公式為
考慮四種路段交通情景的集合Λ={λ1=順暢(V∕C≤0.6);λ2=稍有擁堵(0.6<V∕C≤0.8);λ3=擁堵(0.8<V∕C≤1);λ4=嚴(yán)重?fù)矶拢╒∕C>1)}.其中,估計任一交通情景的發(fā)生概率pλ的基本步驟是:
Step 1初始化,確定OD需求概率分布函數(shù).
Step 2令抽樣次數(shù)k=1.
Step 3隨機生成 OD需求向量 qk,ω=
Step 4采用隨機用戶平衡配流模型,將交通需求分配到路網(wǎng)上,獲得有效影響路段 j上的V∕C比值
Step 5若∈(0,0.6],則 λ1,j=λ1,j+1;若∈(0.6,0.8],則 λ2,j=λ2,j+1;若∈(0.8,1],則λ3,j=λ3,j+1;若∈(1,∞],則λ4,j=λ4,j+1.
Step 6若k小于抽樣規(guī)模S,則k=k+1;返回Step3.
Step 7若k=S,則停止,計算,再由式(1)得到有效影響路段 j產(chǎn)生的信息熵.
3.2 VMS選址雙層規(guī)劃模型
VMS選址要考慮用戶的路徑選擇行為,一般從規(guī)劃角度構(gòu)建上層決策模型,從用戶角度構(gòu)建下層路徑選擇模型.理論上,如整個路網(wǎng)都設(shè)置VMS能最大化VMS的誘導(dǎo)作用,但容易導(dǎo)致集聚反應(yīng),使得網(wǎng)絡(luò)更加擁堵.考慮OD需求和路段交通狀態(tài)的不確定性,不同需求強度和交通狀態(tài)下的VMS選址方案差異很大,決策者也將面臨較大的風(fēng)險決策.為降低選址方案對不確定性的敏感度,采用行程時間的期望和標(biāo)準(zhǔn)差量化不確定決策中的風(fēng)險,使得布置的VMS誘導(dǎo)效用值最大,不確定性的風(fēng)險值最小.
3.2.1 上層規(guī)劃模型
上層規(guī)劃模型包含兩個目標(biāo)函數(shù):一是最大化誘導(dǎo)流量和VMS影響區(qū)域的信息量;二是最小化所有交通情景發(fā)生下的路網(wǎng)總行程時間均值和標(biāo)準(zhǔn)差,決策變量為Zα.模型如下.
式中 Gα(Zα)為路段α配置VMS的投資函數(shù);B為整個路網(wǎng)配置VMS的預(yù)算總額;Zα是0-1決策變量,當(dāng)路段 α設(shè)置VMS時,Zα=1,反之,Zα=0;Fω為需求情景ω時的路網(wǎng)總行程時間;為路網(wǎng)總行程時間的期望值;ρ(0≤ρ≤1)為權(quán)重因子,反映了決策者對網(wǎng)絡(luò)效益和網(wǎng)絡(luò)穩(wěn)定性不同的重視程度.ρ取值越大,表明決策者越重視網(wǎng)絡(luò)效益,而忽略網(wǎng)絡(luò)穩(wěn)定性.
3.2.2 下層規(guī)劃模型
下層規(guī)劃模型為考慮局部網(wǎng)絡(luò)有排隊延遲現(xiàn)象的隨機用戶平衡模型.該局部網(wǎng)絡(luò)由VMS有效影響路段集合Aˉ組成,并在有效影響路段上添加通行能力約束條件.如路段流量超過通行能力,排隊現(xiàn)象就會形成.在基于Fisk的隨機用戶平衡模型上添加容量約束條件,通過VMS的有效布點使常發(fā)性擁擠路段的V/C值小于1,以此刻畫VMS有效誘導(dǎo)行駛車輛、消除排隊現(xiàn)象的作用,達到總行程時間最小的目標(biāo).其中,下層模型的Kuhn-Tucker條件的具體證明過程可參考文獻[7]和[8],本文不再累贅.θ為出行者對VMS發(fā)布信息的認(rèn)知偏差系數(shù),本文取0.1.若θ=0,表明出行者等概率地選擇VMS影響區(qū)域內(nèi)的各條路徑;若θ→∞,表明出行者傾向于選擇最短路徑出行.模型如下:
4.1 雙層模型求解
多目標(biāo)優(yōu)化VMS選址問題的最佳方法是求得問題的Pareto解,然后根據(jù)決策者的偏好程度從多組Pareto解中選出最優(yōu)解[9].因此,采用基于Monte Carlo模擬的非劣排序遺傳算法-II(Nondominated Sorting Genetic Algorithm-II,NSGA-II)算法求解雙層規(guī)劃模型[10],即生成滿足VMS投資預(yù)算要求的初始可行解集后,代入含容量限制的平衡配流模型中,根據(jù)所有OD隨機需求交通分配結(jié)果計算上層規(guī)劃的目標(biāo)函數(shù),得到種群中每個個體(VMS選址方案)的適應(yīng)度,并進行選擇、交叉、變異及非支配排序等步驟,最終獲得VMS選址的Pareto最優(yōu)解集.其中,帶容量約束的SUE模型采用增廣Lagrange對偶算法與MSA算法組合求解.求解流程如圖1所示.
圖1 基于Monte Carlo的NSGA-II算法流程Fig.1 Flow chart of NSGA-II based on Monte Carlo
4.1下層模型求解
為求解含有不等式約束的下層規(guī)劃問題,在式(9)中加入一個Lagrange項,構(gòu)造增廣Lagrange函數(shù),形成只含有非負(fù)線性等式約束的目標(biāo)函數(shù).
式中 η值為懲罰因子(η>0);μ向量為對偶約束的 Lagrange算子向量.若知道 μ,對于L(f,x,μ,η),只要取足夠大的罰因子,就可通過求解等式約束問題得到原問題的最優(yōu)解.
因此,設(shè)計增廣Lagrange對偶算法與MSA算法組合求解式(14).
Step 1初始化.選擇初始的μ值,即
Step 2求解子問題.令路段時間函數(shù)為
利用MSA算法求解一般性的隨機用戶均衡(Stochastic User Equilibrium,SUE)無能力約束交通分配問題,得到路段流量解xω,n.
Step 3終止條件.若(預(yù)置一個很小的數(shù)),停止迭代.否則轉(zhuǎn)下步.
Step 4更新算子和懲罰因子.由式(20)計算新的和 ρn+1:
式中 參數(shù)2≤k≤10,γ=0.25,并令n=n+1,轉(zhuǎn)Step 2.
上述步驟中,Step 2可用基于Logit加載技術(shù)的MSA算法求解隨機用戶平衡的交通分配問題;Step 3是一個確保路段流量有效的停止準(zhǔn)則.在Step 4中,如對偶約束的不可行程度沒有足夠降低,則懲罰算子的η值上升.
算例交通網(wǎng)絡(luò)包含38條路段和20個節(jié)點,從節(jié)點1到20只有1個OD對,如圖2所示.
圖2 VMS候選點與瓶頸路段示意圖Fig.2 Test network
采用BPR函數(shù)作為路阻函數(shù)
式中 tα0表示路段α的自由流行程時間,各參數(shù)取值如表1所示.
為識別瓶頸路段,按照用戶均衡原則進行交通分配,得到最擁堵的8個路段是5,8,16,19,20,27,30和32,則VMS候選點集合為{Z1,Z3,Z12,Z14,Z17,Z23,Z25,Z28},Z1的有效影響路段為{3, 4,5},Z3的有效影響路段為{6,7,8},Z12的有效影響路段為{14,15,16},Z14的有效影響路段為{17, 18,19},Z17的有效影響路段為{20,21},Z23的有效影響路段為{25,26,27},Z25的有效影響路段為{28, 29,30},Z28的有效影響路段為{31,32}.
算法用MATLAB編程實現(xiàn),并設(shè)計4種實驗場景以驗證NSGA-II算法的有效性.NSGA-II算法基本參數(shù)為:種群規(guī)模40,進化代數(shù)100,交叉概率0.9,變異概率0.1.
表1 算例相關(guān)參數(shù)Table 1 Parameters of test network
表2 4種實驗場景基本情況Table 2 The basic situation of four kinds of experiment scenarios
在每一種場景中,應(yīng)用NSGA-II算法求出所有個體的路網(wǎng)總行程時間的期望值(expected total travel time,ETTT)與標(biāo)準(zhǔn)差(standard deviation of total travel time,SDTTT),表3給出了4種實驗場景下的Pareto最優(yōu)VMS選址解集.
表3 4種實驗場景的Pareto最優(yōu)VMS選址Table 3 The Pareto set of VMS locations for four kinds of experiment scenarios
對表3進行初步分析,可以得到如下結(jié)果:
(1)當(dāng)資金預(yù)算相同,出行需求增大時,安裝VMS的交通網(wǎng)絡(luò)ETTT值增大;
(2)當(dāng)出行需求相同,資金預(yù)算減少時,安裝VMS的交通網(wǎng)絡(luò)ETTT值增大.
圖3對比了4種場景下不同選址方案的ETTT值與未安裝VMS的ETTT值.其中,在未安裝VMS的交通網(wǎng)絡(luò)中,分別考慮OD需求均值為1 000和1 500求解得ETTT值:585.23 h和958.54 h.
對參數(shù)τ和ρ捆綁分析發(fā)現(xiàn),τ和 ρ反映了VMS選址對交通網(wǎng)絡(luò)效益和穩(wěn)定性的影響.在需求均值為1 000,資金預(yù)算都相同的情況下,表4給出了三種場景中不同設(shè)計參數(shù)組合的ETTT值和SDTTT值.
表4 三種場景下的ETTT值和SDTTT值Table 4 The ETTT and SDTTT of three experiment scenarios
圖3 交通網(wǎng)絡(luò)中有無VMS的ETTT值對比Fig.3 The Comparison of ETTT between VMS installed and uninstalled in network
本文研究了在不確定性的交通網(wǎng)絡(luò)中尋找VMS的最佳布局點,用基于Monte Carlo的NSGA-II對VMS選址的多目標(biāo)優(yōu)化問題進行求解,考慮了OD需求、資金預(yù)算和設(shè)計參數(shù)不同組合的5種實驗場景,得出以下結(jié)論:
(1)所有實驗場景的ETTT值基本上大于沒有安裝VMS的交通網(wǎng)絡(luò)ETTT值,這一現(xiàn)象可以解釋為在求解下層模型中構(gòu)造了增廣Lagrange函數(shù),使得原本局部網(wǎng)絡(luò)發(fā)生擁擠的路段,通過設(shè)置Lagrange算子μ,強制性增大擁擠路段的出行阻抗,以此刻畫了VMS有效誘導(dǎo)行駛車輛、消除排隊現(xiàn)象的作用;
(2)隨著設(shè)計參數(shù)τ、ρ的變大,OD需求抽樣的隨機性增大,ETTT與SDTTT加權(quán)和的離散程度也隨之增大.發(fā)現(xiàn)ETTT值越大,SDTTT值就越小,ETTT值越小,SDTTT值就越大,存在明顯的替代關(guān)系;
(3)出行者的隨機需求與決策者的風(fēng)險偏好對選址方案具有顯著影響,ETTT與SDTTT作為量化網(wǎng)絡(luò)穩(wěn)定與效益程度的重要指標(biāo),成為直接影響決策者制定方案的重要影響因素.
[1] 戢曉峰,黃永忠,何增輝,等.面向誘導(dǎo)的交通狀態(tài)信息提取方法[J].計算機工程與應(yīng)用,2010,46(25):16-18. [JI X F,HUANG Y Z,HE Z H,et al.Traffic state information extraction methods for traffic guidance[J]. Computer Engineering and Applications,2010,46(25): 16-18.]
[2] ZHONG Shiquan,et al.Effects of different factors on drivers’guidance compliance behaviors under road condition information shown on VMS[J].Transportation Research Part A,2012,46(9):1490-1505.
[3] XU Tiandong,SUN Lijun,PENG Zhongren.Empirical analysis and modeling of drivers’response to variable message signs in Shanghai,China[J].Transportation Research Record,2011(2243):99-107.
[4] 王衛(wèi)衛(wèi),趙小梅,李新剛,等.VMS對駕駛員路徑選擇影響的實證研究與建模[J].交通運輸系統(tǒng)工程與信息,2013,13(3):60-64.[WANG W W,ZHAO X M,LI X G,et al.Empirical study and modeling of variable message signs on route choice behavior[J].Journal of Transportation Systems Engineering and Information Technology,2013,13(3):60-64.]
[5] CHIU YC,HUYNHN,MAHMASSANIHS. Determining optimallocationsforVMS’sunder stochastic incident scenarios[C]∕Transportation Research Board Annual Meeting.Washington D C, 2001.
[6] CHIU Y C,HUYNH N.Location configuration design for dynamic message signs under stochastic incident and ATIS scenarios[J].Transportation Research Part C, 2007,15(1):33-50.
[7] BELL MGH.Stochastic user equilibrium assignment in network with queues[J].Transportation Research Part B, 1995,29(2):125-137.
[8] RYU S,CHEN A,XU X,et al.A dual approach for solving the combined distribution and assignment problem with link capacity constraints[J].Networks and Spatial Economics,2014,14(1):245-270.
[9] 龐曉平,陳進.非支配排序遺傳算法的動壓軸承形狀多目標(biāo)優(yōu)化[J].西南交通大學(xué)學(xué)報,2012,47(4): 639-645.[PANG X P,CHEN J.Multi-objective shape optimization of hydrodynamic journal bearings using non-dominated sorting genetic algorithmⅡ[J].Journal of Southwest Jiaotong University,2012,47(4):639-645.]
[10] DEB K,PRATAP A,AGARWAL S,et al.A fast elitist multi-objective genetic algorithms:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2): 182-197.
Bi-level Programming Model for VMS Layout Considering Local Queuing Delay
JI Xiao-feng1,2,3,QIN Wen-wen1
(1.Faculty of Transportation Engineering,Kunming University of Science and Technology,Kunming 650500,China 2.Key Laboratory of Highway Engineering,Ministry of Education,Changsha University of Science&Technology,Changsha 410004, China;3.State Key Laboratory ofAutomotive Simulation and Control,Jilin University,Changchun 130025,China)
Using Monte Carlo methodology to characterize randomness of the road network state,a number of candidate variable message signs(VMS)locations are deployed in bottleneck links,and then a biobjective bi-level programming model is established for optimization of VMS location.The upper level model is a dual-objective programming model considering the minimum of uncertain risk decision-making and the maximum of guidance benefits.The lower level model is stochastic user equilibrium with local network considering queuing delay.The augmented Lagrange dual algorithm combined with method successive average algorithm is adopted to solve the lower model,and the non-dominated sorting genetic algorithm-II(NSGA-II)is adopted to solve the whole bi-level programming.Analysis result indicates that NSGA-II can effectively solve the bi-level programming model of VMS location under the restriction of capital budget,and get 6 Pareto solutions.Outcomes of this research can provide decision support for optimization and construction of VMS layout in uncertain road network.
intelligent transportation;VMS layout;bi-level programming;traffic guidance;non-dominated sorting genetic algorithm-II;augmented Lagrange dual algorithm
2014-04-03
2014-09-24錄用日期:2014-10-08
國家自然科學(xué)基金項目(61263025);公路工程省部共建教育部重點實驗室開放基金(kfj100107);汽車仿真與控制國家重點實驗室開放基金(20111116).
戢曉峰(1982-),男,副教授,博士.*通訊作者:yiluxinshi@sina.com
1009-6744(2014)06-0194-07
U491.1
A