諸 云 王建宇 高寧波 楊 瑩

(南京理工大學自動化學院, 南京 210094)

基于擁堵辨識的城市路網(wǎng)優(yōu)化模型

諸 云 王建宇 高寧波 楊 瑩

(南京理工大學自動化學院, 南京 210094)

為了改善道路交通擁堵狀況,在分析城市道路網(wǎng)絡交通擁堵博弈關(guān)系的基礎上,建立了以交通擁堵程度為下層決策目標、經(jīng)濟費用為上層決策目標的城市路網(wǎng)優(yōu)化雙層規(guī)劃模型.上層模型以管理者對路網(wǎng)運營成本投入最優(yōu)為目標,下層模型力求路網(wǎng)的出行效率最高,針對該模型提出遺傳算法求解流程.以南京市某區(qū)域道路網(wǎng)絡為例進行分析研究,結(jié)果表明:優(yōu)化后的路網(wǎng)效能優(yōu)于原始路網(wǎng), 路網(wǎng)運行速度、服務水平均有提升;維護費用及延誤均下降.雙層規(guī)劃模型主要針對路網(wǎng)中道路等級低、飽和度高的路段進行改造升級,在一定投入費用范圍內(nèi)實現(xiàn)路網(wǎng)交通擁堵與投入費用的最優(yōu)平衡關(guān)系,能夠為路網(wǎng)優(yōu)化決策提供參考.

交通擁堵;路網(wǎng)優(yōu)化;雙層規(guī)劃;遺傳算法

近年來,國內(nèi)城市機動車保有量增勢迅猛,交通資源和交通需求在時間和空間上的矛盾日益突出,交通擁堵已經(jīng)成為各大中城市亟待解決的問題.從已有成果來看,交通擁堵研究主要集中在城市交通擁堵管理政策、城市道路網(wǎng)絡出行路徑優(yōu)化和城市道路網(wǎng)絡優(yōu)化等方面.陸化普[1]分析了城市交通擁堵形成機理,歸納總結(jié)了交通擁堵的對策體系.曾鸚等[2]從博弈論的角度定義了擁堵成本的概念,證明了擁堵收費的合理性.而發(fā)達國家和地區(qū)所采取的系列治理方案主要涉及到行政限制性政策、擁堵收費性政策和外延支撐性政策[3].徐麗麗等[4]利用路徑誘導信息建立了交通出行選擇的雙層規(guī)劃模型,得出不同路徑誘導信息對出行者影響的范圍.宋留勇等[5]通過分析路段出行時間的波動特性,建立了基于時間可靠度的交通路網(wǎng)出行路徑的簡化模型.Friesz等[6]梳理了非傳統(tǒng)方程在解決城市道路動靜態(tài)網(wǎng)絡優(yōu)化中的研究成果.Karoonsoontawong等[7]建立了基于通行能力的一般雙層規(guī)劃的城市網(wǎng)絡優(yōu)化模型.Mathew等[8]提出了利用雙層規(guī)劃模型優(yōu)化鄉(xiāng)村道路網(wǎng)絡布局.Gao等[9]提出了基于環(huán)境目標的城市網(wǎng)絡優(yōu)化雙層規(guī)劃模型,設計了城市網(wǎng)絡雙層規(guī)劃優(yōu)化算法,總結(jié)了城市交通網(wǎng)絡設計問題中雙層規(guī)劃模型及其運用.

綜上可知,近年來城市交通擁堵在管理政策、對策等方面取得了豐富的研究成果.但是國內(nèi)采用的擁堵收費、常發(fā)擁堵路段改造等措施都只考慮交通擁堵的表象,缺乏基于產(chǎn)業(yè)空間布局、城市管理以及區(qū)域協(xié)調(diào)發(fā)展等方面的綜合考察,致使治堵對策分析存在局限性和片面性.本文從城市資源和擁堵治理的博弈關(guān)系出發(fā),通過對城市交通擁堵的辨識研究,將城市交通擁堵問題分為上層管理者對擁堵治理的投入約束和下層出行者對路網(wǎng)出行效率訴求2個層面,實現(xiàn)治理投入成本與城市擁堵狀態(tài)的最優(yōu)平衡目標.

