The Network Pricing Problem with congestion

Abstract

The Network Pricing Problem (NPP) is a bilevel network optimisation problem where prices have to be set on the arcs of a network in order to maximise the profit of the arcs’ owner. The bilevel structure of the NPP implies that these prices will be influenced by the distribution on the network of one or more users that want to travel on it at the minimum cost. The NPP usually assumes that arc costs are independent of flows. When arc costs do depend on flows, the network is usually referred to as congested. In the present work, we illustrate two asymptotically converging algorithms to solve the NPP in the case of congested networks, hereafter referred to as the Congested Network Pricing Problem (CNPP). In particular, we propose to identify an equilibrium point for the CNPP using the Frank-Wolfe algorithm by reformulating the bilevel CNPP into a sequence of approximating single level linear problems. One of the algorithms uses these linear approximations to solve only the second level problem (that is, the problem of the users) while the other applies the linearisation procedure to the whole CNPP.