孫飛，龍建成

（合肥工業(yè)大學交通運輸工程學院，合肥230009）

考慮速度限制的連續(xù)交通網(wǎng)絡設計問題

孫飛，龍建成*

（合肥工業(yè)大學交通運輸工程學院，合肥230009）

本文提出了一個考慮車速限制的雙目標連續(xù)交通網(wǎng)絡設計問題，旨在通過合理的路段拓展與限速策略提高網(wǎng)絡交通運行效率和減少交通系統(tǒng)的環(huán)境污染.構建了一個雙目標雙層規(guī)劃模型來描述提出的交通網(wǎng)絡設計問題.其中，上層問題從交通管理者的角度出發(fā)，以系統(tǒng)總阻抗與總投資額之和最小及網(wǎng)絡總的車輛尾氣排放最小為目標，制定最優(yōu)的網(wǎng)絡設計方案和不同時段最優(yōu)的限速方案；下層問題基于用戶平衡準則，描述不同時段出行者的路徑選擇行為.設計了基于非支配排序的遺傳算法對提出的雙層規(guī)劃模型進行求解，并采用數(shù)值算例驗證了提出的模型與算法的有效性.

城市交通；交通網(wǎng)絡設計問題；雙層規(guī)劃；車速限制；遺傳算法

1 引言

近年來，隨著經(jīng)濟的發(fā)展和城市化進程的加快，城市機動車擁有量急劇增加，交通供需矛盾日益突出，交通擁擠越來越嚴重.自上世紀70年代以來，國內(nèi)外學者對城市交通網(wǎng)絡設計問題進行了較為系統(tǒng)而深入的研究，并提出了相應的雙層規(guī)劃模型及算法[1-3].隨著城市道路交通擁堵的加重，已經(jīng)不能夠單純依靠修建道路的方式來解決城市交通問題.實踐表明，把城市交通規(guī)劃與交通控制措施結合起來，能夠更為有效地緩解城市交通擁堵.

車速限制是一種有效的交通控制手段，它的實施可以有效提高交通效率，改善交通環(huán)境及交通安全[4].早期有關限速的研究主要集中在分析其對道路局部的影響，忽略了其對整個路網(wǎng)系統(tǒng)的影響.近年來，有很多學者從整個路網(wǎng)系統(tǒng)的角度來研究車速限制，包括車速限制對出行行為的影響[5,7]、動態(tài)車速限制[8]、車速限制與其它交通政策結合等[6,9].例如，Lave和Elias[5]首次研究了車速限制對交通分配的影響.Yang等[6]提出了限速條件下的UE交通分配模型，并證明了在一定的條件下實施車速限制可以與實施道路收費達到同樣的效果. Liu等[7]研究了可變限速策略對于瓶頸通勤出行行為的長期影響.孫靜怡等[8]根據(jù)動態(tài)交通流理論提出了可變限速的模型設計和方法.Madireddy等[9]應用車速限制和信號控制相結合的方法來降低交通系統(tǒng)的碳排放.

當前，交通管理部門主要基于現(xiàn)有路網(wǎng)條件制定速度限制策略，這制約了策略的實際應用效果.而把車速限制策略考慮到交通網(wǎng)絡設計中，可以為策略的實施提供更有利條件，從而更好地提升交通網(wǎng)絡的總體性能.和以往研究不同，本文在傳統(tǒng)網(wǎng)絡設計問題的基礎上，考慮不同交通需求時段車速限制策略的優(yōu)化，提出了一個雙目標交通網(wǎng)絡設計問題，構建了雙目標雙層規(guī)劃模型，設計了基于非支配排序的遺傳算法求解提出的模型，并采用數(shù)值算例驗證了提出的模型與算法的有效性.

2 雙目標雙層優(yōu)化模型

車速限制下的城市交通網(wǎng)絡設計問題可以描述為一個雙層規(guī)劃問題.其中上層問題，交通管理者通過拓寬道路和制定速度限制措施來優(yōu)化交通網(wǎng)絡的性能；下層問題，則描述交通規(guī)劃和管理措施下出行者的出行選擇行為[10].本文同時考慮交通網(wǎng)絡運行效率的提升和交通污染的減少，把上層問題描述為一個雙目標優(yōu)化問題.同時，借鑒大多數(shù)已有網(wǎng)絡設計問題的研究，假設不同交通需求時段的出行者的路徑選擇行為遵循UE準則，即同一交通需求時段同一OD對的出行者具有相同且最小的出行費用.

