A two-step problem of optimizing the structure and routing of flows in a hierarchical multicommodity network

The paper discusses the methodology of mathematical modeling of the two-stage problem of optimization of the backbone hierarchical communication network with multicommodity discrete flows and parameters. The methodology is based on the sequential solution of the problem of optimizing the network structure and the problem of distribution and routing of discrete correspondence flows. As a rule, such networks consist of a decentralized backbone network and fragmented networks in the internal service areas of the backbone nodes. There are four types of network nodes and three levels of its hierarchy. In a multicommodity network, each node can exchange correspondence (products, goods, cargo, messages) with other nodes. Correspondence is characterized by a source node, a drain node and a value, which for transport networks is given by the number of packaged goods, cargo in a package of a unified size, and for data transmission networks – by the number of bytes, kilobytes, etc. In the transport backbone network, all correspondence is first sorted by destination addresses, packed in transport blocks (containers), and then transported in vehicles along the transport highways. In data networks, correspondence is also sorted by destination addresses (multiplexed), packaged in virtual transport blocks, and then transmitted over trunk communication channels. The size (capacity, volume) of the transport blockt is set by the parameter, and is determined by the number of units of correspondence that fit into it. Mathematical models of problems of optimization of network structure, distribution and routing of flows, and an example of numerical modeling of solving problems on a transport network containing 120 nodes and 300 unoriented arcs are presented. Experimental studies have shown high computational efficiency of the proposed algorithms and programs, and they can be recommended for the practical solution of problems of optimizing the processes of processing and transporting flows in communication networks of large dimensions.