421
2 PARTITIONING THE TRAIN TRIP IN ELEMENTAL SEGMENTS
The idea is to divide each trip in elemental sub-trips, in order to generate a list of possible
points or locations where the crew replacement can be made. This partition will be used for
the crew assignment to the elemental sub-trips, in a second model. Let L be the set of possible
locations of change points where the crews can be replaced and K
L
t
K ⊆
all the existing locations along the trajectory of the train t. Each train has a well defined itinerary, that is to say,
we know exactly the time of each train at a given location. Furthermore, trains are classified
in two types: rotative, whose initial and final point on the trajectory are the same, i.e., as a
cycle, and no rotative, whose initial and final point on the trajectory are different. The set of
rotative trains is denote by T c and the no rotative trains T nc , thus,
T
c
n
T T T T c
∪ . Moreover we
know the following set of parameters:
k t,l : Time of train (trip) t at location l ∈ K t
d
t
: Total duration of train t
d l l
d l
t
, : Travel time of train t, from location l to ll
tr l,b : Travel time for driving a crew from from location l to camb b
d bl : Travel time to drive a crew from location l to the nearest camp
The itinerary of a train induces an order in the set of locations, so we say l ll k
l
k
t
t
ll k k
l
l
t
k k ll
<
ll k
l
t
ll k
l l
l
if ,
,
l
t .
For rotative trains this order doesn’t give much information, but for no rotative is really
important define it to write its constraints. The binary decision variables are defined below:
z
t
l K
t l
t
K
, =
∈
⎧
⎨
⎧ ⎧
⎩
⎨ ⎨
1
0
if train t a e a c ew ep ace e t at ocatio
if not
v
l ll K
l l
l ll
t
t
K
,
,
=
1 if locations
are consecutive replacement points for o o
f f f f the train
if not
t
0
⎧
⎨
⎧ ⎧
⎩
⎨ ⎨
In this first model we look for locations that are comparatively near to all bases, in order to
minimize the total travel time in cars. The set of constraints to be considered for this problem
is described below.
To force a no rotative train to start in a given location l initial
i i
L
o
l
( )
K t
K
, ending at location l
final f f
L
d
l l
( )
K t
K
we impose:
l K l l
l l
t
nc
t o
K l t
o
l
v
t
l l
t
t
T n
K l
t
K K l
∑
∀ ∈
,
,
(1)
l K l l
l l
t
nc
t
K
d
l t
d
l t
v
t
l l
t
t
T n
K l
t
K K
∑
∀ ∈
:
,
,
(2)
And to connect variables v and z we impose, which means that if train t stops at location l
then the train arrives to and leaves that location:
ll K l ll
l ll
t
t l
t
t
v
z
l ll
t
t
l K t
∈
<
K l
K K
∑ = ∀
t l
z
∈
∀
T
{ }
d
t
l d
:
,
,
ll
t ,
,
t T
∀ ∀ T
(3)
ll K ll l
ll l
t
t l
t
t
v
z
ll l
t
t
l K t
∈K ll
K K
∑ = ∀
t l
z
∈
∀
T
{ }
o
t
l o
:
,
,
l
t ,
,
t T
∀ ∀ T
(4)
For a rotative train, past constrains turn in:
ll K l ll
ll K ll l
ll l
t
c
t
t
t
ll
ll
v ll l
t
T
l K t
∈
≠
K l
t
K l
K
∈
≠
K ll
t
K
∑
∑
l ll
t
t l
v
z
l ll
t
l
z
∀ ∈
t
∈
l
ll
t
, ,
c
t T c
∈
t
(5)
The number of daily work hours for crews limited by a given parameter JE t :
v d
J
t
l ll K
l
l ll l l
l ll l l
d l
t
t
t
l
,
,
ll l
t t T
,
ll l
t
ll K
l l
≤
∀
JE t
E , ∈ ∀
T, T T
K l
,
K t
K
(6)
2 PARTITIONING THE TRAIN TRIP IN ELEMENTAL SEGMENTS
The idea is to divide each trip in elemental sub-trips, in order to generate a list of possible
points or locations where the crew replacement can be made. This partition will be used for
the crew assignment to the elemental sub-trips, in a second model. Let L be the set of possible
locations of change points where the crews can be replaced and K
L
t
K ⊆
all the existing locations along the trajectory of the train t. Each train has a well defined itinerary, that is to say,
we know exactly the time of each train at a given location. Furthermore, trains are classified
in two types: rotative, whose initial and final point on the trajectory are the same, i.e., as a
cycle, and no rotative, whose initial and final point on the trajectory are different. The set of
rotative trains is denote by T c and the no rotative trains T nc , thus,
T
c
n
T T T T c
∪ . Moreover we
know the following set of parameters:
k t,l : Time of train (trip) t at location l ∈ K t
d
t
: Total duration of train t
d l l
d l
t
, : Travel time of train t, from location l to ll
tr l,b : Travel time for driving a crew from from location l to camb b
d bl : Travel time to drive a crew from location l to the nearest camp
The itinerary of a train induces an order in the set of locations, so we say l ll k
l
k
t
t
ll k k
l
l
t
k k ll
<
ll k
l
t
ll k
l l
l
if ,
,
l
t .
For rotative trains this order doesn’t give much information, but for no rotative is really
important define it to write its constraints. The binary decision variables are defined below:
z
t
l K
t l
t
K
, =
∈
⎧
⎨
⎧ ⎧
⎩
⎨ ⎨
1
0
if train t a e a c ew ep ace e t at ocatio
if not
v
l ll K
l l
l ll
t
t
K
,
,
=
1 if locations
are consecutive replacement points for o o
f f f f the train
if not
t
0
⎧
⎨
⎧ ⎧
⎩
⎨ ⎨
In this first model we look for locations that are comparatively near to all bases, in order to
minimize the total travel time in cars. The set of constraints to be considered for this problem
is described below.
To force a no rotative train to start in a given location l initial
i i
L
o
l
( )
K t
K
, ending at location l
final f f
L
d
l l
( )
K t
K
we impose:
l K l l
l l
t
nc
t o
K l t
o
l
v
t
l l
t
t
T n
K l
t
K K l
∑
∀ ∈
,
,
(1)
l K l l
l l
t
nc
t
K
d
l t
d
l t
v
t
l l
t
t
T n
K l
t
K K
∑
∀ ∈
:
,
,
(2)
And to connect variables v and z we impose, which means that if train t stops at location l
then the train arrives to and leaves that location:
ll K l ll
l ll
t
t l
t
t
v
z
l ll
t
t
l K t
∈
<
K l
K K
∑ = ∀
t l
z
∈
∀
T
{ }
d
t
l d
:
,
,
ll
t ,
,
t T
∀ ∀ T
(3)
ll K ll l
ll l
t
t l
t
t
v
z
ll l
t
t
l K t
∈K ll
K K
∑ = ∀
t l
z
∈
∀
T
{ }
o
t
l o
:
,
,
l
t ,
,
t T
∀ ∀ T
(4)
For a rotative train, past constrains turn in:
ll K l ll
ll K ll l
ll l
t
c
t
t
t
ll
ll
v ll l
t
T
l K t
∈
≠
K l
t
K l
K
∈
≠
K ll
t
K
∑
∑
l ll
t
t l
v
z
l ll
t
l
z
∀ ∈
t
∈
l
ll
t
, ,
c
t T c
∈
t
(5)
The number of daily work hours for crews limited by a given parameter JE t :
v d
J
t
l ll K
l
l ll l l
l ll l l
d l
t
t
t
l
,
,
ll l
t t T
,
ll l
t
ll K
l l
≤
∀
JE t
E , ∈ ∀
T, T T
K l
,
K t
K
(6)