Algorithm for Monitoring Minimum Cost in Fuzzy Dynamic Networks

Alexander Bozhenyuk, Evgeniya Gerasimenko


The present paper examines the task of minimum cost flow finding in a fuzzy dynamic network with lower flow bounds. The distinguishing feature of this problem statement lies in the fuzzy nature of the network parameters, such as flow bounds, transmission costs and transit times. The arcs of the considered network have lower bounds. Another feature of this task is that fuzzy flow bounds, costs and transit times can vary depending on the flow departure time. Algorithm, which implements the solution of considered problem, is proposed.


Fuzzy dynamic network; lower flow bounds; minimum cost flow

Full Text:



I. Chabini and M. Abou-Zeid, The minimum cost flow problem in capacitated dynamic networks. In Annual Meeting of the Transportation Research Board, pages 1–30, Washington, D.C., 2003.

L.R. Ford and D.R. Fulkerson, Constructing maximal dynamic flows from static flows, Oper. Res. 6, pages 419–433, 1958.

L.K. Fleischer and M. Skutella, Quickest flows over time, SIAM J. Comput. 36, pp. 1600–1630, 2007.

X, Cai, D. Sha and C. K. Wong, Time-varying minimum cost flow problems, European J. Oper. Res. 131, pages 352–374, 2001.

J. Halpern, A generalized dynamic flows problem, Networks 9 , pages 133–167, 1979.

L. Cooke and E. Halsey, The shortest route through a network with time- dependent internodal transit times J. Math. Anal. Appl. 14, pages 492– 498, 1966.

R.K. Ahuja, J.B. Orlin, S. Pallottino and M.G. Scutella, Dynamic shortest paths minimizing travel times and costs, Networks 41, pages 197–205, 2003.

S. Pallottino and M.G. Scutella, Shortest path algorithms in transportation models: classical and innovative aspects. In Equilibrium and advanced transportation modelling, P. Marcotte and S. Nguyen, eds., Kluwer, Norwell, MA, 1998, pages 245–281.

G. D. Glockner, G. L. Nemhauser and C. A. Tovey, Dynamic network flow with uncertain arc capacities: decomposition algorithm and computational results, Computational Optimization and Applications, vol. 18, pages 233-250, 2001.

D. Dubois and H. Prade, Operations on Fuzzy Numbers. J. Systems Sci. 9 (6), pages 613-626, 1978.

A. Bozhenyuk, E. Gerasimenko and I. Rozenberg, The methods of maximum flow and minimum cost flow finding in Fuzzy Network. In Ignatov, D., Kuznetsov, S., Poelmans, J. (Eds.) Concept Discovery in Unstructured Data Workshop (CDUD 2012) co-located with the 10th International Conference on Formal Concept Analysis (ICFCA 2012) May 2012, pages 1-12, Katholieke Universiteit Leuven, Leuven, Belgium, 2012.

K.G. Murty, Network programming, N.J.: Prentice Hall, 1992.

N. Christofides, Graph Theory: An Algorithmic Approach. Academic Press, New York, London, San Francisco, 1975.

I. Rozenberg, C. Gittis and D. Svyatov, Geoinformation System Object Land. In Proc. IPI RAN “Systems and Means of Informatics”, Science, Moscow, 2000.


  • There are currently no refbacks.

Copyright (c) 2013 Alexander Bozhenyuk, Evgeniya Gerasimenko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.