高　瑞,　龍建成

(合肥工業(yè)大學(xué) 交通運(yùn)輸工程學(xué)院,安徽 合肥　230009)

?

基于可變車道優(yōu)化的交通網(wǎng)絡(luò)設(shè)計問題

高瑞,龍建成

(合肥工業(yè)大學(xué) 交通運(yùn)輸工程學(xué)院,安徽 合肥230009)

摘要:針對“潮汐交通”問題所引起的道路資源利用不合理的現(xiàn)象,文章提出了考慮可變車道優(yōu)化的交通網(wǎng)絡(luò)設(shè)計問題,旨在通過合理的路段拓展和車道配置方案來提高交通網(wǎng)絡(luò)的運(yùn)行效率;構(gòu)建了一個雙層規(guī)劃模型來描述提出的交通網(wǎng)絡(luò)設(shè)計問題,上層問題以系統(tǒng)總阻抗與總投資額之和最小為目標(biāo),制定最優(yōu)的道路拓展方案,并針對道路網(wǎng)絡(luò)早晚高峰不同的OD需求水平,分時段對車道進(jìn)行優(yōu)化配置,下層模型采用了用戶平衡(UE)配流模型來描述出行者在不同時段的路徑選擇行為;設(shè)計了人工蜂群算法來求解此雙層規(guī)劃模型。最后,采用數(shù)值算例驗(yàn)證了文中模型與算法的有效性。

關(guān)鍵詞:交通網(wǎng)絡(luò)設(shè)計;可變車道;雙層規(guī)劃;人工蜂群算法

0引言

近年來,隨著國民經(jīng)濟(jì)的發(fā)展和城市化進(jìn)程的不斷加快,城市道路交通擁堵已成為影響城市居民生活質(zhì)量的重要問題之一。要緩解城市交通擁堵問題,除了改、擴(kuò)建道路外,還需要對道路資源進(jìn)行優(yōu)化分配[1]。為了更充分地利用有限的道路資源,盡可能地降低交通擁擠,很多國家和城市采用單行線和可變車道的辦法來應(yīng)對,取得了一定效果[2]。

通常城市道路以雙向通行為主,2個車流方向的車道以中間為界,平均分配。然而,由于城市土地利用性質(zhì)不同,易導(dǎo)致某些路段在早、晚高峰出現(xiàn)交通流量不均衡的現(xiàn)象。如早高峰時,郊區(qū)到中心城區(qū)的交通流量較大,同時中心城區(qū)到郊區(qū)交通流量相對較小。為了充分利用現(xiàn)有道路資源,可以考慮在高峰時段將交通流量大的路段實(shí)施交通管制,將更多的道路資源分配給交通流量較大的方向[3]。這種方法通過優(yōu)化道路資源,可以緩解因“潮汐交通”而引起的道路交通擁堵。

一條雙向交通流量不平衡的道路如圖1所示,假設(shè)某一時段a到b方向的交通流量遠(yuǎn)遠(yuǎn)大于b到a方向的,則可以將b到a方向的1條或幾條車道分配給a到b方向。特別地,當(dāng)b到a方向車道全部分給a到b方向時,此時該路段變?yōu)閍到b的單行道。類似地,也可以將a到b方向的車道分配給b到a方向。

圖1　雙向道路示意圖

目前,只有少數(shù)發(fā)達(dá)地區(qū)的城市應(yīng)用了可變車道技術(shù)[4],而且僅限于部分擁擠嚴(yán)重的路段[5]。從效果上看,應(yīng)用可變車道的個別路段交通擁擠情況有所改善,但是由于缺乏對整個路網(wǎng)出行費(fèi)用合理的評估,可變車道的總體實(shí)施效果未知。

一般在城市中心區(qū),道路網(wǎng)絡(luò)已經(jīng)規(guī)劃成型,新建道路可能性極小,在原有道路基礎(chǔ)上進(jìn)行改、擴(kuò)建相對而言較容易,如消除中央綠化帶等方法。本文在離散網(wǎng)絡(luò)設(shè)計問題[6-7]研究的基礎(chǔ)上,針對“潮汐交通”引起的道路交通擁堵問題,不僅考慮對現(xiàn)有道路進(jìn)行拓展(增加車道數(shù)),還考慮在不同的交通時段制定最優(yōu)的可變車道實(shí)施方案。采用雙層規(guī)劃理論[8],以交通系統(tǒng)出行總費(fèi)用最小為目標(biāo),建立考慮可變車道設(shè)置的城市道路網(wǎng)絡(luò)設(shè)計的優(yōu)化模型[9-10]。其中,上層問題為交通管理規(guī)劃部門制定路段拓展方案,并優(yōu)化各時段的車道分配方案;下層問題描述出行者基于用戶平衡(UE)的路徑選擇行為。此外,可變車道的優(yōu)化還考慮了不同時段交通需求的差異性。依據(jù)上層問題都是離散決策變量的模型特征,設(shè)計了人工蜂群算法對提出的雙層規(guī)劃模型進(jìn)行求解。

