隨機需求多目標連續均衡網絡設計

方文彬，王濤，黃汝晴，黃中祥，曾鈴

隨機需求多目標連續均衡網絡設計

方文彬1，王濤2，黃汝晴2，黃中祥1，曾鈴1

(1. 長沙理工大學 交通運輸工程學院，湖南 長沙，410004；2. 中南大學 交通運輸工程學院，湖南 長沙，410075)

為考察多目標特性以及需求不確定性對網絡設計的影響，假設OD(origin destination)需求服從雙側截尾正態分布，構建多目標連續均衡網絡設計的雙層規劃模型。上層規劃以系統出行時間的期望最小、路網服務水平可靠性最大和投資預算最小為目標，下層規劃采用用戶均衡分配刻畫出行者路徑選擇行為。給出基于蒙特卡洛仿真的多目標遺傳求解算法，采用測試網絡驗證模型和算法的有效性。研究結果表明：采用多目標連續均衡網絡設計模型可以獲得多個非劣解供決策者選擇；不同目標之間存在明顯的相關關系，尤其是投資手段存在明顯的邊際遞減效應，宜結合交通管理措施共同使用。

連續均衡網絡設計；多目標規劃；雙層規劃；服務水平可靠性；第二代非支配排序遺傳算法

路網設計是指在給定的約束條件下，通過新建道路或改擴建現有路段，使網絡的某種性能指標達到最優，包括離散、連續和混合網絡設計3種類型[1]。自ABDULAAL等[2]提出連續均衡網絡設計模型以來，國內外學者對網絡設計問題開展了深入研究，取得了豐富的研究成果[3]，并形成了以雙層規劃為代表的研究方法。然而，傳統網絡設計很少考慮交通系統的不確定性，所獲得的路網設計方案魯棒性較差。近年來，隨著對道路網絡可靠性研究的不斷深入，人們逐步認識到不確定性是交通系統的本質特性之一[4]，要獲得更加符合實際的網絡設計方案，就必須在網絡設計過程中考慮交通系統的不確定性。目前，人們在隨機供給和(或)隨機需求影響下的交通網絡設計方面進行了研究，如：許良等[5]從路段容量的隨機變動出發，以概率用戶均衡為基礎研究了基于路段能力可靠性的交通網絡設計；SUMALEE等[6]提出了隨機需求下以出行時間可靠性為目標的網絡設計模型；CHOOTINAN等[7]在交通需求不確定條件下將容量可靠性引入城市交通網絡設計中，建立了基于Probit隨機用戶均衡的連續網絡設計模型；陸化普等[8?9]從發生和吸引交通量的不確定、OD(origin destination)需求的不確定2個方面考察了不確定需求下的離散交通網絡設計問題；蒲云等[10]采用部分隨機用戶均衡模型描述了事故影響下的路網狀態，建立了以期望社會成本最小為目標的可靠網絡設計模型。CHEN等[11]歸納了不確定需求下的隨機網絡設計方法，提出了期望值模型、約束機會模型和相關機會模型這3種建模方法。但現有關于不確定環境下的網絡設計研究多假定路段容量或交通需求服從正態分布或均勻分布，這些概率分布能否真實、合理地刻畫供求的隨機性特征還缺乏必要的論證。另一方面，現有關于網絡設計的研究多局限于系統總阻抗最小或時間可靠性最大等單一目標。然而，交通規劃管理部門對未來的網絡除要求其阻抗小之外，還要求網絡的運行效率高、建設成本低、承載能力大以及網絡能應對較高風險等諸多目標。XU等[12]建立了以系統出行時間與投資預算之和最小為目標的網絡設計模型；YIN[13]則以出行時間最小和網絡效益最大為目標構建網絡設計模型。上述研究雖然考慮了網絡設計的多目標特性，但在建模環節常將多目標問題轉化為單目標問題求解。事實上，在不確定環境下同時優化多個目標的網絡設計更加符合實際，能夠滿足決策者對未來網絡的多種需求，目前該領域的研究成果偏少。CHEN等[14]構建了同時優化容量可靠性和出行時間可靠性的連續均衡交通網絡設計模型，陸化普等[15]假設供求隨機變化，通過引進風險價值理論建立了考慮決策者風險態度的多目標雙層規劃模型。為更真實地描述實際問題，本文作者假定交通需求服從雙側截尾正態分布，以服務水平可靠性最大、系統總阻抗和投資預算最小為目標構建隨機需求作用下的多目標連續均衡網絡設計模型，設計基于蒙特卡洛仿真的多目標遺傳求解算法，最后用算例驗證該網絡設計模型的特性。

1 多目標連續均衡網絡設計建模

1.1 交通需求隨機性刻畫

1.2 網絡設計的優化目標分析

