Authors A.V. Bozhenyuk, E.M. Gerasimenko, I.N. Rozenberg
Month, Year 06, 2015 @en
Index UDC 681.327
Abstract This article describes a method for minimum cost flow finding in a network with fuzzy arc capacities and values of transmission costs of one flow unit along the arc. This problem wasn’t wide described in the literature, as such tasks usually observed in crisp conditions and use Dijkstra’s algorithm for the minimum cost path finding. But since the use of the algorithm is limited due to the negative arc costs of the one flow unit along the arc of the network, proposed method assumes introduction of the node potentials for operating with the negative transmission costs arising during the flow passing along the arcs of the network. Similarly, we introduce a number of definitions and theorems, reflecting the optimality of the minimum cost flow obtained during the execution of the algorithm, in particular, the definition of the node potential, reduced costs, imbalance of the node (the node has excess, deficit or it is balanced A distinctive feature of the algorithm is a fuzzy character of the network parameters such as arc capacities and transmission costs which allows to take into account the environmental changes, in particular, repairs, traffic jams, changes in the gasoline prices. The paper presents a numerical example reflecting the proposed method, principles of the fuzzy residual network construction, network with potentials. The proposed method and its results can be used for solving the practical tasks of the shipping routes finding, cargo planning on the railways and roads.

Download PDF

Keywords Fuzzy network; the minimum cost flow; fuzzy reduced cost.
References 1. Busacker R.G., Gowen P. A procedure for determining a family of minimum-cost network flow patterns, Technical Report 15, Operations Research Office, John Hopkins University, 1961.
2. Klein M. A primal method for minimal cost flows with applications to the assignment and transportation problems, Management. Science, 1967, Vol. 14, pp. 205-220.
3. Maynika E. Algoritmy optimizatsii na setyakh i grafakh [Optimization algorithms for networks and graphs]. Moscow: Mir, 1981, 326 p.
4. Bozhenyuk A., Gerasimenko E. Flows Finding in Networks in Fuzzy Conditions, Supply Chain Management Under Fuzzines, Studies in Fuzziness and Soft Computing; Cengiz Kahraman and Basar Цztaysi (Eds). Springer-Verlag Berlin Heidelberg, 2014, Vol. 313, Part III, pp. 269-291. DOI: 10.1007/978-3-642-53939-8_12.
5. Rukovodstvo po otsenke propusknoy sposobnosti avtomobil'nykh dorog. Minavtodor RSFSR [Guidance for estimating road capacity. Minavtodor the RSFSR]. Moscow: Transport, 1982, 88 p.
6. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers, Ann Oper Res., 2006, pp. 305-315.
7. Kumar A., Kaur J., Singh P. Fuzzy Optimal Solution of Fully Fuzzy Linear Programming Problems with Inequality Constraints, International Journal of Mathematical and Computer Sciencesб 2010, No. 6:1, pp. 37-41.
8. Maleki H.R, Tata M., Mashinchi M. Linear programming with fuzzy variables, Fuzzy Sets and Systems, 2000, Vol. 109, pp .21-33.
9. Maleki H.R., Mashinchi M. Fuzzy Number Linear Programming: a Probabilistic Approach, J. Appl. Math. and Computing, 2004, Vol. 15, pp. 333-341.
10. Yoon K.P. A Probabilistic Approach to Rank Complex Fuzzy Numbers, Fuzzy Sets and Systems, 1996, Vol. 80, pp. 167-176.
11. Allahviranloo T., Lotfi F.H., Kiasary M.K., Kiani N.A., Alizadeh L. Solving Fully Fuzzy Linear Programming Problem by the Ranking, Applied Mathematical Sciences, 2008, Vol. 2, No. 1, pp. 19-32.
12. Bozhenyuk A., Gerasimenko E., Rozenberg I. 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, Katholieke Universiteit Leuven, Leuven, Belgium 2012, pp. 1-12.
13. Bozhenyuk А., Gerasimenko E., Rozenberg I. The task of minimum cost flow finding in transportation networks in fuzzy conditions, Proceedings of the 10th International FLINS Conference on Uncertainty Modeling in Knowledge Engineering and Decision Making Word Scientific, Istanbul, Turkey, 26-29 August 2012, pp. 354-359.
14. Floyd R.W. Algorithm 97: Shortest Path, Communications of the ACM, 1962, Vol. 5 (6), pp. 345.
15. Ford L.R. Jr. Network Flow Theory, Paper P-923, Santa Monica, California, RAND Corporation, 1956, 24 p..
16. Bellman R. On a Routing Problem, Quarterly of Applied Mathematics, 1958, Vol. 16, No. 1, pp. 87-90.
17. Johnson D.B. Efficient algorithms for shortest paths in sparse networks, Journal of the ACM, 1977, Vol. 24 (1), pp. 1-13.
18. Levit B.Yu. Algoritmy poiska kratchayshikh putey na grafe [Algorithms for finding shortest paths on a graph], Trudy instituta gidro-dinamiki SO AN SSSR: Sb. "Modelirovanie protsessov upravleniya [Proceedings of Institute of hydrodynamics of SB as USSR: the Collection "Modelling of control processes]. Novosibirsk, 1971, Issue 4, pp. 1117-1148.
19. Dijkstra E.W. A note on two problems in connextion with graphs, Numerische Mathematik, 1959, Vol. 1, pp. 269-271.
20. Edmonds J., Karp R.M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, 1972, Vol. 19, issue 2, pp. 248-264.
21. Tomizawa N. On some techniques useful for solution of transportation network problems, Networks, 1971, Vol. 1, pp. 173-194.
22. Pouly A. Minimum cost flows, 23 November, 2010. Available at:
23. Gerasimenko E.M. Metod potentsialov dlya opredeleniya zadannogo potoka minimal'noy stoimosti v nechetkom dinamicheskom grafe [Potentials method for minimum cost flow defining in fuzzy dynamic graph], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 4 (153), pp. 83-89.
24. Dubois D., Prade H. Operations on Fuzzy Number, J. Systems Sci., 1978, No. 9 (6), pp. 613-626.
25. Malyshev N.G., Bershteyn L.S., Bozhenyuk A.V. Nechetkie modeli dlya ekspertnykh sistem v SAPR: Monografiya [Fuzzy models for expert systems in CAD systems: Monograph]. Moscow: Energoatomizdat, 1991, 136 p.

Comments are closed.