基于粒子群算法的快速路投資優(yōu)化方法

何勝學(xué),　劉　潔,　張皓東

(上海理工大學(xué) 管理學(xué)院,上?！?00093)

?

基于粒子群算法的快速路投資優(yōu)化方法

何勝學(xué),劉潔,張皓東

(上海理工大學(xué) 管理學(xué)院,上海200093)

從投資影響交通網(wǎng)絡(luò)容量出發(fā),提出一種新的以元胞傳輸模型CTM(cell transit model)理論為基礎(chǔ)的快速路投資優(yōu)化方法.首先,對元胞傳輸模型進行改進以實現(xiàn)局部匝道控制;其次,利用粒子群智能優(yōu)化方法,構(gòu)造了元胞通行能力優(yōu)化問題的粒子群表達方法;并定義了總行車里程(TDT)和系統(tǒng)總延誤(TD)作為衡量快速路系統(tǒng)的性能指標.計算結(jié)果顯示投資前TDT為12 004 874 m,TD為3 582 405.1 s,投資后TDT為13 128 283 m,TD為3 537 468.7 s,總行車里程投資后較投資前增加了1 123 409 m,總延誤投資后較投資前減少了44 936.4 s.結(jié)果分析表明,新優(yōu)化方法使總行車里程顯著增長,使系統(tǒng)總延誤顯著降低,提高了整個路網(wǎng)性能.該投資優(yōu)化方法可以較好地解決快速路投資優(yōu)化問題.

元胞傳輸模型; 投資優(yōu)化; 匝道控制; 粒子群算法; 線性規(guī)劃

快速路是指城市中有較高車速為長距離交通服務(wù)的車道,是城市交通網(wǎng)絡(luò)的骨架,承載著絕大部分的交通出行,其通行效率直接決定著所在交通網(wǎng)絡(luò)的性能.隨著汽車數(shù)量與日俱增,大多數(shù)城市越來越重視快速路交通問題,不斷加大交通設(shè)施投資力度,這也使資金投資問題和投資分配問題日益突出[1].為保證資金投資科學(xué)、高效的分配,對快速路進行投資優(yōu)化勢在必行.

目前,快速路改造投資大都采用傳統(tǒng)的“四階段”法預(yù)測快速路的交通需求,其后探討快速路的通行能力,根據(jù)對交通需求與通行能力的分析,確定快速路投資改造的規(guī)模.然而這種投資改造方法并沒有對快速路系統(tǒng)進行投資優(yōu)化,并且快速路的改造投資具有造價高、系統(tǒng)強、風(fēng)險大、影響遠的特點,對其改造修建應(yīng)十分慎重.而快速路投資優(yōu)化作為快速路投資決策的方法之一,不僅可以緩解快速路交通擁堵,而且可以為交通建設(shè)規(guī)劃決策部門和有關(guān)人員提供科學(xué)、系統(tǒng)的決策方案,最大化發(fā)揮有限資金效益,規(guī)避投資風(fēng)險.

一般而言,快速路改造投資優(yōu)化問題可以歸于定量的連續(xù)交通網(wǎng)絡(luò)設(shè)計問題,即在有限的資金投入條件下,通過改善現(xiàn)有某些路段使整個網(wǎng)絡(luò)達到某種性能最優(yōu)的目的,其路段通行能力的增加是連續(xù)漸進的.而目前專門針對快速路投資優(yōu)化的研究很少,現(xiàn)階段國內(nèi)外關(guān)于快速路的研究主要集中在城市道路交通網(wǎng)絡(luò)設(shè)計問題的研究,如新建道路[2]、單向道路和雙向道路的選擇[3],路段能力的改進[4],信號配時和道路收費[5].關(guān)于快速路的優(yōu)化研究,大都停留在不考慮投資費用時匝道控制優(yōu)化[6-9],很少同時考慮匝道控制策略和投資分配優(yōu)化.于是,隨著投資額增長,研究不同匝道控制策略下快速路投資優(yōu)化特點便成為一個很有意義的問題.

