Finding optimal trajectories for multiple traffic demands in a congested network is a challenging task. To address this problem we consider a dynamical formulation of optimal transport that considers conductivities and fluxes, in analogy with electrical or hydraulic networks.
This formulation has been used extensively to study routing in transportation networks, leaf venations or transport in blood vessels. The standard formulation has also been extended to a multi-commodity scenario where multiple traffic demands are considered to model fluxes of different types, while sharing a unique set of conductivities. While this has been effective to model different traffic scenarios, e.g. congested or distributed, its standard formulation does not account for constraint that would make some problems more realistic. For instance, roads have a limited capacity of vehicles passing at the same time, or networks managers have budget constraints that limit the total amount of edges that can be built.
Here we propose an approach to incorporate constraints on conductivities that allows to incorporate arbitrary constraints (e.g. linear or non-linear, local or global) flexibly and efficiently.
The key idea is to lift the constraints from a position level to a velocity level using geometric insights that have been used in machine learning to solve other constrained optimization problems.
The modelling of constraints on a velocity level leads to a sparse, local and linear approximation of the feasible set, which in many cases, allows for a closed-form update rule,
despite the fact that the feasible set is complex. In this talk we will introduce the general formalism and show how this applies in few relevant examples.