<p>In this paper, we study a minimum cost flow problem on a dynamic network in a discrete-time model, which is known to be NP-hard. All attributes in this network, including capacities, storage capacities, costs, storage costs, and supply or demand at any node, are time-dependent. First, we prove that the existence of a feasible dynamic flow is equivalent to solving a time-dependent maximum dynamic flow problem, and we provide a pseudopolynomial-time exact algorithm for this feasibility problem with computational complexity of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="120" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}((m+n)n^{2}T^{3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mrow> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>T</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$m$</EquationSource> <EquationSource Format="MATHML"><math> <mi>m</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq3.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$n$</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> are the number of arcs and nodes in the network, respectively, and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$T$</EquationSource> <EquationSource Format="MATHML"><math> <mi>T</mi> </math></EquationSource> </InlineEquation> is a given time horizon. Next, based on a feasible dynamic flow, we present an extended cost scaling algorithm that correctly computes a time-dependent minimum cost dynamic flow in <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="191" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}((m+n)n^{2}T^{3}\log (nCT))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mrow> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>T</mi> <mn>3</mn> </msup> <mo>log</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mi>C</mi> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_620_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">$C$</EquationSource> <EquationSource Format="MATHML"><math> <mi>C</mi> </math></EquationSource> </InlineEquation> represents the maximum absolute value of all costs in the network.</p>

Time-Dependent Minimum Cost Dynamic Flow Problems

期刊论文
发表日期：

2025年9月8日

查看全文

Si-Yuan Chen,
Sui-Xiang Gao,
Wen-Guo Yang

摘要

In this paper, we study a minimum cost flow problem on a dynamic network in a discrete-time model, which is known to be NP-hard. All attributes in this network, including capacities, storage capacities, costs, storage costs, and supply or demand at any node, are time-dependent. First, we prove that the existence of a feasible dynamic flow is equivalent to solving a time-dependent maximum dynamic flow problem, and we provide a pseudopolynomial-time exact algorithm for this feasibility problem with computational complexity of $\mathcal {O}((m+n)n^{2}T^{3})$ $O ((m + n) n^{2} T^{3})$ , where $m$ $m$ and $n$ $n$ are the number of arcs and nodes in the network, respectively, and $T$ $T$ is a given time horizon. Next, based on a feasible dynamic flow, we present an extended cost scaling algorithm that correctly computes a time-dependent minimum cost dynamic flow in $\mathcal {O}((m+n)n^{2}T^{3}\log (nCT))$ $O ((m + n) n^{2} T^{3} log (n C T))$ time, where $C$ $C$ represents the maximum absolute value of all costs in the network.