Two Types Of Traffic Equilibrium Models And Fast Algorithms Under Uncertainties

Traffic equilibrium is a classical problem in the traffic theory. Research on traffic equilibrium aims to analyze the pattern of stable traffic flow and hence provides a solid basis for the managers of transportation sector making decisions. In the long-term developing process, there are two main models in traffic equilibrium, which are UE (The User Equilibrium) and SUE (The Stochastic User Equilibrium). In1952, Wardrop proposed the principal (UE) of static equilibrium. It assumes that motorists driving between a given origin and a given destination with clear route cost are likely to choose the route with the shortest travel time. Based on this principal, a stable condition is reached only when no motorist can reduce his or her travel expenses any more by unilaterally changing routes. Ever since the principal was proposed, the Wardrop’s equilibrium has various extensions and wide-range applications, an extension of Wardrop equilibrium is Robust Wardrop (RW) which includes some stochastic factors processed by robust method replacing estimation of distribution. In1982, Sheffi proposed SUE model which is based on the utility theory and the probability theory. With different distributes of random variables, SUE includes two models called Logit with Gumbel distribution and Probit with Normal distribution. SUE shows that the traffic equilibrium would be reached if all of motorists could not improve their perceived travel time based on estimation of routes cost.In this paper, we analyze properties and algorithms of RW and SUE. For the RW problem, we replace the box constrains representing uncertain factors in traffic network by the ball constrains to improve the conservative degree. Furthermore, we relax the RW model to a SDP via a semi-definite programming (SDP) relaxation, which is an effective way for traffic equilibrium under uncertainties. For the SUE problem, it can be represented by a non-convex programming and solved by the traditional MSA (Method of Successive Average) algorithm. However, a fixed step size and a simple descent direction of MSA result in low rate of convergence. To improve these issues, we transform the original programming from non-convex into convex by exchanging variables and use the PR (Polak-Ribiere) conjugate gradient algorithm to solve the new equivalent convex programming.