Study on the Algorithm for Train Operation Adjustment Based on Ordinal Optimization

Abstract

It is a crucial and difficult problem in railway transportation dispatch mechanism to automatically compile train operation adjustment (TOA) plan with computer to ensure safe, fast, and punctual running of trains. Based on the proposed model of TOA under the conditions of railway network (RN), we take minimum travel time of train as objective function of optimization, and after fast preliminary evaluation calculation on it, we introduce the theory and method of ordinal optimization (OO) to solve it. This paper discusses in detail the implementation steps of OO algorithm. A practical calculation example of Datong-Qinhuangdao (hereinafter referred to as Da-Qin) heavy haul railway is performed with the proposed algorithm to prove that OO can ensure getting good enough solution with high probability. Particularly, for complex optimization problems with large amount of calculation, OO can greatly increase computational efficiency, and it can save at least one order of magnitude of calculation amount than general heuristic algorithm. Thus, the proposed algorithm can well satisfy the requirements in engineering.

1. Introduction

It is true with practice that a high qualified and efficient TOA system is strongly required with the speeding up of both trains and expansion of train operation density. In China, automation in the railway dispatching and operation system has been gradually adapted into practice at present, which brings up a demand of great significance to research an efficient TOA method adapting to the special characters of the railway and satisfying the requirements of onsite operation. This is no longer a theoretical research but an issue that should to be put into the onsite practice in train dispatching and operation.

TOA mechanism is a high dimensional study of target optimization with nonlinear mixed integer. Many scholars all over the world have investigated algorithms of TOA and have got flourish achievements. The methods these scholars adopted are mainly focused on linear and nonlinear programming, mixed integer programming, branch-bound method, genetic algorithm, Lagrangian relaxation approach, and so forth. For example, in [1], the mechanism of TOA is researched under given train running time and the highest speed; in [2], genetic algorithm is used to establish a satisfaction optimization model of TOA; in [3], the dispatching mechanism is taken as a mixed integer programming problem which could be resolved by branch-bound method. The authors of [4] enumerate all feasible solutions to deal with trains and choose one that minimizes total delaying time of the trains, while the authors of [5] present the earliest conflict optimizing method which overcomes the huge amount of plans in resolving conflicts by combination and is highly efficient in operation, the authors of [6] take minimum total cost on train delay as an objective function and put forward heuristic search function as an accelerated algorithm that in a large degree reduces the number of node graph and in return speeds up the algorithm-solving process, the authors of [7] propose a new method, generating research for the optimization plan automatically through dividing the original problem into many sub-problems and then trying by delamination method to get solutions to those subproblems. Contributing to hierarchical decision-making method and rolling optimization, the authors of [8] present a general algorithm about both train operation plan and adjustment model.

All of the optimization and algorithms methods (OAM) mentioned above are devoted to getting the best solution to the programming plan; however, the calculating amount grows exponentially with the scale of planning problem growing. A crucial problem is that various mathematic optimization methods are stuck with bottleneck in solving TOA plans in the grand-scale RN, due to unbearably large amount of calculation.

In recent years, simulation optimization and OO methods have become an effective tool in research of discrete event with dynamic systems. As the TOA involves many sectors and factors, it is difficult to propose systematic optimization mathematical models to solve them in practice. It is well known that the problem of train scheduling is a constrained optimization problem and is taken as a nondeterministic polynomial problem (NPP) in mathematics and computer filed. Despite the existence of many intelligent algorithms for solving NPP, such as genetic algorithms, simulated annealing, and ant colony algorithm, they are probabilistic search algorithms and cannot meet real-time requirements as they are time consuming. As a result, the application of OO in solving the problem of TOA emerges as a new way of thinking.

2. Ordinal Optimization (OO)

OO was proposed in 1992 by the Harvard professor Ho et al. [9]. The OO algorithm has been developed into an irreplaceable area of research with hundreds of research papers and is widely used as an important method in resolving simulation optimization problems, especially in those with extraordinarily large space. Below are two main basic ideas of OO.

