具有遗憾值约束的鲁棒性交通网络设计模型研究

摘要/Abstract

摘要：

由于交通网络设计决策的长期性，许多参数会随时间而变化，因此在鲁棒性交通网络设计问题中考虑不确定性因素至关重要。当OD需求不确定时，同时考虑期望行程时间和最大遗憾值，引入一种新的鲁棒性度量标准，将α鲁棒解的概念应用到交通网络设计问题中，提出了一种具有遗憾值约束的鲁棒性交通网络设计模型。然后设计遗传算法求解模型，得出不同遗憾值下网络设计的最佳方案。最后，以Nguyen-Dupius网络作为算例证明了遗传算法求解鲁棒性问题的有效性。详细分析了期望行程时间与最大遗憾值之间的权衡关系，权衡曲线表明最大遗憾值的降低并不一定导致期望行程时间的较大增加；并将鲁棒优化模型与随机优化模型作比较，结果表明鲁棒优化模型比随机优化模型更能规避不确定性带来的风险。

关键词: 系统工程, 交通网络设计, 遗传算法, 鲁棒优化, 遗憾值

Abstract:

Based on longterm transportation network design decisions and potential parameter variations, it is important that demand uncertainty is considered in transportation modeling. In this paper, we present a novel robustness measure that combines the two objectives by minimizing the expected travel time while bounding the relative regret in each scenario facing uncertain origindestination demand (OD demand). The concept of α-robust solution is introduced into the transportation network design problem. We propose a robust transportation network design model with regret value constraints, then design an algorithm based on the genetic algorithm to solve the problem and obtain the optimal solutions for different regret values. Finally, numerical results based on the Nguyen-Dupuis network validate the effectiveness of the algorithm. While detailed analysis on trade-offs, between the expected travel time and the maximum regret value, shows that large reductions in maximum regret do not necessarily result in a great increase in expected travel time. Meanwhile, we compared the robust model presented with the stochastic model and numerical examples demonstrate that the robust planning network is more reliable and less risky than the stochastic model if demand uncertainty is considered in modeling.

Key words: system engineering, traffic network design, genetic algorithm, robust optimization, regret value

中图分类号:

U491

刘慧，杨超，杨珺. 具有遗憾值约束的鲁棒性交通网络设计模型研究[J]. 交通运输系统工程与信息, 2013, 13(5): 86-92.

LIU Hui, YANG Chao, YANG Jun. Robust Transportation Network Design Modeling with Regret Value[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5): 86-92.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18650.shtml

http://www.tseit.org.cn/CN/Y2013/V13/I5/86

参考文献

[1]Unnikrishnan A, Lin D Y. User equilibrium with recourse: continuous network design problem [J]. ComputerAided Civil and Infrastructure Engineering, 2012, 27(7): 512-524.

[2]Chiou S. Bilevel programming for the continuous transport network design problem [J]. Transportation Research, 2005, 39(4): 362-383.

[3]Davis G A. Exact local solution of the continuous network design problem via stochastic user equilibrium assignment [J]. Transportation Research, 1994, 28(1): 61-75.

[4]Farvaresh H, Sepehri M. A single-level mixed integer linear formulation for a bi-level discrete network design problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(5): 623-640.

[5] Xu T Z, Wei H, Hu G H. Study on continuous network design problem using simulated annealing and genetic algorithm[J]. Expert Systems with Applications, 2009, 36(2): 1322-1328.

[6]Ukkusuri S V, Mathew T V, Waller S T. Robust transportation network design under demand uncertainty [J]. ComputerAided Civil and Infrastructure Engineering, 2007, 22(1): 6-18.

[7]Ukkusuri S V, Patil P. Multiperiod transportation network design under demand uncertainty[J]. Transportation Research Part B: Methodological, 2009, 43(6): 625-642.

[8]Chen A, Kim J Y, Lee S, et al. Stochastic multiobjective models for network design problem[J]. Expert Systems with Applications, 2010, 37(2): 1608-1619.

[9]Sharmal S, Ukkusuri S V, Mathew T V. Pareto optimalmultiobjective optimization for robust transportation network design problem [J]. Transportation Research Record: Journal of the Transportation Research Board, 2009, 2090: 95-104.

[10]Dimitriou L, Stathopoulos A. Reliable stochastic design of road network systems[J]. International Journal of Industrial and Systems Engineering , 2008, 3(5): 549-574.

[11]Yin Y, Madanat S M, Lu X. Robust improvement schemes for road networks under demand uncertainty [J]. European Journal of Operation Research, 2009, 198(2): 470-479.

[12]Chen A, Kim J, Zhou Z, et al.Alpha reliable network design problem[J]. Transportation Research Record, 2007, 2029: 49-57.

[13]Lou Y, Yin Y, Lawphongpanich S. A robust approach to discrete network designs with demand uncertainty [J]. Transportation Research Record , 2009, 2090: 86-94.

[14]Chootinan P, Wong S C, Chen A. A reliabilitybased network design problem[J]. Journal of Advanced Transportation, 2005, 39(3): 247-270.

[15]Karoonsoontawong A, Waller S T. Robust dynamic continuous network design problem [J]. Transportation Research Record, 2007, 2029: 58-71.

[16]Ng M, Waller S T. Reliable systemoptimal network design: convex meanvariance model with implicit chance constraints [J]. Transportation Research Record, 2009, 2090: 68-74.

[17]Chen A, Zhou Z, Chootinan P, et al. Transport network design problem under uncertainty: a review and new developments[J]. Transport Reviews: A Transnational Transdisciplinary Journal, 2011, 31(6): 743-768.

[18]孙华,高自友,龙建成. 不确定OD需求下连续交通网络设计的鲁棒优化模型[J]. 交通运输系统工程与信息, 2011, 11(2)：70-76. [SUN H, GAO Z Y, LONG J C. The robust model of continuous transportation network design problem with demand uncertainty[J]. Journal of Transportation System Engineering and Information Technology, 2011, 11(2): 70-76.]

[19]陆化普,蔚欣欣,卞长志. OD需求不确定的离散交通网络设计模型研究［J］. 公路交通科技, 2011, 28(5): 128-132. [LU H P, WEI X X, BIAN C Z. Model and algorithm of discrete network design problem under OD dem and uncertainty [J]. Journal of Highway and Transportation Research and Development, 2011, 28(5): 128-132.]

[20]Sheffi Y. Urban transportation networks: equilibrium analysis with mathematical programming methods[M]. PrenticeHall, Englewood Cliffs, NJ, 1985.

[21] Nguyen S, Dupius C. An efficient method for computing traffic equilibria in networks with asymmetric transportation costs [J]. Transportation Science, 1984, 18(2): 185-202.