420
The problem described above needs to be solved over the a long time-span that consider
in-between resting time of the crew members and overall labor regulations. This gives rise
to a very complex instance that involves the partitioning of trips in elemental segments and
efficient assignments of crews, to comply with train trips and labor regulations.
In order to tackle this problem, we used mathematical programming to address the two
main elements of the problem. For this, the problem has been partitioned in two steps.
Firstly, through a linear mixed integer optimization model, every trip is divided in elemental
segments to be served by different crews. Secondly, another optimization model produces the
crew assignment to fulfil all the trips demand. The drivers must have rest periods (in certain
specific camps, whose locations are also decided by the second model.
Figure 1 briefly represents these two problems. The figure illustrates two train trips: Trip 1
goes from West to East and has 9 possible train stops (model selected 3, in black). Trip 2 goes
from East to West, has 8 potential stops, but 3 only have been selected. Selected train-stops
are points where crew exchanges take place. The figure also represents the schedule of one
crew (for simplicity). This crew starts services at Base A (after resting), then it is transported
to the first stop or Trip 1 and drives that train to its second stop where it is replaced (by other
crew, not depicted in the figure) and transported to Base B. After that it starts its resting time
and then starts to work again at Base C, from where it is taken to the first stop of Trip 2,
driving that train up its second stop. At that point, the crew is replaced (again by a crew not
depicted) and taken to Base A to start a resting period.
It is worth noting that the models and algorithms that we describe have been implemented
with a user interface suitable for the remote execution of real instances on a High Performance Computing platform, on an Intel Xeon E5-2660 v2 processor with 10 cores and 48 Gb
of RAM. The transportation company regularly uses this computerized tool for planning
crew schedules and generating efficient assignments for emerging and changing operational
conditions. The optimization models are solved by using Gurobi, coded in AMPL. Many
different real scenarios can be tackled by the user, permitting an efficient management of the
human resources (drivers) and equilibrate workloads between them.
A similar two-steps approach has been proposed by Drexl et al (2013), but unlike to that
paper which focused in an heuristic solution, we focus on integer programming models. A
general introduction to this kind of rostering, vehicle and crew assignment models can be
found in Ceder (2007), and a practical scheduling model for a crew rotation scheme is solved
by Amaya et al (2018), by using a local search optimization strategy. Şahin et al (2011) address
the problem of finding a minimal number of crews to carry out a given set of duties (trips),
based on a sequential algorithmic procedure. The crew capacity planning problem, to minimize the crew size in railways, is also studied by Suyabatmaz et al (2015).
Figure 1. Schematic representation of two train trips and one crew schedule. Train trips and stops are
in solid black. Crew schedule is represented by segmented lines.
Crew drives t rain
Trip 1 -Origin
Crew travels from
1
Crew travels from
base to train-stop ,'
t rain to base
-- Cr; ; ~ ;e~ting - .,....,
.,. __________ ...L.....J"' ... ,
Trip 2Destination
BaseA ',,,
'
' \ Crew is Base C
o _r_:s~i~g- __ Q
Base B
0 Possible train stops
•
Selected train stops
' ' ' ' \ Crew t ravels from
'
'
Crew drives train
\ base to t rain-stop
' ' '
Trip 2 -Origin
The problem described above needs to be solved over the a long time-span that consider
in-between resting time of the crew members and overall labor regulations. This gives rise
to a very complex instance that involves the partitioning of trips in elemental segments and
efficient assignments of crews, to comply with train trips and labor regulations.
In order to tackle this problem, we used mathematical programming to address the two
main elements of the problem. For this, the problem has been partitioned in two steps.
Firstly, through a linear mixed integer optimization model, every trip is divided in elemental
segments to be served by different crews. Secondly, another optimization model produces the
crew assignment to fulfil all the trips demand. The drivers must have rest periods (in certain
specific camps, whose locations are also decided by the second model.
Figure 1 briefly represents these two problems. The figure illustrates two train trips: Trip 1
goes from West to East and has 9 possible train stops (model selected 3, in black). Trip 2 goes
from East to West, has 8 potential stops, but 3 only have been selected. Selected train-stops
are points where crew exchanges take place. The figure also represents the schedule of one
crew (for simplicity). This crew starts services at Base A (after resting), then it is transported
to the first stop or Trip 1 and drives that train to its second stop where it is replaced (by other
crew, not depicted in the figure) and transported to Base B. After that it starts its resting time
and then starts to work again at Base C, from where it is taken to the first stop of Trip 2,
driving that train up its second stop. At that point, the crew is replaced (again by a crew not
depicted) and taken to Base A to start a resting period.
It is worth noting that the models and algorithms that we describe have been implemented
with a user interface suitable for the remote execution of real instances on a High Performance Computing platform, on an Intel Xeon E5-2660 v2 processor with 10 cores and 48 Gb
of RAM. The transportation company regularly uses this computerized tool for planning
crew schedules and generating efficient assignments for emerging and changing operational
conditions. The optimization models are solved by using Gurobi, coded in AMPL. Many
different real scenarios can be tackled by the user, permitting an efficient management of the
human resources (drivers) and equilibrate workloads between them.
A similar two-steps approach has been proposed by Drexl et al (2013), but unlike to that
paper which focused in an heuristic solution, we focus on integer programming models. A
general introduction to this kind of rostering, vehicle and crew assignment models can be
found in Ceder (2007), and a practical scheduling model for a crew rotation scheme is solved
by Amaya et al (2018), by using a local search optimization strategy. Şahin et al (2011) address
the problem of finding a minimal number of crews to carry out a given set of duties (trips),
based on a sequential algorithmic procedure. The crew capacity planning problem, to minimize the crew size in railways, is also studied by Suyabatmaz et al (2015).
Figure 1. Schematic representation of two train trips and one crew schedule. Train trips and stops are
in solid black. Crew schedule is represented by segmented lines.
Crew drives t rain
Trip 1 -Origin
Crew travels from
1
Crew travels from
base to train-stop ,'
t rain to base
-- Cr; ; ~ ;e~ting - .,....,
.,. __________ ...L.....J"' ... ,
Trip 2Destination
BaseA ',,,
'
' \ Crew is Base C
o _r_:s~i~g- __ Q
Base B
0 Possible train stops
•
Selected train stops
' ' ' ' \ Crew t ravels from
'
'
Crew drives train
\ base to t rain-stop
' ' '
Trip 2 -Origin