Adv Syst Sci Appl 2024; 03:31–42
Published online at https://ijassa.ipu.ru.

The Problem of Dynamic Regulation of Train Formation
on a Marshalling Yard

Elena Musatova1*, Alexander Lazarev1, Alexander Osminin2, Alexey Baushev3

1V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
2Volga State Transport University, Samara, Russia

3Emperor Alexander I St. Petersburg State Transport University, Saint Petersburg, Russia

Abstract: The problem of dynamic freight trains formation at a railway station is considered.
This problem is part of a two-step strategy to create a dynamic train formation plan. It is assumed
that technical routes of all cars and the predicted arrival time of new groups of cars at the station
are known. The problem is to determine the set of cars and the departure time of each train formed
at this station, taking into account the availability of locomotives and restrictions on the length
of trains. The goal is to minimise the total waiting time for cars at the station. Mathematical
models for different versions of the problem are presented as an integer and a mixed integer linear
programming problems. Results of computational experiments allow to estimate the influence
of the amount of information about arriving trains to the station on the value of the objective
function.

Keywords: train formation, integer linear programming, daily planning.

1. INTRODUCTION

The problem of developing a train formation plan (TFP) plays a key role in improving
the quality of freight rail transportation. In different countries there are various approaches
to the organization of freight rail transport. There are two main widely used operational
strategies for freight rail transportation [1]. In the first case, the priority is the scheduled plan.
This means that the departure of trains is carried out exactly according to a predetermined
schedule, regardless of the actual number of cars that need to be transported on a certain day.
Such plans require an accurate forecast of the number of cars. In the USA this type of plan
is used in rail transportation. In the second case, priority is given to the tonnage plan, i.e. the
departure of a train is carried out immediately after the station has the necessary number of
cars to form a train in a given direction. Russia, China and many other countries use such
freight transportation strategy.

In accordance with these two approaches, the formulation of optimization problems
corresponding to them also differs. In general, the problem of calculating the train formation
plan refers to the problems of network routing [2]. From the point of view of the mathematical
model structure, two areas of research can be distinguished: the construction of linear and
nonlinear models. At the same time, most modern research is devoted to linear models of the
TFP (see, for example, [1, 3, 4]), that is, problems of integer linear programming and mixed
integer linear programming. Examples of nonlinear models can be, for example, the problems
considered in [5, 6].

∗Corresponding author: nekolyap@mail.ru



32 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

As a rule, the problem of train formation is a large-scale problem of designing a flow
network and routing with millions, and even billions of decision variables. The size and
mathematical complexity of this problem do not allow us to solve it accurately with the help of
any commercial software [7]. In this regard, most of the studies in the field of train formation
and the distribution of car traffic are devoted to the development of fast heuristic algorithms
(see, for example, [3,4]). In addition, the decomposition of the general problem into a number
of successively solved problems is used. The following subproblems of railway planning are
distinguished [8]:
1) the problem of combining cars into blocks [9]. Each block is characterized by a departure
station and a destination station, while the cars included in it may have other stations of
formation and destination;
2) the problem of constructing routes and train schedules [2];
3) the problem of assigning blocks to trains [10].

However, the direct use of foreign experience in solving the TFP problem for Russian
Railways is impossible due to differences in the organization of the freight transportation
process. The existing methodology for creating the TFP was developed to solve the problems
of a planned economy and does not meet the conditions of the modern market economy.
As a result, the actual planning is reduced to a daily adjustment of the TFP, based on
the experience of process engineers and decision makers. The fast operation of planning
algorithms is extremely important in this problem due to the fact that the moments and
volumes of incoming trains to a marshalling yard differ from year to year and from day
to day.

The formulation of the TFP problem in Russian Railways is determined by a specific
procedure for constructing the formation plan. So there are two plans for the trains formation:
a basic plan and an adaptive one. The basic TFP is built a year in advance and determines
for each station destinations of trains formed at it. The problem of the adaptive formation
plan is to determine technical routes for cars, i.e. sequences of stations through which the
cars must go to destination stations, as well as determining which car is assigned to which
train. Our work deals with the adaptive TFP problem. Building an adaptive formation plan is
a high-dimensional NP-hard problem. Moreover, various local changes and inconsistencies
that arise in practice do not allow solving the problem for the entire railway network at the
same time. An approach is proposed that focuses on the possibility of implementing the
developed algorithms for constructing an approximate solution of the TFP problem in real
railway practice.

The adaptive TFP problem is divided into two subproblems: the problem of technical
routing and the problem of dynamic regulation. This article is devoted to the problem of
dynamic regulation, where it is necessary for a single station to determine a content (set
of cars) and a time of departure of each train formed at this station. Our goal is to build
mathematical models of dynamic formation of trains at the station and trace the influence of
the length of the planning horizon on the solution to the problem.

The article is organised as follows. Section 2 includes a description of the problem,
notation and basic terms. In Section 3 a mathematical statement of the problem is presented.
In Section 4 we present results of computational experiment using solver CPLEX for
problems of small dimensions. Results of solving high-dimensional problems are given in
Section 5. In Section 5 we consider a special case of the problem that is easier to solve.
Section 7 contains conclusions and suggestions.

2. PROBLEM DESCRIPTION

A train formation station (or marshalling yard) is considered. Let K = {1, . . . , n} be a set
of destinations of trains departing from the station. This means that it is possible to form n
types of trains with different destination stations. As a planning horizon, we choose the time

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



PROBLEM OF DYNAMIC REGULATION OF TRAIN FORMATION 33

interval [t0, tmax], the length of which depends on the available information about arrival of
freight trains at the station. In practice, planning can be carried out a day ahead.

T = {t1, . . . , tm} specifies moments of trains arrival to the station in the considered
planning horizon. At the initial moment of time, n storages corresponding to n destinations
already contain groups of cars, called blocks. In addition, there are r0 locomotives at the
station. These are the locomotives that delivered the blocks to the station before the initial
point in time, but were not yet used for new train departures.

At time moments ti, i ∈ I = {1, . . . ,m}, trains consisting of blocks arrive at the station.
Arrived blocks of cars, for which this station is not the final one, are distributed among the
storages in accordance with their destinations, thereby increasing the number of cars in the
corresponding potential trains. Each arrived locomotive can be used to form a new train.

Let G be a set of all blocks considered on the given planning horizon, including the blocks
located in the storages. Each block g ∈ G has the following characteristics:

• τg is the time moment of arrival at the station (if a block g arrived at the station before
the initial moment, then we set τg = t0 = 0);

• kg is the destination of g;
• lg is the number of cars in the group.
Each block is an indivisible group of cars, i.e. all cars of the block must leave the station

in one train. In Section 5 we will additionally consider another version of the statement where
the division of blocks is allowed. Let Gk be the set of blocks of destination k and Lmin, Lmax

be respectively the minimum and the maximum numbers of cars included in one train formed
at the given station, i.e. the departure of a train can only take place if the number of cars
in it satisfies the upper and lower limits. At each time moment from set T it is necessary to
make a decision whether to sent trains to some destinations. Also we have to determine which
blocks will be included in these trains. We assume that the time required to form a train is a
constant equal to β. The goal function is the total number of car-hours spent at the station for
the period under consideration.

3. MATHEMATICAL STATEMENT

Let’s number all the locomotives that are at the station at the zero moment of time plus all
the locomotives that will arrive in the considered time period, from 1 to r0 +m in the order
of their arrival at the station. Let J = {1, . . . , r0 +m} be the set of all locomotives. Denote
by φj the moment of arrival of the locomotive j at the station. If locomotive j arrived at the
station before the beginning of the time period under consideration, then we set φj = 0. Let’s
introduce the following decision variables:

• binary variable yjik, j ∈ J , i ∈ I , k ∈ K, equals to 1 if locomotive j leaves the station
as part of a new train at time ti + β and has a destination k, and 0 otherwise.

• binary variable xgij , g ∈ G, i ∈ I , j ∈ J , is equal to 1 if block g leaves the station at
time ti + β with locomotive j, and 0 otherwise.

• binary variable zg, g ∈ G, takes the value 1 if block g does not leave the station in the
given planning horizon, and 0 otherwise.

We list the main constraints. Each block leaves the station once, or does not leave it at all in
the current planning period: ∑

i∈I

∑
j∈J

xgij + zg = 1 ∀g ∈ G. (3.1)

