ALGORITHM FOR OPTIMAL CORRECTION OF TRAIN TRAFFIC SCHEDULE

<jats:p>The article analyses the problem of train traffic schedule optimal addition according to minimum overall expenditure criteria. The task is to analyze optimal insertion of an additional train track into already made schedule. The methodology is all‐right applicable for ad hoc requests submission. Handling importance of ad hoc requests is emphasized in EU directive 2001/14/EB. The task can be solved applying Monte‐Carlo, genetic algorithms, variants reselection methods or methods of the shortest (according to waste) way in graphs. All these methods are equally exact and can be implemented in modern computers with short enough time consumption.</jats:p>

section_content: Planning of train traffic is more rigorous than planning of road traffic. This occurs not only because trains are bulky, but because they can not move freely, changing their speed or overdriving each other as road transport facilities do. 

Despite high requirements, deviations from railroad traffic schedule are likely to occur: trains fail behind the schedule because of various reasons. Depending on the category of delayed train and freight being transported by this train, traffic managers (dispatchers) correct the situation accepting appropriate heuristic decisions, which often are not optimal or sometimes even faulty. 

Currently a high level of informational transport control systems presents a possibility to install automatic or even self-acting correction system for disturbed train traffic. Science fiction [1] [2] [3] [4] contains similar tasks; however they are solved either by applying the criterion of passenger comfort or by adapting them for railroad infrastructure with semi-automatic blocking without possibility of operative correction for train mobility [2] [3] [4]. Such systems are not typical for railroad networks of various countries: semi-automatic blockings are already obsolete and modern traffic control technologies (e. g. the EU system ERTMS) enable to control train traffic at a high level of exactness. 

This issue presents theoretical principles of optimal correction of train traffic schedule being disturbed in railroad line, having installed a self-acting control system. 

The issue presents the algorithms, which might be successfully applied for automation of "last minute" (ad hoc) application service (by inserting an additional train line in a fully prepared traffic schedule). The current situation of "last minute" (ad hoc) application service is left as the option of infrastructure managers and the service procedure itself is such that the driver (applicant) is not aware of how to formulate the application and satisfy maximum of his interests as well as how to find out the detail, which may cancel the application [5, 6].
section_name: Introduction

section_content: The train traffic schedule is comprised of a number of so called "train lines", each of them describes a particular route. 

In the diagram the "train line" on the plane of time (t) and distance (s) is represented as a broken line, the horizontal segments of which correspond to standing (at the station) and oblique segments correspond to moving at appropriate speed. 

Stations on the train schedule are labelled only by their axial line (i. e. the length of the station is not assessed). Acceleration and deceleration sections are not shown also: it seems that a train stops momentarily and in the same way develops necessary speed (Fig 1). The average speed T j of train j in line i (the line, connecting stations S i and S i+1 ):

is called technical speed of train T j in line, connecting S i and S i+1 stations. 

In Fig 1, as well as in equations

( +, the time when train T j arrives to station S i+1 is presented. 

Analytically "train line" of train j is described as function ) (t s j. In turn each function ) (t s j is comprised of straights and segments: Herein: n -the number of station in line. Traffic schedule:

These parameters are enough to describe the traffic schedule nominally. 

Departure time matrix t i = i ji t. Speed matrix v = ji v. Coordinate vector of station axial lines S = i S. The disturbance of traffic schedule is described as the difference between planned diagram S p (t) and factual diagram S f (t), as even for a single "train line" this equation is applied:

is permissible delay of the train (measured in terms of losses). 

Hereinafter such traffic disturbances are analyzed when only a single train fails behind the schedule impermissibly (Fig

Train T u according to the plan had to run in line ) and the point of route (s) at which the train delays. These assumptions are expressed as function N u ( u τ, s), for which these features are appropriate:

Practically function ), ( s N u u τ is discrete: s acquires coordinate values of station axial lines only s ∈ { z s,. . ., n s }. Herein: z is the station index, where traffic schedule of the train T u was disturbed; n is the index of terminal station. 

In such case

assesses the losses involved in delay of train T u only. This is enough as the task of traffic optimization for delayed train is analyzed, but if a completely new train line must be inserted in a traffic schedule (i. e. as addition but not correction of traffic schedule) it is necessary to use the function:

Herein: T Tui W -component depending on time and involved in exploitation costs of locomotives and carriages of train T u as well as calculated for the period, during which the train T u crosses line i (S i -S i+1 );

T Eui W -Costs for the team of train T u, calculated for the period, during which train T u crosses line i; ui N -Losses, incurred because of ill-timed ar- rival of train T u to terminal station S i+1 of line i (S i -S i+1 ). 

If it were be possible to neglect other traffic participants, train T u would run all the remaining distance (from station S z, where it was forced to delay, up to terminal station S n ) at the reasonable speed

) resulted in minimal costs of fuel and losses u W, incurred because of the delay:

