Time-varying minimum cost flow problems

Time-varying minimum cost flow problems

0.00 Avg rating0 Votes
Article ID: iaor2002396
Country: Netherlands
Volume: 131
Issue: 2
Start Page Number: 352
End Page Number: 374
Publication Date: Jun 2001
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: dynamic
Abstract:

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,cr,cw) be a network with an arc set A and a vertex set V. Each aA is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost cr(a,t), and a positive capacity limit l(a,t). Each xV is associated with two integer parameters: a waiting cost cw(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,... The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.

Reviews

Required fields are marked *. Your email address will not be published.