Article

Article title POTENTIALS METHOD FOR MINIMUM COST FLOW DEFINING IN FUZZY DYNAMIC GRAPH
Authors E.M. Gerasimenko
Section SECTION I. MATHEMATICAL MODELS AND METHODS
Month, Year 04, 2014 @en
Index UDC 681.327
DOI
Abstract This article describes a method for minimum cost flow finding in a fuzzy dynamic graph. Algorithm based on the potentials introduction for any arc of the fuzzy graph will be applied for minimum cost determining. Present algorithm allows escaping the necessity of operating with negative costs, as it deals with «кreduced costs». This modification leads to improving of time complexity of the algorithm. Potentials are computed according to the paths of minimum cost from the initial node to other nodes of the graph. It is not necessary to check all nodes of the graph, as termination condition of the algorithm is assigning the permanent label to the final node. Using node potentials leads to necessity of operating with «reduced costs», receiving based on the initial meanings of the transmission costs and computing of the node potentials. The rules of the «time- expanded» graph construction corresponded to the initial and fuzzy residual network construction, which operates reduced costs are described. The fact that parameters of the graph can be changed in time is taken into account.

Download PDF

Keywords Fuzzy dynamic graph; minimum cost flow; node potentials; time-expanded graph.
References 1. Bozhenyuk Alexandr and Gerasimenko Evgeniya. Flows Finding in Networks in Fuzzy Conditions // Cengiz Kahraman, Basar Oztaysi (eds.), Supply Chain Management Under Fuzziness, Studies in Fuzziness and Soft Computing, Springer-Verlag Berlin Heidelberg. – 2014. – Vol. 313. – P. 269-291.
2. Боженюк А.В., Шадрина В.В. Использование нечеткого логического вывода для управления технологическим процессом на компрессорной станции // Обозрение прикладной и промышленной математики. – 2007. – Т. 14. – Вып. 5. – С. 857-858.
3. Bozhenyuk Alexander and Gerasimenko Evgeniya. Methods for Maximum and Minimum Cost Flow Determining in Fuzzy Conditions // World Applied Sciences Journal 22 (Special Issue on Techniques and Technologies). – 2013. – P. 76-81.
4. Боженюк А.В., Герасименко Е.М. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети // Инженерный Вестник Дона. – 2013. – № 1. – C. 12.
5. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // In Combinatorial Structures and Their Applications, New York, NY, 1970, Gordon and Breach. – P. 93-96.
6. Tomizawa N. On some techniques useful for solution of transportation network problems // Networks. – 1971. – № 1. – P. 173-194.
7. Chabini I.,Abou-Zeid M. The Minimum Cost Flow Problem in Capacitated Dynamic Networks. In TRB 2003 Annual Meeting CD-ROM. – P. 1-30.
8. Боженюк А.В., Герасименко Е.М., Розенберг И.Н. Определение потока минимальной стоимости в нечетком динамическом графе // Известия ЮФУ. Технические науки. – 2013. – № 5 (142). – C. 149-154.

Comments are closed.