1 城市路網(wǎng)交通擁堵辨識的博弈機理

出行交通量集中于某條道路并超過道路容量時,就會造成道路交通擁堵.更為嚴重的是,城市路網(wǎng)銜接緊密,局部擁堵易引發(fā)路網(wǎng)交通癱瘓危機.交通擁堵問題屬于復雜的系統(tǒng)工程問題,在對交通擁堵進行準確辨識的前提下,交通擁堵博弈分析有助于明確擁堵影響邊界,為交通擁堵的治理提供決策依據(jù).

1.1 交通擁堵博弈關(guān)系

不同的交通流量與路網(wǎng)容量的對比關(guān)系產(chǎn)生了2種不同的交通運行狀態(tài),如圖1所示.交通擁堵對城市路網(wǎng)的影響主要集中在2個方面:① 降低路網(wǎng)的機動性能;② 增加路網(wǎng)的基礎費用.為保證交通暢通應從基礎設施投入和管理規(guī)劃2方面考慮.

路網(wǎng)建設后期投入包括基礎維護以及優(yōu)化投入.交通擁堵導致基礎維護費用增加,而基礎維護費用的減少又說明交通趨于順暢;為了保證交通順暢需要增加優(yōu)化投入,交通擁堵又說明優(yōu)化投入不足.因此,如何在城市道路網(wǎng)絡建設后期投入與交通運行狀態(tài)之間取得最優(yōu)平衡,屬于典型的博弈問題.

圖1 城市道路網(wǎng)絡交通擁堵博弈關(guān)系

1.2 擁堵辨識的指標體系

從空間分布來看,城市交通擁堵可劃分為點、線、面3個相互影響的層面進行辨識.因此,采用出行速度、平均延誤以及擁堵指數(shù)分別作為路段、交叉口以及路網(wǎng)的交通擁堵判別指標,并且定義路網(wǎng)維護費用、改造費用以及附加費用作為交通擁堵的經(jīng)濟評價指標,各個指標的計算過程[10]如下.

1) 平均出行速度的函數(shù)關(guān)系式為

(1)

式中,v平均出行速度;vab為路網(wǎng)第a條路段第b輛車的通行速度;N為路段總數(shù);M為每條路段的車輛通行總數(shù).

2) 平均出行延誤的函數(shù)關(guān)系式為

(2)

式中,Δt為平均出行延誤時間;ta為路網(wǎng)每條包含交叉口路段的期望出行時間,即路段交叉口耗時為0;tab為第a條路段第b輛車的實際出行時間.

3) 路網(wǎng)擁堵指數(shù)的函數(shù)關(guān)系式為

(3)

4) 路網(wǎng)維護費用的函數(shù)關(guān)系式為

(4)

5) 擁堵附加費用的函數(shù)關(guān)系式為

(5)

(6)

6) 道路改造費用的函數(shù)關(guān)系式為

(7)

f(lij,di,wij)=lijdiwij

(8)

式中,e為路網(wǎng)道路升級費用,取值為道路面積和單位面積道路升級費用的復合函數(shù)f(lij,di,wij);di為道路從支路到次干路、次干路到主干路、主干路到快速路3種升級類別的道路單位長度升級費用;pi為第i等級道路中需要升級的路段數(shù)量;lij為第i等級道路中第j條路段需要升級的長度.

2 城市路網(wǎng)交通擁堵的優(yōu)化模型

城市交通擁堵路網(wǎng)優(yōu)化雙層規(guī)劃模型的下層決策變量是交通擁堵狀態(tài),上層決策變量是交通流量,通過對該模型的求解得到城市道路網(wǎng)絡維護成本費用和城市交通擁堵狀態(tài)之間的最優(yōu)平衡關(guān)系.

2.1 雙層規(guī)劃模型

