Toll Optimization Problems with Quadratic Costs

We study a bilevel programming problem molding the optimal toll assignment related to a network of toll and free highways. A public operator or a private company running the toll roads make decisions at the upper level by alloting the tolls in order to maximize their profits. The lower level decision makers (highway users), instead, look for the equilibrium among them while attempting to arrange their transportation flows along the routes aiming at minimization of 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 this bilevel 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 modify the well-known "filled function" method which brings us to a neighborhood 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.