Alessandro Lonardi

Alessandro Lonardi

PhD student at Max Planck Institute for Intelligent Systems

Infrastructure adaptation and emergence of loops in network routing with time-dependent loads

Published:

Abstract

Efficient and resilient public transportation that meet the ever-changing demands of users is critical for human-centric cities of the future. Nevertheless, routing algorithms often neglect the time-varying nature of passengers inflows in transport networks. We propose a method that, given time-dependent entry and exit rates of passengers in nodes, outputs edge flows which jointly optimize energy travelling expenditure and infrastructure cost. In particular, we leverage the formalism of capacitated networks, hence we treat passengers’ flows as electrical currents, to find efficient updates of the edge capacities—measuring the infrastructure size needed to allocate passengers. Our key hypothesis is that capacities evolve on a slower timescale than loads of passengers. The physical intuition is that a network manager, who is responsible to build the network infrastructure, has a coarser observation scale of a transportation system than the users, whose paths rapidly fluctuate. In practice, this means that modifications in the network infrastructure occur on a much larger timescale than that of passengers’ fluctuations. Leveraging this assumption, we translate the minimization problem into a closed-form system of differential equations that governs the evolution of capacities and passengers flows, given their time-varying entry and exit rates. In our study, we formally prove that if passengers’ loads are periodic, the evolution of the system is controlled by a matrix obtained with the Fourier coefficients of the input loads. Remarkably, we find a sufficient condition on these coefficients to determine if the resulting networks are trees or have loops. Numerically, we display how the coefficients can be used as a proxy to evaluate the robustness of the outputted transport network. Furthermore, we propose a candidate Lyapunov functional for our dynamical system, which allows us to interpret stationary topologies as optimal networks, i.e., structures minimizing the global cost to build the graph. Not only this result is of theoretical significance, but it also offers a remarkable computational speedup. In fact, our algorithm efficiently extracts optimal networks that can otherwise only be obtained by letting the capacities evolve with the same timescale of passengers’ inflows, and averaging their values at large times. We validate our method on numerous synthetic topologies, and demonstrate its practical relevance by applying it to the Bordeaux bus network.