Data Structures and Route Reduction Procedures in the Problem of Distribution Transport Flows in a Communication Network

Introduction. In the problems of the distribution and routing of flows in communication networks, the input data is vehicle routes or data transmission channels. For the distribution of flows in this problems in optimization algorithms use special data structures – abstract data types, which describe the relationship between distributed flows and routes, as well as route reduction procedures, which can significantly reduce the number of such connections. The paper develops data structures and route reduction algorithms that allow solving the problem of distribution of flows in the case when the number of specified routes is very large, and the amount of computer RAM is limited. Estimates of the time complexity of the algorithm for reducing routes by nodes and arcs, as well as the algorithm for generating a reference data structure, have been obtained. The proposed algorithms were tested on networks with the number of nodes from 50 to 500 and the number of routes from 1225 to 124750, which showed their performance, good computational efficiency and they can be used in practical problems of distribution and routing of flows on large-dimensional networks. Purpose. We present an effective algorithm for the route reduction that allow solving the problem of distribution of flows in the case when the number of specified routes is very large, and the amount of computer RAM is limited. The technique. To get our estimators of time complexity of developed algorithms, we use numerical examples and simulations. Results. Our proposed algorithms it is shown that is sufficient accuracy and speed, which allows us to assert their practical applicability for engineering calculations on large-scale networks. Scientific novelty and practical significance. We demonstrate robustness and efficiency of proposed algorithms through rigorous computer simulations. Keywords: multicommodity networks, discrete flows, problems of combinatorial optimization, computer modelling.