2026-07-22T16:58:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6531 2024-03-06T10:30:01Z ddc:004 open_access

The Maximum Flow Problem for Oriented Flows Schade, Stanley Strehler, Martin network flow with orientation graph expansion approximation container logistics train routing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stanley Schade and Martin Strehler 2016 Is Part Of OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2016.7 urn:nbn:de:0030-drops-65318 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode