Search Results

Documents authored by Sering, Leon

Document
DOI: 10.4230/OASIcs.ATMOS.2023.11
Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks

Authors: Theresa Ziemke, Leon Sering, and Kai Nagel

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
We study the long-term behavior of dynamic traffic equilibria and find that it heavily depends on whether spillback is captured in the traffic model or not. We give an example where no steady state is reached. Although the example consists of a single-commodity instance with constant inflow rate, the Nash flow over time consists of infinitely many phases. This is in contrast to what has been proven for Nash flows over time without spillback [Cominetti et al., 2021; N. Olver et al., 2021]. Additionally, we show that similar phase oscillations as in the Nash flow over time with spillback can be observed in the co-evolutionary transport simulation MATSim. This reaffirms the robustness of the findings as the simulation does (in contrast to Nash flows over time) not lead to exact user equilibra and, moreover, models discrete time steps and vehicles.
Cite as

Theresa Ziemke, Leon Sering, and Kai Nagel. Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ziemke_et_al:OASIcs.ATMOS.2023.11,
  author =	{Ziemke, Theresa and Sering, Leon and Nagel, Kai},
  title =	{{Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{11:1--11:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.11},
  URN =		{urn:nbn:de:0030-drops-187722},
  doi =		{10.4230/OASIcs.ATMOS.2023.11},
  annote =	{Keywords: flows over time, transport simulation, Nash flow, dynamic equilibrium, long-term behavior, steady state, oscillation, spillback, MATSim}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.4
Atomic Splittable Flow Over Time Games

Authors: Antonia Adamik and Leon Sering

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In an atomic splittable flow over time game, finitely many players route flow dynamically through a network, in which edges are equipped with transit times, specifying the traversing time, and with capacities, restricting flow rates. Infinitesimally small flow particles controlled by the same player arrive at a constant rate at the player’s origin and the player’s goal is to maximize the flow volume that arrives at the player’s destination within a given time horizon. Here, the flow dynamics are described by the deterministic queuing model, i.e., flow of different players merges perfectly, but excessive flow has to wait in a queue in front of the bottle-neck. In order to determine Nash equilibria in such games, the main challenge is to consider suitable definitions for the players' strategies, which depend on the level of information the players receive throughout the game. For the most restricted version, in which the players receive no information on the network state at all, we can show that there is no Nash equilibrium in general, not even for networks with only two edges. However, if the current edge congestions are provided over time, the players can adapt their route choices dynamically. We show that a profile of those strategies always lead to a unique feasible flow over time. Hence, those atomic splittable flow over time games are well-defined. For parallel-edge networks Nash equilibria exists and the total flow arriving in time equals the value of a maximum flow over time leading to a price of anarchy of 1.
Cite as

Antonia Adamik and Leon Sering. Atomic Splittable Flow Over Time Games. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adamik_et_al:LIPIcs.SAND.2022.4,
  author =	{Adamik, Antonia and Sering, Leon},
  title =	{{Atomic Splittable Flow Over Time Games}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.4},
  URN =		{urn:nbn:de:0030-drops-159462},
  doi =		{10.4230/LIPIcs.SAND.2022.4},
  annote =	{Keywords: Flows Over Time, Deterministic Queuing, Atomic Splittable Games, Equilibria, Traffic, Cooperation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.12
Multi-Source Multi-Sink Nash Flows over Time

Authors: Leon Sering and Martin Skutella

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
Nash flows over time describe the behavior of selfish users eager to reach their destination as early as possible while traveling along the arcs of a network with capacities and transit times. Throughout the past decade, they have been thoroughly studied in single-source single-sink networks for the deterministic queuing model, which is of particular relevance and frequently used in the context of traffic and transport networks. In this setting there exist Nash flows over time that can be described by a sequence of static flows featuring special properties, so-called `thin flows with resetting'. This insight can also be used algorithmically to compute Nash flows over time. We present an extension of these results to networks with multiple sources and sinks which are much more relevant in practical applications. In particular, we come up with a subtle generalization of thin flows with resetting, which yields a compact description as well as an algorithmic approach for computing multi-terminal Nash flows over time.
Cite as

Leon Sering and Martin Skutella. Multi-Source Multi-Sink Nash Flows over Time. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sering_et_al:OASIcs.ATMOS.2018.12,
  author =	{Sering, Leon and Skutella, Martin},
  title =	{{Multi-Source Multi-Sink Nash Flows over Time}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{12:1--12:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.12},
  URN =		{urn:nbn:de:0030-drops-97176},
  doi =		{10.4230/OASIcs.ATMOS.2018.12},
  annote =	{Keywords: Network congestion, Nash equilibrium, dynamic routing game, deterministic queuing model}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.38
Rainbow Cycles in Flip Graphs

Authors: Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
The flip graph of triangulations has as vertices all triangulations of a convex n-gon, and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of r-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex n-gon, the flip graph of plane spanning trees on an arbitrary set of n points, and the flip graph of non-crossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of non-geometric objects: the flip graph of permutations of {1,2,...,n } and the flip graph of k-element subsets of {1,2,...,n }. In each of the five settings, we prove the existence and non-existence of rainbow cycles for different values of r, n and k.
Cite as

Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering. Rainbow Cycles in Flip Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SoCG.2018.38,
  author =	{Felsner, Stefan and Kleist, Linda and M\"{u}tze, Torsten and Sering, Leon},
  title =	{{Rainbow Cycles in Flip Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.38},
  URN =		{urn:nbn:de:0030-drops-87514},
  doi =		{10.4230/LIPIcs.SoCG.2018.38},
  annote =	{Keywords: flip graph, cycle, rainbow, Gray code, triangulation, spanning tree, matching, permutation, subset, combination}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact