Ein erweitertes kontinuierliches Zeitmodell für dynamische Netzwerkflüsse
Final Report Abstract
Network flows over time (also called dynamic flows in the literature) model the temporal evolution of flows over time and also consider changes of network parameters such as capacities, costs, supplies, and demands over time. These problems have been extensively studied in the past because of their important role in real world applications. Research on flows over time has been pursued in two different and mainly independent directions with respect lo the representation of time: discrete and continuous models. Both models have their advantages and disadvantages. However, in many applications a combination of both models is desirable. In this project we have unified discrete and continuous network flows over time into a single model by extending the class of flows over time to a general setting. In fact, we model the flow on each arc as a measure on the real line (time axis) which assigns to each suitable subset a real value interpreted as the amount of flow entering the arc over the subset. We refer to such measure-based flows over time as Borel flows. In this project, we have generalized key ingredients of the theory of static network flows to Borel flows. More specifically, we have developed measurebased analogues of those concepts and techniques which are the core of static network flow theory. Surprisingly, our techniques are based on the ideas of static flow theory and not by the knowledge about discrete and continuous flows over time. That is, most of our results are proven by adopting the top level ideas used for establishing the corresponding static results. In particular, this emphasizes the far-reaching similarities between static flows and Borel flows which were previously not known for flows over time to this extent.
Publications
- Continuous and discrete flows over time. Mathematical Methods of Operations Research, 73:301-337, 2011
R. Koch, E. Nasrabadi und M. Skutella
- Strong duality for the maximum Borel flow problem. In J. Pahl, T. Reiners, and S. Voß, Hrsg., Network Optimization, Lecture Notes in Computer Science Vol. 6701, S. 256-261. Springer, Berlin, 2011
R. Koch und E. Nasrabadi
