Thumbnail Image

Minimum Cost Flows Over Time without Intermediate Storage

Fleischer, Lisa; Skutella, Martin

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Solving these problems raises issues that do not arise in standard network flows. One issue is the question of storage of flow at intermediate nodes. In most applications (such as, e.g., traffic routing, evacuation planning, telecommunications etc.), intermediate storage is limited, undesired, or prohibited.