| The optimal setting of prices, taxes or subsidies on goods and services can be naturally modeled as a bilevel program. Indeed, bilevel programming is an adequate framework for modeling optimization situations where a subset of decision variables is not controlled by the main optimizer (the leader), but rather by a second agent (the follower) who optimizes its own objective function with respect to this subset of variables. This master's thesis addresses the problem of setting profit-maximizing tolls on a congested transportation network involving several user classes. At the upper level, the firm (leader) sets tolls on a subset of arcs and strives to maximize its revenue. At the lower level, each user minimizes its generalized travel cost, expressed as a linear combination of travel time and out-of-pocket travel cost. We assume the existence of a probability density function that describes the repartition of the value of time (VOT) parameter throughout, the population. This yields a bilevel optimization problem involving a bilinear objective at the upper level and a convex objective at the lower level. Since, in this formulation, lower level variables are flow densities, it follows that the lower level problem is infinite-dimensional. We devise a two-phase algorithm to solve this nonconvex problem. The first phase aims at finding a good initial solution by solving for its global optimum a discretized version of the model. The second phase implements a gradient method, starting from the initial point obtained in the initial phase. |
