Routing-induced phase transitions in traffic efficiency of non-Markovian dynamics

Complex networks provide a natural framework for modeling transportation systems, capturing the interplay between flow dynamics and topology structure. We introduce a non-Markovian traffic model in which the traversal time of each link depends on both its inherent heterogeneous travel time and congestion delays caused by simultaneous usage. Agents may adopt one of two intuitive routing strategies: the shortest-time path (TSP) or the shortest-distance path (GSP). We derive an analytical expression for the system-wide average travel time as a function of routing preference. Remarkably, our analysis reveals three distinct efficiency phases, fast is fast, Parrondo, and slow is fast, resulting from the trade-off between global travel time savings and congestion delays induced by load imbalance. Theoretical conditions for the emergence of each phase are established and corroborated by numerical simulations across diverse networks. Rather than claiming that routing alone resolves congestion, our results reveal when and why routing preferences can shift the system between fundamentally different efficiency phases, providing a statistical-physics foundation for understanding and optimizing transport in communication, logistics, and urban-mobility networks.