2.1 下層用戶平衡配流問題

在一個具有多起點和多訖點的交通網(wǎng)絡G中，定義N為節(jié)點的集合，A為路段的集合，W為OD對集合，Rw為第w個OD對的路徑集合.在道路限速情形下，限速路段的路抗函數(shù)則會根據(jù)路段流量的變化而不同，可以表述為[6]

式中va為路段a上的交通流量；為路段a受速度限制影響的臨界流量；為路段a受速度限制時的旅行時間；為路段沒有速度限制時的旅行時間函數(shù)，有在速度限制下，有其中La為路段a的長度為無限速條件下路段a的阻抗函數(shù)的逆函數(shù).

考慮道路通行能力的拓寬，我們采用如下阻抗函數(shù)[10]：

式中Aa和Ba為參數(shù)；ka和ya分別為路段a現(xiàn)有的和拓寬的通行能力.結合式(1)和式(2)可以看出，路段阻抗ta(va)也是關于限速和拓寬的通行能力ya的函數(shù).

針對一天之內(nèi)不同時段交通需求水平的差異性，下層問題考慮了不同交通需求時段不同限速度策略下的交通分配問題.多時段速度限制條件下的UE交通分配問題也可以描述為一個變分不等式問題，即尋找一個平衡的路徑流量向量f*∈Ω，使得

2.2 上層雙目標優(yōu)化問題

2.2.1 車輛排放成本

假設路段的尾氣排放量是車輛平均行駛速度的函數(shù)，并具有如下函數(shù)形式[11,12]：

式中An、Bn和Cn是污染物n的尾氣排放函數(shù)的系數(shù)；為路段a在第m個時段的平均行駛速度，有

于是，整個網(wǎng)絡總的尾氣排放量可以計算如下[12]：

式中ηn為污染物n的單位排放成本.

2.2.2 上層雙目標優(yōu)化模型

上層問題從提升交通網(wǎng)絡的運行效率[13,14]和保護交通環(huán)境[12]的角度出發(fā)，以不同出行時段系統(tǒng)總阻抗最小和網(wǎng)絡總的尾氣排放最小為目標來改善交通網(wǎng)絡的性能，其優(yōu)化模型可以表述如下：

式中θ為投資匹配系數(shù)；Ga(ya)為路段a的投資費用函數(shù)；為路段a限速的下界；為路段a通行能力拓寬的上界；路段流量由下層變分不等式(3)得到.

上述優(yōu)化問題中，目標函數(shù)式（8）最小化系統(tǒng)總阻抗與匹配投資費用之和，目標函數(shù)式（9）最小化網(wǎng)絡總的尾氣排放，約束條件式（10）和式（11）分別是路段通行能力拓展約束及路段車速限制條件.

3 求解算法

多目標雙層規(guī)劃模型的求解往往非常復雜，即使上層問題和下層問題都是凸的，整個問題也可能是非凸的.本文將設計多目標遺傳算法來求解提出的雙目標雙層規(guī)劃模型.

3.1 下層問題求解

我們采用基于路徑的雙梯度投影算法對下層變分不等式問題進行求解.相比于Flank-wolf算法，基于路徑的雙梯度投影算法不僅可以確保計算精度，還可以大大提高運算效率[15].

3.2 多目標遺傳算法

求解上述雙目標優(yōu)化模型的遺傳算法有很多.其中，Deb[16]提出的非支配排序遺傳算法（NSGAII）運用最為廣泛.本文將運用NSGA-II算法獲得提出的雙目標雙層優(yōu)化問題的Pareto最優(yōu)解.下面給出該算法的詳細設計，具體算法步驟可以參見文獻[16].

3.2.1 種群非支配排序

在NSGA-II算法中執(zhí)行選擇操作之前，對所有個體進行非支配排序，即根據(jù)個體的非劣解水平對個體進行分級，計算個體的序值.非支配排序的基本方法是：設置初始序值為1.依次將種群中未被排序的個體p與其余所有未被排序的個體q進行比較.如果不存在個體q能夠支配個體p，則個體p被賦予當前序值；反之，個體p參與下一輪排序.下一輪序值在當前序值的基礎上加1，并重復以上過程直至所有個體都賦予了序值.

3.2.2 擁擠距離

