Minimum cost time-varying network flow problems

作者：Nasrabadi Ebrahim^*; Hashemi S Mehdi

来源：Optimization Methods and Software, 2010, 25(3): 429-447.

DOI：10.1080/10556780903239121

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

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.

• 出版日期2010