Bilevel optimization for flow control in optimal transport networks

Links

• Abstract: PDF
• Slides: Bilevel optimization for flow control in optimal transport networks

Abstract

Increasing infrastructure robustness while also ensuring high efficiency of transport is a compelling organizing principle of transportation networks at all scales. Nevertheless, the interplay between these two quantities is often poorly understood. We study their relation by formulating a bilevel optimization problem, which can be interpreted as the competition between the objectives of greedy passengers and a network manager. Passengers aim at minimizing their origin-destination travel cost (lower-level problem), whereas the network manager aims at guaranteeing global infrastructural efficiency (upper-level problem) by mitigating traffic bottlenecks. The key is that the lower-level objective depends on parameters set at the upper-level. For instance, a manager can introduce tolls or capacity limits to force passengers to redirect to lower traffic. Hence, the need for a bilevel optimization framework that entangles the two settings. To solve the problem, we propose BROT (Bilevel Routing on networks with Optimal Transport), a method based on optimal transport theory for the lower-level problem, and exploit projected gradient descent to optimize the upper-level one, conditioned on the lower-level constraints. In particular, we leverage the formalism of capacitated networks, hence we treat passengers’ flows as electrical currents, to find efficient closed-form updates of the edge capacities—measuring the infrastructure size needed to allocate passengers—and their weights—the cost of travel. Our model admits a clear interpretation. On one side, greedy passengers travel along the shortest path while disregarding each other routes, hence high capacity is essential to allocate many passengers to central links of transportation infrastructures. On the other side, since congested links can lead to infrastructural failures, the network manager tunes the weights of the edges to incentivize passengers to move away from jammed connections. By updating weights and capacities alternatively with our method, we are able to obtain numerically topologies that trade-off between shortest-path but highly congested networks and distributed but longer-path networks. We validate our method on synthetic data and investigate several metrics to quantify the Pareto efficiency of BROT’s optimal solutions. We then show how this approach can be applied on real networks, which illustrates how decision-makers could be informed on how to design carbon-efficient infrastructures with high transportation performance.