| Nermin Kartli A Dynamic Programming Approach for the Fuzzy Minimum Cost Maximum Flow Problem in the Multi-Stage Networks |
|---|
| Abstract. In this study, we consider the minimum-cost maximum-flow problem in a fuzzy environment for the multi-stage networks. In the problem under investigation, we model edge costs on the network with parametric fuzzy numbers. We transform uncertainty into deterministic subproblems using the α-cut approach and propose a novel dynamic-programming-based heuristic algorithm.
In the proposed method, a dynamic-programming-based shortest-path algorithm, developed to accommodate the multi-stage network structure, is applied to the deterministic problem obtained for each α level. In this process, performed on the residual network, the capacity dominance criterion is considered alongside cost minimization, and paths with higher flow capacity are preferred among alternative paths with the same cost. This approach ensures a more balanced and stable solution process. The algorithm updates the residual network at each increment step and defines reverse edges with negative costs. This results in an iterative improvement process similar to classical minimum cost flow methods. Left and right end solutions are calculated separately, the results are combined, and defuzzification is applied in accordance with fuzzy decision theory. The effectiveness of the proposed algorithm was evaluated through numerical experiments performed on randomly generated multi-stage test networks. The results show that the developed method can produce consistent, stable, and computationally efficient solutions under different uncertainty levels. In this respect, the study offers a practical and applicable approach to solving fuzzy network flow problems. |
| Keywords: Fuzzy optimization, maximum flow at minimum cost, multi-stage networks, dynamic programming, alpha-cuts method, parametric fuzzy numbers, supply chain networks, heuristic algorithms |
 Download PDF |
| DOI: https://doi.org/10.54381/itta2026.1.08 |