First, it is easier to compare with “order” than with “value” (“order” versus “value”). This idea could be understood through experiences. Suppose that there are two balls, one in each of your hands. It is easy to tell which ball is heavier just by feeling although we cannot accurately feel the exact weight of each ball. This idea could also be applied in optimizations that are based on simulation. The original system provides a rough model (RM) which shows that, between the two kinds of solutions, we can exactly tell which one is better, although we do not know the exact differences in their performance. If the question is to tell which one is better but not to tell how much it is better than the others, an RM is efficient enough merely by sorting the solution space with an order. For example, in the TOA model (M1), the simulation, with short time or with an average value based on a small number of (or even only one) sample tracks, could be sorted into RMs. It is possible for RMs to save the amount of calculation since it has a great advantage, compared with the accurate model, in spending of time (or economic cost) for calculation. This is the main content of ordinal comparison and also the first basic idea of OO.

Second, we have the idea of goal softening (GS). When the optional solution space is extremely large and it is very difficult or even not feasible to accurately get the best solution, from the perspective of engineering, it is preferable to get a “good enough solution (GES)” as the final result, that is, a “good enough solution” is so acceptable that we do not have to obtain the best one. This idea is especially viable with large-scale optimization problems. What is more, is that we are free to define what a GES in projects is, and a GES can often meet the engineering needs. This is the main content of GS and also the second basic idea of OO.

We can take these two basic ideas in the TOA as follows. When the train delays and the operation of other trains is affected, when there is a plan to increase or decrease one or more operation plans of the trains, or when it is required to adjust the train operation or eliminate conflicts under the condition that malfunction occurred or normal maintenance is ongoing, the train dispatchers do not have to make an adjustment plan after accurately calculating the distance between train and train/section/station, but to change, with sharp and immediate responding, the running order of the trains (ordinal comparison) and adjust the time trains arrive at or depart from the station, trying to find the best arrangement or adjustment under certain constraints. The idea to solve these problems by experiences (GES) is nearly the same with OO. The TOA is a kind of complex optimization problems, its solution space is also very complex because the solution space grows exponentially with the scale of the problems that need to be solved while growing. Calculation for objective function is very complicated and time consuming since the amount of computation is extraordinarily huge, so it could not meet the real-time requirements of TOA. Therefore, OO emerges as a preferable option to obtain “GES” and solve the problems instantly.

Based on these two important features, OO significantly reduces the amount of computation in obtaining solutions that are widely used in engineering and have achieved very pleasant results. This paper discusses how the OO method is applied in the field of TOA and explains in detail the algorithm progress of TOA under complex train network, as well as its implementation steps. At last, with an example of algorithm, this paper proves that the OO method could save more magnitudinous calculation than heuristic algorithm.

3. Model of TOA

TOA of ordinary railway and high-speed railway aims at maximizing trains' arrive-on-time proportion and minimizing actual deviation from train operation plan. Datong-Qinhuangdao Railway (DQR), one of the coal transportation channels in China, whose yearly transportation capacity is large in the world, focused on heavy-haul freight train. Its arrive-on-time proportion was only for reference. The ultimate goal of the adjustment is to raise the average speed of freight trains. For this reason, the least train traveling time is the optimal target of the proposed model. In order to better describe train event and topological structure of station and then to present TOA model (M1).

Consider objective function as

$\begin{array}{c}\min f_{\mathrm{1}}=\sum _{i=\mathrm{1}}^n\hspace{0.17em}\sum _{j=\mathrm{1}}^m\left(q_{ij}\right)+\sum _{i^{\prime }=\mathrm{1}}^{n^S}\hspace{0.17em}\sum _{j^{\prime }=\mathrm{1}}^{m^S}\left(q_{i^{\prime }{j}^{\prime }}\right),\end{array}$

(M1)

that is subject to the following.

Traveling time constraints of train event at station as

$q_{ij}=\left(y_{ij}-x_{ij}+M\right)\mathrm{mod}M,\phantom{hh}i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right];$

(1)

traveling time constraints of train event at segment as