傳統(tǒng)的連續(xù)交通網(wǎng)絡(luò)設(shè)計問題通常采用雙層規(guī)劃模型進行描述,上層問題的目標函數(shù)是整個網(wǎng)絡(luò)的總阻抗和總投資額,下層問題則是用戶平衡配流模型[10].該模型雖可用于快速路投資優(yōu)化,但求解繁瑣,且未曾考慮匝道控制策略.1994年Daganzo[11-12]提出的元胞傳輸模型不但可以靈活地對路段進行投資優(yōu)化以改變元胞網(wǎng)絡(luò)容量,而且可以對匝道實施不同控制策略.在該連續(xù)交通網(wǎng)絡(luò)設(shè)計研究領(lǐng)域:Sun等[13]利用自適應(yīng)魯棒優(yōu)化方法解決了不確定需求下動態(tài)網(wǎng)絡(luò)設(shè)計問題;Lin[14]利用基于雙變量近似下降方法解決了雙層連續(xù)動態(tài)網(wǎng)絡(luò)設(shè)計問題;Waller等[15]就需求模式不同和投資費用不同時比較了投資前后連續(xù)網(wǎng)絡(luò)設(shè)計的動態(tài)交通分配模型的迥異;Ukkusuri等[16]提出了用戶優(yōu)化動態(tài)網(wǎng)絡(luò)設(shè)計問題模型,并將其與系統(tǒng)優(yōu)化模型進行比較.

以上分析加深了利用元胞傳輸模型(CTM)處理連續(xù)網(wǎng)絡(luò)設(shè)計問題的理解,為解決快速路投資優(yōu)化奠定了基礎(chǔ).另外,CTM模型作為線性規(guī)劃模型,求解簡單,在考慮投資優(yōu)化的同時亦可以引入局部匝道控制策略,并且可以細致地分析每條路段內(nèi)部交通狀態(tài),從而描述交通流的干擾和波的形成.基于以上優(yōu)點,本文采用需求隨時間動態(tài)變化的CTM模型對快速路進行仿真,利用粒子群智能優(yōu)化方法求解在給定限額下快速路路段投資優(yōu)化問題.

1　基于CTM的快速路投資優(yōu)化模型

圖1表示所有元胞的分類.為了方便下文結(jié)構(gòu)的表達,圖2列出4種路段連接方式.其中:圖2(a)是入口匝道連接方式;圖2(b)是出口匝道連接方式;圖2(c)是匯合路段連接方式;圖2(d)是分散路段連接方式.

圖1　元胞分類圖

圖2　4種路段連接方式

(1)

(2a)

(2b)

(2c)

(2d)

匯合路段與入口匝道匯合結(jié)構(gòu)十分相似.對于這種典型的結(jié)構(gòu),流量匯合原理已經(jīng)得到了很好的研究,另外幾個相關(guān)的模型[19-20]已經(jīng)被提出，且已經(jīng)用大量數(shù)據(jù)檢驗了模型的可行性.為了使公式表達更加明確,假設(shè)下游合流路段的實際流量為上游兩條路段的最大釋放流量之和.因此,下面的表達式能夠依次求出來自上游路段匯合的實際流量.

(3a)

(3b)

(3c)

(3d)

(3e)

式(3a)～(3c)共同決定了合流處的最大流量,這個最大流量必須滿足下游路段的通行能力約束以及受到可利用空間限制.同時,任意上游路段的流量必須滿足通行能力這一約束,且釋放的流量必須受到元胞本身可利用流量的限制.在以上假設(shè)的前提下,式(3d)和式(3e)可得出上游兩個合流分支具體的釋放流量.

(4b)

(4c)

交通網(wǎng)絡(luò)中元胞的車輛按照如下算法進行更新:

a. 將實際的快速路路網(wǎng)改建成元胞結(jié)構(gòu)圖,另外初始化快速路系統(tǒng)的參數(shù);

c. 根據(jù)式(5)～(6)進行元胞狀態(tài)的更新.

2　實施局部匝道控制投資優(yōu)化

在實施局部匝道控制的投資模型中,因其缺乏目標函數(shù),所以考慮利用啟發(fā)式算法對其進行優(yōu)化求解.粒子群算法是一種基于群智能的優(yōu)化算法,該算法模擬鳥集群飛行覓食的行為,通過鳥之間的集體協(xié)作使群體達到最優(yōu)目的.其主要包括速度和位置更新公式:

