On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network
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 (hundr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
V.M. Glushkov Institute of Cybernetics
2021-12-01
|
| Series: | Кібернетика та комп'ютерні технології |
| Subjects: | |
| Online Access: | http://cctech.org.ua/13-vertikalnoe-menyu-en/299-abstract-21-4-1-arte |
| _version_ | 1811248707659628544 |
|---|---|
| author | Nikolay Zhurbenko Boris Chumakov |
| author_facet | Nikolay Zhurbenko Boris Chumakov |
| author_sort | Nikolay Zhurbenko |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T15:32:43Z |
| format | Article |
| id | doaj.art-bbb083c79a044cce99d995b1aab4f3d1 |
| institution | Directory Open Access Journal |
| issn | 2707-4501 2707-451X |
| language | English |
| last_indexed | 2024-04-12T15:32:43Z |
| publishDate | 2021-12-01 |
| publisher | V.M. Glushkov Institute of Cybernetics |
| record_format | Article |
| series | Кібернетика та комп'ютерні технології |
| spelling | doaj.art-bbb083c79a044cce99d995b1aab4f3d12022-12-22T03:27:02ZengV.M. Glushkov Institute of CyberneticsКібернетика та комп'ютерні технології2707-45012707-451X2021-12-01451110.34229/2707-451X.21.4.110-34229-2707-451X-21-4-1On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation NetworkNikolay Zhurbenko0Boris Chumakov1V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivV.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivIntroduction. 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.http://cctech.org.ua/13-vertikalnoe-menyu-en/299-abstract-21-4-1-arteoptimal planningmathematical modelsubgradient methodsdual problemsoftware |
| spellingShingle | Nikolay Zhurbenko Boris Chumakov On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network Кібернетика та комп'ютерні технології optimal planning mathematical model subgradient methods dual problem software |
| title | On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network |
| title_full | On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network |
| title_fullStr | On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network |
| title_full_unstemmed | On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network |
| title_short | On the Problem of Planning of Multi-Product Flows and Modernization of the Transportation Network |
| title_sort | on the problem of planning of multi product flows and modernization of the transportation network |
| topic | optimal planning mathematical model subgradient methods dual problem software |
| url | http://cctech.org.ua/13-vertikalnoe-menyu-en/299-abstract-21-4-1-arte |
| work_keys_str_mv | AT nikolayzhurbenko ontheproblemofplanningofmultiproductflowsandmodernizationofthetransportationnetwork AT borischumakov ontheproblemofplanningofmultiproductflowsandmodernizationofthetransportationnetwork |