Each locomotive can be used at most once:∑
i∈I

∑
k∈K

yjik ≤ 1 ∀j ∈ J. (3.2)

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



34 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

Each block leaves the station no earlier than it arrives there:

xgij = 0 ∀g ∈ G, ∀j ∈ J, ∀i ∈ I : τg > ti (3.3)

and no earlier than its locomotive arrives there:

xgij = 0 ∀g ∈ G, ∀j ∈ J, ∀i ∈ I : φj > ti. (3.4)

Each locomotive can depart as part of a new train not earlier than its arrival at the station:

yjik = 0 ∀j ∈ J, ∀i ∈ I : φj > ti, ∀k ∈ K. (3.5)

There is a restriction on the number of cars in the trains being formed:

Lminyjik ≤
∑

g∈G:kg=k

lgxgij ≤ Lmaxyjik ∀k ∈ K, ∀i ∈ I, ∀j ∈ J. (3.6)

Finally, we add the condition of binary variables:

xgij, yjik, zg ∈ {0, 1} ∀g ∈ G, ∀i ∈ I, ∀j ∈ J, ∀k ∈ K. (3.7)

The problem of minimizing the total car-hours at the station in the given planning horizon
is considered. The total number of car-hours for blocks that will be sent in the planning period
is determined as ∑

g∈G

lg
∑
i∈I

∑
j∈J

(ti + β)xgij −
∑
g∈G

τglg
∑
i∈I

∑
j∈J

xgij.

For cars remaining at the station by the end of the period under consideration, the total waiting
time is equal to

tmax

∑
g∈G

lgzg −
∑
g∈G

τglgzg.

The sum of these quantities can be written as∑
g∈G

lg
∑
i∈I

∑
j∈J

(ti + β)xgij + tmax

∑
g∈G

lgzg −
∑
g∈G

τglg(
∑
i∈I

∑
j∈J

xgij + zg).

Due to the constraint (3.1), we get that the objective function of the problem can be written
as ∑

g∈G

lg
∑
i∈I

∑
j∈J

(ti + β)xgij + tmax

∑
g∈G

lgzg −
∑
g∈G

τglg → min . (3.8)

We denote problem (3.1)-(3.8) by (P1). It can be seen that the number of variables is equal
to |J ||I||K|+ |J ||I||G|+ |G|, where | · | is the number of elements in the corresponding set.
The number of constraints is a value of the same order.
Theorem 3.1:
Problem (P1) is strongly NP-hard.

Proof
We consider the multiple subset sum problem with identical capacities (MSSP-I) which is
strongly NP-hard [11]. In this problem we are given a set of values wj , j ∈ {1, . . . , g}, and
we are looking for m subsets of this values with the maximal total sum provided that the sum
in each subset does not exceed a capacity c.

Problem MSSP-I is a special case of problem (P1) where the number of train destinations
n = 1, all m = m trains arrive at zero time moment, |G| = g, lj = wj , j ∈ {1, . . . , g},

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



PROBLEM OF DYNAMIC REGULATION OF TRAIN FORMATION 35

Lmin = 0, Lmax = c and the storage already contains groups of cars. As all locomotives are
available at zero time moment, in this special case we just have to redistribute the cars by m
trains, taking into account the trains in the storage, to maximise the number of cars sent from
the station (or minimise the number of cars remaining at the station). This reduction of the
problem MSSP-I to the special case of problem (3.1)-(3.8) proves the theorem.

Cars in storage: 30 10

Arriving trains:

7:00

9:00

10:00

55 20

20 40 10

35 20 20

Fig. 3.1. Initial data

In practice, a train is formed as soon as the required number lmin >= Lmin of cars
has accumulated at the station for some destination and a locomotive is available for this
departure. We will call this strategy the current approach to planning (CAP). Let’s consider
example 3.1 showing that CAP may be non-optimal.
Example 3.1:
Let trains of two destinations be formed at the station. Suppose that lmin = Lmin = 65,
Lmax = 75, β = 0, the planning horizon is 24 hours. During the period under review, 3 trains
arrive at the station at 7:00, 9:00 and 10:00, respectively. Fig. 3.1 shows data on the size of
blocks in each arriving train and on blocks located in the storages at the initial time moment.
Blocks of different destinations have different colours.

