Abstract
This paper deals with a general minimum cost dynamic flow problem in a discrete time model with time-varying transit times, transit costs, transit capacities, storage costs, and storage capacities. For this problem, an algorithm of time complexity O(V nT(n+T)) is presented, where V is an upper bound on the total supply, n is the number of nodes, and T denotes the given time horizon of the dynamic flow problem. The algorithm is a discrete-time version of the successive shortest path algorithm.
Acknowledgements
The authors would like to thank an anonymous referee for many useful comments that helped to improve the paper.
Notes
Note that if the arcs (i, j) and (j, i) already exist in A, when the artificial arc (j, i) is created, then this artificial arc must be denoted in such a way that it can be distinguished from the original arc (j, i) in A.
We note that waiting times at nodes along a dynamic path in the residual network can be negative.