一般地，交通系統管理部門總是希望用最少的投資來獲得效率最高的網絡，同時還要求規劃路網能應對一定風險。為此，本文在構建考慮需求隨機性的多目標網絡設計模型時，主要從交通系統運行效率、路網服務水平可靠性和資金投入量3方面構建網絡設計模型的優化目標。

從交通系統運行效率的角度考慮，運行效率越高的路網其總阻抗越小，因此，該目標可以采用系統總阻抗的期望最小化來描述：

式中：x為路段上的交通量("?)；y為路段的容量增加值；=(1, …, y, …,|A|)為路段容量增加值向量，||為路段數量；=(1, …, Q, …,|W|)為OD需求向量，||為OD對數量；t(×)為路段的走行時間；(×)表示取均值。本文采用BPR(bureau of public roads)函數作為路段走行時間函數：

式中：r為概率；=(1, …, x, …,|A|)為路段流向量；為某一指定的飽和度閾值；(×)為路網飽和度；l為路段的長度。

通常1個城市用于交通基礎設施建設的資金是有限的，網絡設計過程中應盡可能用較小投資來獲得較大效益。為此，本文將投資費用最小化也作為網絡設計模型的優化目標之一，該目標可表示為

式中：G(×)為投資函數，

1.3 隨機需求多目標連續均衡網絡設計模型

網絡設計問題是一個典型的“領導者—追隨者”問題，通常用雙層規劃來刻畫，其中上層決策者為系統管理者，下層決策者為道路用戶。根據前述分析，以系統總阻抗、路網服務水平不可靠性以及投資費用最小作為上層優化目標，上層決策變量為路段容量的增加值。系統管理者對路網的改善會影響道路用戶的路徑選擇行為，出行者會隨著網絡結構的改變及時調整其路徑選擇，以確保個體出行費用最小，為此，采用用戶均衡來描述下層出行者的路徑選擇。

隨機需求作用下的多目標連續均衡網絡設計可以構建成如下數學規劃模型。

上層規劃：

下層規劃：

2 模型求解算法

在多目標優化問題中，有多個目標函數需要同時優化。由于目標之間無法比較，甚至存在沖突，最終將導致不一定存在同時滿足所有目標的最優解。多目標優化問題通常存在1個解集，其特點是與解集之外的任何解相比，它們至少有1個目標函數比解集之外的解好而其他目標函數又不比解集之外的解差，這種解稱為非支配解或Pareto最優解。求解多目標優化問題時，NSGA-Ⅱ算法是被應用得最廣泛的算法之一。NSGA-Ⅱ通過非支配排序技術尋找最接近真實Pareto前沿的解；擁擠度用來確保非支配解的多樣性，包含最優父代解與最優當前解的精英化策略，增強了算法的收斂性，其具有現代智能優化算法的優點，魯棒性好，計算高效[16]。以NSGA-Ⅱ算法為基礎，結合蒙特卡洛仿真技術，給出求解隨機需求條件下多目標連續均衡網絡設計模型的算法步驟如下。

步驟1 初始化。定義遺傳算法的基本參數，包括編碼方式、種群大小、適應度函數和交叉、變異概率以及最大迭代次數。給定OD需求樣本規模S，隨機生成1個父代種群。在上層模型約束條件對應的搜索空間內隨機生成足夠可信的個體，令進化代數=1。

步驟2 隨機抽樣及路段流量分配。

步驟2.1 采用蒙特卡洛仿真方法進行需求抽樣，并且對每個OD需求方案采用Frank-Wolfe算法求解下層用戶均衡配流模型，得到每個個體對應的路段流量。

步驟2.2 將各路段流量代入上層模型，計算適應度。

步驟3 采用NSGA-Ⅱ更新種群。

步驟3.1 將所有個體按非支配關系排序，令適應度等于非支配序rank。

步驟3.2 選擇、交叉、變異生成1個子代種群Q，大小為。

步驟4 迭代。

步驟4.1 將第代產生的新種群Q與父代P合并成R，大小為2。

步驟4.2 對R進行快速非支配排序，產生一系列非支配集F。

步驟4.3 計算F中每個個體的擁擠度。

步驟4.4 將F放入新的父代種群P+1，直到P+1超過，其最后的非支配集為F。

步驟4.5 對F中的個體按照擁擠度算子排序，取前(?|P+1|)個個體，使P+1個體數量達到。

步驟4.6 通過遺傳算子(選擇、交叉、變異)產生新的子代種群Q+1。

步驟5 判斷是否達到最大進化代數，若不是，則返回上述操作步驟2，同時令=+1；若是，則算法結束，輸出Pareto最優解。

該算法的具體流程如圖1所示。

3 算例

算例網絡如圖2所示。該網絡由9個節點和12條單向路段組成。圖2中線上數字為各路段編號。假定只有1個OD對，從節點A到節點I。測試網絡各路段的長度、路段自由流時間、路段現狀通行能力以及路段容量增加值的上限等特性參數的取值設置如表1所示。

設OD對AI之間的需求均值為3 000輛/h，需求下限為2 000輛/h，上限為4 000輛/h，需求的均方差設為均值的0.3倍。為確保抽樣精度，設抽樣次數為 1 000。遺傳算法的主要參數設置如下：種群規模為100，最大代數為100，個體采用二進制編碼，交叉概率為0.8，變異概率為0.01。BPR函數的參數=0.15，=4，路網飽和度閾值取為=0.85。在上述參數下，運用本文建立的模型和算法求解算例網絡，獲得隨機需求作用下考慮多目標的連續均衡網絡設計模型的Pareto最優解如圖3所示(其中，以投資預算、系統出行時間的期望值和路網飽和度小于0.85的概率為坐標軸)。

圖3表明：Pareto最優解由36個非劣解組成，表明當出行時間期望值增大時，交通擁堵加劇，路網服務水平可靠性逐漸下降，路網出行條件變差。受需求隨機性的影響，Pareto最優解在圖中的分布不是特別集中，但在一定程度上仍回歸于1個曲面；每個點均代表了1種路段容量改善方案，這與單目標網絡設計只能獲得某一確定的最優解有明顯不同。在多目標作用下，系統管理者在權衡總出行時間、服務水平可靠性和投資預算多個目標后，可以獲得多樣化的路段容量改善方案并可根據實際需要選取某一種方案進行實施，這有效地提高了網絡設計的彈性。系統總阻抗的期望、服務水平可靠性與投資預算這3個目標兩兩之間的Pareto最優解見圖4。

圖1 算法流程

圖2 算例網絡

表1 路段特性參數

從圖4(a)可見：系統出行時間的期望值與服務水平可靠性之間存在著相關關系；隨著系統出行時間期望值增加，路網飽和度小于0.85的概率逐漸減少。

圖3 多目標雙層規劃模型的Pareto最優解

(a) 服務水平可靠性與系統出行時間期望值的關系；(b) 服務水平可靠性與投資預算的關系；(c) 系統出行時間期望值與投資預算的關系

從圖4(b)可見：隨著投資預算增加，網絡飽和度小于0.85的概率逐漸增加，但可靠性增加的幅度不斷變小并趨于平緩。這說明路網服務水平可靠性隨投資預算的增大而增大，且單位資金投入對網絡服務水平可靠性的提高逐漸減少，呈現出邊際遞減效應。

單位資金投入的邊際效應遞減現象在投資預算和系統出行時間的期望值之間更明顯，如圖4 (c)所示。前期投資使得系統出行時間的期望值明顯下降，而投資進一步增加對出行時間期望值的影響明顯減弱。這表明單位投資在網絡設計的前期作用較明顯，后期效果逐漸減弱。

4 結論

1) 網絡設計本質上是1個多目標規劃問題。與單目標網絡設計相比，本文提出的方法在對多個目標進行綜合衡量后，可以給出多樣化的決策方案。

