License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2018.12
URN: urn:nbn:de:0030-drops-97176
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9717/
Go to the corresponding OASIcs Volume Portal

Sering, Leon ; Skutella, Martin

Multi-Source Multi-Sink Nash Flows over Time

pdf-format:
OASIcs-ATMOS-2018-12.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{sering_et_al:OASIcs:2018:9717,
  author =	{Leon Sering and Martin Skutella},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9717},
  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}
}

Keywords: Network congestion, Nash equilibrium, dynamic routing game, deterministic queuing model
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI