November 19, 2014, 11:00, Room GC B3 424 (click here for the map)
We consider the problem of setting profit-maximizing tolls on a subset of arcs of a multicommodity transportation network. The case where users are assigned to cheapest paths, which is naturally formulated as an NP-hard bilevel program, has been extensively studied and will serve as the background for an extension where user assignment is performed according to a discrete choice model of the logit family. Following a description of the model and its theoretical properties, we develop an algorithmic framework for determining a near-optimal solution of this nonconvex problem, based on a variety of approximations involving mixed integer programs, either linear or quadratic. Through a battery of tests performed on a variety of network topologies, we reach the conclusion that very crude approximations (that scale well) perform surprisingly well.
Professor at the department of computer science and operations research of the University of Montreal, Patrice Marcotte has published over 80 articles related to network design, variational inequalities, bilevel programming, network pricing and revenue management, traffic assignment, and badminton. He his also the author of two guides and a large website devoted to cycling, and currently sits on the editorial board of the following journals: Operations Research, Transportation Science, Journal of Optimization Theory and Applications, Operations Research Letters, European Journal of Combinatorial Optimization.