Bilevel Optimal Tolls Problems with Nonlinear Costs: A Heuristic Solution Method

We consider a bilevel programming problem modeling the optimal toll assignment as applied to an abstract network of toll and free highways. A public governor or a private lease company run the toll roads and make decisions at the upper level when assigning the tolls with the aim of maximizing their profits. The lower level decision makers (highway users), however, search an equilibrium among them while trying to distribute their transportation flows along the routes that would minimize their total travel costs subject to the satisfied demand for their goods/passengers. Our model extends the previous ones by adding quadratic terms to the lower level costs thus reflecting the mutual traffic congestion on the roads. Moreover, as a new feature, the lower level quadratic costs aren’t separable anymore, i.e., they are functions of the total flow along the arc (highway). In order to solve the bi-level programming problem, a heuristic algorithm making use of the sensitivity analysis techniques for quadratic programs is developed. As a remedy against being stuck at a local maximum of the upper level objective function, we adapt the well-known “filled function” method which brings us to a vicinity of another local maximum point. A series of numerical experiments conducted on test models of small and medium size shows that the new algorithm is competitive enough.