The problem of designing a congestion pricing system, assuming that the road users are distributed according to a static user equilibrium, is commonly formulated as a bi-level program, with the toll locations and toll levels being the decision variables. The upper level objective is to maximize the social surplus, and on the lower level a convex program is solved to obtain the road users response to the toll level solution. This optimization problem is both non-convex and non-smooth and therefore difficult to solve for a global optimum.
For one special case, when all links are tollable and when there are no restrictions on the toll levels, the bi-level program can be formulated as a convex program which can easily be solved, with one optimal solution, among possibly several ones, equal to marginal cost pricing tolls (MSCP). With MSCP tolls, the road users are charged a toll on each congested road segment equal to the marginal increase in total travel cost incurred by one additional road user on the road segment. Any solution which maximizes the social surplus functions is referred to as a first-best toll level solution (as opposed to second-best when there are restrictions on toll locations and/or toll levels) with system optimal link flows and demands. While there may exist several first-best toll level solutions, they all satisfy the principle of MSCP on a route level, if the demand in the traffic network is elastic. This result has previously in the literature been used to devise a set of feasible toll vectors which all result in system optimal flows and demands.
In this paper the set of feasible first-best toll vectors is relaxed to allow second-best solutions. The relaxation is performed on a route level, and the deviation from first-best route tolls is penalized. The objective then becomes to minimize the penalty, weighted by some factor to reflect each routes importance. The optimization problem either takes the form of a linear program (LP), if the toll locations are fixed, or a mixed integer linear program (MILP), if the toll locations are variable. For solutions with optimal objective function value close to zero, the toll level solution will be close to the global maximizer of the social surplus function. As the number of tollable links is reduced, the true equilibrium demands and link flows may differ from the system optimal ones. Thus, the performance of the approach can be assumed to be dependent of the number of tollable links. Numerical results show that the approach can give valuable information on close to optimal toll locations and toll levels, even when a small subset of the links are tollable.