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.2016.7
URN: urn:nbn:de:0030-drops-65318
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6531/
Go to the corresponding OASIcs Volume Portal

Schade, Stanley ; Strehler, Martin

The Maximum Flow Problem for Oriented Flows

pdf-format:
OASIcs-ATMOS-2016-7.pdf (0.5 MB)

Abstract

In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.

BibTeX - Entry

@InProceedings{schade_et_al:OASIcs:2016:6531,
  author =	{Stanley Schade and Martin Strehler},
  title =	{{The Maximum Flow Problem for Oriented Flows}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{7:1--7:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Marc Goerigk and Renato Werneck},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6531},
  URN =		{urn:nbn:de:0030-drops-65318},
  doi =		{10.4230/OASIcs.ATMOS.2016.7},
  annote =	{Keywords: network flow with orientation, graph expansion, approximation, container logistics, train routing}
}

Keywords: network flow with orientation, graph expansion, approximation, container logistics, train routing
Collection: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)
Issue Date: 2016
Date of publication: 24.08.2016

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