In this formula:

G, M and N -parameters of locomotive, presented in its documentation; ui

L ui

W -expressions obtained in accordance with the methods introduced in reference [7]. 

The second component ) ( ui u N τ of formula (4) has no universal expression and is stipulated by technological, arbitrary and other dependences. Seeking that all components in formula (4) would be of the same dimension, it is necessary to express ) ( ui u N τ not in terms of money, but in terms of arbitrary fuel in kg (as E ui W ). The fact permits an assumption that these dependences are known. 

Unfortunately the assumption (made before the formula (4) has been written) that other traffic participants may be neglected (equal to the assumption that other traffic participants do not intervene) is often valid for road transport facilities, but not for trains. 

In railroads with a modern traffic control system being implemented, train T u, performing manipulations of its speed is able to:

1. To catch up with an oncoming slower train, 2. To be caught up by a faster train running after. 

In the first case two events are possible again: 1. 1. The ongoing train T j stops at the primary station of the line, in which it will be caught up and lets train T u pass. 

1. 2. The ongoing train does not stop until its panned station. 

These cases are illustrated in Fig 2. Traffic variations. On the left: slower train T j makes way (the situation 1 T u -1 T j ) or does not make way (the situation 2 T u -2 T j ) for train T u. On the right: train T u does not disturb (the situation 1 T u -1 T j ) or disturbs (the situation 2 T u -2 T j ) train T j to leave timely

In the second case train T u has always to stop and let the train, which is running after, pass because faster trains are usually of higher category. 

The analysis of variations of possible traffic situations shows that the situations below should be applied for the analysis of each line k (with its terminal station S k+1 ):

A -train T u neither in line k nor in its terminal station (S k+1 ) does not catch up with ongoing train T j and can not be caught up by train T j+1, which is running after. 

The other variation of this case: train T j can not be caught up in line k, but according to schedule stops in the terminal station S k+1, belonging to this line. In this case train T u at station S k+1 is able to overtake train T j, without disturbance of its traffic schedule (Right side of D -train T u in line k catches up to ongoing train T j, which does not let train T u pass. The situation is complicated by the fact that according to the schedule T j should not stop at terminal station S k+1 of the line. 

E -train T u in line k catches up with ongoing train T j, which does not let train T u to pass, but according to the schedule it has to stop at terminal station S k+1 of the line. 

F -train T u in line k is caught up by train T j+1, which is running after and T u is forced to let it pass, by stopping on purpose at primary station S k of the line. 

These entire situations are defined by different formulae of general costs. 

Situation A. To run a single line k general costs are:

To run the whole distance from station S z to terminal station S n of the route general costs are:

ui W -alculated according to formula (7a), as k → i; S uz W -the costs of arbitrary fuel for train T u to develop speed at primary station S z, are calculated according to the same methods as the costs of arbitrary fuel for train's speed development after its stopping (see formula (11)). In this formula jg is the index of the last line of train T j route. 

The formula (8) provides the optimization procedure for further movement of train T j being overtaken. The procedure usually does not produce marked effect thus the formula (7b) may be applied instead of formula (8) with a slight error. 

Situation C. To run line k general costs are:

To run the whole distance from station S z to terminal station S n of T u route general costs are:

(9b) The formula (9b) also provides the optimization procedure for further movement of train T j being overtaken. The procedure usually does not produce marked effect thus instead of the formula (8) the formula below may be applied with a slight error. W involved in formulae (8) and (10) are the costs of arbitrary fuel necessary to develop the speed for train j after it was forced to stop. 

In the case of terminal attraction

W is ex- pressed as a formula:

( )

Herein γ -inertia coefficient of turning mass, which depends on the type of train and loader and ranges form γ = 0,028 for loaded carriers to γ = 0,084 for empty carriers and γ = (0,17-0,18) for locomotives;

T a -Braking acceleration m/s 2 (in calculations T a = 0,22 m/s 2 are constant value); i w 0 -expressed as formula (6). D and E situations analytically are not complicated: additional conditions must be satisfied only:

(S r -station of planned stopping for train T j ) in case D and other condition:

in case E Situation F. To run the line k general costs are:

To run the whole distance from station S z to terminal station S n of T u route general costs are:

Here S uk W is calculated according to the formula (11), but using characteristics of T u train. 

Formulae (7b), ( 8 ), (9b), ( 10 ) and (13b) assess costs involved in speed development of train T u in primary line S z only. Not always train T u succeeds in interfering between trains' j and (j+1). It is possible that seeking to keep a safe distance up to interfering train T u, train (j+1) will be forced to reduce the speed that results in delay for the arrival to the stations, starting from (z+1). Due to this fact additional losses may be incurred (penalty) P j W ) 1 ( +, which are calculated as follows:

), (14b)

Formulae ( 14 ) use these symbols:

-braking distance in the first line (S i -S (i+1) ) respectively of train T u and train (j+1), which is running after. 

-distance between two neighbouring scheduled trains j and (j+1), where in line z train T u is able to intervene in this distance;

(

-losses, incurred as train (j+1) comes to station S i at the delay time

i l -length of the line. If train (j+1) is not able to arrive later to the station S i,

( )

Additional losses (penalty)

( + do not usually produce a marked effect thus in the algorithm below, concerned the calculating of general costs uy W, they are not assessed.
section_name: Formulation of the task

section_content: W in accordance with the formulae ( 7 )- ( 13 ) are calculated being aware of the parameters of traffic schedule and traffic participants: 1. Planned traffic schedule S(t) (see (3) formula). 

2. Functions of delay losses (penalty) N j ( ji τ ). 3. Train parameters G j, M j, N j, Q j, and parameters necessary to calculate w 0ji values. 

4. Relief parameters i e (s). 5. Air temperature 0 t. 6. Index z of the station, from which the line of train T u is corrected (inserted). 

7. Index p of the first train line, after which the correction line may be inserted. 

8. Element values jk c ∈ {1, ∞ } of "pass/ do not pass" matrix C = jk c, which may be given or pro- duced accidentally for each iteration of optimization process. 9. Departure time i uz t of train T u from the station S z (chosen with regard to the application of regular or stochastic search algorithms, determinate order or at random) and technical speeds of all lines v u = ui v, (as z ≤ i n-1). 

By choosing the mentioned parameters, the restrictions should be satisfied as:

The particular value of general costs uy W is cal- culated for each fixed vector of variables. It has to be noted that formulae ( 7 )-( 15 ) correspond to such interval system of train control, in which the distance between neighbouring trains may acquire any value (it is continuous). This is involved in the system of ETCS 3 level. If the distance between trains is expressed as the whole number of fixed blocked sectors, so the discrete variables of road, time and speed should be used in ( 7 )-(15) formulae.
section_name: Costs uy

section_content: The correction of the route is performed within permissible field (following the restrictions) seeking such vector of variable value { i uz t, v u, C } ger when the value of general costs uy W is minimal. This problem may be solved by applying algorithms of stochastic search (Monte Carlo method, genetic search algorithm etc. ), method of variations reselection (in respect of discrete variables) and other. 

Monte Carlo algorithm is one of the simplest proposed hereinafter. 

Begin 1. Parameters necessary to enter: 1. 1. Traffic schedule S(t), functions of delay losses (penalties) N j (τ ji ), parameters of trains G j, M j, N j, Q j, w 0ji, relief parameters i e (s), air temperature 0 t. 1. 2. Index z of the station, from which train line T u is corrected (inserted). 1. 3. Index p of the first train line, after which the correction line may be inserted. 24. uk W := 0. → p. 3. 

25. W uy := W uy + S uz W.
section_name: Algorithm for optimal correction of traffic schedule

section_content: The 2 nd, 4 th and 19 th conditions of the subroutine are checked with regard to the data of traffic schedule S(t) and the values selected for i uz t and v u = uji v variables, the 13 th condition is determined by the value of appropriate element of "pass/do not pass" C = jk c matrix, which (subject to optimiza- tion algorithm ) may be fixed or belong to the set of variables (in this case jk c occasionally may acquire values "1" or " ∞ "). The checking of the remaining conditions of subroutine algorithm is concentred to the tasks of a line segment, being expressed as data of traffic schedule S(t) and selected values of i uz t and v u = uji v variables, joint/disjoint tasks and search of the smallest distance between the segments of the line.
section_name: End

section_content: 1. The tasks of train traffic correction and addition are solved having installed modern information control technologies. 

2. It is reasonable to solve the problems of traffic schedule correction and optimal addition by applying the criterion of general costs. The solution is the optimal route line, which has minimal value of general costs. 

3. The algorithms of traffic schedule correction and addition are subject to high "branch" level: there are a lot of conditions, which affect later actions and solutions. 

4. The problems of traffic schedule correction and optimal addition are solved with the help of digital methods (by reselecting all combinations of discrete values of variable or by applying methods of stochastic search).
section_name: Conclusions