A Heuristic Algorithm to Solve Bilevel Toll Optimization Problems by Vyacheslav Kalashnikov

During the early years of industrial development, the production facilities were established near the consumers because the transportation was expensive, time-consuming, and risky. When transportation systems appeared, they allowed the producer to compete in distant markets, promoting economies of scale by increasing sales volume.

Due to the complexity of products and globalization, supply and distribution chains have grown enormously, therefore, logistics costs have “rocketed up” sharply. According to the data from the IMF (International Monetary Fund), logistics costs represent 12% of gross national product, and they range from 4% to 30% of the sales at the enterprise level.

Because of this growth, many countries have attached great importance to the development and modernization of the infrastructure to achieve greater participation in the global economy. There are organizations that deal with the development of communications and transportation infrastructure, building technologies to increase the coverage, quality and competitiveness of the infrastructure. In North America, administration of new (private) roads is commonly conceded to private companies, state governments, or financial institutions (banks, holdings, etc.), who set transportation tolls in order to retrieve money from the drivers.

It has been recently noticed that under the concession model, there is less traffic flow using these tolled highways. One of the strategies taken to increase the use of toll roads is the regulation of tolls (pass rates). However, what are the appropriate criteria to assign these?

Hence, this is the problem of assigning optimal tolls to the arcs of a multi-commodity transportation network. The toll optimization problem (TOP) can be formulated as a bilevel mathematical program where the upper level is managed by a firm (private or public) that raises revenues from tolls set on (some) arcs of the network, and the lower level is represented by a group of users traveling along the cheapest paths with respect to a generalized travel cost. The problem can be interpreted as finding a trade-off among tolls generating high revenues and those attractive for the users.

This talks presents an algorithm based on the allowable ranges to stay optimal (ARSO) resulting from sensitivity (post-optimal) analysis after solving the lower level problem. With this powerful tool, one can analyze possible changes in the coefficients of some variables in the objective function within these allowed ranges that do not affect the optimal solution.

In addition to dealing with the allowable ranges, the proposed technique also uses the concept of “filled function”, which is applied under the assumption that the local maximum (in our case) has been found. Then the “filled function” technique helps one either find another local maximum, better than the previous ones, or determine that we have found the best feasible optimal solution, according to certain parameters of tolerance.


The validity and reliability of this technique are illustrated by the results of numerical experiments with test examples used to compare the proposed approach with the existing ones. The reported numerical results also confirm the robustness of the present algorithm.