Nonlinear Pricing on Transportation Networks

Under nonlinear road pricing (or tolling), the price charged is not strictly proportional to the distance travelled inside a tolling area, the generalized travel cost is not link-wise additive, and finding a user equilibrium distribution is typically formulated as a complementarity problem. The latter is a difficult problem to solve in mathematical programming. In this paper, we use piecewise linear functions to determine tolls and show that finding a user equilibrium distribution with such functions can be formulated as a convex optimization problem that is based on path flows and solvable by traditional algorithms such as simplicial decomposition. For area-based and two-part pricing schemes, the tolling function consists of only one linear piece and finding a user equilibrium distribution reduces to a convex optimization problem formulated in terms of link flows and solvable by any software for linearly constrained convex programs.To find an optimal pricing scheme, e.g., one that maximizes the social benefit, we formulate the problem as a mathematical program with equilibrium constraints, an optimization problem that is generally non-convex and difficult to solve. However, it is possible to use search algorithms to find an optimal scheme because the number of parameters in our piecewise linear function is few. To illustrate, we use a coordinate search algorithm to find an optimal two-part pricing scheme for a small network with randomly generated data.