Download Microsoft PowerPoint - V\355ctor Parada.ppt [Modo de compatibilidad]

An evolutionary and
constructive approach to
the crew scheduling
problem
R. Elizondo1, V. Parada1,
L. Pradenas2, C. Artigues3
1 University
of Santiago of Chile; Complex Engineering Systems Institute
2 Industrial Engineering Department, University of Concepcion
3 LAAS-CNRS, Toulouse France
TRANSLOG, Viña del Mar, Diciembre de 2009
Problem Description
Data set:
(sk, ek, ok, dk ), denotes starting time, ending time, trip origin and
trip destination
.
Index
Train
Starting
time
Trip Origin
Ending time
Trip destination
1
06
06:55:00
ST2
07:25:25
ST1
2
05
07:10:46
ST1
07:40:32
ST2
3
07
07:14:17
ST1
07:44:03
ST2
4
08
07:17:48
ST2
07:47:34
ST1
5
01
07:20:00
ST2
07:49:46
ST1
6
09
07:21:19
ST1
07:51:05
ST2
7
02
07:24:49
ST2
07:54:35
ST1
8
12
07:24:50
ST1
07:54:36
ST2
9
05
07:28:21
ST1
07:58:07
ST2
10
03
07:29:38
ST2
07:59:24
ST3
…
…
…
…
…
Fragment of a Train movement scheduling
TRANSLOG, Viña del Mar, Diciembre de 2009
…
Problem Description
Objective:
•Generate a set of duties from a trip timetable while
minimizing both the idle time and the number of
duties.
Constraints:
•Relief facilities
•Maximum conduction time
•Continuous conduction time
•Meal breaks
•Work shifts
•Conductors as passengers
•Routes
•Conduction interruptions
TRANSLOG, Viña del Mar, Diciembre de 2009
Problem Description
♦ Schematic Representation of the Problem
TRANSLOG, Viña del Mar, Diciembre de 2009
Related Work
Vehicle movement
planning
Crew Scheduling
Crew Rostering
TRANSLOG, Viña del Mar, Diciembre de 2009
Related Work
Portuguese and Dutch train systems; Artificial intelligence techniques
- E. Morgado and J. Martins (1992; 1998)
Italian train system ; Branch and cut
A. Caprara, M. Fischetti, P. Toth, D. Vigo and P. Guida (1997; 1999)
Australian train system; Binary Programming
Ernst, Jiang, Krishnamoorthy, Nott and Sier (2001)
Lisbon underground system; Constructive Algorithm
- L. Cavique et al. (1999)
Singapoure MRT and Hong Kong ; Heuristic method
K. Chew, J.Pang, Q. Liu, J. Ou and C. Teo (2001)
German Railway system; Heuristic column generation-based procedures
- L. Bengtsson, T. Galia, T. Gustafson, C. Hjorring and N. Kohl (2004)
Portuguese bus system; GA and TS
- Lourenco et al. l (2001) and Dias, de Sousa, & Cunha (2002)
TRANSLOG, Viña del Mar, Diciembre de 2009
Crew Scheduling Problem
Dutch railway network; Column generation
D. Pottho, D. Huisman, G. Desaulniers, (2008)
Netherlands Railways, Heuristic Method
E. Abbink, J. van’t Wout, D. Huisman (2007)
Lisbon underground system; LS and TS
M. Gomes, L. Cavique, I. Themido (2006)
The train driver recovery problem—A set partitioning based model and solution method
- N. Rezanovaa, D. Ryan (2010)
TRANSLOG, Viña del Mar, Diciembre de 2009
Constructive-Evolutive Method
• A constructive method can be represented as an
And/Or graph.
• To search on this graph: A*, AO*, AAO*.
1
2
3
4
f(n) = g(n) + h(n)
5
6
7
8
9
• Combinatorial Explotion
• Evolutive Estrategy.
TRANSLOG, Viña del Mar, Diciembre de 2009
Constructive-Evolutive Method
1
2
5
3
6
7
9
Trips
4
8
Partial Duties
Feasible Solution
Feasible
Operator
TRANSLOG, Viña del Mar, Diciembre de 2009
Constructive-Evolutive Method
We consider 4 sets:
• A Genetic Algorithm population (A). In each generation we
update the population by creating constructions each time
larger and more complex. (A)
• Best obtained constructions. (B)
• Basic elements. (E)
• Solutions generated by crossover (C)
Selection by means of roulette
TRANSLOG, Viña del Mar, Diciembre de 2009
Constructive-Evolutive Method
TRANSLOG, Viña del Mar, Diciembre de 2009
Constructive-Evolutive Method
TRANSLOG, Viña del Mar, Diciembre de 2009
Problem Modelling
Crossover and mutation: Constructive
Parent 2
Parent 1
2
1
3
4
7
6
9
5
Offspring 1
Offspring 2
Stopping criterion:
All trips are inserted in a solution
TRANSLOG, Viña del Mar, Diciembre de 2009
8
Problem Modelling
Evaluation Function:
Total idle time:
Construction Cost:
Heuristic Function:
TRANSLOG, Viña del Mar, Diciembre de 2009
Greedy method.
Constructive Algorithm:
1
2
3
4
5
6
7
8
9
Duty 1
Duty 2
Duty 3
TRANSLOG, Viña del Mar, Diciembre de 2009
Greedy method.
TRANSLOG, Viña del Mar, Diciembre de 2009
Tabu search
TRANSLOG, Viña del Mar, Diciembre de 2009
Convergence of C-E
TRANSLOG, Viña del Mar, Diciembre de 2009
Results comparison
TRANSLOG, Viña del Mar, Diciembre de 2009
Conclusions
♦ In 7 out of 10 instances CE found the lowest number of
duties
♦ The lowest computing time correspond to the Greedy
Algorithm
♦ Rostering Constrains can be easily considered in this
approach
TRANSLOG, Viña del Mar, Diciembre de 2009