$\begin{array}{c}{q}_{i^{\prime }{j}^{\prime }}=\left(y_{i^{\prime }{j}^{\prime }}-x_{i^{\prime }{j}^{\prime }}+M\right)\mathrm{mod}M,\\ i^{\prime }∊\left[\mathrm{1}·n^s\right],\hspace{1em}{j}^{\prime }∊\left[\mathrm{1}·m^s\right];\end{array}$

(2)

headway constrains between departure times of two same direction consecutive trains as

$\begin{array}{c}\text{Diff}\left(q_{ij},q_{i_{\mathrm{1}}j}\right)\ge \left(\mathrm{1}-A_j^l\right)I{F}_j^l+A_j^l\left[\text{Len}\left(T{L}_i^l\right)\right],\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(3)

headway constrains between arrival times of the same two direction consecutive trains as

$\begin{array}{c}\text{Diff}\left(q_{i_{\mathrm{1}}j},q_{ij}\right)\ge \left(\mathrm{1}-A_j\right)I{D}_j^l+A_j\left[\text{Len}\left(T{L}_i^l\right)\right],\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(4)

asynchronous departure-arrival interval times constraints of the same direction train as

$\begin{array}{c}\left[\left(y_{ij}-x_{i_{\mathrm{1}}j}+M\right)\mathrm{mod}M\right]\ge TF{D}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(5)

asynchronous arrival-departure interval time constraints of the same direction train as

$\begin{array}{c}\left[\left(y_{ij}-x_{i_{\mathrm{1}}j}+M\right)\mathrm{mod}M\right]\ge TD{F}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}\hspace{0.17em}l∊L;\end{array}$

(6)

interval time constraints of two relative direction trains that pass the station at different time as

$\begin{array}{c}\phantom{∊L;\text{i}}\left[\left(y_{ij}-x_{i_{\mathrm{1}}j}+M\right)\mathrm{mod}M\right]\ge T{G}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}\hspace{0.17em}j∊\left[\mathrm{1}·m\right],\hspace{1em}\\ i^{\prime }∊\left[\mathrm{1}·n^s\right],\hspace{1em}{j}^{\prime }∊\left[\mathrm{1}·m^s\right],\hspace{1em}l∊L;\\ d_{i_{\mathrm{1}}j}\ne d_{ij},\hspace{1em}\hspace{1em}R{I}_{i_1^{\prime }{j}^{\prime }}^{s_l}\cap R{O}_{i^{\prime }{j}^{\prime }}^{s_l}=\varphi ;\end{array}$

(7)

headway constraints between asynchronous arrival times of two trains as

$\begin{array}{c}\text{Diff}\left(q_{ij},q_{i_{\mathrm{1}}j}\right)\ge T{B}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}\hspace{0.17em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(8)

crossing interval time constraints in station of trains as

$\begin{array}{c}\text{Diff}\left(q_{ij},q_{i_{\mathrm{1}}j}\right)\ge T{H}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}\hspace{0.17em}l∊L;\end{array}$

(9)

free running time, starting additional time and stopping additional time constraints of trains at segment as

$\begin{array}{c}\text{Len}\left(q_{ij}\right)=T{Y}_j^l+S{I}_j^l\times T{Q}_j^l+S{O}_j^l\times T{T}_j^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(10)

least dwell time constraints of trains in station as

$\begin{array}{c}\text{Len}\left(q_{ij}\right)\ge T{Z}_i^l,\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}l∊L;\end{array}$

(11)

access route and send out route constraints as

$\begin{array}{c}\left(R{I}_{i^{\prime }{j}^{\prime }}^{s_l}\cup R{O}_{i^{\prime }{j}^{\prime }}^{s_l}\right)\cap \left(R{I}_{i_{\mathrm{1}}^{\prime }{j}^{\prime }}^{s_l}\cup R{O}_{i_{\mathrm{1}}^{\prime }{j}^{\prime }}^{s_l}\right)\ne \varphi ,\\ i^{\prime }∊\left[\mathrm{1}·n^s\right],\hspace{1em}{j}^{\prime }∊\left[\mathrm{1}·m^s\right],\hspace{1em}l∊L;\end{array}$

(12)

crew working time constraints of trains as

