Aplicación de algoritmos genéticos
híbridos para resolver el problema
de “airline crew scheduling”
Paper: Genetic algorithm based approach for the integrated airline crew-pairing
and rostering problem - Nadia Souai, Jacques Teghem
Rodrigo Ros
Diego Fernández
Meta heurísticas, 2do Cuatrimestre del 2010
Introducción
Introducción al problema
Airline Crew Scheduling Problem
El problema de programar la tripulación de una compañía aérea es un problema difícil y
que deben afrontar todas las compañías. El costo relacionado a los miembros de la
tripulación constituye, después del combustible, el principal costo directo que debe
afrontar las compañías aéreas.
El problema se conoce como Airline Crew Scheduling Problem. Generalmente se divide
este problema en dos problemas menores.
Introducción
Airline crew scheduling
11:30 – 12:30
MEM
JFK
9:00 – 11:00
12:45 – 14:00
ATL
< 4hs – 75%
8:30 – 9:30
4-8hs – 100%
+8hs – 200%
10:00 – 11:00
MIA
Introducción
Airline crew scheduling
11:30 – 12:30
MEM
JFK
9:00 – 11:00
12:45 – 14:00
ATL
8:30 – 9:30
0.75
10:00 – 11:00
MIA
Introducción
Airline crew scheduling
11:30 – 12:30
MEM
JFK
1.00
9:00 – 11:00
12:45 – 14:00
ATL
8:30 – 9:30
10:00 – 11:00
MIA
Introducción
Airline crew pairing
11:30 – 12:30
MEM
JFK
9:00 – 11:00
12:45 – 14:00
ATL
8:30 – 9:30
10:00 – 11:00
MIA
Introducción
Airline crew rostering
11:30 – 12:30
MEM
JFK
9:00 – 11:00
12:45 – 14:00
ATL

8:30 – 9:30
10:00 – 11:00
MIA
Introducción
Airline Crew Pairing Problem: Consiste en encontrar un conjunto de viajes (secuencia de
vuelos) que comiencen y terminen en el lugar base de la tripulación y que cubran todos
los vuelos programados para un periodo de tiempo.
Airline Crew Rostering Problem: Consiste en asignar los “pairings” encontrados como
solución del problema anterior a cada uno de los tripulantes teniendo en cuenta, entre
otras cosas, su disponibilidad (vacaciones, exámenes médicos, días de entrenamiento),
preferencia de vuelo, rango, etc.
Ambos problemas son NP-Hard.
Introducción
Introducción
Restricciones diarias: necesarias para armar duty days legales
 La ciudad de llegada de un vuelo debe ser la ciudad de partida del vuelo que sucede
en el día de trabajo.
 El tiempo de espera entre dos vuelos consecutivos debe estar dentro de un mínimo y
un máximo prescripto.
 El tiempo de duración de un día de trabajo debe ser menor a un máximo permitido.
 El tiempo total en vuelo no puede exceder un máximo permitido.
 El día de trabajo no puede tener mas de una cantidad máxima de vuelos.
Restricciones del pairing:
 La ciudad de llegada en un día de trabajo debe ser la ciudad de partida del día de
trabajo siguiente dentro del pairing.
 Cada pairing debe comenzar y terminar en la misma ciudad (ciudad base de la
tripulación).
 El numero de días de trabajo debe ser menor a un máximo.
 El tiempo de descanso entre dos días consecutivos debe estar dentro de un rango
permitido.
 El tiempo total del pairing debe ser menor a un tiempo permitido.
Introducción
Restricciones semanales: restricciones generales para armar una agenda semanal
personalizada por tripulante.
 Los pairings no se pueden superponer.
 El tiempo total de vuelo de todos los pairings no puede superar un máximo.
 Cada agenda semanal debe contener al menos un día de descanso.
Restricciones mensuales: restricciones requeridas para armar una agenda mensual
personalizada por tripulante.
 Las agendas semanales no se pueden superponer.
 El tiempo total de vuelo de todos los pairings del mes no puede superar un máximo.
 Cada uno de los tripulantes recibe un salario mínimo garantizado por cierta cantidad
de horas de trabajo mas un monto adicional por las horas extras en vuelo.
Algoritmos Genéticos
Algoritmos Genéticos
Comienzan con un conjunto de soluciones (representados por cromosomas) llamado
población. Las soluciones de una población son usadas para generar nuevas poblaciones
con la esperanza de que las nuevas poblaciones sean mejores que las anteriores.
Estructura general del algoritmo:
Empezar
t := 0
inicializar P(t)
evaluar P(t)
Mientras no se cumpla la condición de parada hacer
Empezar
t:= t + 1
construir P (t) a partir de P( t-1)
modificar P(t)
evaluar P (t)
Fin
Fin
Algoritmos Genéticos
Para construir un algoritmo genético específico para un problema se necesita:
 Representación genética de las soluciones (Cromosomas)
 Forma de generar la población inicial
 Función de evaluación (fitness)
 Operadores genéticos que alteren la composición de los hijos. (Crossover,
Mutación)
 Determinación de parámetros
