We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial-time algorithm with a worst-case precision guarantee of (1/2) log m_T+1, where m_T denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached.

We provide a global heuristic for a class of bilevel programs with bilinear objectives and linear constraints. The algorithm relies on an interior point approach that can be seen as a combination of the smoothing and implicit programming techniques well known in the MPEC literature. But contrary to what is usually done, our focus is on global optimality. We tested the algorithm on large-scale instances of a network pricing problem, one of the main applications of this model. The results show that on hard instances, the heuristic is a good alternative to exact solvers based on mixed 0-1 programming formulations.

In this presentation, we study a pricing model that has two levels of decision making in a network. At the first level, the firm (leader) sets prices on a subset of arcs and strives to maximize its revenue. At the second level, the customers (follower) minimize their perceived travel which depends on the firm's decision and their value of time (VOT). We assume that this latter parameter follows a continuous random law. We demonstrate that if one discretizes the continuous density function for the VOT, our model becomes a finite dimensional bilevel program that can be solved using branch-and-cut techniques. We use the discretization in order to find a good solution and use the latter as a starting point in a subgradient method. Finally, we present some numerical results that show that our model can be solved, even when the density has two humps!

We present some decomposition approaches for toll optimization on large multicommodity transportation networks. A Benders decomposition approach where toll variables are kept in the master problem will be presented. We will discuss the impact of several branching and cut generation strategies on the computation time.