TY - GEN

T1 - Long term behavior of dynamic equilibria in fluid queuing networks

AU - Cominetti, Roberto

AU - Correa, José

AU - Olver, Neil

N1 - Funding Information:
We warmly thank Schloss Dagstuhl for its hospitality during the Seminar 15412 “Dynamic Traffic Models in Transportation Science” at which this research started. We also express our sincere gratitude to Vincent Acary, Umang Bhaskar, and Martin Skutella for enlightening discussions. This work was partially supported by Núcleo Milenio Información y Coordinación en Redes (ICM-FIC RC130003), an NWO Veni grant, and an NWO TOP grant.
Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - A fluid queuing network constitutes one of the simplest models in which to study flow dynamics over a network. In this model we have a single source-sink pair and each link has a per-time-unit capacity and a transit time. A dynamic equilibrium (or equilibrium flow over time) is a flow pattern over time such that no flow particle has incentives to unilaterally change its path. Although the model has been around for almost fifty years, only recently results regarding existence and characterization of equilibria have been obtained. In particular the long term behavior remains poorly understood. Our main result in this paper is to show that, under a natural (and obviously necessary) condition on the queuing capacity, a dynamic equilibrium reaches a steady state (after which queue lengths remain constant) in finite time. Previously, it was not even known that queue lengths would remain bounded. The proof is based on the analysis of a rather non-obvious potential function that turns out to be monotone along the evolution of the equilibrium. Furthermore, we show that the steady state is characterized as an optimal solution of a certain linear program. When this program has a unique solution, which occurs generically, the long term behavior is completely predictable. On the contrary, if the linear program has multiple solutions the steady state is more difficult to identify as it depends on the whole temporal evolution of the equilibrium.

AB - A fluid queuing network constitutes one of the simplest models in which to study flow dynamics over a network. In this model we have a single source-sink pair and each link has a per-time-unit capacity and a transit time. A dynamic equilibrium (or equilibrium flow over time) is a flow pattern over time such that no flow particle has incentives to unilaterally change its path. Although the model has been around for almost fifty years, only recently results regarding existence and characterization of equilibria have been obtained. In particular the long term behavior remains poorly understood. Our main result in this paper is to show that, under a natural (and obviously necessary) condition on the queuing capacity, a dynamic equilibrium reaches a steady state (after which queue lengths remain constant) in finite time. Previously, it was not even known that queue lengths would remain bounded. The proof is based on the analysis of a rather non-obvious potential function that turns out to be monotone along the evolution of the equilibrium. Furthermore, we show that the steady state is characterized as an optimal solution of a certain linear program. When this program has a unique solution, which occurs generically, the long term behavior is completely predictable. On the contrary, if the linear program has multiple solutions the steady state is more difficult to identify as it depends on the whole temporal evolution of the equilibrium.

UR - http://www.scopus.com/inward/record.url?scp=85020493058&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59250-3_14

DO - 10.1007/978-3-319-59250-3_14

M3 - Conference contribution

AN - SCOPUS:85020493058

SN - 9783319592497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 161

EP - 172

BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings

A2 - Eisenbrand, Friedrich

A2 - Koenemann, Jochen

PB - Springer Verlag

T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

Y2 - 26 June 2017 through 28 June 2017

ER -