Congestion control with pricing in the absence of demand and cost functions: An improved trial and error method

Without the information of the origin-destination demand function and users' valuation for travel time saving, the precise estimation of the road tolls for various pricing schemes must go in a trial-and-error manner, as suggested by [2] and [15], and recently realized by [6, 7, 11, 22, 24]. For a trial of the tolls pattern, the responses of the users can be observed and used to update the toll pattern for the next trial. Since getting the responses of the users is expensive, it is desirable to use the acquired information exhaustively; That is, we need to make the method converge to an approximate solution of the problem within as little number of changes as possible.
   In this paper, we propose to update the link tolls pattern in an improved manner, where the profit direction is the combination of two known directions. This combined manner makes the method more efficient than the method using solely one of them. We prove the global convergence of the method under suitable conditions as those in [6, 7, 24]. Some preliminary computational results are also reported.