1模型建立

(1)

其中,α和β為模型參數(shù),一般取α=0.15,β=4。

城市道路交通管理部門根據(jù)交通網(wǎng)絡(luò)中高峰時段的交通需求情況,制定車道調(diào)整方案,以減小整個交通網(wǎng)絡(luò)系統(tǒng)的阻抗,即系統(tǒng)總出行時間;出行者則根據(jù)道路車道設(shè)置情況調(diào)整個人出行,以期最小化個人出行成本。與大多數(shù)交通網(wǎng)絡(luò)設(shè)計問題的相關(guān)文獻(xiàn)[5]相同,本文假設(shè)出行者的路徑選擇遵循Wardrop用戶平衡(UE)準(zhǔn)則,采用UE配流模型來描述出行者的出行選擇行為。

1.1　上層問題

交通管理部門在制定道路拓展方案以及可變車道設(shè)置方案時,需要同時考慮道路的拓展費(fèi)用以及出行者的總出行費(fèi)用,使得交通系統(tǒng)綜合費(fèi)用最小。因此,考慮可變車道的道路網(wǎng)絡(luò)設(shè)計優(yōu)化問題的上層問題可以描述如下:

(2)

其中,Ga(ya)為道路拓寬的投資函數(shù);u和y分別為路段分配的車道數(shù)和拓展車道構(gòu)成的向量；x為路段流量構(gòu)成的向量；φ為投資費(fèi)用與出行時間的轉(zhuǎn)換系數(shù)。

車道數(shù)守恒約束為：

(3)

非負(fù)和整數(shù)約束分別為：

(4)

(5)

1.2　下層問題

本文采用UE配流模型來描述下層問題,即每個時段,網(wǎng)絡(luò)流量達(dá)到平衡狀態(tài)時,所有被利用的路徑具有相等而且最短的走行時間,而未被利用的路徑與其相比具有相等或更長的走行時間。對任意時段m,采用如下UE配流模型來得到平衡條件下的路段交通流量，即

(6)

任意OD間各條路徑上的交通量之和,應(yīng)等于OD交通需求總量,即

(7)

路段流量與路徑流量之間的關(guān)系描述為：

(8)

流量非負(fù)約束為：

(9)

2求解算法

雙層規(guī)劃模型屬于NP-Hard問題,傳統(tǒng)的下降算法通常需要計算上層目標(biāo)函數(shù)的導(dǎo)數(shù),對于大規(guī)模問題這是非常困難的[8]。此外,下降算法往往只能得到局部最優(yōu)解。智能優(yōu)化算法是求解雙層規(guī)劃的有效方法之一[9]。

本文依據(jù)上層模型為離散決策變量的特征,設(shè)計了人工蜂群算法求解提出的雙層規(guī)劃模型。相比于傳統(tǒng)遺傳算法,人工蜂群算法具有非常好的局部搜索能力[11]。

人工蜂群算法[11-14]是模仿蜜蜂行為的一種優(yōu)化方法，它通過對解集進(jìn)行隨機(jī)而有目標(biāo)的操作尋求最優(yōu)解。

2.1　解的編碼和初始解的生成

圖2　解的編碼示意圖

2.2　鄰域操作

圖3　點(diǎn)變異鄰域操作示意圖

2.3　適應(yīng)度評價

2.4　食物源選擇

常用的食物源選擇方法主要有輪盤賭選擇法和錦標(biāo)賽選擇法[14]。本文選擇輪盤賭選擇法對食物源進(jìn)行選擇。

2.5　求解步驟

應(yīng)用蜂群算法求解本文模型的步驟如下:

(1) 初始化。隨機(jī)生成n個初始解{xi}(i=1,2,3，…,n),置迭代次數(shù)v=0和鄰域搜索計數(shù)li=0(i=1,2,3,…,n);設(shè)置算法參數(shù)limit和MaxIterations。

