Robust Transport Over Networks
From MaRDI portal
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10)
Abstract: We consider transport over a strongly connected, directed graph. The scheduling amounts to selecting transition probabilities for a discrete-time Markov evolution which is designed to be consistent with certain initial and final marginals. The random evolution is selected to be closest to a prior measure on paths in the relative entropy sense, i.e., a Schroedinger bridge between the two marginals. This is an atypical stochastic control problem where the control consists in suitably modifying the transition mechanism. The prior can incorporate cost of traversing edges or allocate equal probability to all paths of equal length connecting any two given nodes, i.e., a uniform measure on paths. This latter choice relies on the so-called Ruelle-Bowen random walk and gives rise to a scheduling that tends to utilize all paths as uniformly as the topology allows. Thus, when the Ruelle-Bowen law is taken as prior, the transportation plan tends to lessen congestion and ensure a level of robustness. We show that the Ruelle-Bowen law is itself a Schroedinger bridge albeit with a prior that is not a probability measure. The paradigm of Schroedinger bridges as a mechanism for scheduling transport on networks can be adapted to graphs that are not strongly connected as well as to weighted graphs. The latter leads to transportation plans that effect a compromise between robustness and transportation cost.
Cited in
(9)- Fast and asymptotic steering to a steady state for networks flows
- What is a stochastic Hamiltonian process on finite graph? An optimal transport answer
- Design of biased random walks on a graph with application to collaborative recommendation
- Wasserstein geometry of quantum states and optimal transport of matrix-valued measures
- Stochastic control liaisons. Richard Sinkhorn meets Gaspard Monge on a Schrödinger bridge
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
- Robust rolling stock in rapid transit networks
- Dynamic programming in probability spaces via optimal transport
- Propagation of chaos for mean field Schrödinger problems
This page was built for publication: Robust Transport Over Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566839)
