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.