基于雙層規劃的交通疏散中車輛出發與交通控制綜合優化

高明霞

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

基于雙層規劃的交通疏散中車輛出發與交通控制綜合優化

高明霞

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

在有組織的區域性疏散中,從需求調節（即疏散車輛出發安排）和供給管理（即交通管控）兩方面對疏散交通流進行合理組織,是提高疏散效率的有效途徑。論文立足于疏散車輛出發組織與路網交通管控之間的雙層決策關系,建立雙層規劃模型對集結點疏散車輛的發車頻率、路線和交叉口控制參數進行綜合優化,其中上層模型通過優化信號交叉口的相位綠燈時間即綠信比以降低平均延誤,其決策影響到交叉口通行能力等供給特性；下層模型通過優化疏散車輛的分批出發時間與路線以壓縮疏散總時間,其決策影響到交叉口流量等需求特性。設計了基于遺產算法的求解步驟,給出了一個數值算例。將模型優化方案和只從交叉口控制參數出發的單方面優化模式所得結果進行了比較,結果表明只從調整綠燈時間著手不結合車輛的出發組織,很難有效降低延誤和壓縮疏散時間。

交通疏散；出發安排；交通控制；綜合優化；雙層規劃

1 引言

近年來,隨著各種災害性事件的不斷升級,對應急管理提出了更高的要求。疏散是應急管理的重要內容,由于災害的可預報性、事發地點的可預知性等各異,疏散管理的側重點也有所不同。對事發地點、疏散范圍相對明確的區域性疏散,國內外組織方式大體上可分為兩種,一種是政府發布消息由居民自行決定出發時間和疏散方式等的無組織出發式疏散,另外一種是在指定的集結點由相關部門統一安排的有組織出發式疏散。我國家庭小汽車保有率低,交通疏散主要依賴公交車、單位車等方式,更適合有組織出發的疏散方式。對有組織疏散而言,疏散期間產生的交通流在很大程度上是可“組織”的,如果能夠制定科學的疏散交通組織預案,干預疏散交通流在路網中的分布模式,使其向期望的良性方向發展,則能夠大大提高疏散效率。

疏散交通流在路網中的分布情況,主要受疏散需求和供給特征兩方面的影響,疏散交通組織也應從需求調節和供給管理兩方面著手。就需求調節而言,總需求調節的彈性很小,而通過調節動態需求,如合理安排集結點疏散車輛的分批次出發時間或發車頻率,可以避免交通流在短時間內突然加載到路網引發道路擁堵。在供給管理方面,道路網的幾何特征在短時間內不易改變,而施加在其上的交通管控措施更具操作彈性見效也較快,所以適時改變路網中的交通管控措施,如優化交叉口的信號配時方案,可以對疏散交通流起到良性的干預和引導作用,緩解交通擁堵。

