Dan Stratila, year. V, Fac. of Mathematics and Computer Science
Dumitru Lozovanu, dr. hab. prof. univ., scientific advisor

We study the minimum-cost flow problem on dynamic networs. Let be a directed graph without directed cycles, where V contains the subsets such that and . Consider the supply and demand functions and that satisfy the condition

,

and the cost function . A dynamic flow on the dynamic network is a function that satisfies the constraints:

where is the maximum length of a directed path in P. The problem consists of findind a dynamic flow on P that minimizes the objective function

.

Note that the above problem is equivalent to the acyclic unit-time minimum-cost flow problem without holdover edges and capacities. We prove that this problem can be solved on a time-expanded network [1,2] maximum of nodes, and edges. We then show a method of reducing the size of the time-expanded network to at most intermediate nodes, where . An algorithm for building the reduced network has been developed. Finally, we discuss generalizations for networks with arbitrary transit times, and networks with capacities.

References
[1] L. R. Ford, Jr., D. R. Fulkerson. Flows in networks. Princeton, N. J., 1962.
[2] L. Fleischer, É. Tardos. Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett., 1998.