Document Open Access Logo

The Maximum Flow Problem for Oriented Flows

Authors Stanley Schade, Martin Strehler

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.7.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Stanley Schade
Martin Strehler

Cite As Get 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.

Subject Classification

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

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River, New Jersey, 1993. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. Daniel Dressler and Martin Strehler. Polynomial-time algorithms for special cases of the maximum confluent flow problem. Discrete Applied Mathematics, 163:142-154, 2014. Google Scholar
  5. 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. Google Scholar
  6. Lester R. Ford and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8(3):399-404, 1956. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. Andrew V. Goldberg and Robert E. Tarjan. Efficient maximum flow algorithms. Communications of the ACM, 57(8):82-89, 2014. Google Scholar
  10. Te C. Hu. Multi-commodity network flows. Operations research, 11(3):344-360, 1963. Google Scholar
  11. Alon Itai. Two-Commodity Flow. JACM, 25(4):596-611, 1978. Google Scholar
  12. Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms, volume 21 of Algorithms and Combinatorics. Springer, 4th edition, 2008. Google Scholar
  13. Bruce L. Rothschild and Andrew B. Whinston. Feasibility of two commodity network flows. Operations Research, 14(6):1121-1129, 1966. Google Scholar
  14. Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003. Google Scholar
  15. Eva Tardos. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2):250-256, 1986. Google Scholar
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 About DROPS Imprint Privacy Contact