An Integer Network Flow Problem with Bridge Capacities
- In this paper a modified version of dynamic network ows is discussed. Whereas dynamic network flows are widely analyzed already, we consider a dynamic flow problem with aggregate arc capacities called Bridge Problem which was introduced by Melkonian [Mel07]. We extend his research to integer flows and show that this problem is strongly NP-hard. For practical relevance we also introduce and analyze the hybrid bridge problem, i.e. with underlying networks whose arc capacity can limit aggregate flow (bridge problem) or the flow entering an arc at each time (general dynamic flow). For this kind of problem we present efficient procedures for special cases that run in polynomial time. Moreover, we present a heuristic for general hybrid graphs with restriction on the number of bridge arcs. Computational experiments show that the heuristic works well, both on random graphs and on graphs modeling also on realistic scenarios.
Author: | Horst W. Hamacher, Anika Kinscherff |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-46674 |
Series (Serial Number): | Report in Wirtschaftsmathematik (WIMA Report) (163) |
Document Type: | Working Paper |
Language of publication: | English |
Date of Publication (online): | 2017/06/13 |
Year of first Publication: | 2017 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2017/06/14 |
Page Number: | 21 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Licence (German): | Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0) |