Using CAP strategy we form a train at 7:00 (see fig. 3.2). But it turns out to be more
profitable to wait for the arrival of the second train, then send two trains at once (see fig. 3.3).
Indeed, in the case of CAP the first train contains fewer cars and block of 10 cars remains
unshipped until the end of the planning period. The total car-hours at the station for CAP is
equal to 3035, while the optimal solution gives us 3015 car-hours.

7:00

9:00

10:00

55 10

30 20 20

35 40

Undelivered cars: 20 10 20

Fig. 3.2. CAP strategy

The purpose of this article is to evaluate the effect of implementing a planning method
that uses more information about trains arriving at the station than is done in practice. In fact,

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



36 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

7:00

9:00

10:00

55 10 1030 20 20

35 40

Undelivered cars: 20 20

Fig. 3.3. Optimal strategy

if we use information about only one moment of train arrival, we apply CAP: if it is possible
to form trains at this time moment, then a train with the maximum possible number of cars
is formed. Applying this strategy at every moment of T , we get some feasible solution to the
problem (P1). The task arises of choosing a suitable planning horizon that would improve
the goal function compared to the CAP, but would not require too much time to solve the
problem.

4. SOLVING PROBLEMS OF SMALL DIMENSIONS

In this section we analyse and compare the behaviour of CAP and an exact method of solving
problem (P1) using small-dimensional test instances. In this experiment, we vary values of
parameters m and n to determine how the gain from using the exact method changes.

During computational experiments, CAP was compared with the optimization solver IBM
ILOG CPLEX 22.1.0.0. [12]. In CAP, to make a decision at each point in time about which
train should be sent, we also used CPLEX to solve the problem (P1) with |T | = 1.

The planning horizon is 24 hours, lmin = Lmin = 61, Lmax = 75, β = 0. The datasets
generated and analysed during the current study are available from the corresponding author
on reasonable request. The running time of CAP and the CPLEX solver was limited to 10
min., because, in practice, the decision-making system should work quickly. In Table 4.1
the results of solving the randomly generated problems are given. The following notations
are used in the table: ”m” is the number of incoming trains, ”n” is the number of train
destinations generated at the given station, ”CAP” is the value of the objective function
obtained when applying CAP, ”CPLEX” is the value of the objective function obtained as a
result of CPLEX operation for 10 minutes, ”GAPCPLEX” is the gap between the best integer
solution and the best bound in CPLEX after 10 minutes of work (by default, the gap equal to
0.01% is set as a stop criterion in CPLEX), ”Dif” is the percentage of improvement in the
value of the objective function when using CPLEX for problem (P1). The calculations were
performed on a personal computer (Intel Core i7-7700K, 4.2 GHz, 32.0 GB).

As can be seen from the table, using the exact solution method gives a win in all
cases, with the exception of instances of very small dimensions. It is also worth noting that
the winning percentage varies depending on number of train destinations generated at the
given station. In problems with m < 30, the smaller the value of n, the greater the winning
percentage. This can be explained by the fact that the fewer the number of train destinations,
the more likely it is that new cars of given destination will arrive in the near future, and
therefore it is more profitable to wait for these cars.

It can also be noted that starting from m = 25 CPLEX has not found a guaranteed exact
solution in many cases. As the dimension of the problem increases, the GAP will increase.
So when running the test example at m = 140, n = 70 after 10 minutes of CPLEX operation,

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



PROBLEM OF DYNAMIC REGULATION OF TRAIN FORMATION 37

Table 4.1. Results of comparing CAP and the exact method on small-dimensional instances.

m n CAP CPLEX GAPCPLEX Dif
5 2 5903 5865 0,01% 0,66%
5 3 6140 6140 0,01% 0,00%
5 4 6288 6288 0,01% 0,00%