以往關于這類問題的研究,從需求調節（即疏散車輛出發安排）和供給管理（即交通管控）兩個角度分別探討的較多,但是將兩者結合起來綜合考慮的很少。Campos[1］提出了一種k-最短路方法尋求最佳疏散路線。Satoko等[2］采用動態最快流模型,對分批次車隊的疏散路線和出發時間進行優化。Cova等[3］建立了一個基于車道的路口緊急疏導模型,通過人為干預車輛在路口的轉彎,減少沖突、縮短疏散時間。Zhang Hailin等[4］將大面積疏散過程劃分為步行至集結點和從集結點由交通工具疏散兩個階段,通過仿真對疏散車輛出發方案進行了比選。Wang Junwei等[5］研究了單源多匯情形下疏散道路的合理利用與修復問題。盧兆明等[6］建立了基于GIS和動態最快流模型的疏散管理系統框架,其中提出了綜合車流出發安排與途中引導進行疏散交通組織的思路,但未有深入的量化結果。宋永朝等[7］運用最小費用最大流理論研究了局域路網中的疏散交通分配。

本文立足于疏散需求調節（即出發安排）和供給管理（即交通管控）之間的雙層決策關系,建立雙層規劃模型對集結點疏散車輛的分批次出發時間、路線,以及路網中主要信號交叉口的控制參數進行綜合優化,其中上層模型以疏散期間信號交叉口的車均延誤（即平均每輛車的延誤）最小為目標,對信號交叉口的相位綠信比（即有效綠燈時間與信號周期之比）進行優化,下層模型以總疏散時間（包括車輛在集結點的等待時間和途中的走行時間）最小為目標,對集結點疏散車輛的分批次出發時間、路線進行優化。對給定的上層決策,下層模型是一個動態系統最優的出發時間與疏散路線綜合優化模型。設計了基于遺傳算法的求解步驟,將其應用于一個小規模疏散路網,結果表明了該方法的有效性。

2 問題描述及模型

2.1 建模基礎

由于疏散車輛出發安排和交叉口干預引導的主體及出發點不同,對疏散車輛的交通組織具有典型的雙層決策特征,可將其描述為雙層決策問題,其中決定交叉口管控方案的交管部門可看作上層決策者,而決定車輛出發時間及路線的組織方可看作下層決策者。上層決策者以充分發揮路網能力為目標,其決策直接影響著交叉口通行能力等供給特性,而下層決策者通常以縮短總疏散時間為目標,其決策決定著動態加載到路網的交通流及其空間分布等需求特性,上下層各自有其獨立的決策空間,目標達成又都受對方的影響。

基于這一特征,建立雙層規劃模型,對集結點疏散車輛的分批次出發時間、路線和途中主要信號交叉口的相位綠信比（或綠燈時間）進行優化。為簡便起見,對以下條件進行適當簡化：

（1）所有信號交叉口都采用定時信號控制,信號周期固定,擬通過調節各相位綠燈時間來縮短疏散期間車輛經過交叉口的平均延誤；

（2）各疏散集結點的總出行量已知,可根據集結點服務范圍內的人口數及疏散車輛類型等綜合確定,換算為標準當量小客車單位（pcu）；

（3）假定所有路段及交叉口的背景交通量為0,直接以路段、交叉口通行能力作為其疏散通行能力。區域性疏散不同于點對點式的救援疏散,其要求災害影響范圍內人群全部疏散,因此在疏散路網中,除了疏散初期存在部分背景交通流外,在疏散中后期主要包括自集結點產生的疏散交通流和調配空車產生的救援交通流,救援交通流與疏散交通流在占用同一道路時通常是相反方向且疏散期間的管制措施可以將兩者有效分流,所以忽略兩者影響；對疏散前期社會交通流的影響,可結合調查數據用路段通行能力等減去相應背景交通量,作為其疏散通行能力。

2.2 模型構造

將疏散路網抽象為有向網絡G=｛V,A｝,其中V為節點集合,表示交叉口、疏散源點和疏散終點, A為弧集和,表示相鄰節點之間的有向路段。設問題所在的時間段為[0,T］,并將[0,T］劃分為K個大小為Δ的時段。另外為表述方便,定義以下符號和變量,其中下層模型中涉及變量如下：

R,S：道路網中疏散源點和終點的集合；r,s：疏散源點和終點,r∈R,s∈S；a：疏散路網中的路段,a∈A；n：疏散路網中的交叉口,n∈V；prs：源點r與終點s之間路徑的集合；l：時段編號,表示車輛出發所在的時段,l=1,2,…,K；k：時段編號,表示車輛行駛在路網上的時刻所屬時段,k=1,2,…, K；Drs：r、s之間總的疏散需求（車數）；：時段l內由r出發去往s且沿路徑p走行的車輛數,p∈prs；F：的集合,?r,s,p,l；xak：第k個時段的初始時刻行使在路段a上的車輛數；uak,vak：時段k內進入（離開）路段a的車輛數；,：時段l內由r出發去往s且沿路徑p走行的車輛中,在時段k內進入（離開）路段a的車輛數；（F）：在F決定的交通狀態下,在時段l內由r出發去往s且沿路徑p走行的車輛花在路上的平均走行時間；A（n）,B（n）：以節點n為起點和終點的路段集合。：0-1變量,若時段l內由r出發去往s且沿路徑p走行的車輛在時段k內進入路段a,則取1,否則取0。

上層模型中涉及的變量和符號如下：

I—信號控制交叉口個數；Ji—交叉口i的信號相位數；Ei—交叉口i的進口引道總數；y=（：i=1,2,…I；i=1,…Ji）為決策向量,其中表示交叉口i中相位i的綠信比（即該相位有效綠燈時間與周期之比）；ci—交叉口i的信號周期長（sec）；Li—交叉口i一個信號周期內的總損失時間（s）；—交叉口i的最小綠燈時間（s）；di—疏散期間交叉口i的車均延誤（s）,即平均每輛車在該交叉口ii—0 -1變量,對于交叉口i,當進口道e在相位i的綠燈時間里允許通行時,δe經歷的延誤；qi-—疏散期間交叉口i的平均流率（pcu/s）,等于各進口道平均流率之和；—疏散期間交叉口i處進口道e的車均延誤（s）；—疏散期間交叉口i處進口道e的平均流率（pcu/s）,等于疏散期間經過該進口道的總車數除以疏散時間；—0 -1變量,對于交叉口i,當進口道e在相位i的綠燈時間里允許通行時,=1,否則=0—交叉口i處,允許進口道e通行的綠燈時間在信號周期中所占的比例交叉口i處進口道e的飽和流量（pcu/h）；：交叉口i處進口道e的最大通過流率即通行能力（pcu/s）,由飽和流率和允許其通行的綠燈時長決定。

在上述前提下,疏散期間路網中信號交叉口的相位綠信比與疏散車輛組織方案的綜合優化問題,可表示為以下雙層規劃模型：

式（1）為上層模型的目標函數,表示上層目標為疏散期間所有信號交叉口的車均延誤（即平均每輛車的延誤）最小化,決策變量為信號交叉口的相位綠信比,其中di,qi可結合下層優化結果通過的下面的式子推算：

式（2）和式（3）是對信號交叉口相位綠信比的一般性約束；式（4）-（12）為下層模型,其目標是使包括車輛在疏散源點等待時間和途中走行時間的總疏散時間最小化,決策變量為疏散源點車輛的分批次出發時間和走行路線,對給定的上層決策,下層模型是一個動態系統最優的疏散路線與出發時間綜合優化模型。對給定上層決策下,（4）-（11）所示下層模型的說明和求解,已在作者發表的其它論文中給出[9］,限于篇幅此處不再贅述。

2.3 模型的作用機制

模型可以對交叉口控制參數和疏散車輛的分批出發時間及路線同時進行優化,其作用機制如下：上層模型根據其目標確定決策變量y,即信號交叉口相位綠信比,該決策直接影響下層優化問題所依賴的路網條件,在此表現為各交叉口進口道的通行能力。對任意交叉口i,其進口道e的通行能力根據飽和流率模型由下式計算[8］：

下層模型在由上層決策決定的路網條件下,根據其目標確定決策變量F的取值,即各小時段內由疏散源點出發的車輛數及其路線,該決策直接影響和決定著疏散期間交通流在路網中的分布狀態,包括交叉口進口道不同時刻的流率（t）和整個疏散期間的平均流率,這些流率取值直接關系到交叉口延誤的大小,即上層目標的達成。下層決策的結果F通過流率反饋給上層,促使上層調整決策,改變y的取值。而y的改變造成了路網條件的變化,促使下層重新決策,這樣反復循環,直至達到一個平衡,平衡狀態下的解可認為是模型的最優解。

3 算法

3.1 算法步驟

上述雙層規劃模型中,下層模型本身是一個基于仿真的優化模型,而且上、下層決策變量之間的聯系是隱含在描述疏散車輛走行的加載仿真模塊中,無法給出其解析的表達,整個模型的解析性質較差。因此,采用遺傳算法進行求解,算法主要步驟如下：

步驟1：確定編碼方式、種群規模N、交叉概率pc和變異概率pm等參數；

步驟2：將式（1）所示的目標函數轉換為適應度函數；

步驟3：初始化種群,產生N個可行的初始個體,即N個可行的y；

步驟4：計算個體的適應度

步驟4.1：將個體（解向量）y的值代入式（15）,得到下層模型中關于交叉口通行能力的約束；

步驟4.2：基于上層決策對應的路網條件,采用基于仿真的啟發式算法求解下層模型；

步驟4.3：利用加載仿真模塊,將下層模型的解所對應的車流加載到路網,得到交叉口各進口道的動態車流量qei（t）,?i,e,t；

步驟4.4：根據式（1）、式（13）-（14））計算上層目標值H（y）；

步驟4.5：根據給定的適應度函數,計算個體適應度。

步驟5：根據適應度大小以一定的方式選擇或復制個體；

步驟6：按交叉概率進行交叉操作；

步驟7：按變異概率進行變異操作；

步驟8：判斷是否達到收斂條件,若已經達到則輸出搜索結果,否則返回步驟4。

3.2 具體環節的實現

上述步驟中,步驟4.2和步驟4.3的實現,即給定上層決策下下層模型的求解已在作者發表的其它論文中介紹[9］。其他主要環節的具體實現分別說明如下：

（1）編碼和解碼

問題的可能解本身是連續變化的實數,所以采用實數編碼,將解向量y直接表示為個體,解向量中的變量（yii）可看作是一個基因。這種方式下,求解過程不存在編碼和解碼操作,交叉、變異等遺傳操作和解的評估、選擇都是在同一個解空間中進行。

（2）設計適應度函數

此處的優化問題是個極小化問題,目標函數不能直接作為適應度函數,設計如下的適應度函數：

式中,Hmax為給定的足夠大正數。

（3）遺傳操作

此處采用輪盤賭的方式進行個體的選擇；按一定交叉概率選擇個體并分對,進行算術交叉；對以一定變異概率選中的個體y,采用單重均勻變異法進行變異,即按均勻分布隨機選擇個體中一個基因（變量）,并將它變異為其可行區間中的均勻隨機數。

4 算例

圖1所示為某城市局部疏散路網,其中節點1為疏散源點,節點9為該區域的疏散出口,其他節點代表交叉口,某些路段由于應急需要被規定為單向通行。

圖1 算例中的疏散路網

假定疏散期間交叉口5、6均實行定時信號控制,其他交叉口則為無控交叉口。交叉口5、6的基本信息如表1所示,其信號相位方案分別如圖2和圖3所示。疏散路網中各路段的基本信息如表2所示,路網中無控交叉口各進口道的通行能力如表3所示。

令種群規模N=30,交叉概率pc=0.6,變異概率pm=0.06,最大迭代次數為400。假設疏散車輛數D1-9=1500（pcu）,采用上述模型對交叉口綠信比方案和車流出發組織方案進行綜合優化,得綠信比方案及對應的延誤如表4所示,與之對應的車流出發組織方案如表5所示。

另外,不難得到不考慮和車流出發組織的協調,只從上層目標—車均延誤最小化出發,關于交叉口綠信比方案的優化結果。將下層模型的解固定,仍采用上面給出的遺傳算法求解上層模型,其中取消步驟4.2,其他步驟保持不變,即可得到不考慮下層決策,只從上層目標出發的最優綠信比方案。本例中分別將疏散組織方案固定為前面綜合優化過程中,編號為1至10的初始個體所對應的車流出發組織方案,依次按取消步驟4.2后的算法步驟求解上層模型,得到的優化結果如表6所示。

表1 信號控制交叉口的基本信息

表2 路段的基本信息

圖2 交叉口5疏散相位方案

圖3 交叉口6的疏散相位方案

表3 無控交叉口各進口道的通行能力

表4 基于雙層規劃的最優綠信比案及延誤

表5 基于雙層規劃的疏散車輛出發組織方案

從表4與表6中結果的對比情況可以看出,不結合疏散車輛的出發組織,只從上層目標出發單方面優化得到的綠信比方案,不但導致疏散時間明顯增加,交叉口延誤也沒有得到有效降低。因為實際疏散中,交叉口延誤不僅和綠信比有關,還取決于疏散期間通過交叉口的交通量。如果不結合疏散車輛的出發組織,不改變車流的出發模式,僅僅依靠綠信比的變化,很難有效降低延誤、壓縮疏散時間。

5 結語

區域交通疏散是應急管理的一項重要內容,科學合理的交通疏散預案對提高疏散效率具有重要作用。本文首先深入分析了疏散車輛出發組織和路網交通管控兩者之間的雙層決策關系,在此基礎上建立了雙層規劃模型,對信號交叉口控制參數和集結點車隊的分批次出發時間及路線進行綜合優化,并跟據模型特點設計了基于遺傳算法的求解步驟,最后通過一個算例說明了模型的應用,結果表明了該方法的有效性和較之單方面優化模式的優越性。

但是要真正服務于實際問題,還需要在大規模網絡中結合實際數據進行進一步的實證研究。另外,如何將這些模型和算法與GIS等技術有效融合,開發真正能為疏散決策者所用的實用軟件,也是下一步要研究的問題。

[1］Campos V B G,da Silva P A L,Netto P O B.Evacuation transportation planning：A method of identifying optimal independent routes[M］//Surcharov L J.Urban transport V：Urban transport and the environment for the 21st century.Southampton：WIT Press,2000：555-564.

[2］Satoko M,Kazuhisa M,Takashi T,et al.The Evacuation problem,dynamic network flows,and algorithms [C］.Proceedings of SICE Annual Conference,Fuku, Japan,August 4-6,2003.

[3］Cova T J,Johnson J P.A network flow model for lanebased evacuation routing[J］.Transportation Research Part A,2003,37（7）：579-604.

[4］Zhang Hailin,Liu Hao,Zhang Ke,et al.Modeling of evacuations to no-notice event by public transit system [C］.Proceedings of 13th International IEEE Annual Conference on Intelligent Transportation Systems,Madeira Island,Portugal,September 19-22,2010.

[5］Wang Junwei,Ip W H,Zhang Wenjun.An integrated road construction and resource planning approach to the evacuation of victims from single source to multiple destinations[J］.IEEE Transactions on Intelligent Transportation Systems,2010,11（2）：277-289.

[6］盧兆明,林鵬,黃河潮,基于GIS的都市應急疏散系統[J］.中國公共安全（學術版）,2005,1（2）：35-40.

[7］宋永朝,潘曉東,楊軫,等.災害事件下局域路網應急疏散交通分配模型[J］.公路交通科技,2010,27（5）：88-92.

[8］王殿海.交通流理論[M］.北京：人民交通出版社,2002.

[9］高明霞,賀國光.動態系統最優的疏散路線與出發時間綜合優化模型[J］.系統工程,2009,27（6）：73-77.

Optimization of Vehicle Departure Arrangement and Traffic Control in Traffic Evacuation Based on Bi-level Programming

GAO Ming-xia
（School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China）

It is an efficient method to manage traffic flow genarated in an organized regional evacuation from two aspects：demand regulation（means to regulate the departure mode of evacuation vehicles）and supply management（means to control traffic flow in road network）.Based on the bi-level decision relationship be-tween departure arrangement and traffic control in road network,a bi-level programming model is presented to optimize the departure plan and control parameters of intersections simultaneously.The green ratio of signalized intersections appears as the decision variable of upper level to minimize the average delay, which will influence some supply characteristics such as intersection capacity；the departure schedule and routes of evacuation vehicles appear as the decision variable of lower level to minimize the total evacuation time,which will affect some demand characteristics such as flow through intersections.A genetic-based algorithm is presented,and a numerical example is given.By comparing the optimization results of the bilevel model and the results got from the optimization mode that only consider the control parametar,it is shown that the bi-level model really holds advantage in decreasing delay and evacation time.

traffic evacuation；departure arrangement；traffic control；integrated optimization；bi-level programming

U491；O157.6

A

1003-207（2014）12-0065-07

2012-03-15；

2013-05-15

教育部博士點基金資助項目（20116204120005）；教育部人文社科基金項目（12XJCZH002）；蘭州交通大學青年基金

高明霞（1979-）,女（漢族）,寧夏中衛人,蘭州交通大學交通運輸學院副教授,博士,研究方向：交通系統工程.