A new approach to robust transportation over networks

Abstract—We consider transporting a mass on a given directed graph. The mass is initially concentrated on certain nodes and needs to be transported in a certain time period to another set of nodes, typically disjoint from the first. We seek a transport plan which is robust with respect to links and nodes failure. In order to achieve that, we need our mass to spread over time on all available routes between source and sink nodes as much as the topology of the graph allows. The scheduling consists in selecting transition probabilities for a Markovian evolution which is designed to be consistent with given initial and final marginal distributions. In order to construct such a transportation plan, we set up a maximum entropy problem (Schro ̈dinger bridge problem) for probability laws on paths which can be viewed as an atypical stochastic control problem. To achieve robustness, we employ a prior distribution on paths which allocates equal probability to paths of equal length connecting any two nodes namely the Ruelle-Bowen random walker (MRB). The latter is also shown to be itself the time- homogeneous solution of a maximum entropy problem for (unnormalized) measures on paths. Since the optimal transport plan is computed via a Schro ̈dinger bridge like problem, for which an efficient iterative algorithm is available [1], our approach appears also computationally attractive. We provide a few examples which illustrate the effectiveness of this method. While in this paper, we only consider strongly connected graphs, in a forthcoming journal paper [2], we show that our approach can be readily extended to not strongly connected graphs and weighted graphs. In the latter case, this strategy may be used to design a transportation plan which effectively compromises between robustness and other criteria such as cost.