10 2 11146 10978 0,01% 1,50%
10 5 11584 11565 0,01% 0,16%
10 8 14421 14400 0,01% 0,15%
15 5 14514 14167 0,01% 2,39%
15 7 17614 17394 0,01% 1,25%
15 10 22869 22738 0,01% 0,57%
20 5 17861 17693 0,01% 0,94%
20 10 20341 20242 0,01% 0,49%
20 15 31260 31201 0,01% 0,19%
25 5 20882 19753 1,40% 5,41%
25 10 26423 25442 2,36% 3,71%
25 15 30402 29590 0,45% 2,67%
25 20 35303 34870 0,01% 1,23%
30 5 26646 26375 3,31% 1,02%
30 10 34299 33836 0,43% 1,35%
30 15 35486 35243 0,01% 0,69%
30 20 40439 40431 0,01% 0,02%
40 5 34350 34185 2,37% 0,48%
40 10 40586 40566 2,89% 0,05%
40 20 47524 47467 1,42% 0,12%
40 30 53888 53780 0,11% 0,20%

we got GAP = 95.9% and the value of the objective function which is significantly worse
than when using CAP. That is why the next section discusses reducing the planning horizon,
i.e. considering fewer arriving trains for solving high-dimensional problems.

5. SOLVING HIGH-DIMENSIONAL PROBLEMS

As we noted above, the exact solution method is not applicable for problems with a large
number of arriving trains on the planning horizon. However, in practice, some marshalling
yards of Russian railways (for example, Sverdlovsk) operate with up to 8000 cars, i.e. with
more than 130 arriving freight trains per day and form new trains in almost 70 destinations.
One of the approaches to planning at stations of this size is to use less information about
incoming trains, that is, to reduce the planning horizon of the problem.

In our experiment, we examined randomly generated high-dimensional problems. To
solve them, we first used CAP. Next, we used the following approach. Let ν be the number of
train arrival moments that we take into account when planning. The problem (P1) was solved
for T = {t1, . . . , tν}. If in the received schedule some blocks and locomotives were sent, they
were removed from the input data, and then the problem was solved with T = {tν+1, . . . , t2ν}
and so on. Since the size of ν strongly affects the complexity and time of solving the problem,
we have considered those options for ν that allow us to solve the general problem (P1) in
less than 10 minutes. As a result, the values 2, 3, 4, 5, 6 were considered for ν. Note that
ν = 1 coincides with CAP. The test results are shown in the table 5.2. The cells of the table
show the values of the objective function at different values of ν. The best values of the
objective function for each example are highlighted in gray. Dif here shows the maximum
improvement in the value of the objective function relative to the value obtained by CAP.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



38 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

We can see from the table that it cannot be argued that increasing the planning horizon
necessarily improves the final value of the target function per day. For example, the algorithm
with ν = 5 shows a worse result than with ν = 4. The largest number of minimum values of
the objective function is obtained at ν = 6. However, in many other cases, the value of the
function at ν = 6 is worse than when using CAP. Note also that the spread of the values of
the objective function when using 6 variants does not exceed 1%, except the instance with
m = 50, n = 10.

Thus, it can be argued that in high-dimensional problems the exact method of solving the
problem (P1), which takes into account all trains arriving per day, is not applicable, since it
requires too much time. Besides, considering additional 1, ...,5 trains arriving at the station
does not give a gain in the value of the objective function by more than 1%, while an increase
in the number of trains under consideration does not necessarily lead to a decrease in car-
hours.

The question remains how far the solution obtained by CAP is from the optimal one. A
partial answer to this question will be given in the next section, where a special case of the
problem will be considered.

Table 5.2. Solving high-dimensional instances.

m n CAP ν = 2 ν = 3 ν = 4 ν = 5 ν = 6 Dif
50 10 52215 52478 50686 50865 51193 50060 4,13%
60 10 60947 61236 60932 60817 60928 61146 0,21%
70 10 63682 63787 63911 63609 63858 64071 0,11%
80 10 74505 74526 74265 74503 74442 73932 0,77%
90 10 79333 79063 78925 79434 79369 78792 0,68%

100 10 87419 87482 88023 87700 87684 88006 0,00%
110 10 97006 96985 97080 96575 96715 96572 0,45%
120 10 108222 108289 108266 108153 108344 108508 0,06%
130 10 121505 121650 121368 121266 121665 121521 0,20%
140 10 126714 127093 126214 126998 126683 126627 0,39%
50 20 51584 51609 51600 52009 51699 52041 0,00%
60 20 63448 63377 63351 63222 63548 63298 0,36%
70 20 74696 74687 74612 74013 74351 74656 0,91%
80 20 80400 80427 80372 80643 80381 80357 0,05%
90 20 85539 85464 85570 85704 85805 85591 0,09%