(5) 收斂判斷。如果v=MaxIterations,算法結(jié)束;否則置v=v+1,返回步驟(2)。

3數(shù)值算例

本文采用圖4所示的算例網(wǎng)絡(luò)來驗(yàn)證所提出的模型與算法的有效性。該網(wǎng)絡(luò)由9個節(jié)點(diǎn)、24條路段,72個OD對構(gòu)成。算例網(wǎng)絡(luò)路段參數(shù)見表1所列。早高峰時段的OD需求矩陣見表2所列。晚高峰時段的OD需求矩陣為早高峰OD需求矩陣的轉(zhuǎn)置。

圖4　算例網(wǎng)絡(luò)示意圖

表1　算例網(wǎng)絡(luò)路段參數(shù)

表2　早高峰OD需求矩陣

路網(wǎng)未優(yōu)化前，對早、晚高峰OD需求矩陣采用用戶平衡(UE)配流方法進(jìn)行流量分配，得到早、晚高峰系統(tǒng)總阻抗之和為2.45 h。運(yùn)用本文方法，根據(jù)早、晚高峰OD需求矩陣對道路網(wǎng)絡(luò)進(jìn)行優(yōu)化，得出車道優(yōu)化配置方案。優(yōu)化后，早晚高峰系統(tǒng)總阻抗之和降為2.28 h，比優(yōu)化前降低了6.94%。其中，出行者總的出行成本為2.25 h，投資總額轉(zhuǎn)化為出行費(fèi)用部分為0.03 h?？梢?，提出的可變車道網(wǎng)絡(luò)設(shè)計優(yōu)化方案可以有效地降低系統(tǒng)總阻抗，實(shí)現(xiàn)現(xiàn)有資源和資金的合理利用。

表3　網(wǎng)絡(luò)設(shè)計和可變車道優(yōu)化結(jié)果

在人工蜂群算法和遺傳算法的求解過程中,計算時間主要消耗在求解下層UE配流問題的求解上。因此,本文以下層UE配流問題的求解次數(shù)來評價不同算法的求解效率。

人工蜂群算法和遺傳算法[16]都設(shè)置初始解的規(guī)模為10,UE配流次數(shù)為1 500次。遺傳算法中交叉概率pm=0.8,變異概率pc=0.1。2種算法交通分配次數(shù)與目標(biāo)函數(shù)值的關(guān)系如圖5所示。由圖5可知,人工蜂群算法計算到1 000次時已經(jīng)得到最優(yōu)目標(biāo)函數(shù)值;而遺傳算法計算1 400次才得出最優(yōu)目標(biāo)函數(shù)值。結(jié)果表明,在相同的計算時間內(nèi),人工蜂群算法得出的目標(biāo)函數(shù)最優(yōu)值要優(yōu)于遺傳算法的結(jié)果,即人工蜂群算法的求解效率優(yōu)于遺傳算法。

圖5　用戶平衡配流次數(shù)與最優(yōu)目標(biāo)函數(shù)值關(guān)系

4結(jié)束語

本文采用了雙層規(guī)劃模型來描述城市道路網(wǎng)絡(luò)高峰時路段雙向流量不平衡的網(wǎng)絡(luò)設(shè)計問題,并考慮了可變車道的優(yōu)化配置。其中,下層問題描述為一個多時段的用戶平衡配流模型,上層問題描述為一個以系統(tǒng)總阻抗與總投資額之和最小為目標(biāo)的整數(shù)規(guī)劃問題。提出了人工蜂群算法來求解雙層規(guī)劃模型,得到最優(yōu)的道路拓展方案和不同時段可變車道的配置方案。數(shù)值結(jié)果表明,本文提出的方法能有效地提高道路網(wǎng)絡(luò)的利用率,降低道路交通擁擠。

本文提出的模型與算法為城市道路的建設(shè)和可變車道的調(diào)整提供了優(yōu)化方案,并對擬提出的優(yōu)化方案做出合理評價,最終實(shí)現(xiàn)交通規(guī)劃與管理的統(tǒng)籌優(yōu)化。本文的研究沒有考慮可變車道設(shè)置對交叉口交通組織的影響,引入動態(tài)交通分配模型可以潛在地解決該問題,這將是進(jìn)一步研究的方向。

[參考文獻(xiàn)]

[1]張好智, 高自友.可變車道的道路交通網(wǎng)絡(luò)設(shè)計優(yōu)化方法[J].中國管理科學(xué),2007,15(2):86-91.

