Global bilevel polynomial optimization model for continuous traffic network design
Article Text (Baidu Translation)
-
摘要: 提出了一种面向典型连续交通网络设计问题的全局双层多项式优化模型，其函数均为多项式，且下层问题为凸问题；上层问题旨在优化网络性能，下层问题用来刻画确定性用户均衡(DUE)交通流模式；利用Fritz John条件和乘子代替下层规划，将提出的双层多项式优化模型转换为等价单层优化问题，并利用矩半定规划(MSDP)方法得到其全局最优解；利用矩矩阵的秩作为保证全局最优性的充分条件，并估计全局最优解的个数；给出了最优道路收费问题的数值算例，用提出的双层多项式优化模型描述了算例中的最优道路收费问题，并通过Wardrop用户均衡约束调整现有路段上的交通流量，使总通行费收益最大化。研究结果表明：该简单算例的最大收益为13.5元，同时可以得到该算例的矩矩阵的秩为1，从而证明了该结果的全局最优性，提出的方法克服了均衡约束数学规划(MPEC)法和值函数法等现有求解双层优化问题的经典算法由于连续交通网络设计固有的非凸性，只能找到局部最优的问题；提出的全局双层多项式优化模型与算法为典型连续交通网络设计提供了更好的探索工具。Abstract: A global bilevel polynomial optimization model for a typical continuous traffic network design problem was proposed. In this model, all the functions are polynomials, and the lower-level problem is a convex problem. The upper-level problem is to optimize the network performance, and the lower-level problem is to characterize the traffic flow pattern of the deterministic user equilibrium (DUE). The bilevel polynomial optimization model was transformed into an equivalent single-level optimization problem by replacing the lower-level programming with the Fritz John conditions and multipliers, and then the moment semi-definite programming (MSDP) method was employed to obtain its global optimal solutions. The ranks of moment matrices were taken as sufficient conditions to guarantee the global optimality and were used to estimate the number of global optimal solutions. Moreover, a numerical example for the optimal toll problem was given, and the optimal toll problem was depicted by the proposed bilevel polynomial optimization model. The total toll revenue was maximized by adjusting the traffic flow on the existing road sections under the Wardrop user equilibrium constraint. Research results reveal that the maximum revenue in this simple example is 13.5 yuan, and meanwhile, the rank of the moment matrix for the example is 1, which proves the global optimality of the results. The classical approaches to solving the bilevel optimization problem, such as the mathematical program with equilibrium constraints (MPEC) and value function methods, can only find local optimal solutions due to the inherent nonconvexity in the continuous traffic network design. However, the proposed approach overcomes the problem existing in classical algorithms, and the proposed global bilevel polynomial optimization model and algorithm provide a better exploration tool for a typical continuous traffic network design. 2 figs, 37 refs.
-
[1] FARAHANI R Z, MIANDOABCHI E, SZETO W Y, et al. A review of urban transportation network design problems[J]. European Journal of Operational Research, 2013, 229(2): 281-302. doi: 10.1016/j.ejor.2013.01.001 [2] BOYCE D E. Urban transportation network-equilibrium and design models: recent achievements and future prospects[J]. Environment and Planning A: Economy and Space, 1984, 16(11): 1445-1474. doi: 10.1068/a161445 [3] MAGNANTI T L, WONG R T. Network design and transportation planning: models and algorithms[J]. Transportation Science, 1984, 18(1): 1-55. doi: 10.1287/trsc.18.1.1 [4] FRIESZ T L. Transportation network equilibrium, design and aggregation: key developments and research opportunities[J]. Transportation Research Part A: General, 1985, 19(5/6): 413-427. [5] MIGDALAS A. Bilevel programming in traffic planning: models, methods and challenge[J]. Journal of Global Optimization, 1995, 7(4): 381-405. doi: 10.1007/BF01099649 [6] YANG Hai, 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. doi: 10.1080/01441649808717016 [7] XU Xiang-dong, CHEN A, YANG Chao. A review of sustainable network design for road networks[J]. KSCE Journal of Civil Engineering, 2016, 20(3): 1084-1098. doi: 10.1007/s12205-016-1729-1 [8] MENG Qiang, YANG Hai. Benefit distribution and equity in road network design[J]. Transportation Research Part B: Methodological, 2002, 36(1): 19-35. doi: 10.1016/S0191-2615(00)00036-9 [9] GAO Zi-you, SUN Hui-jun, ZHANG Hao-zhi. A globally convergent algorithm for transportation continuous network design problem[J]. Optimization and Engineering, 2007, 8(3): 241-257. doi: 10.1007/s11081-007-9015-1 [10] WANG D Z W, LO H K. Global optimum of the linearized network design problem with equilibrium flows[J]. Transportation Research Part B: Methodological, 2010, 44(4): 482-492. doi: 10.1016/j.trb.2009.10.003 [11] YANG Hai, BELL M G H. A capacity paradox in network design and how to avoid it[J]. Transportation Research Part A: Policy and Practice, 1998, 32(7): 539-545. doi: 10.1016/S0965-8564(98)00017-2 [12] CHIOU S W. A hybrid approach for optimal design of signalized road network[J]. Applied Mathematical Modelling, 2008, 32(2): 195-207. doi: 10.1016/j.apm.2006.11.007 [13] YANG Hai. Sensitivity analysis for the elastic-demand network equilibrium problem with applications[J]. Transportation Research Part B: Methodological, 1997, 31(1): 55-70. doi: 10.1016/S0191-2615(96)00015-X [14] YANG Hai, SASAKI T, ⅡDA Y, et al. Estimation of origin -destination matrices from link traffic counts on congested networks[J]. Transportation Research Part B: Methodological, 1992, 26(6): 417-434. doi: 10.1016/0191-2615(92)90008-K [15] YANG Hai. Heuristic algorithms for the bilevel origin-destination matrix estimation problem[J]. Transportation Research Part B: Methodological, 1995, 29(4): 231-242. doi: 10.1016/0191-2615(95)00003-V [16] BEN-AYED O, BLAIR C E. Computational difficulties of bilevel linear programming[J]. Operations Research, 1990, 38(3): 556-560. doi: 10.1287/opre.38.3.556 [17] NIE Jia-wang, WANG Li, YE J J, et al. A Lagrange multiplier expression method for bilevel polynomial optimization[J]. SIAM Journal on Optimization, 2021, 31(3): 2368-2395. doi: 10.1137/20M1352375 [18] BEN-AYED O, BLAIR C E. Computational difficulties of bilevel linear programming[J]. Operations Research, 1990, 38(3): 556-560. doi: 10.1287/opre.38.3.556 [19] LAMPARIELLO L, SAGRATELLA S. A bridge between bilevel programs and Nash games[J]. Journal of Optimization Theory and Applications, 2017, 174(2): 613-635. doi: 10.1007/s10957-017-1109-0 [20] 高自友, 张好智, 孙会君. 城市交通网络设计问题中双层规划模型、方法及应用[J]. 交通运输系统工程与信息, 2004, 4(1): 35-44. doi: 10.3969/j.issn.1009-6744.2004.01.009GAO Zi-you, ZHANG Hao-zhi, SUN Hui-jun. Bi-level programming models, approaches and applications in urban transportation network design problems[J]. Communication and Transportation Systems Engineering and Information, 2004, 4(1): 35-44. (in Chinese) doi: 10.3969/j.issn.1009-6744.2004.01.009 [21] ABDULAAL M, LEBLANC L J. Continuous equilibrium network design models[J]. Transportation Research Part B: Methodological, 1979, 13(1): 19-32. doi: 10.1016/0191-2615(79)90004-3 [22] MARCOTTE P. Network optimization with continuous control parameters[J]. Transportation Science, 1983, 17(2): 181-197. doi: 10.1287/trsc.17.2.181 [23] DAVIS G A. Exact local solution of the continuous network design problem via stochastic user equilibrium assignment[J]. Transportation Research Part B: Methodological, 1994, 28(1): 61-75. doi: 10.1016/0191-2615(94)90031-0 [24] MIRRLEES J A. The theory of moral hazard and unobservable behaviour: Part Ⅰ[J]. The Review of Economic Studies, 1999, 66(1): 3-21. doi: 10.1111/1467-937X.00075 [25] DEMPE S, DUTTA J. Is bilevel programming a special case of a mathematical program with complementarity constraints?[J]. Mathematical Programming, 2012, 131(1/2): 37-48. [26] YE J J, ZHU Dao-li. Optimality conditions for bilevel programming problems[J]. Optimization, 1995, 33(1): 9-27. doi: 10.1080/02331939508844060 [27] YE J J, ZHU Dao-li. New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches[J]. SIAM Journal on Optimization, 2010, 20(4): 1885-1905. doi: 10.1137/080725088 [28] MENG Q, YANG H, BELL M G H. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem[J]. Transportation Research Part B: Methodological, 2001, 35(1): 83-105. doi: 10.1016/S0191-2615(00)00016-3 [29] LI Chang-min, YANG Hai, ZHU Dao-li, et al. A global optimization method for continuous network design problems[J]. Transportation Research Part B: Methodological, 2012, 46(9): 1144-1158. doi: 10.1016/j.trb.2012.05.003 [30] JEYAKUMAR V, LASSERRE J B, LI G, et al. Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems[J]. SIAM Journal on Optimization, 2016, 26(1): 753-780. doi: 10.1137/15M1017922 [31] PARRILO P A. Semidefinite programming relaxations for semialgebraic problems[J]. Mathematical Programming, 2003, 96(2): 293-320. doi: 10.1007/s10107-003-0387-5 [32] LASSERRE J B. Global optimization with polynomials and the problem of moments[J]. SIAM Journal on Optimization, 2001, 11(3): 796-817. doi: 10.1137/S1052623400366802 [33] CURTO R E, FIALKOW L A. Recursiveness, positivity, and truncated moment problems[J]. Houston Journal of Mathematics, 1991, 17(4): 603-635. [34] STURM J F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[J]. Optimization Methods and Software, 1999, 11(1/2/3/4): 625-653. [35] TÜTÜNCÜ R H, TOH K C, TODD M J. Solving semidefinite -quadratic-linear programs using SDPT3[J]. Mathematical Programming, 2003, 95(2): 189-217. doi: 10.1007/s10107-002-0347-5 [36] HENRION D, LASSERRE J B. Detecting global optimality and extracting solutions in GloptiPoly[M]//HENRION D, GARULLI A. Positive Polynomials in Control: Lecture Notes in Control and Information Science. Berlin: Springer, 2005: 293-310. [37] 张小宁. 双层优化交通模型及其算法[J]. 同济大学学报(自然科学版), 2005, 33(2): 169-173. doi: 10.3321/j.issn:0253-374X.2005.02.007ZHANG Xiao-ning. Bi-level optimization in transportation analysis[J]. Journal of Tongji University (Natural Science), 2005, 33(2): 169-173. (in Chinese) doi: 10.3321/j.issn:0253-374X.2005.02.007 -
下载:
点击查看大图
图(2)
计量
- 文章访问数: 851
- HTML全文浏览量: 276
- PDF下载量: 93
- 被引次数: 0
