Efficient robust routing for single commodity network flows

Yongxin Chen, Tryphon T. Georgiou, Michele Pavon, Allen Tannenbaum

Research output: Contribution to journalArticlepeer-review


We study single commodity network flows with suitable robustness and efficiency specs. An original use of a maximum entropy problem for distributions on the paths of the graph turns this problem into a steering problem for Markov chains with prescribed initial and final marginals. From a computational standpoint, viewing scheduling this way is especially attractive in light of the existence of an iterative algorithm to compute the solution. This paper builds on the work proposed by Y. Chen et al., ['Robust transport over networks,' IEEE Transactions on Automatic Control, vol. 62, no. 9, pp. 4675-4682, Sep. 2017] by introducing an index of efficiency of a transportation plan and points, accordingly, to efficient robust transport policies. In developing the theory, we establish two new invariance properties of the solution (called bridge) - an iterated bridge invariance property and the invariance of the most probable paths. These properties, which were tangentially mentioned in our previous work, are fully developed here. We also show that the distribution on paths of the optimal transport policy, which depends on a 'temperature' parameter, tends to the solution of the 'most economical' but possibly less robust optimal mass transport problem as the temperature goes to zero. The relevance of all of these properties for transport over networks is illustrated in an example.

Original languageEnglish (US)
Pages (from-to)2287-2294
Number of pages8
JournalIEEE Transactions on Automatic Control
Issue number7
StatePublished - Jul 2018


  • Maximum entropy problem
  • most probable path
  • temperature parameter
  • transport over networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Efficient robust routing for single commodity network flows'. Together they form a unique fingerprint.

Cite this