[2]李麗麗,曲昭偉.可變車道的控制方法[J].吉林大學(xué)學(xué)報:工學(xué)版,2009,39(Z1):98-103.

[3]孫剛,王豐元.可變車道技術(shù)對提高交通高峰時段交通流量的研究[J].科技資訊,2006(25):176-177.

[4]崔妍,劉東.北京市朝陽路可變車道交通組織研究[J].道路交通與安全,2006,6(9):21-24.

[5]陳堅(jiān),霍婭敏.典型潮汐車流路段可變車道設(shè)置方案研究[J].重慶交通大學(xué)學(xué)報:自然科學(xué)版,2008,27(6):1127-1130.

[6]Gao Z Y,Wu J J,Sun H J.Solution algorithm for the bi-level discrete network design problem[J].Transportation Research Part B:Methodological,2005,39(6):479-495.

[7]Miandoabchi E,Daneshzand F,Szeto W Y,et al.Multi-objective discrete urban road network design[J].Computers and Operations Research,2013,40(10):2429-2449.

[8]高自友,宋一凡.城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計理論與方法[M].北京:中國鐵道出版社,2000:89-91.

[9]高自友,張好智,孫會君.城市交通網(wǎng)絡(luò)設(shè)計問題中雙層規(guī)劃模型、方法及應(yīng)用[J].交通運(yùn)輸系統(tǒng)工程與信息,2004,4(1):35-44.

[10]Yang H,Bell M G H.Models and algorithms for road network design:a review and some new developments[J].Transport Reviews,1998,18(3):257-278.

[11]Karaboga D.An idea based on honey bee swarm for numerical optimization,Technical Report-TR06[R].Erciyes University,Engineering Faculty,Computer Engineering Department,2005.

[12]Singh A.An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem[J].Applied Soft Computing,2009,9(2):625-631.

[13]Szeto W Y,Jiang Y.Hybrid artificial bee colony algorithm for transit network design[J].Transportation Research Record Journal of the Transportation Research Board,2012,2284:47-56.

[14]Long J C,Szeto W Y,Huang H J.A bi-objective turning restriction design problem in urban road networks [J].European Journal of Operational Research,2014,237(2):426-439.

[15]Sheffi Y.Urban transportation networks:equilibrium analysis with mathematical programming methods[M].New Jersey:Prentice Hall,1985:111-132.

[16]周和平.基于遺傳算法的公路網(wǎng)絡(luò)設(shè)計的雙層優(yōu)化模型[J].同濟(jì)大學(xué)學(xué)報:自然科學(xué)版,2005,33(7):920-925.

(責(zé)任編輯胡亞敏)

王保華(1972-),男,河南南陽人,博士，湖北汽車工業(yè)學(xué)院教授,碩士生導(dǎo)師.

A transportation network design problem with optimization of variable lanes

GAO Rui,LONG Jian-cheng

(School of Transportation Engineering, Hefei University of Technology, Hefei 230009, China)

Abstract:Unreasonable utilization of road resources can be arisen due to tidal traffic. To overcome this problem, a transportation network design problem(NDP) with consideration of optimization of variable lanes is proposed. The proposed NDP aims to improve traffic efficiency by designing reasonable road network and lane allocation. A bi-level programming model is developed to formulate the proposed NDP. The upper level problem aims to minimize the sum of the total system travel cost and the total investment by optimizing road expanding scheme. With consideration of the different OD demand levels in the morning and evening peak hours, the lane allocation schemes in different traffic demand periods are also optimized. The lower level problem is formulated as a user equilibrium(UE) traffic assignment model to describe travelers’ route choice behavior during different traffic demand periods. An artificial bee colony(ABC) algorithm is introduced to solve the proposed bi-level model. Finally, a numerical example is developed to illustrate the effectiveness of the proposed model and algorithm.

Key words:transportation network design; variable lane; bi-level programming; artificial bee colony(ABC) algorithm

doi:10.3969/j.issn.1003-5060.2015.11.003

作者簡介：鄧召文(1979-),男,山東安丘人,湖北汽車工業(yè)學(xué)院講師;

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(51375151)；湖北省自然科學(xué)基金重點(diǎn)資助項(xiàng)目(2013CFA134)和湖北省重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(ZDK1201504)

收稿日期：2014-10-06；修回日期：2015-03-04

中圖分類號:U121

文獻(xiàn)標(biāo)識碼：A

文章編號：1003-5060(2015)11-1446-05