连续交通网络设计的全局双层多项式优化模型

提出了一种面向典型连续交通网络设计问题的全局双层多项式优化模型，其函数均为多项式，且下层问题为凸问题；上层问题旨在优化网络性能，下层问题用来刻画确定性用户均衡(DUE)交通流模式；利用Fritz John条件和乘子代替下层规划，将提出的双层多项式优化模型转换为等价单层优化问题，并利用矩半定规划(MSDP)方法得到其全局最优解；利用矩矩阵的秩作为保证全局最优性的充分条件，并估计全局最优解的个数；给出了最优道路收费问题的数值算例，用提出的双层多项式优化模型描述了算例中的最优道路收费问题，并通过Wardrop用户均衡约束调整现有路段上的交通流量，使总通行费收益最大化。研究结果表明:该简单算例的最大收益为13.5元，同时可以得到该算例的矩矩阵的秩为1，从而证明了该结果的全局最优性，提出的方法克服了均衡约束数学规划(MPEC)法和值函数法等现有求解双层优化问题的经典算法由于连续交通网络设计固有的非凸性，只能找到局部最优的问题；提出的全局双层多项式优化模型与算法为典型连续交通网络设计提供了更好的探索工具。 

Global bilevel polynomial optimization model for continuous traffic network design

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.