The Maximum Flow Problem for Oriented Flows

Schade, Stanley; Strehler, Martin

doi:10.4230/OASIcs.ATMOS.2016.7

File

OASIcs.ATMOS.2016.7.pdf

Filesize: 0.5 MB
13 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2016.7
URN: urn:nbn:de:0030-drops-65318

Author Details

Stanley Schade

Martin Strehler

Cite AsGet BibTex

Stanley Schade and Martin Strehler. The Maximum Flow Problem for Oriented Flows. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/OASIcs.ATMOS.2016.7

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.

Keywords

network flow with orientation
graph expansion
approximation
container logistics
train routing

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River, New Jersey, 1993.
Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondřej Pangrác, Heiko Schilling, and Martin Skutella. Length-bounded cuts and flows. ACM Trans. Algorithms, 7(1):4:1-4:27, 2010.
Ralf Borndörfer, Marika Karbstein, Julika Mehrgahrdt, Markus Reuther, and Thomas Schlechte. The cycle embedding problem. In Operations Research Proceedings 2014, pages 465 - 472, 2016.
Daniel Dressler and Martin Strehler. Polynomial-time algorithms for special cases of the maximum confluent flow problem. Discrete Applied Mathematics, 163:142-154, 2014.
Shimon Even, Alon Itai, and Adi Shamir. On the Complexity of Timetable and Multi-Commodity Flow Problems. In FOCS, pages 184-193. IEEE Computer Society, 1975.
Lester R. Ford and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8(3):399-404, 1956.
Naveen Garg and Jochen Koenemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing, 37(2):630-652, 2007.
Ewgenij Gawrilow, Ekkehard Köhler, Rolf H. Möhring, and Björn Stenzel. Dynamic routing of automated guided vehicles in real-time. In Willi Jäger and Hans-Joachim Krebs, editors, Mathematics - Key Technology for the Future, pages 165-178. Springer, 2008.
Andrew V. Goldberg and Robert E. Tarjan. Efficient maximum flow algorithms. Communications of the ACM, 57(8):82-89, 2014.
Te C. Hu. Multi-commodity network flows. Operations research, 11(3):344-360, 1963.
Alon Itai. Two-Commodity Flow. JACM, 25(4):596-611, 1978.
Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms, volume 21 of Algorithms and Combinatorics. Springer, 4th edition, 2008.
Bruce L. Rothschild and Andrew B. Whinston. Feasibility of two commodity network flows. Operations Research, 14(6):1121-1129, 1966.
Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003.
Eva Tardos. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2):250-256, 1986.