Optimal multicommodity flows in dynamic networks and algorithms for their finding
Maria Fonoberova, Dmitrii Lozovanu · 2005
In this paper we study two basic problems related to dynamic flows: maximum multicommodity flow and the minimum cost multicommodity flow prob- lems. We consider these problems on dynamic networks with time-varying capaci- ties of edges. For minimum cost multicommodity flow problem we assume that cost functions, defined on edges, are nonlinear and depending on time and flow, and the demand function also depends on time. We propose algorithms for solving these dy- namic problems, which are based on their reducing to static ones on a time-expanded network. In this paper we study dynamic versions of the maximum multicommodity flow and the nonlinear minimum-cost multicommodity flow problems on networks. These problems generalize the classical static flow problems and extend some dynamic (10, 11) and control models on networks (12). We propose algorithms for solving these dynamic problems, which are based on their reducing to static ones on a time-expanded network (7). We also note some different methods for constructing time-expanded networks in the case of acyclic graphs. For our problems the time is an essential component, either because the flows of some commodity take time to pass from one location to another, or because the structure of network changes over time. Classical static network flow models are known as valuable tools for different applications but they fail to capture the property of many real-life problems. To tackle this problem, we use dynamic network flow models instead of the static ones. Dynamic flows are widely used to model network-structured, decision-making problems over time: problems in electronic communication, production and distri- bution, economic planning, cash flow, job scheduling, and transportation (1)) In considered dynamic models the flow passes an arc with time, it can be delayed at nodes, flow values on arcs and the network parameters can change with time. While very efficient solution methods exist for static flow problems, dynamic flow problems have proved to be more difficult to solve.