Model And Algorithm For Asymmetric Traffic Network Optimization Problems

The behavior of human society is closely related to traffic and the appearance of the automobile made the whole transportation pattern produce tremendous change. Traffic industry development has greatly promoted the process of human society. At the same time, limited traffic resources and backward traffic management has seriously restricted the sustainable development of economy. How to solve and alleviate the traffic jam in the city and the associated environmental pollution and safety has become a worldwide difficult problem.In the most of research achievements, assuming that the link travel time in traffic network is only related to the link flow itself, the Jaccobi matrix of link flow travel function is diagonal matrix. In this situation, traffic assignment problem was formulated as mathematical program and network equilibrium design problem was formulated as bi-level program. As far as a real urban traffic road network is concerned, the link flow and travel cost are influenced by own flow, neighboring link flow, opposite link flow and the capacity of the relating link flow signal-controlled junctions. For example, in signal-controlled junction, crowed downstream link will lead to that the own link travel time become longer. In fact, for crowed city traffic network, this effect is often asymmetric, that is, the Jaccobi matrix of link flow travel time function is asymmetric. At this time, traffic assignment problem can not be formulated as mathematical program and network equilibrium design problem can not be formulated as bi-level program. So it is more reasonable and significant for studying traffic assignment problem and network equilibrium design problem in the asymmetric traffic network. In this paper, we have studied how to formulate models and design algorithms for asymmetric traffic assignment problem based on stochastic user equilibrium and user equilibrium and asymmetric traffic network equilibrium design problem with overall consideration of signal setting of junctions, link expansions and network reserve capacity.For asymmetric traffic assignment problem, two kinds of situations are considered, which are stochastic user equilibrium and user equilibrium. Firstly, variational inequality model is formulated for stochastic user equilibrium and the traffic flows corresponding with solutions are proved to follow Logit assignment principle. And then the variational inequality model of stochastic user equilibrium traffic assignment with elastic demand is further derived.Secondly nonlinear complementariy problem model is presented for Wardrop user equilibrium assignment with turning delay. The traffic flows corresponding with optimal solutions are proved to follow Wardrop user equilibrium principle and the results of existence and uniqueness of solution are presented. Then a modified FBTRA algorithm is designed which makes full use of the convergence of trust region based on FB function and the advantage of dealing with large-size road network of column generation method.Thirdly, for the asymmetric user equilibrium traffic assignment traffic assignment problem with link capacity, a variational inequality problem is constructed. The traffic flows corresponding with optimal solutions are proved to satisfy Wardrop user equilibrium principle and the optimal multiplier variables are exactly the queuing delay of juctions. Homotopy equations of variational inequality are constituted and homotopy solution curve is analyzed. The optimal solution can be received by following combined homotopy curve with convergent predictor-corrector algorithm and the convergence of algorithm is fully proved.On the other hand, mathematical program with equilibrium constraints and feasibly descent algorithm are studied asymmetric traffic network design problems with considering signal setting, link capacity expansion and network reserve capacity on two kinds of aforementioned situations. For asymmetric network design problem based on stochastic user equilibrium, because the solution set of variational inequality is singleton, the gradient of link flow variable about the parameters of signal setting, link expansion and reserve capacity can be computed by sensitivity analysis of KKT condition of variational inequality. With the results of sensitivity analysis, mathematical program with equilibrium constraints can be viewed as an implicit program. Although unable to obtain the specific expression of the objective function, the gradient about the parameters of signal setting, link expansion and reserve capacity can be easily obtained. Owing to this gradient, a feasible and descent direction can be attained and a feasibly descent algorithm is proposed for mathematical program with equilibrium constraints.For asymmetric network design problem based on user equilibrium, the solutions of variational inequality model are set-valued mapping. With the sensitivity analysis of parametric varitional inequality, the generalized gradient can be received by solving a linearly variational inequality. On the analogy of stochastic user equilibrium, a feasibly descent algorithm based on generalized gradient can be developed.