422
In order to control the number of sub-trips for each train, we include the next constraint
in case of no rotative trains:
l K
t l
t
t
nc
t
K
z
d
JE t
k
t T n
∑ ≤
⎡
⎣
⎢
⎡ ⎡
⎣ ⎣
⎤
⎦
⎥
⎤ ⎤
⎦ ⎦
+ k
∈
,
,
(7)
and in case of rotative trains:
d
JE
d
JE
k
t T
t
t
E
l K
t l
t
t
E
c
T T
t
K
≤
z t l
≤
⎡
⎣
⎢
⎡ ⎡
⎣ ⎣
⎤
⎦
⎥
⎤ ⎤
⎦ ⎦
+ k
∈
∑ ,
,
(8)
where k ≥ 1 because the value
d
JE
t
t
E
⎡
⎣
⎡ ⎡ ⎤
⎦
⎤ ⎤ + 1 represents the minimal number of sub-trips that
fulfill the precedent constraints. This is necessary because the problem may have multiple
solutions and we want to keep the one that has a minimal points of crew replacements. In
principle, the value k = 1 is good if we only consider past constraints, but if we add some
additional, as we will show below, the value k = 1 could generate infeasibility.
For operational reasons, we need to impose an additional constraint, saying that some
changes of crews must be made at a certain prefixed zones (subset of locations). Let
L i
nz
i ⊆
=
L i
,
,
i
..,
1
the zones where a crew replacement is mandatory. Then,
l K Zc
t l
t
i
t
i
K K Zc
z t l
i
n K t Zc
∑ ≥ ∀
≠ ∅
∩ Z Z Z Z
∩ Z Z
,
,
,
t
,.., ,
1
t T i
∀ ∈
=
T i
t ∈ T
(9)
In the context of our specific application, those zones are determined by the capability
of the operators (crews) to drive in each geographic; in other words, not all the drivers are
authorized to drive train in every zones. The zones (actually, there are three, but this is a
parameter of the model) have well defined intersections to ensure feasibility, because changes
of crews can be done in the intersections to allow train crossing from a zone to another. The
zones are represented by the sets Zc in the model.
Concerning the choice of the objective function, we firstly propose to minimize the total
distance between the change points and all rest camp for crews:
min
,
,
t T l K b B
l b
, t l
,
t
K K
tr l z
T l
∑ ∑ ∑
(10)
Another option is to choose locations at minimal distance to nearest camp:
min
,
t T l K
l t l
t
K K
db l z
T l
∑ ∑
(11)
The result of this model generate an efficient choice of locations for crews changes, as near
as possible to the rest camps for crews. In the next section we will introduce a model to generate an optimal crew assignment for the whole set of trains along one week period.
3 THE CREW ASSIGNMENT MODEL
Let us consider a set of M crews (in our specific application, each crew is composed by two
operators) and the set V containing all the sub-trips to be fulfilled, defined by the previous
model. All those sub-trips have as starting and final stop, two consecutive locations for crew
change (in fact, these are points of the timetable for each train). Each one is determined by
the variables v l ll
t
,
having value 1. We also denote D v the set of days in which the trip v runs
(typically D v = {1, ...,7}).
The idea of this model is to connect a sequence of compatible elemental trips to be fulfilled
by each specific crew. For this, we need to add two artificial trips v 0 and v f , to connect with the
In order to control the number of sub-trips for each train, we include the next constraint
in case of no rotative trains:
l K
t l
t
t
nc
t
K
z
d
JE t
k
t T n
∑ ≤
⎡
⎣
⎢
⎡ ⎡
⎣ ⎣
⎤
⎦
⎥
⎤ ⎤
⎦ ⎦
+ k
∈
,
,
(7)
and in case of rotative trains:
d
JE
d
JE
k
t T
t
t
E
l K
t l
t
t
E
c
T T
t
K
≤
z t l
≤
⎡
⎣
⎢
⎡ ⎡
⎣ ⎣
⎤
⎦
⎥
⎤ ⎤
⎦ ⎦
+ k
∈
∑ ,
,
(8)
where k ≥ 1 because the value
d
JE
t
t
E
⎡
⎣
⎡ ⎡ ⎤
⎦
⎤ ⎤ + 1 represents the minimal number of sub-trips that
fulfill the precedent constraints. This is necessary because the problem may have multiple
solutions and we want to keep the one that has a minimal points of crew replacements. In
principle, the value k = 1 is good if we only consider past constraints, but if we add some
additional, as we will show below, the value k = 1 could generate infeasibility.
For operational reasons, we need to impose an additional constraint, saying that some
changes of crews must be made at a certain prefixed zones (subset of locations). Let
L i
nz
i ⊆
=
L i
,
,
i
..,
1
the zones where a crew replacement is mandatory. Then,
l K Zc
t l
t
i
t
i
K K Zc
z t l
i
n K t Zc
∑ ≥ ∀
≠ ∅
∩ Z Z Z Z
∩ Z Z
,
,
,
t
,.., ,
1
t T i
∀ ∈
=
T i
t ∈ T
(9)
In the context of our specific application, those zones are determined by the capability
of the operators (crews) to drive in each geographic; in other words, not all the drivers are
authorized to drive train in every zones. The zones (actually, there are three, but this is a
parameter of the model) have well defined intersections to ensure feasibility, because changes
of crews can be done in the intersections to allow train crossing from a zone to another. The
zones are represented by the sets Zc in the model.
Concerning the choice of the objective function, we firstly propose to minimize the total
distance between the change points and all rest camp for crews:
min
,
,
t T l K b B
l b
, t l
,
t
K K
tr l z
T l
∑ ∑ ∑
(10)
Another option is to choose locations at minimal distance to nearest camp:
min
,
t T l K
l t l
t
K K
db l z
T l
∑ ∑
(11)
The result of this model generate an efficient choice of locations for crews changes, as near
as possible to the rest camps for crews. In the next section we will introduce a model to generate an optimal crew assignment for the whole set of trains along one week period.
3 THE CREW ASSIGNMENT MODEL
Let us consider a set of M crews (in our specific application, each crew is composed by two
operators) and the set V containing all the sub-trips to be fulfilled, defined by the previous
model. All those sub-trips have as starting and final stop, two consecutive locations for crew
change (in fact, these are points of the timetable for each train). Each one is determined by
the variables v l ll
t
,
having value 1. We also denote D v the set of days in which the trip v runs
(typically D v = {1, ...,7}).
The idea of this model is to connect a sequence of compatible elemental trips to be fulfilled
by each specific crew. For this, we need to add two artificial trips v 0 and v f , to connect with the