(7)

(8)

圖3　利用粒子群算法優(yōu)化投資模型流程

3　交通網(wǎng)絡(luò)性能評價指標

為了有效評價投資優(yōu)化給快速路交通網(wǎng)絡(luò)性能帶來的效益,必須選擇能夠衡量交通網(wǎng)絡(luò)性能的指標.如果只對快速路一部分路段進行研究,目前的研究已給出了一些可選取的指標,例如:流量、服務(wù)水平(LOS)、V/C等.但是如果研究的是整體的快速路路網(wǎng),就必須采取衡量整個路網(wǎng)性能的指標.本文采用總行車里程(TDT)和系統(tǒng)總延誤(TD)作為衡量交通網(wǎng)絡(luò)性能的指標.在元胞傳輸模型中兩個指標的計算公式為

(9)

(10)

4　模型案例分析

4.1案例分析

圖4　路網(wǎng)元胞結(jié)構(gòu)圖

圖5　快速路主干路源元胞動態(tài)交通需求變化趨勢

4.2仿真結(jié)果分析

圖6和圖7(見下頁)表示的是利用粒子群算法得出的快速路在采用局部匝道控制策略時投資前和投資后總行車里程和系統(tǒng)總延誤的對比.從圖6和圖7中可以看出當給予最優(yōu)投資策略時,路網(wǎng)性能發(fā)生較大的變化,投資后總行車里程顯著增長,而系統(tǒng)總延誤顯著降低,說明最優(yōu)投資策略對路網(wǎng)性能的改善起了很大的作用.

圖6　投資前和投資后總行車里程對比

圖7　投資前和投資后系統(tǒng)總延誤對比

圖8和圖9分別表示的是采取局部匝道控制策略時投資前后元胞狀態(tài)x隨時間步長的變化圖.從圖中可以看出兩幅圖都呈現(xiàn)出前一部分波動性很大,后面平穩(wěn)變化.這是因為前面的時間段內(nèi),元胞內(nèi)未產(chǎn)生擁堵狀態(tài),元胞狀態(tài)x的靈敏度很高.隨著交通需求的增長,路段逐漸擁堵,元胞內(nèi)車流的傳播以最大流進行傳遞,所以當開始產(chǎn)生延誤時元胞狀態(tài)x開始平穩(wěn)變化.同時,可以看到元胞13,14,15在投資后元胞狀態(tài)x有了明顯提高.

圖8　投資前采用局部匝道控制策略元胞狀態(tài)

圖9　投資后采用匝道協(xié)調(diào)控制投資后元胞狀態(tài)

圖10是采用局部匝道控制策略時分配給各元胞的投資額.從圖中可以看出同一路段上的元胞在局部匝道控制策略下被分配以相等的投資額.例如元胞11,12,13,14,15,22,23,24,25,26為同一路段,元胞27,28,29為同一路段.不同路段被分配以不同投資額是由于不同路段的交通狀況以及快速路拓撲結(jié)構(gòu)所決定.

圖10　采用局部匝道控制分配給各元胞的投資額

5　結(jié)束語

本文提出了一種以元胞傳輸模型理論為基礎(chǔ)的快速路投資優(yōu)化方法,同時通過改變?nèi)肟谠训赖膬?yōu)先釋放權(quán)實現(xiàn)了快速路局部匝道控制,最后利用粒子群算法對該問題進行優(yōu)化求解.該優(yōu)化思想可應(yīng)用于快速路其他匝道控制方式以及城市道路交叉口信號燈控制.該模型也可延伸考慮在現(xiàn)有的交通網(wǎng)絡(luò)中添加新路段來進行投資優(yōu)化.

[1]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.

[2]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.

[3]DREZNER Z,WESOLOWSKY G O.Selecting an optimum configuration of one-way and two-way routes[J].Transportation Science,1997,31(4):386-394.

[4]ABDULAAL M,LEBLANC L J.Continuous equilibrium network design models[J].Transportation Research Part B:Methodological,1979,13(1):19-32.

[5]FERRARI P.Road pricing and network equilibrium[J].Transportation Research Part B:Methodological,1995,29(5):357-372.

