Authors E. M. Gerasimenko
Month, Year 04, 2018 @en
Index UDC 519.178
Abstract This article is devoted to solving the problem of the maximum two-commodity flow finding in a fuzzy transportation network. The task of determining the volume of a multi-commodity flow passing through the transportation network is an important task in transport planning and optimization of traffic. This article describes a variation of this task, in particular, the problem of determining the flow of two commodities in a transportation network. The main difficulty of this task is the fact that the max-flow min- cut theorem is not fulfilled for such tasks, however, it is performed to find the flow of two commodities in the undirected transportation network. A feature of this task is the ability of the first flow to block the flow of the second product in such a way that we may not get the optimal result. The central part of this task is the parameters of the transportation network, presented in a fuzzy form, such as the arc capacities of its arcs. The developed method uses a modified search path method for augmented paths, allowing to take into account fuzzy network parameters assigned to the arcs of the graph. The described method can be applied when planning the transportation of two types of goods, each of which has its own source and sink, for example, in the case of passenger and freight trains or cars and trucks. The method of operating with fuzzy numbers is considered, which does not lead to a “blurring” of the boundaries of the resulting number and allows operating with fuzzy boundaries at the last iterations, while at the previous preceding iterations they are performed with calculations only with centers of fuzzy numbers.

Download PDF

Keywords Two-commodity flow; fuzzy graph; fuzzy double path..
References 1. Hu T. Multi-commodity network flows, Oper. Res., 1963, No. 11, pp. 344-360.
2. Itai A. Two-commodity flow, Journal of the Association for Computing Machinery, 1978,
Vol. 25, No. 4, pp. 596-611.
3. Rajagopalan S. Two-commodity flow, Oper. Res. Lett., 1994, Vol. 15, pp. 151-156.
4. Costa M., Letocart L., Roupin F. Minimal multicat and maximal integer multiflow: A survey, Eur. J. Oper. Res., 2005, Vol. 162 (1), pp. 55-69.
5. Kureichik V., Gerasimenko E. Approach to the Minimum Cost Flow Determining in Fuzzy Terms Considering Vitality Degree. In Silhavy R., Senkerik R., Kominkova Oplatkova Z., Prokopova Z., Silhavy P. (eds), Artificial Intelligence Trends in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing. Springer, Cham, 2017, Vol. 573, pp. 200-209.
6. Bozhenyuk A., Gerasimenko E., Kacprzyk J., Rozenberg I. Flows in networks under fuzzy conditions, Studies in Fuzziness and Soft Computing. Heidelberg: Springer-Verlag, 2017,
Vol. 346, pp. 269-291.
7. Bozhenyuk A.V., Gerasimenko E.M., Rozenberg I.N. Razrabotka metoda opredeleniya potoka minimal'noy stoimosti v transportnoy seti s nechetkimi propusknymi sposobnostyami i stoimostyami s pomoshch'yu metoda potentsialov [Development of the minimum cost flow method with fuzzy arc capacities and costs by the potential method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 138-149.
8. Bozhenyuk A, Gerasimenko E., Rozenberg I. Determining the Minimum Cost Flow in Fuzzy Dynamic Network with GIS «ObjectLand», Proceedings of 9th International Conference on Application of Information and Communication Technologies, AICT 2015. Rostov on Don, 2015, pp. 294-298.
9. Kolman P., Scheideler C. Improved bounds for the unsplittable flow problem, J. Algor., 2006, Vol. 61 (1), pp. 20-44.
10. Barnhart C., Krishnan N., Vance P.H. Multicommodity Flow Problems. In Floudas C., Pardalos P. (eds), Encyclopedia of Optimization. Springer, Boston, MA, 2008.
11. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems, Oper Res., 2000, Vol. 48 (2), pp. 318-326.
12. Karakostas G. Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, 2002, pp. 166-173.
13. McBride R.D., Carrizosa E. Conde E. Munoz-Marquez M. Advances in solving the multi-commodity flow problem, Interfaces, 1998, Vol. 28 (2), pp. 32-41.
14. Sedeño-Noda A., González-Martín C., Alonso-Rodríguez S. A new strategy for the undirected two-commodity maximum flow problem, Computational Optimization and Applications, 2010, Vol. 47 (2), pp. 289-305.
15. Kureichik V., Gerasimenko E. Multi-Commodity Maximum Flow Determining in a Fuzzy Graph with Vitality Degrees, Proceedings of 11th International Conference on Application of Information and Communication Technologies, AICT 2017, Moscow, Russia, pp. 347-351.
16. Bozhenyuk A., Gerasimenko E., Rozenberg I. Method of Maximum Two-Commodity Flow Search in a Fuzzy Temporal Graph, Proceedings of the 10th Conference of the European Society for Fuzzy Logic of and Technology EUSFLAT-2017, September 11-15, 2017, Warsaw, Poland, pp. 249-260.
17. Cormen T.H, Leiserson C.E, Rivest R.L., Stein C. Introduction to Algorithms (3rd ed.). MIT Press and McGraw–Hill, 2009.
18. Ganesan K., Veeramani P. Fuzzy Linear Programs with Trapezoidal Fuzzy Numbers, Ann Oper Res., 2006, pp. 305-315.
19. 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 6:1, 2010, pp. 37-41.
20. Bozhenyuk A. Gerasimenko E., Rozenberg I. Algoritm nakhozhdeniya nechetkogo potoka v transportnoy seti s nechetkimi stoimostyami i propusknymi sposobnostyami [Algoritm nahozhdeniya nechetkogo potoka v transportnoy seti s nechetkimi stoimostyami i propusknyimi sposobnostyami], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 5 (130), pp. 118-122.
21. Gerasimenko E. Nakhozhdenie potoka minimal'noy stoimosti v transportnoy seti metodom ranzhirovaniya matematicheskogo ozhidaniya nechetkikh funktsiy stoimostey [Minimum cost flow finding in the network by the method of expectation ranking of fuzzy cost functions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 4 (129), pp. 247-251.

Comments are closed.