100 20 99386 99264 99420 99389 99356 99431 0,12%
110 20 110324 110354 110265 110235 110215 110418 0,10%
120 20 113795 113817 113510 113595 113677 113382 0,36%
130 20 120042 119951 120382 120157 120180 120192 0,08%
140 20 126933 127063 127258 127576 127277 126875 0,05%
50 25 55104 55087 54850 55138 55094 55096 0,46%
60 30 73218 73232 73170 73202 73188 73217 0,07%
70 35 83956 83907 83775 83895 83793 83788 0,22%
80 40 93114 93011 93026 92813 93295 92868 0,32%
90 45 105207 105079 105125 105038 105086 104977 0,22%

100 50 120615 120638 120565 120419 120436 120465 0,16%
110 55 130184 129782 129778 129948 129917 129558 0,48%
120 60 152286 152290 152265 152207 152250 152005 0,18%
130 65 153508 153507 153688 153961 153359 153190 0,21%
140 70 169040 169138 169043 169215 168975 168997 0,04%

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



PROBLEM OF DYNAMIC REGULATION OF TRAIN FORMATION 39

6. SPECIAL CASE OF THE PROBLEM

We will also consider a simplified formulation of the problem, where blocks can be separated,
i.e. cars of the same block can be sent by different trains. Obviously, the possibility of splitting
blocks increases the bureaucratic difficulties of tracking cars, but reduces the load of stations
and the number of car-hours.

Denote by αik, i ∈ I ∪ {0}, k ∈ K, the number of cars that arrive at the station at time
moment ti for further shipment in the direction k, i.e.

αik =
∑

g∈Gk: τg=ti

lg, i ∈ I ∪ {0}, k ∈ K.

We introduce the following decision variables:

• integer variable ỹik, i ∈ I , k ∈ K, equals to the number of trains formed at time moment
ti + β for destination k.

• integer variable x̃ik, i ∈ I , k ∈ K, is equal to the number of cars departing from the
station at time moment ti + β to destination k.

The constraints of the problem take the following form. At any given time moment, we cannot
send more cars than are left at the station for a given destination:

x̃ik ≤
i∑

j=0

αjk −
i−1∑
j=1

x̃jk ∀i ∈ I, ∀k ∈ K. (6.9)

We cannot use more locomotives than we have at the station:∑
k∈K

ỹik ≤ r0 + i−
∑
k∈K

i−1∑
j=1

ỹjk ∀i ∈ I. (6.10)

The restriction on the number of cars in the trains can be written as follows:

Lminỹik ≤ x̃ik ≤ Lmaxỹik ∀i ∈ I, ∀k ∈ K. (6.11)

The integer condition is
x̃ik, ỹik ∈ N0 ∀i ∈ I, ∀k ∈ K, (6.12)

where N0 is the set of non-negative integers. The objective of the problem is to minimise the
following function:∑

i∈I

∑
k∈K

x̃ik(ti + β) + (
m∑
i=0

∑
k∈K

αik −
∑
i∈I

∑
k∈K

x̃ik)tmax → min . (6.13)

We denote problem (6.9)-(6.13) by (P2). Unlike problem (P1) with binary variables, problem
(P2) has integer variables, but the number of variables is equal to 2|I||K|, that is significantly
fewer than in (P1). It should be noted that the optimal value of the objective function of the
problem (P2) is a lower bound for the problem (P1). In addition, the integer condition (6.12)
can be replaced with a more lenient condition

x̃ik ≥ 0, ỹik ∈ N0 ∀i ∈ I, ∀k ∈ K. (6.14)

Indeed, denote by (P3) the problem (6.9)-(6.11), (6.14), (6.13), that is problem (P2) without
requirements for the integers of variables x̃ik, i ∈ I , k ∈ K. We can use (P2) instead of(P3)
due to the following theorem:

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



40 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

Theorem 6.1:
In any optimal solution of problem (P3) variables x̃ik, i ∈ I , k ∈ K, take integer values.

Proof
Let’s assume the opposite. Consider an optimal solution x̃∗

ik, ỹ
∗
ik, i ∈ I, k ∈ K. Choose an

