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 HP-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 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.