我們定義每個個體與其相鄰的兩個個體在每個子目標函數(shù)上的距離差之和為該個體的擁擠距離.擁擠距離的計算可以反映每個解周圍其它解的分布情況.圖1中所示虛線長方形的長和寬之和即為個體i的擁擠距離.如圖1中兩端的兩個個體的擁擠距離都設為無窮大.在NSGA-II算法中，擁擠距離大的個體將獲得更多參與繁殖和進化的機會，以確保算法能收斂到一個均勻分布的Pareto曲面，從而維持種群的多樣性.

圖1 擁擠距離計算示意圖Fig.1 Illustration of the crowd distance

3.2.3 遺傳策略

定義遺傳參數(shù)變量：種群大小PS，最大遺傳代數(shù)T，變異概率pm，交叉概率pc.

（1）解的編碼.

把網(wǎng)絡中路段通行能力拓寬值ya和不同時段路段限速值sa作為求解變量進行實數(shù)向量編碼.

（2）初始種群的產(chǎn)生.

初始群體P0的個數(shù)PS一般取50～100，也可通過試算確定.初始群體P0的PS個體利用路段通行能力拓展約束，以及路段車速限制條件隨機生成.

（3）適應度評價.

對每個個體求解下層UE配流問題，計算對應的上層目標函數(shù)，并通過非支配排序法，以及擁擠距離的計算，得到個體的序值和擁擠距離，個體序值越小適應度越高，序值相同的個體擁擠距離越大適應度越高.

（4）遺傳操作.

遺傳算法的操作算子一般包括選擇、交叉和變異等三種基本形式.從PS組初始群體中通過錦標賽法選取PS個個體組成父代群體Pt，對父代群體進行交叉、變異操作.其中，交叉操作采用SBX交叉算子，對實數(shù)編碼的父個體進行交叉操作，對兩個配對染色體隨機選擇交叉點，然后交換交叉點后的部分，從而產(chǎn)生兩個新個體；變異操作采用多項式變異算子，從群體Pt中依據(jù)變異概率pm選取部分基因進行變異，有助于NSGA-II跳出局部最優(yōu)的狀態(tài).

（5）精英保留.

為了保持種群中個體的多樣性，采用非支配排序法和錦標賽法從當前代Pt及其子輩Qt中選取PS個優(yōu)良個體遺傳到下一代.選擇的過程是：首先將當前代Pt及其子輩Qt組合成新的種群Rt，對種群Rt進行非支配排序，計算每個個體的序值和擁擠距離，通過錦標賽法選取PS個優(yōu)良個體.

4 數(shù)值分析

本文采用Nguyen-Dupuis網(wǎng)絡[17]來驗證提出的模型與算法的有效性.該網(wǎng)絡有13個節(jié)點，19條路段，4個OD對.各路段自由流速度均為60 km/h，路段12–8的自由流走行時間為1m in，路段1–12、7–8、7–11、8–13和10–11的自由流走行時間為0.6m in，其他路段的自由流走行時間均為0.45min. OD對1–2、1–3、4–2、4–3的需求比為2:4:3:3.路段8–2、12–8和13–3為1條車道，路段7–8和9–13為2條車道，其它路段均為3條車道.每條車道的路段通行能力為2 000 pcu/h.本文只考慮對路段5–9和9–13進行速度限制.早高峰、晚高峰和平峰時段網(wǎng)絡總的OD需求分別為24 000輛/小時，21 000輛/小時，18 000輛/小時.采用的投資費用函數(shù)2.表1給出了污染物常數(shù)系數(shù)與其單位排放成本.算法參數(shù)設置如下：種群大小popsize=100，進化最大迭代次數(shù)gen=2 000，交叉概率p=0.9，變異概率q=0.1，終止參數(shù)ξ=10-6.

表1 排放因子參數(shù)及不同污染物排放成本價值[11]Table 1 Parameters ofem ission rate functions andmonetary valuation ofeach type of pollutants[11]

4.1 進化迭代次數(shù)校正

我們采用設計的NSGA-II算法對提出的雙目標雙層優(yōu)化模型進行求解.通過多次計算，我們得到了圖2中的Pareto近似最優(yōu)前沿面.可以看出，交通效率和交通環(huán)境之間存在目標沖突.在進行網(wǎng)絡設計的過程中，交通規(guī)劃與管理者需要在交通效率和交通環(huán)境上做出權衡.圖3給出了不同迭代次數(shù)下的Pareto前沿面與Pareto近似最優(yōu)前沿面的比較.可以發(fā)現(xiàn)，迭代次數(shù)越多，NSGA-II算法得到的Pareto前沿面越接近最優(yōu)的Pareto前沿面.當?shù)螖?shù)達到2 000時，NSGA-II算法已經(jīng)能夠達到比較好的求解效果.