$\begin{array}{c}\sum _{i=\mathrm{1}}^n\hspace{0.17em}\sum _{j=\mathrm{1}}^m\left(q_{ij}\right)+\sum _{i^{\prime }=\mathrm{1}}^{n^S}\hspace{0.17em}\sum _{j^{\prime }=\mathrm{1}}^{m^S}\left(q_{i^{\prime }{j}^{\prime }}\right)\le T{C}_{ij},\\ i∊\left[\mathrm{1}·n\right],\hspace{1em}j∊\left[\mathrm{1}·m\right],\hspace{1em}{i}^{\prime }∊\left[\mathrm{1}·n^s\right],\\ j^{\prime }∊\left[\mathrm{1}·m^s\right],\hspace{1em}l∊L.\end{array}$

(13)

The notations of parameters and variables are shown in Table 1.

Table 1:

Subscripts and parameters used in mathematical formulations.

Symbol	Definition
f	Object function of optimization
L	Trains number in RN, $L=\{l\mid l=\mathrm{1,2},\dots ,n\}$
V	Set of station, $V=\{v_i\mid i=\mathrm{1,2},\dots ,n\}$
V s	Sets of isolated rail joint, turnout center, intersections of curves, and arrival-departure lines center, $V^s=\{v_i^s\mid i=\mathrm{1,2},\dots ,n^s\}$
E s	Set of the shortest rail that make isolated rail joint, turnout center, intersections of curves, and arrival-departure lines center as vertices, $E^s=\{e_j^s\mid j=\mathrm{1,2},\dots ,m^s\}$
B s	Set of boundary points, $B^s=\{b_j^s\mid j=\mathrm{1,2},\dots ,m^s\}$
RI s	Set of access route that composed by boundary points and line points sequence
RO s	Set of send-out route that is composed by boundary points and line points sequence
x ij	Starting time for train events x ij > 0
y ij	Closing time for train events y ij > 0
RI ij s l	Access route for train l at station v i or at segment e j
RO ij s l	Send out-route for train l at station v i or at segment e j
A j l	Driving occlusion mode for train l at segment e j ; automatic block system A j l = 0 or other A j l = 1
d ij l	Direction indicator for train l; d ij l = 0 for an outbound train or d ij l = 1 for an inbound train
SI j l	Driving mode for train l enter segment e j nonstop (stop) SI j l = 0 or SI j l = 1
SO j l	Driving mode for train l enter segment e j nonstop (stop) SO j l = 0 or SO j l = 1
q ij	Traveling time for train events
IF j l	Departure tracing interval time for trains at segment e j
ID j l	Arrival tracing interval time for trains at segment e j
TY j l	Free running time for train l at segment e j
TQ j l	Starting additional time for train l at segment e j
TT j l	Stopping additional time for train l at segment e j
TB j l	Asynchronous arrival interval time for trains at station v i
TH j l	Crossing interval time for trains at station v i
TL j l	Continuous departure interval time for trains at station v i
TFD j l	Asynchronous departure-arrival interval time for trains at station v i
TDF j l	Asynchronous arrival-departure interval time for trains at station v i
TG j l	Asynchronous passing interval time for trains at station v i
TZ j l	Least dwell time standard that train l at station v i
M	Unit time of diel, M = 1440 or M = 86400
Len	Length time for train events
Diff	Difference of train events

4. Implementation Steps of the Algorithm

OO used to solve TOA under complex RN can be achieved through the following four steps.

