Large-scale rail company operation requires extensive service network (SN) distributed in many regions. The complexity of keeping SN in working condition requires its separation on fragments - regional SN. Each one ensures the operation of the respective regional section of rail network, called a polygon. Responsible for support of each regional SN has its centre. We investigated the problem of optimizing the number of such regional support centers and boundaries of their responsibilities. The solution to these problems related to optimal graph partitioning. We have developed methods for partitioning large-scale networks taking into account the speci cs of the Russian railways. We base this decomposition on the de nition of the complexity of managing the rail network and its polygons. Conceptual and methodological approaches to assessing the complexity of such managing are considered. Mentioned speci cs and NP-hardness do not allow the use of standard approaches to the solution of those problems. Therefore we developed methods for local search and heuristic optimization algorithms of nding the number of regional support centers and the boundaries of their responsibility minimizing the maximum complexity of regional management. These algorithms based on proposed methods of network reduction taking into account informal requirements and restrictions. The obtained optimization results were used in programs of holding Russian Railways development, such as modernization of Baikal-Amur main line and the construction of high-speed rail Moscow-Kazan.
A large-scale rail company carries out transportation processes on an extensive rail network located on a vast territory (for example, in di erent regions or even Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org countries). For this purpose, a system of territorial branches is created to ensure the technological processes of company transportation on regional fragments of the rail network.
Under conditions of changes, the company should have a program for the
development of those branches. For example, the holding Russian Railways
implements the development program of its branch Far Eastern Railway. According
to this program, the section of the Baikal-Amur mainline (BAM) with a length
of 504 km should be equipped with a service network (SN), which includes an
automatic blocking and dispatching system for train tra c [
In this regard, there are problems both in the development of CoSN and in
supporting its e ciency in the development process. For this, forecasting and
optimal planning of the structures of the CoSN servicing are necessary. In this
paper, based on the general concepts of distributed system design [
Together with territorial branches, CoSN is also developing. This happens in
stages and takes time. For example, these works at the BAM, begun in 2016,
will last until 2020 [
Principle of fragmentation. Support of large-scale CoSN, distributed across many regions, requires its separation into fragments - regional SNs. Each such fragment provides technological processes of transportations on a corresponding site of a rail network, called a polygon. Responsibility for the functioning of such a fragment is borne by the corresponding regional center of SN support (brie y - Regional Service Center or RSC). The RSC operates within its competence, supporting the SN, which, in turn, servicing transportation within the relevant polygon. Thus, the e ective functioning of CoSN should be provided by an organizational structure that includes RSCs. Thus there are two questions: 1) how many RSC should become in the company, if the plans of development of its rail network and technological processes of transportation will be realized? 2) what will be the boundaries of responsibility of each RSC? The answers to these questions are based on the following principle.
Principle of adequacy means that the subject of the control system should be adequate to the managed object. In the process of company evolution, CoSN should ensure the changing needs of the company. In accordance with the principle of adequacy, control system must be adequate to the managed object. Therefore CoSN, as an element of the control system, should be adequate to the management facility - the company's production complex, including its railway network and technological processes. Thus CoSN, like the company itself, should be large-scale. The RSC operates within its competence, supporting the regional SN, which provide services on regional fragments of the rail network.
Principle of simpli cation. It is well known that railway processes are associated with increased danger. Therefore, the most important requirement for the company governance system is reliability. The more complex the control system, the less reliable it is, and the more time it takes to restore it after an accident. In addition, the more complex the management system, the more expensive it is. Therefore, we should strive to reduce the complexity of management.
In work [
Consider the prerequisites for evaluating the SN complexity. In accordance with the principle of adequacy, the subject of the control system should be adequate to the managed object. Thus the complexity of CoSN is determined by the complexity of the company's management. In turn, the complexity of management of a company (or part of it) is due to the complexity of managing of corresponding rail network and transport processes. Thus the complexity of regional SN is determined by the complexity of managing the corresponding polygon.
In addition, when assessing the complexity of SN, such characteristics as
reliability, cost, maintainability, etc. are important [
Thus, the complexity of support of regional SN is determined by the complexity of this SN and, consequently, by the complexity of managing the corresponding polygon. Based on this, we will further use the hypothesis of a directly proportional dependence of the complexity of regional SN support and the complexity of managing the corresponding polygon.
The complexity of CoSN depends on the complexities of its constituent fragments - regional SNs. In turn, the complexity of regional SN is determined by the complexity of the rail network and technological processes. Therefore, when creating a support structure for CoSN, we must, above all, strive to simplify the most complex regional SNs. In view of the foregoing, this means that the best characteristics of CoSN (such as reliability, economy, maintainability) are achieved with the same or similar regional SN complexity.
Complexity and adequacy. In accordance with the principle of adequacy,
the estimation of the CoSN complexity can be based on an assessment of the
complexity of the whole rail network and the transportation process of the
company. Thus the forecasting of the regional support structure for CoSN can be
based on the company's plan for the development of the rail network and the
technological processes of transportation. At the same time, the complexity of
supporting the regional SN should be adequate for the complexity of
managing the relevant polygon. There are 2 prerequisites for ensuring such adequacy.
First, there is a methodology for assessing the complexity of managing the
railway network and its polygons [
Optimization of the regional support structure of CoSN. Note that the appearance of even one new RSC leads to a change in the existing service boundaries and a ects the conditions and complexity of the operation of all other RSCs. In this connection, there arises the problem of choosing the organizational structure of CoSN on the basis of the requirement to minimize the complexity of its support. It is necessary to determine the required number of support centers and the boundaries of their competence, taking into account the forecast of the state of the company, its rail network and transportation processes. This leads to the problem of optimizing the number of RSCs and their boundaries, which minimizes the projected maximum complexity of supporting the regional SN, taking into account the company's development plan. As was shown above, the complexity of supporting the regional SN is determined by the complexity of managing the appropriate polygon. Proceeding from the hypothesis of a directly proportional dependence of the complexity of the regional SN support and the complexity of the corresponding polygon, this problem reduces to the problem of optimizing the number and boundaries of polygons, in which the forecast maximum complexity of the polygons is minimized taking into account the company's development plan.
We consider methods for solving an optimizing problem of the polygons
number and their boundaries using the methodology of synthesis of optimal
structures [
Let a company rail model is a network S with n nodes. The network S is divided into a system of N transport subnets consisting of N polygons giN ; i = 1; :::; N , where n < N . It is assumed that each polygon is a connected subgraph of the network S. Suppose that a partition into polygons satis es the conditions: SiN=1 giN = S and giN \ gjN = ;, where i 6= j; i; j = 1; :::; N . The boundaries of each of the partitions pass through the vertices of the network. We supplement the network at each node with an edge that is a loop. Moreover, for each kind of partition, the loop at the node through which the boundary passes can only refer to one polygon. Each polygon has a management center.
There are a large number of methods for solving the problem of
partitioning a graph. Classi cation of these methods and a detailed review is presented
in [
KN (gN ) = KN (K0gN ; K1gN ; :::; KigN ; :::; KNgN ) Kmax: The set GN may not contain certain "forbidden" partitions, determined by the speci cs of the particular model. In general, the problem of optimizing the complexity of control is posed as minimizing KN (gN ) by choosing the number of polygons N in the partition and the partition gN itself on the set GN : max max KN (gN );
Nmin N Nmax gN 2GN where Nmin and Nmax de ne low and upper restrictions on the polygons number.
In general, such a problem is di cult to solve. Therefore, it is proposed to replace it (decompose), possibly with loss of accuracy of the solution for two problems: estimates of the number of polygons N in partitions, and of the partition itself. In this case, we propose to replace the search for an optimal partition on a set GN for a given N by a search for an equisyllabic decomposition (partition).
The principle of the equal complexity of a partition : the di erence in complexity of polygon control should be minimal: gN = min [ max KiG(ligiN ) g2GN 1 i N min KiG(ligiN )]; 1 i N where gN is a equisyllabic partition.
This principle re ects a partitioning rule at which the polygons management complexities are very close. For the further investigation of the problem, it is necessary to describe procedures for the polygon complexity indicators formation.
The complexity of polygon management. As noted above, the complexity of polygon management KigN = KigN (ligiN ) is formed as a given function of a complexity parameters of polygon elements ligiN . A set of parameters ligiN is a set of indicators for the di culty of managing the network edges (edges representing loops at the nodes of the network characterize the complexity of the corresponding node). Note that the management center of each polygon has its own idea of the complexity index corresponding to the edge (i; j). Thus, all the complexity indicators of network elements (vertices and edges) can be represented as N matrices LkN = klij kn, where likjN are the complexity indices of the edge (i; j) from kN the point of view of the kN -th polygon in the partition gN . Note that likjN = ljkiN . We supplement the network with an edge (i; j) of zero complexity, where the i-th node is not connected to the j-th node by an edge in the network under consideration. We de ne as wikN = likiN the i-th node complexity (i = 1; :::; n). Let us brie y describe one of the options for calculating the complexity of polygon. Let's imagine the index of complexity of the polygon control as a sum: KkgNN ( ) = KkgNN #( ) + bKkgNN ##( ), where b is the weight coe cient, 0 b < 1. Suppose that the rst term in KkgNN ( ) depends on the set of indices of the edges entering the i-th polygon. For example, the complexity of a polygon management (and, correspondingly, the complexity of SN support) depends on the intensity of the transportation process, the operational length of the freight trains, the availability of infrastructure facilities in the rail network. In the case of the additive index, KkgNN #( ) = kN Pi;j2pkN likjN = kN Pi;j2pkN vi1jkN vi2jkN vi3jkN : : :. Here kN are the coe cient allowing to bring the value of the indicator of complexity to some meaningful representation, for example, to estimating the time spent on management, likjN = vi1jkN vi2jkN vi3jkN : : : { the complexity index of the j-th edge of the polygon, likiN = vi1ikN vi2ikN vi3ikN : : : { the complexity of the i-th node, pkN { is the set of edges and nodes included in kN -th polygon. Values vi1jkN are calculated as follows: vi1jkN = 1 + a1kN (zi1jkN =ze1kN 1), where a1kN { the weight coe cient, zi1jkN { the intensity of tra c ows on the j-th edge of the network, ze1kN { the average (normative) intensity. Values vi2jkN ; vi3jkN : : : are calculated using a similar formula, and characterize, for example, the operational length of the track, the number of large customers on the j-th edge, and the gN ##( ) in KkgNN ( ) depends on the set of volume of loading. The second term KkN indicators of the edges of the kN subnet, but only those edges that are incident to the vertices located at the boundary of the kN -th polygon. 4
The above problem of complexity optimization is decomposed into two subproblems. Let's consider the rst subproblem { the estimation of the polygons number provided the network is divided into equivalent polygons. Suppose that we can realize the "ideal case" when gN = 0, i.e. in the partition gN all the polygons have the same complexity. In this case, we can write down that the complexity of the control of each polygon is equal to RgN = min1 i N Kig(ligiN ) = ; K1 ; : : : ; Ki ; : : : KN sented in the form KN (gN ) = KN (K0gN ; RgN ; : : : ; RgN ; : : : RgN ). max1 i N Kig(ligiN ), where gN is the ideal equisyllabic partition. Then the complexity index KN (gN ) = KN (K0gN gN gN gN ) can be repre
We introduce two more assumptions. Firstly, let the complexity K0g = K0g(N )
of the body coordinating the activities of the polygons be represented as K0g =
K0g(N ) = a1N +a2N 2. Here the rst term re ects the complexity of management
of each of the equisyllabic polygons, and the second term is the complexity of
coordination of pairwise interaction between polygons. Coe cients a1 and a2
characterize, for example, the time spent for management each polygon and
coordinating their interactions. Secondly, let the value RgN decrease depending
on the number of polygons, because sizes of polygons decrease. Let us assume
that this quantity decreases proportionally to some power m of the number of
polygons RgN = B=N m. In articles [
Network compression. We use the network compression procedure in the algorithms for determining polygon boundaries presented below as the main procedure. By reduction (compression) of a network we call the transformation of the initial network to a simpler one with a smaller number of edges and nodes due to: { the union of some edges and nodes; { a priory binding of individual edges and nodes to certain centers (their number is determined by the number of polygons N ).
Reduction determines the typical step used in the following algorithms for sequential formation of polygons. The reduction and the standard step of the algorithms are described by the following procedure. Renumber the nodes of the received network so that the rst N numbers receive the selected nodes (polygon centers), i = 1; : : : ; N; : : : ; n. We denote Lk0 = likj0 0n the initial matrices of the arcs and nodes of the network under consideration. Here, the superscript 0 denotes the step number in the successive reduction of network, the index k denotes the representation of the matrix from the point of view of the center of the k-th polygon. Note that this matrix is symmetric, has dimension n, and its elements take non-negative values. In the case where the i-th node is not connected to the j-th node by an edge in the network under consideration, we supplement the network with an edge (i; j) of zero complexity, i.e. likj0 = ljki0 = 0. Let that the selected node are not joined by edges of nonzero length. The polygons formation is represented as a consecutive assignment of edges and nodes to one or another selected node, which is the center of the polygon, and the formation of a new network with a smaller number of nodes per unit (network compression). This transforms the matrix Lk0 = likj0 0n into matrices Lk1 = likj1 1n 1 of dimension n 1 in the rst step, and at the second step in dimension n 2, and so on, until we obtain a matrix of dimension N at the (n N )-th step. Let us consider the rst step of reduction. Let the unselected node with the number j (j > N ) connected to the edge (i; j) be attached to the selected node with the number i (i N ), and lij > 0. Then the transformation of the complexities of nodes and edges of the network will be determined by the following relations: wi1 = liki1 = KigN 1 = KigN 1(ligiN 1), where the set ligiN 1 includes the node with the number j, the edge liij0 and ljkt1 for the attached edges (j; t), where t is the number of the unseparated node such that ljkt0 > 0. Similar to the rst step, the following reduction steps are carried out. The complexity recalculation formulas at the -th step have the form wi +1 = liki +1 = KigN +1 = KigN (ligiN +1) where the set ligiN +1 includes the joining node with the number j, the edge liij and k +1 = 0 are established for the attached edges (j; t), where t is the number of ljt the unseparated node such that ljkt > 0, = 1; : : : ; n N . After carrying out the described reduction steps, N diagonal matrices corresponding to the number of polygons are obtained. There is complexity of the k-th polygon at the intersection of the k-th row and the k-th column of the k-th matrix.
Algorithms of De ning Polygon Boundaries. We base construction of heuristic algorithms on local optimization. The polygon centers are located at N nodes of the initial network, and then we use the method of the reduction described above. We perform this reduction according to some rules characterizing the heuristic sequentially compresses the network. The algorithms are based on a directional search of options and sequential expansion of subnets (reduction of the source network), until a complete network partition is obtained. We carried out the reduction process in a directed way to improve the indicator of the equidistance of the polygons at each step. To reduce the number of searchable variants algorithms introduce additional heuristic requirements to the "geometry" of polygons. Some railway geometry requirements de ne speci cs of algorithms.
Algorithm of the nearest center. Let us the net already reduced at some -th step. We calculate the complexity of the reduced nodes wk selected as centers of the polygons, where k = 1; : : : ; N . In calculating the complexity of polygon, we use the representation of complexity matrices Lk = likj n related to the k-th center of the polygon.
Step algorithm. We determine the shortest distances between the s-th and t-th centers (distinguished nodes) of the polygons of the reduced network in two variants, using matrices Ls = lisj n and Lt = litj n , respectively, s; t = 1; : : : ; N . If the shortest distance between centers is 0, then this means that at the corresponding point the polygons they manage are neighboring. This fact is xed, but the edge of zero length is excluded from further consideration in the algorithm. We also denote the shortest distances st > 0 and ts > 0 between the s-th and t-th, as well as the t-th and s-th centers of the reduced network. Note that, generally speaking, st 6= ts, by force Ls 6= Lt . Let us determine the minimum distance between all pairs of centers: i j = mini6=j ij . Let it be a couple with the indices j ; i . Let us compare the complexity of polygons corresponding to these reduced centers { wj and wi . Let wj > wi . Then in the reduction of the node i we add an edge incident to the node i along the considered shortest path, and also a node connected by this edge to the center i . After that, we recalculate the complexity of the corresponding polygons. Then again we compare the complexities of all the selected nodes after which we add the edge and node to the reduction of the center of the polygon whose complexity was less. In the case of equality of complexities, we arbitrarily choose one of the centers. We obtain the "distance" between the centers j ; i equal to zero. It is a result of the described reduction along the shortest path. We exclude this zero edge from consideration. The algorithm is at the end when after the next reduction there are no shortest distances of non-zero length. The nal reduction determines splitting into polygons.
Algorithm of the nearest boundary. Let us describe step algorithm. We de ne t such that wt = min1 j N wj . Consider the reduction of the selected center of the polygon. This reduction is a subnet that is reduced ("compressed") into the reduced center t. Using the representation Lt = litj n of the t-th polygon center, for a network subnet, we de ne the minimum "radius", which is de ned as the shortest path from the polygon center to the "periphery" i.e. subnet boundaries t. We determine the boundary of the network by the nodes with which the edges that are not part of the reduction in question are incident. We determine the node of the boundary corresponding the minimal distance, and then we add an edge incident to this node. We add this edge and the associated node to the reduction of the t-th center of the polygon. We carry out this addition only from the number of edges not included in the reduction of other nodes. If there are several such edges then the selection rule from these edges establishes a modi cation of the considered algorithm. This completes the algorithm step. We pass again to the beginning of the described step. In the event, we can not add an edge (since the neighboring edge is in the reduction of another center of the polygon), we believe that a point of contact between neighboring polygons has been found. This point is excluded from the boundary points to which the radius is calculated. The algorithm ends when all edges that are not included in any reductions are exhausted. 6
The development of a large-scale rail company is based on the improvement of the rail network and the transportation process. This leads to a change in the architecture of the company and, accordingly, the regional structure of its service. New regional support centers (RSCs) are emerging, and the boundaries of the responsibilities of the old RSCs are changing. In this regard, the article raises two questions: 1) how much RSC should become in the company if longterm plans for the development of rail networks and technological processes are implemented? 2) what should be the boundaries of each RSC? To answer these questions, we considered the prerequisites for forecasting and optimizing the SN support structure founded on the principles of adequacy, fragmentation and simpli cation of management. Based on the concept of complexity of the management of the rail network and the concept of the complexity of supporting the regional SN is de ned. It is shown that the complexity of regional SN support is determined by the complexity of managing the corresponding polygon.
The conducted researches give the following answer to the above-mentioned questions: the number and boundaries of RSC liability coincide, respectively, with the number and boundaries of the future rail network polygons, determined by the results of solving the problem of minimizing the maximum forecast complexity of managing these polygons.
Methods for optimizing the number of RSC and service boundaries have been
developed taking into account company plans for improving rail network and
technological processes of transportation. The obtained solutions of this problem
are constructive since algorithms for optimizing the number and boundaries of
polygons have been developed. These solutions have been used in the project of
the holding "Russian Railways" management structure optimization [
The results obtained are especially useful at the initial stage of planning the
development of a large rail company which precedes the development of new SN.
Even at such a pre-project stage when the details of the new SN are not known
it is possible to estimate the number of future RSC and the parameters of their
boundaries since there is already a reliable forecast and planned information on
the future state of the polygons. After making a decision on the formation of
new RSC, they may be entrusted with the development of regional projects for
the SN development (within their competence). The obtained results have been
used in such programs of development of the holding "Russian Railways" as
the modernization of BAM and the construction of the high-speed rail
MoscowKazan-Yekaterinburg [