圖2 Pareto近似最優(yōu)前沿Fig.2 The Pareto frontier for the fixedmatching coefficient

圖3 不同迭代次數(shù)的近似最優(yōu)前沿Fig.3 The Pareto frontier for differentperiodsof column generation procedure

4.2 投資匹配系數(shù)比較

上層優(yōu)化模型中投資匹配系數(shù)θ取值的不同，可以看作交通規(guī)劃者在最大程度地改善交通網(wǎng)絡和盡可能地減少投資費用這相互矛盾的二者之間的權衡.圖4給出了投資匹配系數(shù)θ分別取值0.5、1和2時的Pareto近似最優(yōu)前沿面.θ取值越大，表明投資預算越緊張；反之，則表明投資資金越寬裕.從圖4可以看出，當θ的值減少時，交通網(wǎng)絡尾氣污染物總排放量不斷下降，同時交通網(wǎng)絡的系統(tǒng)總阻抗與投資總額之和也不斷降低.這是因為，當θ取值減少時，將會投入更多的資金進行道路網(wǎng)絡改善，可以更大程度地提升網(wǎng)絡交通效率，減少交通污染.

4.3 不同時段限速控制對比

為了驗證分時段限速控制措施的有效性，我們在θ=0.5時對比了只設置高峰時段限速和綜合設置各時段限速兩種情形.圖5中給出了兩種情形下近似的Pareto最優(yōu)前沿面.可以看出，綜合考慮各時段交通狀況進行限速可以顯著提升城市網(wǎng)絡交通效率和減少城市交通污染.

圖4 不數(shù)的Pareto近似最優(yōu)前沿Fig.4 The Pareto frontier for differentmatching coefficients

圖5 單獨高峰時段限速與各時段均限速情形下的Pareto前沿面Fig.5 The Pareto frontier for considering the speed limitin peak only and differentperiods

5 研究結論

本文提出了雙目標雙層規(guī)劃模型來描述環(huán)境目標下考慮速度限制的連續(xù)交通網(wǎng)絡設計問題，分別設計了基于路徑的雙投影算法和遺傳算法求解下層問題和整個雙層規(guī)劃模型.數(shù)值結果表明：考慮速度限制的最優(yōu)網(wǎng)絡設計方案，不僅可以有效地提高交通運行效率，還可以大幅降低交通尾氣污染；隨著投資預算的增加，可以更大程度地緩解交通擁擠和減少尾氣污染；有必要針對不同OD需求水平的時段，分別制定交通控制措施以最大化交通網(wǎng)絡性能，從而實現(xiàn)交通規(guī)劃與管理的統(tǒng)籌優(yōu)化.

[1]趙彤,高自友.交通離散網(wǎng)絡設計與土地使用問題的組合模型及求解算法[J].土木工程學報,2003,36:5-10.[ZHAO T,GAO Z Y.A combined models and solution algorithm for transport discrete network design and land-use problem[J].China Civil Engineering Journal,2003,36:5-10.]

[2]高自友,張好智,孫會君.城市交通網(wǎng)絡設計問題中雙層規(guī)劃模型方法及應用[J].交通運輸信息工程學報，2004，4(1)：35-44.[GAO Z Y,ZHANG H Z, SUN H J.Bi-level programming models,approaches and applications in urban transportation network design problems[J].Journal of Transportation Systems Engineering and Information Technology,2004,4(1): 35-44.]

[3]秦進,倪玲霖,董玉龍.考慮可持續(xù)發(fā)展的交通網(wǎng)絡設計雙層模型與算法[J].交通運輸信息工程學報,2010, 4:111-113.[QIN J,NI L L,DONG Y L.Bi-level programming model and algorithm for transportation network design problem considering sustainable development[J].Journal of Transportation Systems Engineering and Information Technology,2010,4:111-113.]

[4]張鎖,李杰,李連升.道路交通事故車速分析的探討[J].交通標準化,2006,8:1-2.[ZHANH S,LIJ,LI L S.Study speed of vehicles for road traffic accident[J]. Communicatioms Standardization,2006,8:1-2.]