(1) Producing a Set ⊝ _N for TOA Programs. The prerequisite is not to directly solve algorithm of the TOA model (M1) when applying OO theory to solving the TOA problems but to repeatedly assess the value of objective functions corresponding to all of the feasible solutions within the set ⊝ _N (a characterization set with a certain number of randomly selected feasible solutions) and determine the pros and cons of each solution. The characterization set ⊝ _N is composed of a certain number (N = 100) of randomly selected feasible solutions taken from the time period when train operation needs to be adjusted. OO helps to transfer operation on solution space to a limited set ⊝ _N . All of the following steps are working on the representative set ⊝ _N suppose and that there is no further explanation. When making plans to adjust the train, assume that train 77011 is delayed, the following ones, such as 77013 and 77015, will be influenced to change operation as scheduled, or the three trains will crush into each other in sections S1S2 and S2S3. Consequently, a feasible solution is a solution without any conflicts among trains. Under the premises that train 77011 departures at the scheduled time, there will be several plans to adjust the departure time of the following trains. Every solution from the set ⊝ _N is not feasible until it passes the feasibility test. We take it as a feasible solution that there is no conflict of trains in the plan and the running time is minimized. If the term “arbitrary adjustment” goes under provision of “adjustment plan,” the number of solutions will shrink sharply. For what is shown in Figure 1, OO here is to reduce the size of solution space, transferring operation on all of the adjustment plans (solution space) to certain adjustment plans (finite set ⊝ _N ) occurring in a limited period of time. In the Figure, the condition in which conflict points mainly occur is that the time interval that train travels in the section does not satisfy the required interval. In model (M1), the conflict points refer to not only time conflict but also route conflict that the train arrive and depart, and thus the TOAs are to eliminate conflicts both in time and in space. In order to simplify the solving progress of algorithm, this paper discusses the problems only under condition of time conflict, and problems with constraints in both time and space will be discussed in further researches.

Figure 1:

Train operation adjustment plan set ⊝ _N .

(2) Assessing the Ordered Performance Curves (OPC) of TOA Plan, Building up an RM, and Verifying the Type of the TOA Problem. Limited by computing ability, it is unavailable to accurately calculate and get every exact solution of the solution set ⊝ _N . However, according to the special character of “order comparison” of OO, it is available and feasible to build up an RM for objective function and assess each feasible solution in solution set ⊝ _N . This is a key point in the theory of OO by roughly assessing the OPC [10] and determinig the type of the problems that need to be researched.

By building up an RM of TOA model (M1), we assess rapidly each of the feasible solutions from set ⊝ _N based on OO and then sequence them in order from “least” to “most” according to the principle of “the least total travel time of freight trains.” As is shown in Figure 2, we take the serial number of each sequenced feasible solution as horizontal axis, the corresponding value of rough assessment as vertical axis, and the curves as OPCs based on the RM of TOA. According to the shape of the OPCs, we can determine which type of the problems belong to, flat style, U-shaped style, neutral style, bell style, or steep style. All types are referring to [10].

Figure 2:

Schematic diagram of OPC curve type.

Certain requirements need to be satisfied in the RM building for TOA model (M1). If the model is too simple, although the pros and cons of the set ⊝ _N of all feasible solutions could be preliminarily assessed and the amount of computing OPC shape could be sharply reduced, it could lead to the fact that the results of rough assessment deviate largely from the actual practice and the chosen set S for simulation is too large to reflect the advantages of OO theory; otherwise, if the model is too accurate, the computing amount for solving algorithm in the preliminary assessment of feasible solution set ⊝ _N will be too large to be accomplished. Therefore, what we need to do is to establish an appropriate RM in order to fully reflect economic advantage of OO in computing. However, the solving algorithm of model (M1) includes not only the departure and arrival time of the train but also the access route and send-out route of trains, which apparently ensure the TOA plan rational and feasible. However, for an RM that not too precise to be calculated, the conditions of station conflicts will not be taken into consideration. According to the special features of constraints in space and time for TOA. By simplifying model (M1) with RM, we get a new model (M2) with only time conflicts, formulated as:

