Computation of Dynamic Equilibria in Series-Parallel Networks

Marcus Kaiser ()
Additional contact information
Marcus Kaiser: Lehrstuhl für Operations Research, Technische Universität München, 80333 München, Germany

Mathematics of Operations Research, 2022, vol. 47, issue 1, 50-71

Abstract: We consider dynamic equilibria for flows over time under the fluid queuing model. In this model, queues on the links of a network take care of flow propagation. Flow enters the network at a single source and leaves at a single sink. In a dynamic equilibrium, every infinitesimally small flow particle reaches the sink as early as possible given the pattern of the rest of the flow. Although this model has been examined for many decades, progress has been relatively recent. In particular, the derivatives of dynamic equilibria have been characterized as thin flows with resetting, which allows for more structural results. Our two main results are based on the formulation of thin flows with resetting as a linear complementarity problem and its analysis. We present a constructive proof of existence for dynamic equilibria if the inflow rate is right-monotone. The complexity of computing thin flows with resetting, which occurs as a subproblem in this method, is still open. We settle it for the class of two-terminal, series-parallel networks by giving a recursive algorithm that solves the problem for all flow values simultaneously in polynomial time.

Keywords: Primary: 91A; secondary: 05C21; 05C57; 91A07; 91A68; flow over time; fluid queuing model; dynamic equilibrium; series-parallel (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1108 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:50-71

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().