城市交通擁堵路網(wǎng)優(yōu)化的數(shù)學模型中,上層目標函數(shù)F(Vij)為整個路網(wǎng)的運行成本費用以及道路升級費用之和,決策變量為路網(wǎng)上各個路段的交通流量Vij.下層目標函數(shù)G(ti)以城市道路網(wǎng)擁堵程度為目標,決策變量為路網(wǎng)上每個路段的出行耗時ti.Vij與ti互相作用.

1) 上層規(guī)劃模型

minF(Vij)=q0+q+e=

(9)

2) 下層規(guī)劃模型

(10)

2.2 優(yōu)化模型求解

雙層規(guī)劃模型屬于多目標約束函數(shù)模型,遺傳算法對非線性問題具有強的空間搜索能力,被廣泛運用于多目標規(guī)劃問題的求解.因此,采用遺傳算法求解雙層規(guī)劃[11],具體過程如下.

1) 遺傳算子設計

① 解空間數(shù)值化.采用0-1關(guān)聯(lián)矩陣(0為端點間有路段,1為端點間無路段)表示路網(wǎng)的空間結(jié)構(gòu),采用0-4效用矩陣表示路網(wǎng)屬性,其中,0為端點間無路段;1為支路;2為次干路;3為主干路;4為快速路.

② 適應度函數(shù)選擇.利用遺傳算法尋優(yōu)的過程中,需要以某一函數(shù)作為優(yōu)化目標和搜索方向.在城市道路網(wǎng)絡交通擁堵雙層規(guī)劃模型中可分別采用式(9)和(10)作為上、下層遺傳算法的目標函數(shù).

③ 交叉和變異方法.交叉運算是遺傳算法區(qū)別于其他算法的重要特征,本文采用單點交叉算子作為交叉方法;變異操作是提高全局搜索能力的有效步驟,本文采用的變異策略是選取2個任意基因位,然后將基因交換的方法.

④ 確定其他相關(guān)參數(shù).遺傳算法中涉及的其他參數(shù)還包括群體規(guī)模Ns、交叉概率Pc(經(jīng)驗取值范圍為0.40～0.99)、變異概率Pm(經(jīng)驗取值范圍為0.001～0.100)等,這些參數(shù)均可通過經(jīng)驗取值方法確定.

2) 規(guī)劃模型空間尋優(yōu)

① 上層規(guī)劃初始化和編碼.在上層規(guī)劃的界限約束上隨機生成N0個初始路網(wǎng)(N0≥1),設定上層最優(yōu)循環(huán)最大迭代次數(shù)N1,將路網(wǎng)轉(zhuǎn)換成為數(shù)值化矩陣.

② 路網(wǎng)交通運行參數(shù)仿真.將上層規(guī)劃中釋放的可行路網(wǎng)進行仿真,得到包括路網(wǎng)交通流量、路段平均運行速度等路網(wǎng)交通參數(shù).

③ 下層規(guī)劃函數(shù)尋優(yōu)計算.利用步驟②的參數(shù)計算路網(wǎng)下層規(guī)劃的目標函數(shù),并進行適應度評價,根據(jù)評價排序結(jié)果從高到低進行選擇、交叉、變異操作,得到最優(yōu)的路網(wǎng)結(jié)構(gòu),并返回到上層規(guī)劃模型中.

④ 上層規(guī)劃解空間更新.對上層規(guī)劃的解空間根據(jù)目標函數(shù)進行適應度評價,排序后剔除適應度值低的解，保留適應度高的解;對解空間選擇、交叉、變異,將變異后的種群作為新一代種群,重復步驟②.

⑤ 終止運算與條件.如果當前上層規(guī)劃外循環(huán)迭代次數(shù)s達到最大迭代次數(shù)N1，或者當上層規(guī)劃的解空間無法進行更新,則停止,將當前的路網(wǎng)及其交通流參數(shù)作為雙層規(guī)劃的最優(yōu)解，記錄并輸出，見圖2.

圖2 基于遺傳算法的雙層規(guī)劃求解流程

3 仿真分析

