Train Platforming Problem - Geoinformatics for Intelligent Transportation - page 151

track k, which is expressed by constraint ( 13 ). Constraint ( 14 ) holds for the reverse
order of trains i, .

Constraint ( 15 ) states that y aa
ij

i ′

is 1 if train i is followed by train j at the arrival and
both trains travel on the same in-line.
Constraint ( 16 ) ensures that each train is always dispatched to exactly one
platform track.
The remaining obligatory constraints ( 17 ) ( 22 ) specify the de nition domains of

-

the variables.
This multiple-criteria optimisation problem was solved using the lexicographic
approach, where the objective functions are ranked according to their importance.
In the problem at hand, the first objective function (i.e. to meet the timetable) is

more important that the second one (i.e. to respect track preferences). This ordering
re

ects how decisions are currently made in practice. The solution technique
consists of two steps. In the

fl

first step the problem ( 1 ), ( 3 ) ( 22 ) is solved giving the

-

best value of the weighted sum of deviations f best
1

. Then the constraint

X

c i ð u i þ v i Þ f best ð 18 Þ

1

i 2 U

is added and the model ( 2 ) ( 22 ), ( 24 ) is solved. Because both MIP problems are

hard and the optimal solutions cannot be found within a reasonable time limit, we
decided to implement the local branching heuristic [ 7 ] using the general optimi-
sation software Xpress.

-

3 Case Study

The model was veri ed by using the real data of Prague main station and the

timetable valid for the years 2004/2005. Prague main station is a large station that at
the given time had 7 platforms, 17 platform tracks and 8 arrival or departure line
tracks. According to the timetable 2004/2005, the station dealt with 288 regular
passenger trains per a weekday. We could use any timetable for validation, however
we used the timetable valid for 2004/2005 because we knew that it was done with
some mistakes. We wanted to demonstrate that our model is valid, can detect every
possible con

ict in the timetable and suggest its solution.
Since the model with 288 trains contains 41,279 variables and 595,323 con-
straints, it is not possible to solve it to optimality in a reasonable time. That is why
the decomposition of the problem must be done. The planning period (a day) was
divided into shorter time periods. They were chosen in such a way so that the
morning and evening peak hours were taken as a whole and the rest of the day was
divided into shorter periods with approximately the same number of trains. The
resulting time intervals can be seen in Table 1 .

fl