Keywords

1 Introduction

Maintaining the high traffic intensity, ensuring the safety of the urban rail transport system, observing the rules of comfortable passenger service and properly use of resources are based on an integrated approach of the transportation planning process [1, 2]. The planned train schedule is the result of transportation planning process. The passenger metro trains are closely related to the maintenance schedule of electric rolling stock and the working schedule of locomotive crews [3]. Many articles have been discussed the problem of urban transportation planning system by various methods [4,5,6,7,8]. The paper [9] examines the information system for automating the process of urban passenger transport system. The work of [10] describes the optimization model for working schedule of crews according to the interaction and restrictions of the European agreement. In the work of Zherbina [11], this problem is described as a classical assignment problem. The research of Sidorenko [12] discusses the formalization of the maintenance schedule by using the graph theory and Bellman’s principle.

The use of graph theory and Bellman’s principle allows to get all possible sets of maintenance services and choose one which will correspond to the planned train schedule and minimal differ from the optimal according to the chosen criterion. But it takes a lot of time and the problem is when we need to choose the criterion of uniformity maintenance under limited resources. Therefore, the main purpose is to reduce the time of planning for the urban rail transportation system and to improve the automated planning system for the transportation process. In this case, the genetic algorithm is an effective tool for the optimization process [13,14,15].

The article examines the possibility of using genetic algorithms for all three tasks of planning the transportation process such as planned train schedule, maintenance schedule and working schedule for locomotive crews. The study intends to improve an automated system of train schedules with the uniformity criterion by using a variety of resources under limited restrictions. In this research, the mathematical models is based on the combinatorics, graph theory and genetic algorithms. The authors developed the adaption of the crossover and mutation of genetic algorithms according to the characteristics of the tasks. The research examined the possibility of genetic algorithm by using various types of crossover, mutations and the influence of genetic algorithm parameters on the results of transportation planning process.

The urban rail transport system includes metro, monorail systems, suburban railway and high-speed tram. Many papers have been discussed on the automation of planned train schedule for passenger metro which is important for the planning of urban rail transportation system and can be classified:

  • general issues for the automation of planned train schedule for metro:

    • development of mathematical models for planned train schedule,

    • observation of business processes for the planned train schedule,

    • adjustments of interval time,

    • visualization,

    • planning for train maintenance,

    • planning for locomotive crews,

    • planning energy-optimal schedule,

  • some other parts of planned train schedule:

    • traditional planned train schedule,

    • zone type schedule of metro and suburban railways,

    • circular line.

2 Approach

When we solve the optimization problems by using genetic algorithm, these following main steps must be carried out [16, 17]:

  • initialization of the initial data for the operation of the algorithm:

    • importing the chromosome or individual that determined by the tasks,

    • importing data to calculate the fitness function,

    • setting the parameters of the algorithm (crossover, population size, the maximum number of iterations without improving the values of the fitness function, determining the accuracy of the value of fitness function, the maximum running time of the algorithm, etc.),

  • creation of the first generation of the population,

  • calculating the value of fitness function for each chromosome,

  • the formation of a new generation, modeling of the evolutionary process:

    • individuals with the best fitness function values that are part of the current population,

    • individuals from the result of crossover of individuals selected as parents of the current population,

    • individuals from result of mutations of individuals selected as parents of the current population.

  • checking the termination condition for the algorithm. If the termination is not occurred, go to step (c).

3 Methods for Solution

It is necessary to adapt the concepts of genetic algorithm for the problems of planning the transportation process. The results of this adaptation are shown in Table 1. The genotype is specified by a set of individual chromosomes when solving the problem of planned train schedule. Each of chromosome consists of genes and each of gene has its own set of alleles. The number of locus in each chromosome is equal to the number of places where the choice for planned train schedule takes place. The number of element in the set of alleles for each of locus is determined by the number of variants of planned train schedule at this stage. The description of the genotype is given in Table 2, and Tables 3, 4 and 5 contain the information of various types of chromosomes.

Table 1. The adaption of genetic algorithm for the planning of transportation process.
Full size table
Table 2. Genotype.
Full size table

The possible options for fitness functions of the corresponding tasks are the followings. When creating a planned train schedule, the main criteria is the uniformity [19, 20]:

  • uniformity intervals by departure of trains from stations,

  • uniformity arrangement of train entry or withdraw.

