Designing optimal networks for multi-commodity 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 multi-commodity scenario. In this paper we present a model based on optimal transport theory for finding optimal multi-commodity 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 new 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 to the sources and sinks or when enforcing robustness to damage. Finally, we provide an efficient implementation of our model which convergences faster than standard optimization methods based on gradient descent.

arXiv comment13 pages, 7 figures

References in corpus (14)

• Damage and fluctuations induce loops in optimal transport networks
• Fluctuations and redundancy in optimal transport networks
• Structure, Scaling and Phase Transition in the Optimal Transport Network
• Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks
• From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
• Phenotypes of vascular flow networks
• Networking - A Statistical Physics Perspective
• Numerical Solution of Monge-Kantorovich Equations via a dynamic formulation
• Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
• Discontinuous transition to loop formation in optimal supply networks
• Optimal transport in multilayer networks for traffic flow optimization
• Optimal Transport Flows for Distributed Production Networks
• Network extraction by routing optimization
• A Laplacian Approach to ${\ell }_1$-Norm Minimization

Cited by in corpus (13)

• Urban transportation networks and optimal transport-based infrastructures: similarity and economy of scale
• Sustainable optimal transport in multilayer networks
• Multicommodity routing optimization for engineering networks
• Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
• Bilevel Optimization for Traffic Mitigation in Optimal Transport Networks
• Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Bilevel optimization in flow networks: A message-passing approach
• Optimal transport with constraints: from mirror descent to classical mechanics
• Immiscible Color Flows in Optimal Transport Networks for Image Classification
• Adaptive Node Positioning in Biological Transport Networks
• Integer Traffic Assignment Problem: Algorithms and Insights on Random Graphs
• Self-organized transport in noisy dynamic networks