| This thesis is concerned with the problem of identifying optimal tolls over a multi-commodity network. More precisely, we are interested in the situation whereby an economic agent, called the "Leader", seeks to maximize network revenue by imposing tolls on a subset of arcs, while taking into account the reaction of network users, called "Followers", who strive to transport products over the network at minimal cost.; We first propose an exact method based on a clever enumeration of the Follower's problem solutions. Improvements to the enumeration process also allow to identify better upper bounds on the Leader's revenue. Numerical results illustrate the performance of this approach, especially on instances where tolls are unconstrained.; Secondly, we present a local search algorithm and describe its integration into a tabu-search method. This algorithm exploits the underlying structure of the Follower's problem to more efficiently explore the solution space. The tabu-search method is shown to provide near-optimal (less than 1%) solutions within a very short computation time.; The great efficiency of our methods is achieved through the resolution of an inverse optimization problem. This formulation allows to quickly identify an optimal toll scheme given a known Follower's reaction. A column-generation approach is proposed to adress this problem and obtain better Follower's problem solutions. |