The comparison of planned train schedule options is carried out according to the following:

  • number of route exchanges by the depot,

  • parameters of adjusting slopes on station tracks of the line (number (total), average,

  • maximum duration and other parameters of adjusting slopes,

  • completion times for each of the main tracks,

  • parameters of the zone type schedule or trains withdraw/entry at intermediate stations,

  • parameters of train maintenance times at terminal and intermediate stations.

Table 3. Chromosome structure for transitional processes of entry (withdraw) of metro trains before (after) the morning (evening) rush hour \( a_{{tr^{m + } }}\), \(a_{{tr^{m - } }}\), \(a_{{tr^{e + } }}\) and \(a_{{tr^{e - } }}\).
Full size table

The provision of small uniformity criteria values is achieved by the implemented algorithms. The end times of the first and second main tracks are used as a fitness function. It helps to compare the quality of options for the planned train schedule. We should pay attention to these indicators in order to be in time all the train movements along the metro line. This is necessary to provide the time as long as possible for night placement. The previous results have been shown that, despite the potentially large number of options for choosing the planned train schedule with the given initial data, the number of options for the successful schedule is still not enough. Therefore, another criterion for a successful planned train schedule is the number of night placement pointers where can be assigned the trains which failed to assign the night placement with the selected options. If the schedule is successful, there is no need such pointers. As a criterion for the rational planning of the maintenance services, the uniformity of the placement of services was introduced which is determined by one of those methods:

  • as the sum of the squared deviations of maintenance start times for the candidate from the desired service start times,

  • as the sum of the squares of the time intervals between services.

Table 4. Structure of chromosomes \(a_{m}\) and \(a_{e}\).
Full size table
Table 5. Structure of chromosomes \(a_{nepik}\)
Full size table

In the case of limited resources, the value of the total exceed time between services over the admissible time is used as a criterion of solution for any initial data. For the locomotive crew schedule, the criterion is determined by the balance between the skills and the number of the personnel who performing the regular requirements. In our case, the criterion is the standard deviation of the working time of various locomotive crews during a period of time.

4 Determining the Size of the Primary Population

The process of adjusting the parameters of the genetic algorithm includes the population size, which determines how many individuals are present in each generation. With a large population size, the genetic algorithm searches the solutions more carefully and reducing the probability that only a local rather than a global minimum will be found. At the same time, a large population size leads to the fact that the algorithm will run slower. The size of the population can range from one to maximum number of options for constructing a planned train schedule, which is equal to the product of the number of options for implementing all stages of the planned train schedule.

With a population size equal to the maximum number of options for the planned train schedule, genetic algorithm degenerates into an exhaustive search algorithm, and population size 1 is a degenerate case (random choice of any value and declaring it optimal in a voluntarist manner). If the size of the primary population is determined by the maximum value of two quantities:

  • the maximum value among the powers of the set of alleles of all genes of chromosomes described in Tables 2, 3, 4 and 5, except for genes associated with assigning a route to a string, delivering it to the night stay point or sending it for inspection. In this case, it guaranteed ensured the presence of all possible alleles for each of the genes,

  • the maximum number of permutations of alleles between locus when assigning routes to threads, delivering them to night placement or when sending them for inspection. In this case, the calculation is calculation in this case is as shown below by calculating the size of the population when solving the problem of maintenance schedule.

Let the population size be N. Our objective is to find the number of individuals at which the chromosomes of an individual to get all the values of elements for the complete set by recombination. For this, the population size must be for each locus in the entire population of all possible allele. Let’s calculate the probability that a random set of chromosomes will contain all possible allele values at the selected locus. The probability that any one of the locus will contain the same value in all chromosomes is equal to \( \frac{1}{{\left( {N_{a} } \right)^{N} }} \). In a population, a complete set of alleles at one of the locus may be present in the case of \( N \ge N_{a}\). In this case, in \( N_{a}\) chromosomes the values differ, and in the remaining ones they take arbitrary values. The number of realizations of filling the locus of the same name in the population, in which the chromosome will contain all possible values of the alleles, in the selected locus, is determined by the following expression:

$$ \overline{C}_{{N_{a} }}^{{N - N_{a} }} = C_{{N_{a} + N - N_{a} - 1}}^{{N - N_{a} }} = C_{N - 1}^{{N - N_{a} }} = \frac{{\left( {N - 1} \right)!}}{{\left( {N - N_{a} } \right)!\left( {N - 1 - N + N_{a} } \right)!}} = \frac{{\left( {N - 1} \right)!}}{{\left( {N - N_{a} } \right)!\left( {N_{a} - 1} \right)!}} $$
(1)

where:

\( \overline{C}_{{N_{a} }}^{{N - N_{a} }} = C_{{N_{a} + N - N_{a} - 1}}^{{N - N_{a} }}\) – the number of combinations with repetitions of alleles Na in the same locus of all remaining after filling with different alleles \(N - N_{a} \) chromosome,

\( N_{a}\) – the number of elements in a set of allele.

In total, there are \(\overline{C}_{{N_{a} }}^{N} = C_{{N_{a} + N - 1}}^{N} = \frac{{\left( {N_{a} + N - 1} \right)!}}{{\left( N \right)!\left( {N_{a} - 1} \right)!}}\) options for filling the same locus in the population. Then the probability that a random set of chromosomes will contain all possible allele values at the selected locus is:

$$ \begin{array}{*{20}l} {p_{1} = \frac{{{\text{Number}}\;{\text{of}}\;{\text{favorable}}\;{\text{events}}}}{{{\text{Number}}\;{\text{of}}\;{\text{all}}\;{\text{events}}}} = \frac{{\frac{{\left( {N - 1} \right)! }}{{\left( {N - N_{a} } \right)!\left( {N_{a} - 1} \right)! }}}}{{\frac{{\left( {N_{a} + N - 1} \right)!}}{{\left( N \right)!\left( {N_{a} - 1} \right)!}}}} } \hfill \\ { = \frac{{\left( {N - 1} \right)!\left( N \right)!\left( {N_{a} - 1} \right)! }}{{\left( {N - N_{a} } \right)!\left( {N_{a} - 1} \right)! \left( {N_{a} + N - 1} \right)!}} = \frac{{\left( {N - 1} \right)!\left( N \right)!}}{{\left( {N - N_{a} } \right)!\left( {N_{a} + N - 1} \right)!}} } \hfill \\ { = \frac{{\left( {N_{a} + N - 1 - N_{a} } \right)! \left( N \right)!}}{{\left( {N - N_{a} } \right)! \left( {N_{a} + N - 1} \right)!}} = \frac{{A_{N}^{{N_{a} }} }}{{A_{{N_{a} + N - 1}}^{{N_{a} }} }} = \frac{{N \cdot \left( {N - 1} \right) \ldots \left( {N - N_{a} + 1} \right)}}{{ \left( {N_{a} + N - 1} \right) \cdot \left( {N_{a} + N - 2} \right) \cdot \ldots \cdot N}}} \hfill \\ { = \frac{{\left( {N - 1} \right) \ldots \left( {N - N_{a} + 1} \right)}}{{ \left( {N_{a} + N - 1} \right) \cdot \left( {N_{a} + N - 2} \right) \ldots \left( {N + 1} \right)}}} \hfill \\ \end{array} $$
(2)

where:

\({\text{A}}_{N}^{{N_{a} }} {,}A^{{N_{a} }}_{{N_{a} { + }N{ - 1}}}\) – number of placements.

Accordingly, the probability that all \(N_{c}\) locus will contain the full set of alleles each is equal to:

$$ p_{{N_{a} }} = \left( {p_{1} } \right)^{{N_{c} }} = \left( {\frac{{A_{N}^{{N_{a} }} }}{{A_{{N_{a} + N - 1}}^{{N_{a} }} }}} \right)^{{N_{c} }} $$
(3)

The probability of the locus which will not contain the full set of alleles is:

$$ 1 - p_{{N_{a} }} = 1 - \left( {\frac{{A_{N}^{{N_{a} }} }}{{A_{{N_{a} + N - 1}}^{{N_{a} }} }}} \right)^{{N_{c} }} $$
(4)

Figure 1a, 1b, and 1c shows the results of the calculation of the following probabilities for one of the lines of the Moscow metro according to formulas (2)–(4):

  • the probability that a random set of chromosomes will contain all possible allele values at the selected locus,

  • the probability that all \(N_{c}\) locus will contain the full set of alleles,

  • the probability of the locus which will not contain the full set of alleles.

In this case, \(N_{a} = 38\) and \(N_{c} = 13\).

Fig. 1.
figure 1

a. The probability that a random set of chromosomes will contain all possible allele values at the selected locus, b. The probability that all \(N_{c}\) locus will contain the full set of alleles, c. The probability of the locus which will not contain the full set of alleles

Full size image

5 Crossover

Crossover is the main genetic operator which exchange the genetic material between individuals as shown in Table 1. Crossover methods take into account the peculiarities of the alleles which are used in organizing the work of the genetic algorithm when solving a specific problem of planning the transportation process. This crossover differs from previous. Crossover and mutation actions can be performed by different algorithms such as single-point crossover, two-point crossover, arithmetic crossover, heuristic crossover, scattered crossover, intermediate crossover, cyclical crossover, coercive with subgroup inheritance, coercive with the inheritance of genes selected position and coercive with inheritance of selected genes to the same positions.

6 Mutation

Mutations occur in the process of evolution in accordance with the probability of user-defined mutations. This probability should be low. If it is too high, then the search will turn into a primitive random search. The purpose of mutation in genetic algorithm is to represent diversity. Mutation prevents the termination of evolution process after finding the local minima, or a situation in which the chromosome are very similar to each other, thereby slowing down or even stopped evolution. According to the limited size of the population is less than the upper boundary, the probability of any iterations will be obtained a set of chromosomes from which any possible chromosome cannot be obtained by recombination. This is why we used mutation in genetic algorithm [13, 21]. We can find the probability of mutation for one chromosome to restore the lost variants Pmc. A chromosome mutation occurs if one of the genes has been mutated:

$$ P_{mc} = N_{c} P_{m1} $$
(5)

where:

\( P_{m1}\) – probability of mutation for one gene,

\(N_{c}\) – the length of chromosome.

In this case, the probability of mutation for specified gene in a chromosome is equal to Pm1 = Pmc/Nc. The probability of this chromosome gene that does not mutate is equal to 1 − Pm1 = 1 − Pmc/Nc. The probability of this gene that does not mutate in any chromosome is equal to (1 − Pm1)N = (1 − Pmc/Nc)N. Accordingly, the probability of a given locus that mutates in at least one of the chromosomes is equal to 1 − (1 − Pm1)N = 1−(1 − Pmc/Nc)N. For reliability, we need to exceed the probability of a given locus mutation in chromosomes (at least one of the chromosomes) is larger than the probability of the value absence in this locus of all chromosomes. If the number of mutation is bigger than the entire set of alleles, it already does not mean mutation. Therefore:

$$ \begin{gathered} 1 - \left( {1 - p_{m1} } \right)^{N} > 10\left( {1 - p_{{N_{a} }} } \right) \hfill \\ \frac{{1 - \left( {1 - p_{m1} } \right)^{N} }}{10} > \left( {1 - p_{{N_{a} }} } \right) \hfill \\ \frac{{1 - \left( {1 - p_{m1} } \right)^{N} }}{10} - 1 > \left( { - p_{{N_{a} }} } \right) \hfill \\ - \frac{{1 - \left( {1 - p_{m1} } \right)^{N} }}{10} + 1 < \left( {p_{{N_{a} }} } \right) \hfill \\ p_{{N_{a} }} > 1 - \frac{{1 - \left( {1 - \frac{{p_{mc} }}{{N_{c} }}} \right)^{N} }}{10} \hfill \\ \end{gathered} $$
(6)

If the population is large, then the mutation is meaningless:

$$ 1 - \left( {1 - \frac{{p_{mc} }}{{N_{c} }}} \right)^{N} > 10 \left( {1 - \left( {\frac{{A_{N}^{{N_{a} }} }}{{A_{{N_{a} + N - 1}}^{{N_{a} }} }}} \right)^{{N_{c} }} } \right) $$
(7)

Hence:

$$ \begin{gathered} p_{mc} > N_{c} \left( {1 - \left( {1 - 10\left( {1 - \left( {\frac{{A_{N}^{{N_{a} }} }}{{A_{{N_{a} + N - 1}}^{{N_{a} }} }}} \right)^{{N_{c} }} } \right)} \right)^{1/N} } \right) \hfill \\ , p_{mc} > N_{c} \left( {1 - \left( {1 - 10\left( {1 - p_{{N_{a} }} } \right)} \right)^{1/N} } \right) \hfill \\ \end{gathered} $$
(8)

7 Results

In this research, the authors developed a decision support system for the planning of the transportation process by using the genetic algorithm. Figures 2, 3, 4 and 5 show the results of train maintenance services planning for one of the Moscow metro lines by using the decision support system.

Fig. 2.
figure 2

The result of maintenance schedule while the resources are enough for the necessary condition of maintenance scheduling

Full size image

Figure 2 shows the results of maintenance schedule in which the resources are enough for the maintenances of electric trains and fitness function of genetic algorithm reflects the uniformity of maintenances services. This figure allows to compare with the corresponding maintenance schedule which is using in Moscow metro. The blue rectangles are the real maintenances and the green rectangles are the proposed maintenances. Analysis of the result data shows the following:

  • maintenances of the metro trains are carried out more often than the safety requirements. There are 18–23 maintenances on the schedule, but according to the safety requirements, there should be 13. This is showing that there are sufficient resources to carry out inspections and the number of trains on the line in non-rush hour is one third less than the maximum,

  • according to the planned train schedule for metro, many routes are neither start running from the beginning moment of applying voltage to the contact rail nor until to the end of the day. Only one third of the routes start before 6 am or end later than 1 am.

In this regard, it makes sense to consider the situations of limited resources for maintenance schedule. Figure 3 shows the corresponding maintenance schedule in which the set of candidates that can be used for inspections has been decreased to a half.

Fig. 3.
figure 3

The result of maintenance schedule while the resources are enough for the necessary condition of maintenance scheduling

Full size image

In this case, the planned train schedule must reduce the running time interval between two inspections by early departure or late exit from the night stay point. The quadratic criterion was used for the solution and the “imaginary” inspection was on a chain of 10–14 routes. If sufficient resources are available, this chain should accommodate three inspections, not two.

The decision support system takes into account various features of the metro lines, for example, the presence of two depots and one linear inspection point on the line, which can carry out the train maintenance of both depots. The restrictions of maintenance schedule affect the formation of primary population. In this case, at first, for each of the depots, all the possibilities of inspections or the technical maintenance for the routes of this depot are distributed between the inspections of the same depot. After that, the remained inspections are determined. For their implementation, candidates related to the technical inspection places are appointed, who can serve all the depots of the line. The maintenance schedules for such conditions are presented in Figs. 4 and 5.

Fig. 4.
figure 4

Maintenance schedule for the first depot of the metro line which has two depots

Full size image

Initially, we get the size of the population. Then we create a matrix based on the population to work in the program. Further, according to our code snippet, we understand which train is going to which depot, therefore:

  • if we get 1, then the train goes to the Svivlovo depot,

  • if we get 2, then the train goes to the Kaluzhskoye depot,

  • if we get 3, then the train goes to the Medvegkovo depot.

Based on these calculations, we can obtain maintenance schedule information for the conditions of limited resources. This information contains the initial data of the operation for calculating the maintenance schedule of electric rolling stock.

Fig. 5.
figure 5

Maintenance schedule for the Kaluzhskaya depot on the Kaluzhsko-Rizhskaya line of the Moscow metro

Full size image

8 Conclusions

The article describes the adaptation of genetic algorithm for solving the problems of planning the transportation process such as the planned train schedule, the maintenance schedule of rolling stock and the working schedule for locomotive crews. The developed decision support system illustrates its capabilities for performing in adaptation by using various crossover types, mutations and different input parameters (such as population size, number of iteration, accuracy, etc.). It made possible to solve the problems of planning the movement of trains in the presence of limited resources by assuming the total excess time over the limited interval time as an additional criterion and the implementation of optimal maintenance schedules for the planning of urban rail transport system. The decision support system has been developed an interface for the data exchange of automated planned schedules of passenger trains for the Moscow metro [22], which is an example of the implementation of the centralized intelligent control system of the urban rail transport system.