以南京市某一區(qū)域路網(wǎng)為例,分析上述模型的可行性.該路網(wǎng)外圍由13條快速路組成,內(nèi)部由10條主干路以及8條次干道組成,路網(wǎng)結(jié)構(gòu)如圖3(a)所示.

(a) 優(yōu)化前

(b) 優(yōu)化后

3.1 參數(shù)界定

為對模型進行求解,需要進一步確定各參數(shù)的設定值.其中,路網(wǎng)中不同等級道路的維護費用和升級費用數(shù)據(jù)見文獻[12],課題組對該路網(wǎng)的路段等級、道路長度、道路交通流量和道路通行能力等進行了為期1周的調(diào)查,并根據(jù)估算得到不同等級道路的最大通行能力,遺傳算法中選擇概率和變異概率分別設定為0.80和0.05,終止迭代數(shù)設置為100,選擇模式和交叉模式分別為輪盤賭方式和單點交叉方式,具體見表1.

表1 南京市某道路網(wǎng)絡參數(shù)信息

3.2 模型求解

利用Matlab(R2012)對建立的雙層規(guī)劃模型進行編程求解[13],將路網(wǎng)中31個路段設置為因變量,每個變量包含道路長度、道路等級、交通流量、平均行程車速4個變量,經(jīng)過反復調(diào)試,得到數(shù)值仿真結(jié)果.

模型求解的演化過程可分為3個階段:① 從第0代到第20代,種群變異速度較快,適應度值下降速度快,空間尋優(yōu)效果明顯;② 從第20代到第50代,種群變異速度開始降低,適應度值開始收斂;③ 從第20代到第100代,適應度值收斂在3.73×105,得到路網(wǎng)的最優(yōu)解向量、優(yōu)化后路網(wǎng)空間結(jié)構(gòu),如圖3(b)所示.

通過對比優(yōu)化前后的路網(wǎng)可知,優(yōu)化路網(wǎng)在原始路網(wǎng)基礎上將路段14、路段15以及路段18等主干道升級為快速路,路段23由次干路升級為主干路,路段27和路段28由支路分別升級為次干路和主干路,總升級費用為442.86萬元.由表2對比發(fā)現(xiàn),所有升級的道路中最大飽和度達到0.990,最小飽和度為0.769,平均路段飽和度為0.892,說明升級的路段均處于交通較為擁堵的狀態(tài),選擇對這些道路升級,從一定程度上說明模型優(yōu)化的可靠性.

表2 城市道路網(wǎng)絡優(yōu)化變動情況

3.3 對比分析

為檢驗城市道路網(wǎng)絡交通擁堵雙層規(guī)劃模型(式(3)和(4))的有效性,將已優(yōu)化路網(wǎng)和原路網(wǎng)在VISSIM中建立模型進行仿真,采用節(jié)點控制和分散采集的模式獲取優(yōu)化前后路網(wǎng)各路段在仿真過程中的平均出行速度、平行出行時間延誤以及擁堵狀態(tài)等交通參數(shù),結(jié)果如表3所示.

表3 基于VISSIM的南京市某路網(wǎng)優(yōu)化前后部分仿真結(jié)果對比

3.4 路段服務水平分析

路網(wǎng)中優(yōu)化后的路段服務水平與原始路網(wǎng)中路段相比,主要有如下特點:

① 運行速度增加.優(yōu)化后路段的平均出行速度達到[30 km/h,55 km/h]區(qū)間,原始路網(wǎng)中未優(yōu)化路段的平均出行速度位于[10 km/h,25 km/h]區(qū)間,提升道路等級后,相應道路的運行速度提升明顯.

② 延誤時間降低.原始路網(wǎng)中未優(yōu)化的路段平均延誤位于[10 min/(h·pcu),20 min/(h·pcu)]區(qū)間,在優(yōu)化路網(wǎng)中,相應路段的出行延誤降低到[5 min/(h·pcu),10 min/(h·pcu)]區(qū)間.

