Multicommodity routing optimization for engineering networks

Abstract

Optimizing passengers routes is crucial to design efficient transportation networks. Recent results show that optimal transport provides an efficient alternative to standard optimization methods. However, it is not yet clear if this formalism has empirical validity on engineering networks. We address this issue by considering different response functions-quantities determining the interaction between passengers-in the dynamics implementing the optimal transport formulation. Particularly, we compare a theoretically-grounded response function with one that is intuitive for settings involving transportation of passengers, albeit lacking theoretical justifications. We investigate these two modeling choices on the Paris metro and analyze how they reflect on passengers’ fluxes. We measure the extent of traffic bottlenecks and infrastructure resilience to node removal, showing that the two settings are equivalent in the congested transport regime, but different in the branched one. In the latter, the two formulations differ on how fluxes are distributed, with one function favoring routes consolidation, thus potentially being prone to generate traffic overload. Additionally, we compare our method to Dijkstra’s algorithm to show its capacity to efficiently recover shortest-path-like graphs. Finally, we observe that optimal transport networks lie in the Pareto front drawn by the energy dissipated by passengers, and the cost to build the infrastructure.

Publication
Submitted
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