2) 系統總阻抗與服務水平可靠性及系統總阻抗與投資預算之間均存在負相關關系，而投資預算與服務水平可靠性之間存在著正相關關系。

3) 增加預算能夠減少系統出行時間和增加路網服務水平可靠性，但其存在明顯的邊際遞減效應，不能作為緩解擁堵和提高交通系統運行效率的一種長期有效措施。

[1] 高自友, 張好智, 孫會君. 城市交通網絡設計問題中雙層規劃模型、方法及應用[J]. 交通運輸系統工程與信息, 2004, 4(1): 35?44. GAO Ziyou, ZHANG Haozhi, SUN Huijun. 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.

[2] ABDULAAL M, LEBLANC L J. Continuous equilibrium network design models[J]. Transportation Research Part B: Methodological, 1981, 15(4): 249?266.

[3] 《中國公路學報》編輯部. 中國交通工程學術研究綜述·2016[J]. 中國公路學報, 2016, 29(6): 71?77. Editorial Department of China Journal of Highway and Transport. Review on China’s traffic engineering research progress: 2016[J]. China Journal of Highway and Transport, 2016, 29(6): 71?77.

[4] 況愛武, 黃中祥. 隨機供求下的道路服務水平可靠性[J]. 系統工程, 2007, 25(6): 25?30. KUANG Aiwu, HUANG Zhongxiang. On the service reliability in stochastic supply and demand[J]. Systems Engineering, 2007, 25(6): 25?30.

[5] 許良, 高自友. 基于路段能力可靠性的城市交通網絡設計問題[J]. 中國公路學報, 2006, 19(2): 86?90. XU Liang, GAO Ziyou. Urban transport network design based on link capacity reliability[J]. China Journal of Highway and Transport, 2006, 19(2): 86?90.