[6]ALLSOP R E.Some possibilities for using traffic control to influence trip distribution and route choice[C]∥Proceedings of the 6th International Symposium on Transportation and Traffic Theory.New York:Elsevier,1974:345-373.

[7]李曉文.快速路匝道控制優(yōu)化方法研究[D].長春:吉林大學(xué),2015.

[8]朱炯,郭海鋒,俞立,等.基于蟻群算法的城市快速路優(yōu)化控制[J].計算機工程,2011,37(23):174-176.

[9]馬繼萍.快速路出口匝道控制策略研究[D].西安:長安大學(xué),2013.

[10]何勝學(xué),范炳全.多用戶動態(tài)交通流分配模型及算法研究[J].上海理工大學(xué)學(xué)報,2006,28(5):460-464.[11]DAGANZO C F.The cell transmission model:a dynamic representation of highway traffic consistent with the hydrodynamic theory[J].Transportation Research Part B:Methodological,1994,28(4):269-287.

[12]DAGANZO C F.The cell transmission model,part II:network traffic[J].Transportation Research Part B:Methodological,1995,29(2):79-93.

[13]SUN H,GAO Z Y,ZHAO F X.Dynamic network design problem under demand uncertainty:an adjustable robust optimization approach[J].Discrete Dynamics in Nature and Society,2014,2014:739656.

[14]LIN D Y.A dual variable approximation-based descent method for a bi-level continuous dynamic network design problem[J].Computer-Aided Civil and Infrastructure Engineering,2011,26(8):581-594.

[15]WALLER S T,MOUSKOS K C,KAMARYIANNIS D,et al.A linear model for the continuous network design problem[J].Computer-Aided Civil and Infrastructure Engineering,2006,21(5):334-345.

[16]UKKUSURI S V,WALLER S T.Linear programming models for the user and system optimal dynamic network design problem:formulations,comparisons and extensions[J].Networks and Spatial Economics,2008,8(4):383-406.

[17]CHUNG B D,YAO T,XIE C,et al.Robust optimization model for a dynamic network design problem under demand uncertainty[J].Networks and Spatial Economics,2011,11(2):371-389.

[18]NEWELL G F.Applications of queuing theory[M].2nd ed.London:Chapman and Hall,1982.

[19]CASSIDY M J,AHN S.Driver turn-taking behavior in congested freeway merges[J].Transportation Research Record:Journal of the Transportation Research Board,2005(1934):140-147.

[20]JIN W L.Continuous kinematic wave models of merging traffic flow[J].Transportation Research Part B:Methodological,2010,44(8/9):1084-1103.

[21]Transportation Research Board.Highway capacity manual[M].4th ed.Washington DC:Transportation Research Board,National Research Council,2000.

(編輯:丁紅藝)

Decision Method for Express Way Investment Based on a Particle Swarm Algorithm

HE Shengxue,LIU Jie,ZHANG Haodong

(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

From the view point of the affection of investment on traffic network capacity,a new kind of expressway investment optimization method based on the cell transmission model (CTM) theory was put forward.The cell transmission model was improved in order to realize the local ramp control.A particle swarm expression method for the meta cell capacity optimization problem was constructed by using the particle swarm intelligent optimization method.And the total mileage (TDT) and system delay (TD) were defined as a measure of the performance of expressway system.The calculation results show that before the investment,the TDT is 12 004 874 m,the TD is 3 582 405.1 s,and after investment,the TDT is 13 128 283 m,increased by 1 123 409 m,the TD is 3 537 468.7 s,reduced by 44 936.4 s.The results show that the new optimization method makes the total mileage significantly grow and the total delay significantly reduce.The performance of the entire road network is also improved.The investment optimization method can better solve the optimization problem of expressway investment.

cell transmission model; investment optimization; ramp comtrol; particle swarm algorithm; line programming

1007-6735(2016)04-0373-07

10.13255/j.cnki.jusst.2016.04.012

2015-09-29

國家自然科學(xué)基金資助項目(70672110);上海市重點學(xué)科(第三期)建設(shè)資助項目(S30540);上海市教委科技創(chuàng)新項目(10YS105)

何勝學(xué)(1976-),男,副教授.研究方向:交通網(wǎng)絡(luò)建模.E-mail:lovellhe@163.com

U 411

A