2021, issue 4, p. 5-11
Received 12.09.2021; Revised 30.09.2021; Accepted 21.12.2021
Published 30.12.2021; First Online 27.01.2022
https://doi.org/10.34229/2707-451X.21.4.1
Previous | FULL TEXT (in Ukrainian) | Next
On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network
Nikolay Zhurbenko *, Boris Chumakov
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The problems of optimal planning of multi-product flows on transportation networks have a variety of important practical applications (transportation, logistics, communication networks). The mathematical models of these problems, as a rule, are characterized by a large dimension (hundreds of thousands of variables). Due to the specific features of multi-product transportation problems (pronounced block structure), the use of standard general-purpose optimization packages for their solution is not advisable. In this work of an applied nature, we propose a method for solving one class of such problems, taking into account their specificity. The method is based on the decomposition scheme with respect to a set of binding constraints. The corresponding dual problem is the nonsmooth optimization problem. To solve it, a new version of the subgradient algorithm with space dilation of variables is used. This approach to solving block optimization problems has been tested in solving a wide class of applied problems and, as experience shows, is characterized by a fairly high efficiency.
Purpose of the article to develop a solution method and software for the problem of optimal planning of multi-product flows and modernization of the transportation system.
Results. A mathematical model of the problem of optimal planning multi-product flows on the transportation network is proposed. The model is based on a variant transportation realization scheme. The software is developed in the C++ language in the style of object-oriented programming. The following algorithms are used as basic elements of the software: an algorithm for finding the shortest paths on a graph, an algorithm for solving a transportation problem on a graph, nonsmooth optimization algorithm.
Conclusions. The output data of the developed software determines the following information: rational transportation scheme, critical by capacity sections of the transportation network, recommendations for the rational distribution of funds for the reconstruction of the transportation network. The software is designed to solve the problems of long-term planning of the functioning and development of the transportation system.
Keywords: Optimal planning, mathematical model, subgradient methods, dual problem, software.
Cite as: Zhurbenko N., Chumakov B. On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network. Cybernetics and Computer Technologies. 2021. 4. P. 5–11. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.4.1
References
1. Shor N.Z. Minimization methods for non-differentiable functions. Berlin: Springer-Verlag, 1985. 178 p. https://doi.org/10.1002/bimj.4710280427
2. Zhurbenko N.G., Chumakov B.M. On one model of multicommoditi transportation problem. Teoríya optymal'nykh ríshen’. 2013. P. 119–124. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/85053
3. Mikhalevich, V.S., Sergienko, I.V., Trubin, V.A., Shor N.Z. et al. Program package for solving large-scale production and transportation planning problems (PLANNER). Cybern Syst Anal. 1983. 19 (3). P. 362–382. https://doi.org/10.1007/BF01072152
4. Zhurbenko N.G. Towards a two-stage scheme of the decomposition method for solving block linear programming problems. Teoríya optymal'nykh ríshen’. 2001. P. 22–26. (in Russian)
5. Belyaeva L.V., Shor N.Z., Zhurbenko N.G. On the method of solving one class of dynamic distribution problems. Ekonomika i matematicheskiye metody. 1978. 14 (1). P. 137–146. (in Russian)
6. Zhurbenko N.G., Lykhovyd O.P. On the numerical efficiency of a modification of r-algorithm. Komp'uternaya matematika. 2019. N 1. P. 2–10. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/161942
7. Shor N.Z., Zhurbenko N.G. A minimization method using the operation of extension of the space in the direction of the difference of two successive gradients. Cybern Syst Anal. 1971. 7 (3). P. 450–459. https://doi.org/10.1007/BF01070454
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next