④ 維護成本降低.優(yōu)化后路段的維護費用(基礎道路維護費用和擁堵附加費用之和)位于[5萬元,15萬元]區(qū)間,原始路網(wǎng)中對應未優(yōu)化的路段維護費用位于[15萬元,35萬元]區(qū)間.

⑤ 服務水平提高.優(yōu)化后路段的擁堵服務水平位于[二級,三級]區(qū)間,原始路網(wǎng)中相應路段的擁堵服務水平位于[四級,五級]區(qū)間.

3.5 路網(wǎng)綜合性能分析

為對優(yōu)化路網(wǎng)進行性能分析,采用經(jīng)濟性能指標和機動性能指標作為路網(wǎng)性能評價指標.優(yōu)化前后的路網(wǎng)性能指標對比如表4所示.

表4 優(yōu)化前后路網(wǎng)交通性能對比

4 結(jié)語

本文從城市道路網(wǎng)絡性能和投入費用2個方面分析了城市道路網(wǎng)絡交通擁堵博弈關(guān)系,運用平均出行速度、平均出行延誤、擁堵指數(shù)、道路維護費用等指標作為城市道路網(wǎng)絡交通擁堵的博弈指標.在此基礎上,建立了下層決策變量是交通擁堵狀態(tài)、上層決策變量是交通流量的城市道路網(wǎng)絡交通擁堵雙層規(guī)劃模型,提出了基于遺傳算法的求解流程.以課題組對南京市某區(qū)域路網(wǎng)的調(diào)查數(shù)據(jù)進行模型參數(shù)標定,然后在Matlab中對雙層規(guī)劃模型進行求解,優(yōu)化結(jié)果表明雙層規(guī)劃模型主要針對路網(wǎng)中道路等級低、飽和度高的路段進行改造升級.為分析優(yōu)化路網(wǎng)和原始路網(wǎng)之間的路網(wǎng)性能,在VISSIM中建立路網(wǎng)模型并進行了仿真分析,結(jié)果表明優(yōu)化路網(wǎng)在平均速度、出行延誤等方面均優(yōu)于原始路網(wǎng).

References)

[1]陸化普.城市交通擁堵機理分析與對策體系[J].綜合運輸,2014(3):10-19. Lu Huapu. Congestion mechanism analysis and countermeasures system of urban traffic [J].ComprehensiveTransportation, 2014(3):10-19. (in Chinese)

[2]曾鸚,李軍.合作博弈視角下城市道路交通擁堵收費研究[J]. 運籌與管理,2013,22(1):9-14.DOI:10.3969/j.issn.1007-3221.2013.01.002. Zeng Ying, Li Jun. Research about charge for traffic congestion of urban roads under perspective of cooperation. [J].OperationsResearchandManagementScience, 2013, 22(1):9-14. DOI:10.3969/j.issn.1007-3221.2013.01.002. (in Chinese) [3]趙蕾.城市交通擁堵治理:政策比較與借鑒[J].中國行政管理,2013,335(5):82-85. Zhao Lei. Management of urban traffic congestion: Countermeasures comparison and reference research[J].ChineseJournalofManagement, 2013,335(5): 82-85. (in Chinese)

[4]徐麗麗,邵春福.路徑信息誘導的雙層規(guī)劃模型[J].交通運輸工程學報,2007,7(5):15-21.DOI: 10.3321/j.issn:1671-1637.2007.05.020. Xu Lili, Shao Chunfu. Bi-level programming model of path information induction [J].JournalofTrafficandTransportationEngineering, 2007,7(5):15-21. DOI: 10.3321/j.issn:1671-1637.2007.05.020. (in Chinese)

[5]宋留勇, 王銳, 周永旺. 動態(tài)城市交通網(wǎng)絡優(yōu)化模型研究及算法設計[J]. 測繪科學, 2011, 36(1):134-136. Song Liuyong, Wang Rui, Zhou Yongwang. Network optimization model and algorithm design of urban traffic [J].ScienceofSurveringandMapping, 2011, 36(1):134-136. (in Chinese)