$\begin{array}{c}\min \hspace{0.5em}{f}_{\mathrm{2}}=\sum _{i∊\Omega }\hspace{0.17em}\left[\sum _{j,j^{\prime }∊V}\hspace{0.17em}\left(y_{i{j}^{\prime }}⊝x_{ij}\right)+\sum _{\left(j,j^{\prime }\right)∊E}\hspace{0.17em}\left(y_{i\left(j,j^{\prime }\right)}⊝x_{i\left(j,j^{\prime }\right)}\right)\right]\\ \text{s}.\text{t}.\hspace{1em}{x}_{ij}⊝x_{i^{\prime }j}\ge \left(\mathrm{1}-A_{\left(j,j^{\prime }\right)}^i\right)I{F}_{\left(j,j^{\prime }\right)}^i+A_{\left(j,j^{\prime }\right)}^i\left[\text{Len}\left(q_{i^{\prime }j}\right)+T{L}_j^i\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{1em}\forall i∊\Omega ,\hspace{1em}j∊E\cap V,\hspace{0.17em}\hspace{1em}{d}_{ij}=d_{i^{\prime }j},\hspace{0.17em}\\ \hspace{1em}\hspace{1em}\hspace{0.5em}{y}_{i^{\prime }j}⊝y_{ij}\ge \left(\mathrm{1}-A_{\left(j,j^{\prime }\right)}^i\right)I{D}_{\left(j,j^{\prime }\right)}^i\hspace{0.17em}+A_{\left(j,j^{\prime }\right)}^i\mathrm{\hspace{0.17em}\hspace{0.17em}}\left[\text{Len}\left(q_{ij}\right)+T{L}_j^i\right],\\ \forall i∊\Omega ,\hspace{1em}j∊E\cap V,\hspace{1em}\hspace{0.17em}{d}_{ij}=d_{j^{\prime }j},\\ \hspace{1em}\hspace{1em}\hspace{0.5em}{y}_{ij}⊝x_{i^{\prime }j}\ge TD{F}_j^i\hspace{1em}i,i^{\prime }∊\Omega ,\hspace{0.17em}i\ne i^{\prime },\hspace{0.17em}{d}_{ij}j∊V,\hspace{0.17em}{d}_{ij}=d_{i^{\prime }j},\\ \hspace{1em}\hspace{1em}\hspace{0.5em}{y}_{ij}⊝x_{i^{\prime }j}\ge T{G}_j^i,\hspace{1em}i,i^{\prime }∊\Omega ,\hspace{0.17em}i\ne i^{\prime },\hspace{0.17em}j∊V,\hspace{0.17em}{d}_{ij}=d_{i^{\prime }j},\\ R{I}_j^i\cap R{O}_j^{i^{\prime }}=\varphi ,\\ \hspace{1em}\hspace{1em}\hspace{0.5em}{y}_{ij}⊝y_{i^{\prime }j}\ge T{B}_j^i,\hspace{1em}i,i^{\prime }∊\Omega ,i\ne i^{\prime },\hspace{0.17em}j∊V,d_{ij}=d_{i^{\prime }j},\\ \hspace{1em}\hspace{1em}\hspace{0.5em}{y}_{ij}⊝y_{i^{\prime }j}\ge T{H}_j^i,\hspace{1em}i,i^{\prime }∊\Omega ,i\ne i^{\prime },\hspace{0.17em}j∊E,\hspace{0.17em}{d}_{ij}=d_{i^{\prime }j},\\ \hspace{1em}\hspace{1em}\hspace{0.5em}\text{Len}\left(q_{ij}\right)=T{Y}_{\left(j,j^{\prime }\right)}^i+S{I}_{\left(j,j^{\prime }\right)}^i\times T{Q}_{\left(j,j^{\prime }\right)}^i\hspace{0.17em}+S{O}_{\left(j,j^{\prime }\right)}^i\times T{T}_{\left(j,j^{\prime }\right)}^i,\\ \forall i∊\Omega ,\\ \hspace{1em}\hspace{1em}\hspace{0.5em}\text{Len}\left(q_{ij}\right)\ge T{Z}_{\text{j}}^i,\hspace{1em}\forall i∊\Omega ,\hspace{0.17em}\forall j∊V.\end{array}$

(M2)

Algorithm steps for assessment of the model equation (M2) are as follows.

Step 1. Choose the first train that causes conflicting events in the section of the complex railway network and the section where the train is.

Step 2. If there is no conflicting event, the algorithm is aborted, and the results of the RM of TOA should be outputted.

Step 3. Choose an algorithm section with the earliest time conflict and judge and generate the follow-up moments during which the conflict is eased or solved. Collect all of the moments that satisfy the requirements to ease or solve the conflicts.

Step 4. Choose the minimum travel time from the follow-up moments as the solution of the RM, horizontally traverse the algorithm interval, and ease and solve all of the conflicting points in this section.

Step 5. Take the first moment among the conflict time as the starting point and vertically traverse the second algorithm interval. If there is no conflicting point, then turn to Step 2 or turn to Step 3.

Step 6. Ease or solve all of the conflicting points, and there the algorithm will end, and output a rough TOA plan.

Randomly, we choose 20 adjustment plans. Under the above steps, we assess rapidly the objective function f₂ in model equation (M2) with data from those 20 adjustment plans, calculate the rough values of total travel time (min) of the train, and then sequence those values from “the smallest” to “the largest.” All of the feasible solutions can be got and a corresponding OPC will be drafted, as shown in Figure 3. We can judge the optimization type of TOA after comparison with [10]: this OPC belongs to the bell one.

Figure 3:

OPC curve of train operation adjustment system.

(3) Determine the Set S of TOA That Need to Be Accurately Simulated. OO aims at saving the amount of calculation by building up RMs; that is, its aim is to get a desirable set S of TOA plans by using an RM, with great probability to include at least k solutions that simulate to p layer. It must be ensured to select at least k solutions from the set S of the TOA plan with the least travelling time and without any conflicting events. To highlight the advantages in saving the amount of computation, it is a must that the number of solutions within the set S should be less numerously than that of the whole solution space. After determining the type of the OPC, the value of p and k, and the deviation distribution of the relatively accurate value under rough evaluation—U ∼ [– w, w], we can get parameters z, ρ, γ and the regression value of η according to [10]. β, the value of TOA set S, can be calculated by (14) as

$\beta =\lceil e^z{k}^{\rho }{p}^{\gamma }+\eta \rceil .$

(14)

In (14), $|e^z{k}^{\rho }{p}^{\gamma }+\eta |$ represents the minimum integer which is smaller than or equal to e ^z k^ρp^γ + η.

(4) Choosing a Solution with Least Total Travel Time (TTT) and No Train Conflicts from the TOA Set S. Based on the set S of the TOA plan, we introduce simulation algorithm to solve each subobjective function corresponding to each feasible solution, sequence them from smallest to largest, and select k of them as “GESs.” To improve the accuracy of the “GESs,” Steps 1–4 and OO calculation should be repeated. After each time of OO calculation, k ones of the “GESs” should be chosen to constitute an alternative set. At last, the best k “GESs” from the alternative set can be chosen as the solution and final plan for TOA.

5. Case Study

The data is from the practical operation of Da-Qin heavy haul railway, with a length of 653 km, 24 CTC control stations, 2 TDCS command centers, and 1 dispatch control center, whose annual carriage capacity lists top in China or even in the world [11]. Thereafter, we use data of Da-Qin Number 1 dispatch control from 14:30 to 18:30, 30 December 2008 to realize simulation based on the above-mentioned algorithm method and steps.

When trains conflict, as shown in Figure 4, firstly, we should find out the first conflict event and define the operation space of TOA and the set ⊝ _N for the feasible solutions. Secondly, we limit the time space of the feasible solution set ⊝ _N within the adjustment plan, and then a feasible solution set ⊝ _N with N = 100 is generated.

Figure 4:

Schematic diagram of conflict point of TOA system.

According to the operation line of Da-Qin heavy haul railway, figure “– ○  –  ○ –” represents combined heavy haul trains and “–  ⊳  –  ⊳  –”represents stand-alone trains; besides these, there are still 20 thousand-ton heavy haul trains, C80 unit heavy haul trains, unit heavy haul trains, common goods trains, and so forth, and we distinguish them with different colors and signals.

After times of quickly evaluating the model equation (M2), Figure 3 can be got and OPC of the TOA plan can be made—type bell. According to feasible solution set ⊝ _N and OPC, the set S of TOA plan will be got.

According to [10], there is a specific method to determine set S and further parameter:

1. Type of OPC: bell.

2. Range of p: the set ⊝ _N is accurately evaluated and the top 20%, after sequencing all solutions, are defined as GESs, that is, p = 100 × 20% = 20.

3. Range of k: it is required that there is at least one real GES in the selected set S, that is, k = 1 and the probability a% ≥ 95%.

4. Deviation distribution of the relatively accurate value of rough evaluation value f₂—U ∼ [– w, w]: 30 feasible solutions from set ⊝ _N are randomly selected, and the total train operation time under both rough evaluation and accurate evaluated value is calculated (i.e., optimized total operation time after adjustment). The difference between the two is used to describe the deviation of rough evaluation to accurate evaluation. by statistic method, we get the standard variance of the deviations, the value is 0.0532; to be more accurate, we make twice the variance of the deviation as the value of w for U ∼ [– w, w], that is, w = 0.1064 ∊ [– 0.5,0.5].

Thus, according to the regression Table 1 of [10], values of the followed will be got: z = 8.1998, ρ = 1.9164, γ = – 2.0250, and η = 10.00.

According to (M2), the scale of TOA set S of GESs will be known, that is, 26.1819, which means that 26 feasible solutions from the set ⊝ _N , after rough evaluation, are selected and then the total train operation time can be accurately calculated.

We make careful simulation for the 26 solutions within set S, calculate their total train time, and sequence the results from the smallest to the biggest. We select the first 5 smallest results as the final GESs of TOA optimizing system, which are 5078, 5095, 5088, 5069, and 5084 minutes. In this case, the final GES is the 86th feasible solution, and total operation time of which is 5069 minutes. The TOA system will automatically work on from the first interval conflict of the descending trains and will solve or optimize all of the conflict points in interval 1, as shown in Figure 5. Identically, the system could gradually solve conflicts in the followed-up intervals quickly layer by layer till all of the conflict points are eased or solved, and an optimized TOA plan of the descending trains with no conflicts will be achieved. The optimized TOA plan of the up-going trains can be achieved by the same way. Then we will have a consummate TOA plan.

Figure 5:

Schematic diagram after untwining conflict automatically by TOA system.

All in all, it is an efficacious way to solve the TOA plan based on OO since it is can help to reach the set ⊝ _N with enough high probability and the real GESs in the whole solution space, which greatly improves the efficiency of calculation in solving problems of TOA. This method used to deal with conflicts in TOA has been verified in the Da-Qin railway as the algorithm could enhance the efficiency and accuracy in train operation, declining greatly the work intensity of the dispatchers.

Under complex conditions of railway networks, based on data from the train dispatch and operation system of Da-Qin heavy haul railway, from the perspective of the real time work, this paper takes minimum travel time of the freight train as objective function of optimization, which aims at adjusting train operation to ease or solve conflict events in intervals and building up a TOA model based on the complex train networks. This method is achieved by simplifying TOA and roughly evaluating the total train operation time of the optimized objective, which could, with greatly decreasing the work in calculation, get GESs for the TOA system. in this paper, “Ordinal Comparison” and “Goal Softening” are made full use of, which avoids directly calculating the TOA model by repeatedly evaluating the value of the objective function. Besides that, to get GESs that meet the requirements, OO could reduce the standards for solving.

As to those optimization problems that are not only real time but also high dimensional and nonlinear with great uncertainty under the complex RN, this method can meet the practical requirements of TOA.

Algorithm analysis and practical application prove well that the method of OO could achieve GESs for TOA plans while reducing greatly the amount of calculation. In addition, it is supposed to find a standard to judge whether a TOA plan is optimum or not, that is to say, from which perspective the adjustment is the best? In contrast to other regular heuristic methods, OO can well quantize the extent of the pros and cons of the solution results, that is, with what probability TOA plan set S can contain k GESs. These quantitative information is just what regular heuristic methods cannot provide, which is also one of the advantages of applying OO in TOA.

Considering the particularity of Da-Qin heavy haul train, we take the TOA problem in Da-Qin heavy haul rail as a single-objective optimization problem, yet it is not just a single-objective optimization problem but should be a multiple objectives that target at least deviation of TOA plan, minimum train travel time, enhancing the on-time rate of train arrival and departure, and decreasing the number of trains that run late than scheduled. The conditions discussed in the TOA model are limited only to conflicting events in intervals, with considering the conflicts in stations and universality in which the TOA model is applied in different train lines. The questions and problems not mentioned in this paper will be researched and discussed in the future work.