Control Systems and Computers, N3, 2016, Article 5
DOI: https://doi.org/10.15407/usim.2016.03.043
Upr. sist. maš., 2016, Issue 3 (263), pp. 43-53.
UDC 004.942
V.A. Vasyanin, PhD, Senior Researcher, Senior Researcher of Institute of telecommunications and global information space NAS of Ukraine, Kiev, Chokolovsky Boulevard, 13, 03186, Kiev, Ukraine, archukr@meta.ua
Computer Simulation of the Distribution and Discrete Multicommodity Flows Routing in a Communication Network
Introduction. We consider computer technology of modeling processes distribution and routing of multicommodity flows in communication network. The computer program is part of the software tools of automated information and analytical decision support system, which is being developed at the Institute of Telecommunications and Global Information Space of the NAS of Ukraine. Are given statement and a mathematical model of the problem, discusses the features and options to solve it. Considered numerical example of distribution and routing of container flows in road transport network.
Purpose. The purpose of research is to improve the functioning of the projected communication networks at decrease expense of scarce material, raw materials, energy, financial and human resources. Increased efficiency is achieved by using the
methodology of mathematical modeling and optimization of processes of processing and distribution of discrete flows, and a set of measures of information and analytical support and automate the decision-making procedures in the management of flows.
Methods. It is noted, that formulated nonlinear problem of distribution and routing flow is NP-hard, so has been proposed method of her transformation to a some set of simpler linear multidimensional knapsack problems with binding constraints. In transformed problem the initial nonlinear objective function on minimum replaced by a linear, when is maximized loading of arcs routes of vehicles or communication channels. Algorithms solutions are based on heuristic methods of solving multidimensional knapsack problem with using of specifics structure of problem and abstract data types. The features of cost functions on processing and transportation flows at the solving of problem for transport networks and data network are discusses.
Are considered different variant solutions at the possibility of branching flows and account of constraints on the average delay time flows in the network, as well as at strict account and relaxation others restrictions of problem.
Result. Describes the simulation program of distribution and routing flows, which consists from scenarios action of the designer and the software at selection various options for solving the problem, when some restrictions are taken into account, while others – not. The program run in interactive mode and allows to change routes, their characteristics, and other parameters of the designed network and calculate the basic technical and economic parameters of its functioning.
Conclusion. The proposed computer technology of solution a problem of distribution and routing flows allows modeling various options for the transport network or data transmission network; in interactive optimization mode change the routes vehicles or transmitting information, various parameters and constraints of the model and from the set of obtained results choose the best option with considering the selected purpose function and adopted constraints; improve the efficiency of the network functioning at the level of the current planning by optimizing the use of its existing resources and reducing operating costs, which makes it possible to reduce the tariffs for the carriage of goods or transfer of information to attract additional clientele and to ensure a constant profit growth; operatively to redistribute flows in the event of equipment failure at the nodes net and on transport routes, emergency situations, natural disasters, etc.; receive technical and economic indicators of network performance for given and predictive values of flows, assess the cost of additional resources and plan the magnitude of required investment for the modernization and development of nodes and transport routes.
Download full text! (In Russian).
Keywords: simulation, computer technology,multicommodity flows of correspondence, communications networks, hierarchical structures.
1. Trofimchuk, A.N., Vasyanin, V.A., 2016. “Komp’yuternoye modelirovaniye iyerarkhicheskoy struktury kommunikatsionnoy seti s diskretnymi mnogoproduktovymi potokami”. Upravlausie sistemy i masiny, 2, pp. 48–57 (In Russian).
2. Trofimchuk, A.N., Vasyanin, V.A., 2015. “Modelirovaniye upa-kovki, raspredeleniya i marshrutizatsii melkopartionnykh potokov v mnogoproduktovoy seti”. Problemy upravleniya i informatiki, 4, pp. 132–146. (In Russian).
3. Vasyanin, V.A., Trofimchuk, A.N., 2010. “Avtomatizatsiya protsessov prinyatiya resheniy v mnogoproduktovykh kommunikatsionnykh setyakh s melkopartionnymi diskretnymi potokami”. Yekologíchna bezpeka ta pri-rodokoristuvannya: Zb. nauk. prats’, 5, pp. 172–213. (In Russian).
4. Vasyanin, V.A., 2015. “Zadacha raspredeleniya i marshrutizatsii transportnykh blokov so smeshannymi vlozheniyami i yeye dekompozitsiya”. Problemy upravleniya i informatiki, 1, pp. 144–156. (In Russian).
5. Vasyanin, V.A., 2014. “Spravochnaya matritsa sliyaniya potokov
v zadachakh optimizatsii upakovok na mnogoproduktovykh setyakh”. Sistemny doslidzhennya ta informatciyni tekhnologii, 3, pp. 42–49. (In Russian).
6. Geri, M., Dzhonson, D., 1982. Vychislitel’nyye mashiny i trudnoreshayemyye zadachi. M.: Mir, 416 p. (In Russian).
7. Ahuja, R.K., Magnanti, T.L., Orlin, J.B., 1993. Network flows: theory, algorithms, and applications. Upper Saddle River (New Jersey): Prentice-Hall, Inc., 846 p.
8. Barnhart, C., Krishnan, N., Vange, P.H., 2009. “Multicommodity Flow roblems: In Encyclopedia of Optimization”, C.A. Floudas and P.M. Pardalos (Eds.). Springer, New York, pp. 2354–2362.
https://doi.org/10.1007/978-0-387-74759-0_407
Received 10.03.2016
