Analysis of Complex Networks

15.2 Optimal Dynamic Single-Commodity Flow Problems and Algorithms for Solving Them

In this section we consider two basic models concerning dynamic flows: the minimum cost flow problem and the maximum flow problem on dynamic networks. We formulate and investigate the minimum cost dynamic flow problem on a network with nonlinear cost functions, defined on arcs, that depend on time and on flow, and demand–supply and capacity functions that depend on time. The maximum dynamic flow problem is also considered in the case where all network parameters depend on time. To solve the considered problems, we propose algorithms based on the reduction of dynamic problems to classical static problems on auxiliary time-expanded networks. Generalized problems with transit time functions that depend on the amount of flow and the entering time-moment of flow in the arc are analyzed and algorithms for solving such problems are developed and grounded.

15.2.1 The Minimum Cost Dynamic Flow Problem

A dynamic network N = (V, E, τ, d, u, φ) is determined by directed graph G = (V, E) with set of vertices V,|V| = n, set of arcs E, |E| = m, transit time function τ: E → R₊, demand-supply function d: V × → R, capacity function u: E × → R₊, and cost function φ: E × R₊ × → R₊. We consider the discrete time model, ...