[5]Lave C,Elias P.Resource allocation in public policy: the effects of the 65-mph speed limit[J].Economic Inquiry,1997,35(3),614-620.

[6]Yang H,Wang X,Yin Y.The impact of speed limits on traffic equilibrium and system performance in networks[J].Transportation Research Part B,2012,46 (10)：1295-1307.

[7]Liu W,Yin Y,Yang H.Effectiveness of variable speed limits considering commuters'long-term response[J]. Transportation Research Part B,2014,doi:10.1016/j. trb.2014.12.001.

[8]孫靜怡,沈俊江,劉擁華.城市快速路可變限速策略[J].公路交通科技,2012,11:20.[SUN JY,SHEN J J,LIU Y H.Variable speed limits strategy of urban expressway[J].Journal of Highway and Transportation Research and Development,2012,11:020.]

[9]Madireddy M,Coensel B D,Can A,et al.Assessment of the impact of speed limit reduction and traffic signal coordination on vehicle emissions using an integrated approach.Transportation Research PartD，2011，16(7)：504-508.

[10]高自友,宋一凡,四兵峰.城市交通連續(xù)平衡網(wǎng)絡設計－理論與方法[M].北京:中國鐵道出版社, 2000.[GAO Z Y,SONG Y F,SIB F.Continuously balanced network design of city transportation-theory andmethod[M].Beijing:China railway press,2000.]

[11]Mayeres,I,Ochelen,S,Proost,S,Themarginal external costs of urban transport[J].Transportation Research Part D,1996,1(2):111-130.

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

[13]孫華,高自友,龍建成.不確定OD需求下連續(xù)交通網(wǎng)絡設計的魯棒優(yōu)化模型[J].交通運輸系統(tǒng)工程與信息,2011,2:70-71.[SUN H,GAO ZY,LONG JC.The robust model of continuous transportation network design problem with demand uncertainty[J].Journal of Transportation Systems Engineering and Information Technology,2011,2:70-71.]

[14]劉慧,楊超,楊珺.具有遺憾值約束的魯棒性交通網(wǎng)絡設計模型研究[J].交通運輸系統(tǒng)工程與信息,2013,5:86-87.[LIU H,YANGC,YANG J.Robust transportation network design modeling with regret value[J].Journal of Transportation Systems Engineering and Information Technology,2013,5:86-87.]

[15]Barbara P,Massimo P,Mauro P.A path-based double projection method for solving the asymmetric traffic network equilibrium problem[J].Optimization Letter, 2007,1:171-185.

[16]Deb K,Aarawal S,Pratap A,et a1.A fast elitist nondominated sorting genetic algorithm formulti-objective optimization:NSGA-II[J].Lecture Notes in Computer Science,2000,1917:849-858.

[17]Nguyen S,Dupuis C.An effi cientmethod for computing traf fi c equilibria in networks with asymmetric transportation costs[J].Transportation Science,1984, 18:185-202.

A Continuous Transportation Network Design Problem with Considering of Speed Limit

SUN Fei，LONG Jian-cheng

(Schoolof Transportation Engineering,HefeiUniversity of Technology,Hefei230009,China)

This paper proposes a bi-objective continuous transportation network design problem with considering of speed lim it.The efficiency of traffic network and reduce the network environment pollution are improved by reasonable road capacity enhancing and speed lim it strategy.A bi-objective bi-level programm ing model is developed to formulate the proposed network design problem.The upper level problem aims tominimize both the summation of the total system travel time and the total investment,and the cost of total vehicle em issions from the viewpoint of traffic managers,and obtains the optimal road capacity enhancing scheme and the optimal speed lim iting scheme for different time periods.Based on user equilibrium(UE)theory,the lower level problem represents travelers'route choice behavior during different time periods.A genetic algorithm based on non-dominated sortingmethod is designed to solve the bi-level programm ing model.Finally,numerical examples are developed to demonstrate the effectiveness of the modeland algorithm proposed in this paper.

urban traffic;transportation network design problem;bi-level programm ing;speed lim it; genetic algorithm

1009-6744（2015）02-0146-06

U12

A

2014-11-05

2015-3-17錄用日期：2015-03-23

外專千人計劃項目（WQ20123400070）；國家自然科學基金項目（71271075，71431003）.

孫飛（1989-），男，重慶人，碩士生.＊通信作者：jianchenglong@hfut.edu.cn