TY - JOUR

T1 - Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks

AU - Cominetti, Roberto

AU - Correa, José

AU - Olver, Neil

N1 - Funding Information:
Funding: This work was partially supported by Agencia Nacional de Investigacion y Desarrollo (ANID, Chile) [Grants FONDECYT 1190043, FONDECYT 1171501, AFB 170001, and AFB180003]; and by the Dutch Science Foundation (NWO) [Grants TOP 614.001.510 and 016.Vidi.189.087].
Publisher Copyright:
© 2021 INFORMS.

PY - 2022/1/1

Y1 - 2022/1/1

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 50 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 nonobvious 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 50 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 nonobvious 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.

KW - Dynamic equilibria

KW - Flows over time

KW - Steady state

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

U2 - 10.1287/OPRE.2020.2081

DO - 10.1287/OPRE.2020.2081

M3 - Article

AN - SCOPUS:85124970240

VL - 70

SP - 516

EP - 526

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 1

ER -