Resolución
Resolución
Solución de ambos problemas en simultaneo (pocos estudios).
Algoritmo genético híbrido
 Multi-point Crossover
 Roulette wheel selection
 Heurísticas de búsqueda local
 Elitist replacement
Una solución X del problema es un conjunto de agendas personalizadas para cada uno de
los miembro de la tripulación.
Resolución - Objetivo
Objetivo
Definición del costo:
El costo de un día de trabajo, expresado en tiempo es:
 mg1 es el mínimo garantizado de horas.
 f1 es una fracción del tiempo transcurrido elpasedl del día de trabajo.
 flyl es el tiempo de vuelo del día de trabajo.
El costo de un pairing, expresado en tiempo es:
 un mínimo garantizado de mg2 veces el numero de días de trabajo (NDP) en el
pairing.
 una fracción f2 del tiempo total del pairing TAFB_P.
 la suma de los costos de cada uno de los días del pairing.
Resolución - Objetivo
Sea X una solución al problema (un conjunto de las agendas personalizadas de los
para cada uno de los tripulantes), se define
donde HS es el monto que la compañía aérea paga por cada hora excedente de
vuelo.
El costo total de la solución X es:
Resolución - Objetivo
Definición del desvío:
Es deseable que el trabajo este bien repartido entre la tripulación.
Sean
 RF_k(X) el tiempo real de vuelo del tripulante k en la solución X
 AVf el tiempo promedio de vuelo para los tripulantes