[6]Friesz T L, Shah S. An overview of nontraditional formulations of static and dynamic equilibrium network design[J].TransportationResearchPartB:Methodological, 2001, 35(1): 5-21. DOI:10.1016/s0191-2615(00)00002-3.

[7]Karoonsoontawong A, Waller S T. Integrated network capacity expansion and traffic signal optimization problem: Robust bi-level dynamic formulation [J].NetworksandSpatialEconomics, 2010, 10(4): 525-550.

[8]Mathew B S, Isaac K P. Optimisation of maintenance strategy for rural road network using genetic algorithm [J].InternationalJournalofPavementEngineering, 2014, 15(4): 352-360. DOI:10.1080/10298436.2013.806807.

[9]Gao Z, Wu J, Sun H. Solution algorithm for the bi-level discrete network design problem [J].TransportationResearchPartB:Methodological, 2005, 39(6): 479-495. DOI:10.1016/j.trb.2004.06.004.

[10]鄭淑鑒,楊敬鋒. 國內(nèi)外交通擁堵評價指標計算方法研究[J]. 公路與汽運, 2014,6(1): 57-61. DOI: 10.3969/j.issn.1671-2668.2014.01.016. Zheng Shujian, Yang Jingfeng. The research on traffic congestion evaluation index at home and abroad[J].Highway&AutomotiveApplications, 2014, 6(1): 57-61.DOI: 10.3969/j.issn.1671-2668.2014.01.016.(in Chinese)

[11]趙志剛, 王偉倩, 黃樹運. 基于改進粒子群的雙層規(guī)劃求解算法[J]. 計算機科學, 2013, 40(11a): 115-119. Zhao Zhigang, Wang Weiqian, Huang Shuyun. Bi-level programming algorithm based on improved particle swarm[J].ComputerScience, 2013, 40(11a): 115-119. (in Chinese)

[12]胡啟洲,葉茂,鄧衛(wèi).城市路網(wǎng)交通擁堵態(tài)勢監(jiān)控的測度理論方法[M].北京:科學出版社, 2013:8-23.

[13]張德豐.MATLAB/Simulink建模與仿真實例精講[M].北京:機械工業(yè)出版社, 2010:56-76.

Urban traffic congestion optimization model based on bi-level programming

Zhu Yun Wang Jianyu Gao Ningbo Yang Ying

(School of Automation, Nanjing University of Science and Technology, Nanjing 210094, China)

To improve the situation of road traffic congestion, based on the analysis of the game relationship of urban road network traffic congestion, the lower decision-making objectives for traffic congestion level were established, the economic costs take the upper decision-making objectives of the urban road network optimization as a bi-level programming model. The upper model aimed at the optimization of the cost in which operators invest for road network operation. The lower model optimized the travel efficiency of the road network.The genetic algorithm was proposed to solve the process. Taking a regional traffic network in Nanjing as an example, the results show that the optimized network performance is better than that of the original road network. Both the speed of the road network running and the service level are improved.Both maintenance costs and delays are reduced. The bi-level programming model is mainly used to reform and upgrade the road sections with the low level and the high saturation in the road network. In a certain cost range,realizing the optimal balance between traffic congestion and costs can provide a reference for road network optimization decisions.

traffic congestion; road network optimization; bi-level programming;genetic algorithm

10.3969/j.issn.1001-0505.2017.03.031

2016-09-03. 作者簡介: 諸云(1985—),女,博士生;王建宇(聯(lián)系人),男,博士，教授,博士生導師,jianyu_wang2000@163.com.

國家自然科學基金資助項目(51178157)、國家統(tǒng)計科研計劃資助項目(2012LY150)、中央高?；究蒲袠I(yè)務費專項資金資助項目(30916011338)、江蘇省普通高校專業(yè)學位研究生創(chuàng)新計劃資助項目(SJLX16_0154).

諸云，王建宇，高寧波，等.基于擁堵辨識的城市路網(wǎng)優(yōu)化模型[J].東南大學學報(自然科學版),2017,47(3):607-612.

10.3969/j.issn.1001-0505.2017.03.031.

U294

A

1001-0505(2017)03-0607-06