Tariff optimization in Networks

We consider the problem of determining a set of optimal tariffs for an agent in the network, who owns a subset of all the arcs, and who receives revenue by setting the tariffs on the arc he owns. Multiple rational clients are active in the network, who route their demands on the cheapest paths from source to destination. The cost of a path is determined by fixed costs and tariffs on the arcs of the path.We introduce a remodeling of the network, using shortest paths. We develop three algorithms, a path oriented mixed integer program and a known arc oriented mixed integer program. Combined with reduction methods this remodeling enables us to solve the problem to optimality, for quite large instances. We provide computational results for the methods developped and compare them with the results of the arc oriented mixed integer programming formulation of the problem, applied to the original network.