Se define el desvío de la solución X como:
Objetivo:
Se establece un bi-objetivo jerárquico: minimizar el costo cost(X) y para las soluciones que
tengan igual costo el segundo objetivo es minimizar el desvío DV(X).
Resolución - Notación
Notación
J
K
I
DP(j)
Ijl
Conjunto de días del mes
Conjunto de todos los tripulantes
Conjunto de todos los segmentos de vuelo a asignar
Conjunto de todos los periodos de trabajo del día j
Conjunto de los vuelos del día j que constituyen el periodo de
trabajo l
Legalidad de una solución: X es legal si se cumplen todas las restricciones.
Factibilidad de una solución: X es factible si cada vuelo es cubierto exactamente una vez.
Resolución - Algoritmo
Algoritmo
Cada iteración del algoritmo genético propuesto se puede dividir en dos etapas:
La primera etapa esta basada en un multi-point crossover o una mutación. Las operaciones
consisten principalmente en reasignar ciertos días de trabajo entre los diferentes
tripulantes.
Se permiten soluciones que sean solamente legales (pueden no ser factibles).
Para la segunda etapa dos heurísticas son aplicadas al azar para reducir la penalidad
relacionada a la factibilidad de la solución.
Resolución - Algoritmo
Resolución - Algoritmo
Representación genética
Los cromosomas de las soluciones son representados mediante una matriz
Donde el gen
puede tomar los siguientes valores:
Resolución - Algoritmo
Población inicial
Determinación de las tareas diarias DP(j)
Se construye un grafo dirigido G(j) = <V(j),E(j)> para cada día j.
V(j) representa los vuelos
El eje <i, i’> significa que el vuelo i’ puede suceder al vuelo i en el mismo día.
1) Por cada nodo raíz seleccionar de manera aleatoria un camino factible según las reglas
de restricción.
2) Eliminar los nodos del camino recientemente elegido del grafo.
3) Repetir hasta que todos los nodos hayan sido utilizados.
El conjunto DP(j) cubre todos los vuelos exactamente una vez pero puede no de
cardinalidad mínima.
Resolución - Algoritmo
Asignación de las tareas diarias
: posibles tareas diarias para el tripulante k en el día j que cumplen la legalidad de
la solución respecto a las asignaciones de días anteriores.
Resolución - Algoritmo
Selección
Se utiliza el método roulette wheel selection.
El método consiste en asociar una probabilidad de selección a cada una de las soluciones
basado en el valor de evaluación de la solución.
Se utiliza principalmente para incluir dentro de la selección algunas soluciones que no estén
dentro de las mejores.
La función de evaluación esta dada por:
donde
Resolución - Algoritmo
Multi Point Crossover
Se seleccionan de forma aleatoria:
 Un numero T, 1<= T <= min(|K|, |J|)
 T genes distintos de forma tal que no compartan días ni tripulantes (no pueden estar
en la misma fila ni misma columna)
Se presentan dos versiones del crossover:
Versión simplificada: Se intercambian directamente los genes entre las soluciones.
Versión probabilística: Se intercambian los genes que no violan la legalidad de la solución.
Para los genes que violan la legalidad: si el intercambio disminuye la penalidad del día, se
acepta el cambio. Si no disminuye se realiza el intercambio con una probabilidad P.
Como no se puede asegurar la legalidad de la solución, luego del crossover se utiliza la
heurística “reparación de legalidad”.
Resolución - Algoritmo
Heurística de búsqueda local: “legality repair”
Se aplica después de los algoritmos de crossover y mutación, para obtener soluciones
legales
Una solución es legal si cumple con las restricciones. Para una
solución X, L(X) es la lista de pares (crew, día) con asignaciones
ilegales. X es legal si L(X) = 
Objetivo:
Reconstruir el conjunto de asignaciones (DP) para que cubra la mayor cantidad de
vuelos posibles.
Resolución - Algoritmo
Heurística de búsqueda local: “legality repair”
Por cada solución ilegal X
Por cada xkj = (k, j)  L(X)
Construir un conjunto DPkj(X) con todas las posibles asignaciones para k que cubra
al menos uno de los vuelos posibles (Nf = vuelos del día j  vuelos no asignados) .
Si DPkj(X)   entonces
Seleccionar el I’  DPkj(X) que cubra el máximo número de vuelos de Nf
xkj  I’
si no
xkj  0
Resolución - Algoritmo
Mutación
La mutación consiste en seleccionar de forma aleatoria un día j y dos tripulantes k1 y k2
que tenga disponibilidad ese día (
y
) e intercambiarlos.
Como no se puede asegurar la legalidad de la solución es necesario correr la heurística
“reparación de legalidad”.
Resolución - Algoritmo
Heurísticas “feasibility repair”
El objetivo de estas heurísticas es mejorar la solución propuesta en cada iteración del
algoritmo genético.
Una solución es viable (feasible) si cubre todos los vuelos solo una vez.
Se aplican dos posibles heurísticas de reparación de viabilidad:
Random feasibility repair (RFRH)
Improved feasibility repair (IFRH)
La elección de una heurística u otra se hace aleatoriamente en base a un parámetro que
determina la probabilidad de aplicar o no RFRH.
Resolución - Algoritmo
ri = asignaciones que cubren el vuelo i
Heurística Random feasibility repair (RFRH)
|ri| = 0
Selecciona al azar un miembro que pueda cubrir el vuelo i.
Y reemplaza la asignación para ese miembro de forma tal de cubrir i.
|ri| > 1
Del conjunto de miembros que cubren el vuelo i (Ki) selecciona uno al azar y quita la
asignación del resto mientras se mantenga la legalidad.
Heurística Improved feasibility repair (IFRH)
|ri|= 0 – Igual que la heurística anterior
|ri| > 1
Reasigna las tareas de todos los miembros de Ki de forma tal que se cubra la mayor
cantidad de vuelos posibles sin repetir i.
Resolución - Algoritmo
Reemplazo de soluciones
Elitist replacement
Una vez obtenida una nueva solución (mutación o crossover) se reemplaza la peor solución
de la población anterior por la nueva solución siempre y cuando ésta última sea mejor
(función de evaluación).
Esta técnica permite que los mejores padres coexistan con los mejores hijos.
Resultados
Resultados
Las instancias de prueba fueron datos reales provistos por la compañía aérea Air – Algérie.
Instancia 1
65 pairings, 220 vuelos, 5 pilotos del 1/3/2004 al 31/3/2004
Instancia 2
155 pairings, 631 vuelos, 19 pilotos del 1/5/2005 al 31/3/2005
Instancia 3
558 pairings, 1872 vuelos, 68 pilotos del 1/3/2006 al 31/3/2006
Resultados
Resultados
Iteraciones = 300
Probabiliad Crossover (Pc) = 0,7
#Población = 100
Resultados
Conclusiones
Conclusiones
La combinación de heurísticas RFRH y IFRH dio mejores resultados, que utilizar solo RFHR
o IFHR (en este segundo caso la diferencia fue mucho menor)
El cross-over multipoint probabilístico dio en general mejores asignaciones en cuanto al
desvío del tiempo (DV)
La inicialización con programación lineal dío mejores resultados en cuanto a DV y obtuvo
soluciones viables en una menor cantidad de iteraciones.
Gracias por su atención.
Descargar

Introducción al problema Airline Crew Scheduling Problem