Exploring Network Topologies from Routing Optimization Problems

Abstract

While routing optimization problems are relevant in various domains, solving them computationally is often challenging. This thesis explores Optimal Transport (OT) principles to solving routing optimization problems, focusing on a biologically-inspired dynamical formulation. We first explore how to translate the solutions of a dynamical system of equations into meaningful network topologies, while preserving the important optimality properties of these solutions. Our graph extraction method provides a valuable tool to help practitioners bridging the gap between the abstract mathematical principles of OT and the more interpretable language of network theory.

In addition to addressing the graph extraction problem, we explore how to find community structures inspired by the problem of measuring the OT Wasserstein distance, combined with the notion of geometric curvature in a graph. The proposed approach allows for tuning between different transportation regimes, while controlling the information shared between nodes' neighborhoods. We evaluated our algorithm's performance with various synthetic and real networks, achieving comparable or superior results to other OT-based methods on synthetic data, while identifying communities that more accurately represent node metadata in real data.

Last, we study how our graph extraction method can be extended to designing and optimizing urban transportation networks. We use only a limited number of origins and destination points to generate network structures directly from a continuous space, representing the initial stage of development of a transportation infrastructure. By tuning one parameter, we show how our method can simulate a range of different subway, tram and train networks that can be further used to suggest possible improvements in terms of relevant transportation properties.

In summary, this thesis investigates various applications of optimal transport principles for solving routing optimization problems. We provide a tool to explore networks that are solutions from a mathematical formulation of optimal transport theory, showing how it can be explored to design more efficient urban transportation networks, and including a measure of graph similarity which is then applied to a geometric-based community detection method.