Research On The Efficiency Loss Of Traffic Networks Based On Stochastic Demands

As a complex giant system,the traffic network is subject to the limit of the urban's road resource on the one hand.On the other hand,if any management or control measures are absent in the system,the people's path choices are non-cooperative game processes.The travelers always pursue their own maximum profits,namely,they select the routes with minimum travel time,distance or cost.This leads to the user equilibrium,rather than the system optimal state.Therefore,the selfish route choice mechanism will give rise to the system efficiency loss.The studies on the relations between user equilibrium and system optimum are age-old.However,the quantitative analysis on the efficiency loss of the user equilibrium compared with system optimum only started from the studies of Roughgarden and Tardos in 2002.The authors proposed that if the link costs are all the polynomial functions of degree at most p,then the upper bound of the price of anarchy is a function ofp.Particularly,when the link costs are linear functions,the upper bound is 4/3.These discoveries led to people to rethink the relation between the user equilibrium and system optimum,and carried on extended researches from many aspects.This dissertation is the further study on the problem of system efficiency loss in theory:the one is to study the system efficiency loss in the case of stochastic demand from the demand viewpoint;the other is to study the effect of restricted tolls in improving the system efficiency from road pricing viewpoint.The main contents of this research are as follows:(1)Analyzing the effect of second-best road pricing in improving the system efficiency in the stochastic demand network.The corresponding price of anarchy upper bounds are provided,and the first-best road pricing are obtained.Let the link costs be the polynomial functions of degree at most p,then the specific expression of price of anarchy upper bounds are obtainded by using the analytical derivation,which generalizes the previous work.Some special cases are considered,for instance the demands follow log-normal distributions.The specific expressions of price of anarchy upper bound are obtainded,and the graphs shows that the upper bounds decreasing gradually as the road pricing tends to the optimal pricing.Secondly,two user equilibrium extend situations in the stochastic demand network are studied:(i)the expectations of the stochastic demands are elastic,and(ii)the links are interact.For the elastic expectation demand cases,the "weaker" upper bound is derived,which depends not only on the link costs function itself,but also the ratio between“user benefit”and"social surplus" at equilibrium state.For the second case,it is proved that a semidefinite programming determines the price of anarchy upper bound.(2)Proposing the notion of Cournot-Nash equilibrium in the stochastic demand network,the corresponding variational inequality is obtained.Motivated by the fixed demand case,proposing the notions of smooth and semi-smooth of game playing in stochastic demand setting,and the corresponding variational inequality is provided.On this basis,the general price of anarchy upper bounds of Cournot-Nash equilibrium are derived for any types of link costs function.Deriving the specific expressions of price of anarchy upper bounds in the case that link impedances are polynominal function and the demand follows log-nomal distribution.The graph shows that the upper bound tends to infinity as the maximum coefficient of variation tends to 0.51.Secondly,considering the efficiency gain problem of Cournot-Nash equilibrium when imposing tolls on links in the stochastic demand network.The optimal road pricing scheme which can minimize the efficiency loss is obtained.Finally,when the link costs are all the polynomial functions of degree at most p,the the optimal road pricing schemethe is derived.The function expression of optimal road pricing with regard to maximum coefficient of variation is obtained when p = 1,2,3.(3)Defining the route cost in the case that the demands are stochastic and the travelers are risk-averters.On this basis,the system optimum traffic assignment model and the user equilibrium variational inequlity model are provided in this case.Unlike the user equilibrium in the risk neutral case,the variational inequlity here is path-based,rather than link-based.This makes us are unable to follow the derivation for the classical user equilibrium directly to establish the corresponding price of anarchy upper bound.Therefore,some imporant properties of the aforementioned system optimum and the user equilibrium traffic assignment models are proposed.By using these properties,the geometry and convexity upper bounds of the inefficiency of the user equilibrium compared with system optimum are analytical derived.The specific expression of these two upper bounds are estiblished when the link costs are polynominal function.Finally,the comparative analysis between the geometry and convexity upper bounds in some special cases,such as log-normal demand distribution,single OD pair,and linear link cost function,respectively.(4)Studing the efficiency problem of the restricted toll scheme with fixed demand and heterogeneous users.Under mild conditions for the minimum and maxmum value of time,the price of anarchy upper bounds is obtained when imposing the restricted toll scheme with polynominal link cost function and heterogeneous users.The corresponding minimum upper bound are obtained when adopting the optimal tolls.The upper bounds are proved to be tight by a special case.Secondly,the efficiency problem of restricted toll scheme in the stochastic demand and homogeneous users network is explored,the corresponding price of anarchy upper bounds are derived.The function expression of price of anarchy upper bound with regard to maximum coefficient of variation and road pricing is obtained in the special log-normal distribution case.