=Paper=
{{Paper
|id=Vol-2098/paper34
|storemode=property
|title=Service Support Structure Optimization of a
Large-Scale Rail Company
|pdfUrl=https://ceur-ws.org/Vol-2098/paper34.pdf
|volume=Vol-2098
|authors=Anver Enaleev,Vladimir Tsyganov
}}
==Service Support Structure Optimization of a
Large-Scale Rail Company==
https://ceur-ws.org/Vol-2098/paper34.pdf
Service Support Structure Optimization of a
Large-Scale Rail Company
Anver Enaleev and Vladimir Tsyganov
V.A. Trapeznikov Institute of Control Sciences of Russian Academy Sciences,
65 Profsoyuznaya street, 117997, Moscow, Russia
anver.en@gmail.com, bbc@ipu.ru
Abstract. 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 specifics of the Russian railways. We base this decomposition
on the definition 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 specifics 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 finding the number of regional sup-
port 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 mod-
ernization of Baikal-Amur main line and the construction of high-speed
rail Moscow-Kazan.
Keywords: Graph partitioning · Optimization · NP-hardness · Local
search · Heuristic · Transport network
1 Introduction
A large-scale rail company carries out transportation processes on an extensive
rail network located on a vast territory (for example, in different 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
Service Structure Optimization 397
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 im-
plements 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 traffic [8]. In the process of
implementing such a program, it is necessary to support changes in the entire
service network of the company (briefly - CoSN).
In this regard, there are problems both in the development of CoSN and in
supporting its efficiency 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 [4], problems
of optimizing support structure of the CoSN are considered on the principles of
adequacy, fragmentation and simplification of management.
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 [8]. In this regard, there are problems with the development
of CoSN, as well as supporting its effectiveness in the development process. For
this, optimal planning of the CoSN support structure is necessary. In this paper
the problems of optimizing the structure of CoSN support are considered using
the principles of adequacy, fragmentation and simplification of management.
2 Service Support Structure Principles
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 (briefly
- 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 effective functioning of CoSN should be provided by an or-
ganizational 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 prin-
ciple 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
398 A. Enaleev, V. Tsyganov
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 simplification. 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 acci-
dent. 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 [8] the concept of complexity of network management and method-
ological approaches to an estimation of such complexity was offered. In accor-
dance with this concept, the complexity of a rail network managing is defined as
the complexity of managing its parts - polygons, and the complexity of managing
the central body, coordinating the work of all polygons. Since SN is a subsys-
tem of network management, similar approaches can also be used to assess the
complexity of SN.
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 [4]. The more complex the
regional SN, the less reliable it is, the more time it takes to repair it, the more
expensive its support. Therefore the more complex the regional SN, the more
difficult its support.
Thus, the complexity of support of regional SN is determined by the com-
plexity of this SN and, consequently, by the complexity of managing the corre-
sponding polygon. Based on this, we will further use the hypothesis of a directly
proportional dependence of the complexity of regional SN support and the com-
plexity of managing the corresponding polygon.
The complexity of CoSN depends on the complexities of its constituent frag-
ments - 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 com-
Service Structure Optimization 399
pany. 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 manag-
ing the relevant polygon. There are 2 prerequisites for ensuring such adequacy.
First, there is a methodology for assessing the complexity of managing the rail-
way network and its polygons [8]. Secondly, the above-mentioned plan includes
a forecast of the state of regional rail networks. Thus, the forecast of the com-
plexity of supporting the created or modernized regional SN can be constructed
on the basis of an assessment of the complexity of managing the appropriate
future rail network and the technological processes of transportation, obtained
with the help of this plan. For example, the forecast of the complexity of the
Far Eastern SN of the holding ”Russian Railways” until 2020 is based on plan
to equip the branch of the holding company ”Far Eastern Railway” with auto-
matic locking systems and dispatching centralization within the framework of
the BAM development program [8].
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 affects 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 maxi-
mum 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 num-
ber and their boundaries using the methodology of synthesis of optimal struc-
tures [7], [9] and organizational control [3]. Note that in practice it is known the
railway network partitioning into traffic management polygons and polygons of
SN (for example, SN of locomotive services) [8]. The functioning of the traffic
management polygons is supported by the respective centers, and the SN poly-
gons have their own RSCs. If the boundaries of these polygons do not match
the traffic control centers and the RSC bear additional coordination costs. The
conditions for minimizing these costs and for matching polygon boundaries were
obtained in [5]. In what follows, we shall assume that these conditions are satis-
400 A. Enaleev, V. Tsyganov
fied. Therefore, we will focus on the problem of partitioning the railway network
into traffic management polygons.
3 Statement of the Problem
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
SN network S. Suppose that a partition into polygons satisfies the conditions:
N
g
i=1 i = 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 partition-
ing a graph. Classification of these methods and a detailed review is presented
in [2]. The review [2] contains more than one hundred references. We propose
here methods based on solving applied problems and taking into account the
specifics of Russian railways. To calculate the efficiency of the network manage-
ment structure we will need indicators of ”management complexity” that will be
assigned to the graph edges. For the uniformity of the description, the manage-
ment complexity for the node of a graph is determined by the loop complexity
assigned to this node. Suppose that for each partition g N there is given a gener-
alized indicator characterizing the management complexity (hereinafter simply
N N N
gN
”complexity”) by the whole network: K(g N ) = K̄(K0g , K1g , ..., Kig , ..., KN ),
N N
where K0g = K0g (N ) is an indicator characterizing the complexity for the
N N gN
central body coordinating the activity of all polygons, Kig = Kig (l¯i i ) is an
indicator characterizing the complexity for the i-th management body of the
gN
polygon in the partition g N , i = 1, ..., N . Here l¯i i is a set of complexity pa-
rameters for elements of the i-th polygon (included in the polygon of vertices and
edges of the network) in the given partition g N (the meaning of these parame-
ters will be clarified below). We assume that the function K̄(·) is non-decreasing,
N
i.e. the value of K̄(g N ) does not decrease in magnitude Kig , i = 1, ..., N . We
gN
also assume that the functions K0g = K0g (N ) and Kig = Kig (l¯i i ) do not de-
crease in their arguments. Suppose that a set GN of admissible partitions is
given. It can be defined as constraints on the maximum local complexity values:
N N
0 ≤ K0g (N ) ≤ K0max , 0 ≤ Kig ≤ Kimax , i = 1, ..., N as well as by restrictions
on the generalized index of complexity:
N N N N
K N (g N ) = K̄ N (K0g , K1g , ..., Kig , ..., KN
g
) ≤ K̄ max .
The set GN may not contain certain ”forbidden” partitions, determined by the
specifics of the particular model. In general, the problem of optimizing the com-
plexity of control is posed as minimizing K N (g N ) by choosing the number of
Service Structure Optimization 401
polygons N in the partition and the partition g N itself on the set GN :
max max K N (g N ),
Nmin ≤N ≤Nmax g N ∈GN
where Nmin and Nmax define low and upper restrictions on the polygons number.
In general, such a problem is difficult 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 difference in com-
plexity of polygon control should be minimal:
N∗ N N
g g
∆g = min [ max KiG (¯li i ) − min KiG (¯li i )],
g∈GN 1≤i≤N 1≤i≤N
where g N ∗ is a equisyllabic partition.
This principle reflects 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 forma-
tion.
The complexity of polygon management. As noted above, the complex-
N N gN
ity of polygon management Kig = Kig (¯li i ) is formed as a given function of a
gN gN
complexity parameters of polygon elements ¯li i . A set of parameters ¯li i is a set
of indicators for the difficulty of managing the network edges (edges representing
loops at the nodes of the network characterize the complexity of the correspond-
ing 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 ma-
N
kN kN
trices Lk = klij kn , where lij are the complexity indices of the edge (i, j) from
N N
the point of view of the k N -th polygon in the partition g N . Note that lij
k k
= lji .
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
N
kN
consideration. We define as wik = lii the i-th node complexity (i = 1, ..., n).
Let us briefly describe one of the options for calculating the complexity of poly-
gon. Let’s imagine the index of complexity of the polygon control as a sum:
N N N
KkgN (·) = KkgN # (·) + bKkgN ## (·), where b is the weight coefficient, 0 ≤ b < 1.
N
Suppose that the first term in KkgN (·) 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 ad-
N N P
kN kN 1kN 2kN 3kN
ditive index, KkgN # (·) = αk
P
i,j∈p N lij = α
k i,j∈p N vij vij vij
k
. . ..
402 A. Enaleev, V. Tsyganov
N
Here αk are the coefficient allowing to bring the value of the indicator of com-
plexity to some meaningful representation, for example, to estimating the time
kN 1kN 2kN 3kN
spent on management, lij = vij vij vij . . . – the complexity index of the
N N N N
k 1k 2k 3k
j-th edge of the polygon, lii = vii vii vii . . . – the complexity of the i-th
node, pkN – is the set of edges and nodes included in k N -th polygon. Values
1kN 1kN N
1kN N N
vij are calculated as follows: vij = 1 + a1k (zij /ze1k − 1), where a1k –
N
1k
the weight coefficient, zij – the intensity of traffic flows on the j-th edge of the
N N N
network, ze1k – the average (normative) intensity. Values vij
2k 3k
, vij . . . are cal-
culated 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
N N
volume of loading. The second term KkgN ## (·) in KkgN (·) depends on the set of
indicators of the edges of the k N subnet, but only those edges that are incident
to the vertices located at the boundary of the k N -th polygon.
4 Polygons Optimal Number Estimation
The above problem of complexity optimization is decomposed into two sub-
problems. Let’s consider the first subproblem – the estimation of the polygons
number provided the network is divided into equivalent polygons. Suppose that
N∗
we can realize the ”ideal case” when ∆g = 0, i.e. in the partition g N ∗ all the
polygons have the same complexity. In this case, we can write down that the com-
N∗ gN ∗
plexity of the control of each polygon is equal to Rg = min1≤i≤N Kig (¯li i ) =
N∗
g
max1≤i≤N K g (¯l i ), where g N ∗ is the ideal equisyllabic partition. Then the com-
i i
N∗ N∗ N∗ N∗
plexity index K N (g N ∗ ) = K̄ N (K0g , K1g , . . . , Kig g
, . . . KN ) can be repre-
N∗ N∗ N∗ N∗
sented in the form K N (g N ∗ ) = K̄ N (K0g , Rg , . . . , Rg , . . . Rg ).
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 ) = a1 N +a2 N 2 . Here the first term reflects the complexity of management
of each of the equisyllabic polygons, and the second term is the complexity of
coordination of pairwise interaction between polygons. Coefficients a1 and a2
characterize, for example, the time spent for management each polygon and
N∗
coordinating their interactions. Secondly, let the value Rg 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
N∗
polygons Rg = B/N m . In articles [1], [6], when estimating the cost functions,
m = 2 is adopted. Now the complexity indicator can be represented in the form
K N (g N ∗ ) = K̄ N (a1 N + a2 N 2 , B/N m , . . . , B/N m , . . . , B/N m ). Then from the
condition minNmin ≤N ≤Nmax K̄ N (a1 N + a2 N 2 , B/N m , . . . , B/N m , . . . , B/N m ) it
is possible to determine the estimate of the polygons optimal number N ∗, where
Nmin and Nmax are the given boundaries of the number of polygons.
Service Structure Optimization 403
5 Polygon Boundaries Calculation
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 num-
ber is determined by the number of polygons N ).
Reduction determines the typical step used in the following algorithms for se-
quential 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 first N numbers receive the selected nodes (polygon
k0 0
centers), i = 1, . . . , N, . . . , n. We denote Lk0 = lij n
the initial matrices of the
arcs and nodes of the network under consideration. Here, the superscript 0 de-
notes 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
k0 k0
network with an edge (i, j) of zero complexity, i.e. lij = lji = 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
k0 0 k1 1
transforms the matrix Lk0 = lij n
into matrices Lk1 = lij n−1
of dimen-
sion n − 1 in the first 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 first 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:
N N gN 1 gN 1
wi1 = lii
k1
= Kig 1 = Kig 1 (¯li i ), where the set ¯li i includes the node with
i0 k1
the number j, the edge lij and ljt for the attached edges (j, t), where t is the
k0
number of the unseparated node such that ljt > 0. Similar to the first step, the
following reduction steps are carried out. The complexity recalculation formulas
N N g N τ +1
at the τ -th step have the form wiτ +1 = lii kτ +1
= Kig τ +1 = Kig (¯li i ) where
N
g τ +1
the set ¯li
i
includes the joining node with the number j, the edge liτ and ij
kτ +1
ljt = 0 are established for the attached edges (j, t), where t is the number of
kτ
the unseparated node such that ljt > 0, τ = 1, . . . , n − N . After carrying out
the described reduction steps, N diagonal matrices corresponding to the num-
ber 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.
404 A. Enaleev, V. Tsyganov
Algorithms of Defining 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 charac-
terizing the heuristic sequentially compresses the network. The algorithms are
based on a directional search of options and sequential expansion of subnets (re-
duction of the source network), until a complete network partition is obtained.
We carried out the reduction process in a directed way to improve the indica-
tor 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 define specifics 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
kτ τ
polygon, we use the representation of complexity matrices Lkτ = lij n−τ
re-
lated 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
sτ τ tτ τ
variants, using matrices Lsτ = lij n−τ
and Ltτ = lij 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 fixed, 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 complex-
ity 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 final reduction
determines splitting into polygons.
Algorithm of the nearest boundary. Let us describe step algorithm. We
define 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”)
tτ τ
into the reduced center t. Using the representation Ltτ = lij n−τ
of the t-th
polygon center, for a network subnet, we define the minimum ”radius”, which
Service Structure Optimization 405
is defined 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 modification 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 Discussion
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 long-
term 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 simplification 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 defined. 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 com-
plexity 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 [8].
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.
406 A. Enaleev, V. Tsyganov
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 Moscow-
Kazan-Yekaterinburg [8]. A similar approach is can be used in other optimization
methods applications in economics, management, design, and education, deals
with the optimal graph partitioning.
References
1. Baumol, W.J., Panzar, J.C., Willig, R.: Contestable Markets and the Theory of
Industry Structure. CA: Harcourt Bracejovanovich, San Diego (1982)
2. Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in
graph partitioning. Preprint; arXiv:1311.3144 (2013)
3. Burkov, V.N., Gubko, M.V., Korgin, N.A., Novikov, D.A.: Mechanism Design and
Management. Mathematical Methods for Smart Organizations / Business Issues,
Competition and Enterpreneurship. NOVA Publishers, New York (2013)
4. Coulouris, G., et al: Distributed Systems: Concepts and Design (5th Edition).
Addison-Wesley, London (2011)
5. Enaleev, A.K.: Promoting the coincidence of different partitioning types at large-
scale network. In: Proceedings of the 10th International Conference on Manage-
ment of Large-Scale System Development (MLSD 2017), IEEE Conference Publica-
tions: http://ieeexplore.ieee.org/document/8109616/, [On-line; accessed 29-March-
2018]
6. Fare, R., Martins-Filho, C., Vardanyan, M.: On functional form representation of
multi-output production technologies. Journal of Productivity Analysis 33, 81–96
(2010)
7. Novikov, D.A.: Theory of Control of Organizational Systems. Fizmatlit, Moscow
(2007), (in Russian)
8. Tsyganov, V.V., Malygin, I.G., Enaleev, A.K., Savushkin, S.A.: Large-scale Trans-
port Systems, Theory, Methodology, Development and Expertise. IPTRAS, Saint
Petersburg (2016), (in Russian)
9. Voronin, A.A., Goubko, M.V., Mishin, S.P., Novikov, D.A.: Mathematical Models
of Organizations. Lenand, Moscow (2008), (in Russian)