Nash flows over time with spillback

DOI10.1137/1.9781611975482.57MaRDI QIDQ5236241zbMATH OpenOpenAlexFDO

Authors Leon Sering, Laura Vargas Koch

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.05862

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Traffic problems in operations research (90B20)

Abstract: Modeling traffic in road networks is a widely studied but challenging problem, especially under the assumption that drivers act selfishly. A common approach is the deterministic queuing model, for which the structure of dynamic equilibria has been studied extensively in the last couple of years. The basic idea is to model traffic by a continuous flow that travels over time through a network, in which the arcs are endowed with transit times and capacities. Whenever the flow rate exceeds the capacity the flow particles build up a queue. So far it was not possible to represent spillback or kinematic waves in this model. By introducing a storage capacity arcs can become full, and thus, might block preceding arcs, i.e., spillback occurs. Furthermore, we model kinematic waves by upstream moving flows over time representing the gaps between vehicles. We carry over the main results of the original model to our generalization, i.e., we characterize Nash flows over time by sequences of particular static flows, so-called spillback thin flows. Furthermore, we give a constructive proof for the existence of dynamic equilibria, which suggests an algorithm for their computation. This solves an open problem stated by [13].

Recommendations

• The impact of spillback on the price of anarchy for flows over time
• Nash equilibria and the price of anarchy for flows over time
• A dynamic travel time model for spillback
• Nash equilibria and the price of anarchy for flows over time
• Dynamic equilibria in fluid queueing networks

Cited in

(15)

• The impact of spillback on the price of anarchy for flows over time
• Algorithms for flows over time with scheduling costs
• Long-term behavior of dynamic equilibria in fluid queuing networks
• Atomic dynamic flow games: adaptive vs. nonadaptive agents
• Algorithms for Flows over Time with Scheduling Costs
• Computation of Dynamic Equilibria in Series-Parallel Networks
• On the price of anarchy for flows over time
• Bounding Residence Times for Atomic Dynamic Routings
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• Dynamic flows with adaptive route choice
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• Nash flows over time
• Bicriteria Nash flows over time
• Atomic dynamic routing games with multiple destinations
• Optimizing throughput and makespan of queuing systems by information design

This page was built for publication: Nash flows over time with spillback

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236241)