Convergence of a Packet Routing Model to Flows over Time

Leon Sering (), Laura Vargas Koch () and Theresa Ziemke ()
Additional contact information
Leon Sering: Institute for Operations Research, ETH Zürich, 8092 Zürich, Switzerland
Laura Vargas Koch: Institute for Operations Research, ETH Zürich, 8092 Zürich, Switzerland
Theresa Ziemke: Combinatorial Optimization and Graph Algorithms, Technische Universität Berlin, 10623 Berlin, Germany; Transport Systems Planning and Transport Telematics, Technische Universität Berlin, 10587 Berlin, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 3, 1741-1766

Abstract: Mathematical approaches for modeling dynamic traffic can be roughly divided into two categories: discrete packet routing models and continuous flow over time models . Despite very vital research activities on models in both categories, their connection was poorly understood so far. We build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and proving its convergence to the intensively studied model of flows over time with deterministic queuing. More precisely, we prove that the limit of the convergence process when decreasing the packet size and time step length in the packet routing model constitutes a flow over time with multiple commodities. In addition, we show that the convergence result implies the existence of approximate equilibria in the competitive version of the packet routing model. This is of significant interest as exact pure Nash equilibria cannot be guaranteed in the multicommodity setting.

Keywords: Primary: 05C21; secondary: 90B10; 91A25; flow over time; packet routing; multi-commodity; dynamic equilibrium; convergence of discrete to continuous; discretization error; approximate equilibrium; dynamic traffic assignment (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1318 (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:48:y:2023:i:3:p:1741-1766

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 ().