arbitrary k̄ ∈ K for which there exists i ∈ I such that x̃∗
ik̄

is fractional. Denote by Ī(k̄) ⊂ I

the set of all such indexes i. If this set consist of one index, i.e. Ī(k̄) = {̄i}, then we change
x̃∗
īk̄

by [x̃∗
īk̄
] + 1, where [x] is the integer part of the number x. It is easy to see that constraints

(6.9) and (6.11) are fulfilled for the new value of x̃∗
īk̄

. At the same time, the value of the goal
function is strictly better than the previous one.

Now suppose that w = |Ī| > 1. Let’s arrange all indexes of |Ī| in increasing order:

Ī = {i1, i2, . . . , iw}, i1 < i2 < . . . < iw.

Let ε1, . . . , εw be fractional parts of the corresponding optimal values of the variables
x̃∗
i1k̄

, . . . , x̃∗
iwk̄

.
If ε2 + . . .+ εm ≤ 1− ε1 we can change x̃∗

i1k̄
by [x̃∗

i1k̄
] + 1 and x̃∗

ij k̄
— by [x̃∗

ij k̄
] for

j ∈ {2, . . . , jw} without violating constraints (6.9), (6.11) and with strict improvement of
the value of the goal function. In the case of ε2 + . . .+ εm > 1− ε1 we denote by j̄ the
maximal value of j for which ε2 + . . .+ εj ≤ 1− ε1. Then we can change x̃∗

i1k̄
by [x̃∗

i1k̄
] + 1

and x̃∗
ij k̄

— by [x̃∗
ij k̄
] for j ∈ {2, . . . , j̄} by improving the value of the goal function. Applying

the same approach for the remaining indexes ij̄+1, . . . , iw the required number of times we
will get solution with integer values of x̃∗

ik̄
for all i ∈ I . Repeating this procedure for all

k ∈ K for which there are fractional values of x̃∗
ik, we will get a feasible solution with integer

x̃∗
ik, i ∈ I, k ∈ K, and better goal function value, which proves the theorem.

It is worth noting that the CAP technique is also simplified in the case when it is possible
to divide blocks. At each step, there is no need to solve a combinatorial optimization problem
of the Knapsack type to make up the train with the largest number of cars. It is enough to
choose the destination for which the maximum number of cars is located at the station.

We used the same test data for testing the model (P3) as for (P1), but it was assumed
that the blocks could be divided. The results are presented in table 6.3. The same notation
was used as in table 4.1, except for a new column called ”Gap1,2”, in which we have a
percentage decrease in the value of the objective function obtained using CPLEX for problem
(P3) compared to the best found solution to the problem (P1) (see table 5.2). Values Gap1,2
and GAPCPLEX together allow us to estimate the error of solving the problem (P1). So, for
the considered test problems, it can be argued that the error of the solutions found for (P1) is
guaranteed not to be very large. At the same time, it can be seen from the table that the exact
method of solving the problem (P3) allows us to find a solution with acceptable accuracy for
high-dimensional problems in 10 minutes.

7. CONCLUSION

In the paper, we proposed and investigated two models of dynamic train formation at a
marshalling yard with divisible and indivisible train blocks, respectively. For the first model,
computational experiments have shown that in problems of small dimension (a small number
of incoming trains per day and a small number of train destinations), it is possible to find an
exact solution to the problem of minimizing car-hours at the station per day in an acceptable
time. This is impossible for high-dimensional problems. However at the same time, the trains
formation without taking into account the trains coming later in such problems gives an
acceptable result relative to the found lower bounds. Moreover, increasing information about

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



PROBLEM OF DYNAMIC REGULATION OF TRAIN FORMATION 41

Table 6.3. Solving the special case.

m n CAP CPLEX GAPCPLEX Dif Gap1,2
50 10 50272 49046 0,01% 2,44% 2,03%
60 10 60490 59586 0,01% 1,49% 2,02%
70 10 63422 62210 0,01% 1,91% 2,20%
80 10 73466 72858 0,49% 0,83% 1,45%
90 10 78303 77259 0,29% 1,33% 1,95%