[6] SUMALEE A, WATLING D P, NAKAYAMA S. Reliable network design problem: case with uncertain demand and total travel time reliability[J]. Journal of the Transportation Research Record, 2006, 1964(1): 8l?90.

[7] CHOOTINAN P, WONG S C, CHEN A. A reliability-based network design problem[J]. Journal of Advanced Transportation, 2005, 39(3): 247?270.

[8] 陸化普, 蔚欣欣, 卞長志. 發生吸引量不確定的離散交通網絡設計模型[J]. 統計與決策, 2011(6): 8?12.LU Huapu, WEI Xinxin, BIAN Changzhi. Discrete traffic network design model under attracting quantity uncertainty[J]. Statistics and Decision, 2011(6): 8?12.

[9] 陸化普, 蔚欣欣, 卞長志. OD需求不確定的離散交通網絡設計模型研究[J]. 公路交通科技, 2011, 28(5): 128?132. LU Huapu, WEI Xinxin, BIAN Changzhi. Model and algorithm of discrete network design problem under OD demand uncertainty[J]. Journal of Highway and Transportation Research and Development, 2011, 28(5): 128?132.

[10] 蒲云, 劉海旭. 基于部分隨機用戶均衡的可靠性網絡設計[J]. 西南交通大學學報, 2011, 46(2): 321?325. PU Yun, LIU Haixu. Reliable network design based on partial stochastic user equilibrium[J]. Journal of Southwest Jiaotong University, 2011, 46(2): 321–325.

[11] CHEN A, KIM J Y, LEE S, et al. Models and algorithm for stochastic network designs[J]. Tsinghua Science and Technology, 2009, 14(3): 341?351.

[12] XU Tianze, WEI Heng, WANG Zhuande, et al. Study on continuous network design problem using simulated annealing and genetic algorithm[J]. Expert Systems with Applications, 2009, 36(2): 2735?2741.

[13] YIN Yafeng. Multiobjective bi-level optimization for transportation planning and management problems[J]. Journal of Advanced Transportation, 2002, 36(1): 93?105.

[14] CHEN A, ZHOU Zhong, CHOOTIANA P, et al. Optimizing capacity reliability and travel time reliability in the network design problem[C]// Proceedings of the 12th International Conference of Hong Kong Society for Transportation Studies. Hong Kong, China, 2007: 223?232.

[15] 陸化普, 李銳, 蔚欣欣. 供給與需求不確定的離散交通網絡設計模型[J]. 東南大學學報(自然科學版), 2012, 42(6): 1221?1226. LU Huapu, LI Rui, WEI Xinxin. Discrete traffic network design model under supply and demand uncertainty[J]. Journal of Southeast University(Natural Science Edition), 2012, 42(6): 1221?1226.

[16] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi?objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182?197.

(編輯 陳燦華)

Network design of multi-objective continuous equilibrium with stochastic demand

FANG Wenbin1, WANG Tao2, HUANG Ruqing2, HUANG Zhongxiang1, ZENG Ling1

(1. School of Traffic and Transportation Engineering, Changsha University of Science and Technology, Changsha 410004, China;2. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

To investigate the impacts of multi-objective characteristics and the uncertain traffic demands on road network design, a bi-level programming model for the continuous equilibrium network design with multiple objectives was proposed with the assumption that the OD(origin destination) demands followed the bilaterally truncated normal distribution. The upper-model was a multi-objective programming model with the minimum expected network travel time, the maximum reliability of network service level and the minimum investment budget. The lower-level model was a user equilibrium distribution model. A multi-objective genetic algorithm was employed to solve the problem based on the Monte Carlo simulation. A small-scale network was used to demonstrate the validity of the model and the algorithm. The results show that the multi-objective continuous equilibrium network design model can measure some indicators comprehensively, and obtain as many non-inferior solutions as possible for decision makers to choose. There is a clear correlation between the objectives. In particular, the investment has significant marginal diminished effect, and should be used together with traffic management measures.

continuous equilibrium network design; multi-objective programming; bi-level programming; service level reliability; non-dominated sorting genetic algorithm-II

10.11817/j.issn.1672-7207.2018.09.031

U491

A

1672?7207(2018)09?2350?06

2017?10?15；

2017?12?16

國家自然科學基金資助項目(51338002，51208064)；湖南省研究生科研創新項目(CX2015B342) (Projects(51338002, 51208064) supported by the National Natural Science Foundation of China; Project(CX2015B342) supported by the Research and Innovation Program of Graduate Students in Hunan Province)

黃中祥，教授，博士生導師，從事交通運輸規劃研究；E-mail: mehzx@126.com