Minimum cost time-varying network flow problems

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.

Keywords:

• network flows
• time-varying networks
• shortest dynamic path
• minimum cost dynamic flow

AMS Subject Classification Codes :

• 90C27
• 90C35
• 90B10
• 90B05

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.

Additional information

Notes on contributors

Ebrahim Nasrabadi

Present address: Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.