100 10 86858 85753 0,27% 1,27% 1,91%
110 10 96408 95057 0,47% 1,40% 1,57%
120 10 107656 106307 0,61% 1,25% 1,71%
130 10 120075 118958 0,55% 0,93% 1,90%
140 10 125843 124201 0,37% 1,30% 1,59%
50 20 50619 49591 0,01% 2,03% 3,86%
60 20 61268 60517 0,01% 1,23% 4,28%
70 20 73438 72211 0,01% 1,67% 2,44%
80 20 79151 78185 0,15% 1,22% 2,70%
90 20 83164 81306 0,32% 2,23% 4,86%

100 20 97922 96880 0,36% 1,06% 2,40%
110 20 107770 106505 0,53% 1,17% 3,37%
120 20 112236 110087 0,66% 1,91% 2,91%
130 20 118159 116098 0,71% 1,74% 3,21%
140 20 124708 122654 1,22% 1,65% 3,33%
50 25 52875 52308 0,01% 1,07% 4,63%
60 30 72030 71487 0,01% 0,75% 2,30%
70 35 83002 82538 0,01% 0,56% 1,48%
80 40 90429 89742 0,01% 0,76% 3,31%
90 45 102158 101367 0,01% 0,77% 3,44%

100 50 118017 117136 0,01% 0,75% 2,73%
110 55 125432 123572 0,01% 1,48% 4,62%
120 60 146170 143839 0,17% 1,59% 5,37%
130 65 148858 147924 0,06% 0,63% 3,44%
140 70 164399 163193 0,03% 0,73% 3,42%

incoming cars of 2-5 trains in advance does not give a tangible benefit. If we talk about the
model for the case of divisible cars blocks, then this problem can be solved with high accuracy
for any dimensions that have a practical application.

REFERENCES

1. Yaghini, M., Mirghavami, M., & Zare Andaryan, A. (2021) A mathematical formulation
and an lp-based neighborhood search matheuristic solution method for the integrated
train blocking and shipment path problem. Networks, 78, 523–542.

2. Cordeau, J.-F., Toth, P., & Vigo, D. (1998) A survey of optimization models for train
routing and scheduling. Transportation science, 32, 380–404.

3. Yaghini, M., Momeni, M., & Sarmadi, M. (2014) Solving train formation problem
using simulated annealing algorithm in a simplex framework. Journal of Advanced
Transportation, 48, 402–416.

4. Zhang, X., Kang, L., Liu, W., & Yao, Y. (2016) Solving train formation plan problem
in freight transportation corridors. In 2016 International Conference on Engineering
Science and Management, 102–104, Atlantis Press.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)



42 E. MUSATOVA, A. LAZAREV, A. OSMININ, A. BAUSHEV

5. Lin, B., Zhao, Y., Lin, R., & Liu, C. (2021) Integrating traffic routing optimization
and train formation plan using simulated annealing algorithm. Applied Mathematical
Modelling, 93, 811–830.

6. Zhao, Y. & Lin, B. (2019) The multi-shipment train formation optimization problem
along the ordered rail stations based on collection delay. IEEE Access, 7, 75935–75948.

7. Ahuja, R. K., Jha, K. C., & Liu, J. (2007) Solving real-life railroad blocking problems.
Interfaces, 37, 404–419.

8. Xiao, J. & Lin, B. (2016) Comprehensive optimization of the one-block and two-block
train formation plan. Journal of Rail Transport Planning & Management, 6, 218–236.

9. Barnhart, C., Jin, H., & Vance, P. H. (2000) Railroad blocking: A network design
application. Operations research, 48, 603–614.

10. Xiao, J., Pachl, J., Lin, B., & Wang, J. (2018) Solving the block-to-train assignment
problem using the heuristic approach based on the genetic algorithm and tabu search.
Transportation Research Part B: Methodological, 108, 148–171.

11. Kellerer, H., Pferschy, U., & Pisinger, D. (2004) Knapsack Problems. Springer-Verlag,
Berlin, Heidelberg.

12. (2024, December 06), Ibm ilog cplex optimization studio. Available
https://www.ibm.com/products/ilog-cplex-optimization-studio.

Copyright © 2024 ASSA. Adv Syst Sci Appl (2024)


	Introduction
	Problem description
	Mathematical statement
	Solving problems of small dimensions
	Solving high-dimensional problems
	Special case of the problem
	Conclusion