V.I. Munerman – Ph.D.(Eng.), Associate Professor, Department of Informatics, Smolensk State University E-mail: vimoon@gmail.com

T.A. Samoylova – Ph.D.(Eng.), Associate Professor, Department of Informatics, Smolensk State University E-mail: tatsamoilova24@gmail.com

The article deals with the algebraic approach to increasing the efficiency of data processing when solving the problems of constructing routes. The approach is based on the theory of multidimensional matrices and special two-basic algebraic systems (abstract algebraic machines). This approach allows efficient parallelization of algorithms for constructing all possible routes, as well as the use of technology in database to build all routes. It is shown that this is possible due to the isomorphism of the algebra of multidimensional matrices and the relational algebra for the class of problems under consideration. As the basic algebraic operation, one of the variants of multiplication of multidimensional matrices (1,0)-convoluted product is used, for which summation of elements is not performed (there are no Cayley indices). The algorithm is given for constructing all routes with given properties, which realizes multiple applications of this operation. A description of the representation of sparse multidimensional matrices in a relational database is given. An algorithm is given for constructing all routes with given properties that implements multiple operations of the Join operation. An example illustrating the proposed approach is given.

1. Bast H. Car or public transport – two worlds // Efficient Algorithms. LNCS. Springer. 2009. V. 5760. P. 355−367.
2. Belyakov S.L., Kolomiytsev Ya.A., Rozenberg I.N., Savelyeva M.N. Model resheniya zadachi marshrutizatsii v intellektualnoy geoinformatsionnoy sisteme // Izvestiya YuFU. Tekhnicheskiye nauki. 2011. T. 118. № 5. S. 113−119.
3. Ageyev D., Ignatenko A., Wehbe F. Design of Information and Telecommunication Systems with the Usage of the Multi-Layer Graph Model // XII International Conference «The Experience of Designing and Application of CAD Systems in Microelectronics». LvivPolyana. Ukraine. 2013. P. 1−4.
4. Miller J.A., Ramaswamy L., Kochut K.J., Fard A. Research Directions for Big Data Graph Analytics // IEEE International Congress on BigData. 2015. P. 785−794.
5. Margolis B.I., Muzanna M.M. Sintez magistralnykh telekommunikatsionnykh setey // Programmnyye produkty i sistemy. 2014. № 1(105). S. 162−168.
6. Semenov Yu.N., Semenova O.S. Primeneniye metodov klasterizatsii pri organizatsii mezhdunarodnykh perevozok gruzov // Vestnik KuzGTU. 2016. № 6. S. 201−205.
7. Masum K., Faruque F., Shahjalal M., Sarker H. Solving the Vehicle Routing Problem using Genetic Algorithm // International Journal of Advanced Computer Science and Applications. 2011. V. 2. № 7. 126−131.
8. Sokolov N.P. Vvedeniye v teoriyu mnogomernykh matrits. Kiyev: Naukova dumka. 1972. 176 s.
9. Munerman V.I. Modeli obrabotki bolshikh obyemov dannykh v sistemakh massovogo parallelizma // Sistemy vysokoy dostupnosti. 2013. V. 9. № 1. S. 35−43.
10. Munerman V.I. Arkhitektura programmno-apparatnogo kompleksa dlya massovoy obrabotki dannykh na baze mnogomerno-matrichnoy modeli // Sistemy vysokoy dostupnosti. 2015. T. 11. № 2. S. 13−18.
11. Zakharov V.N., Munerman V.I. Parallelnyy algoritm umnozheniya mnogomernykh matrits // Sovremennyye informatsionnyye tekhnologii i IT-obrazovaniye. 2015. T. 2. № 11. S. 384−390.