Designing optimal networks for multicommodity transport problem

Abstract

Designing and optimizing different flows in networks is a relevant problem in many contexts. While a number of methods have been proposed in the physics and optimal transport literature for the one-commodity case, we lack similar results for the multicommodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multicommodity flow configurations on networks. This model introduces a dynamics that regulates the edge conductivities to achieve, at infinite times, a minimum of a Lyapunov functional given by the sum of a convex transport cost and a concave infrastructure cost. We show that the long-time asymptotics of this dynamics are the solutions of a standard constrained optimization problem that generalizes the one-commodity framework. Our results provide insights into the nature and properties of optimal network topologies. In particular, they show that loops can arise as a consequence of distinguishing different flow types, complementing previous results where loops, in the one-commodity case, were obtained as a consequence of imposing dynamical rules on the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation of our model which converges faster than standard optimization methods based on gradient descent.

Publication
Physical Review Research, 3(043010),(2021)
Alessandro Lonardi
Alessandro Lonardi
PhD student

The main focus of my current research is studying routing problems combining approaches stemming from optimal transport and belief propagation. In particular, I am interested in understanding how different route selection mechanisms affect traffic and total path length of networks. The applications of my work span from urban to biological networks. Previously I was a Master’s Student in Mathematical Engineering at UniPd (Padua, Italy), where I also obtained my Bachelor’s degree in Physics.

Caterina De Bacco
Caterina De Bacco
CyberValley Research Group Leader

My research focuses on understanding, optimizing and predicting relations between the microscopic and macroscopic properties of complex large-scale interacting systems.

Related