Informe acerca de crew pairing

INTELIGENCIA ARTICIAL
CREW PAIRING

Pedro Lucero C.
Roberto Araya B.

Junio 2010
Profesor: Eduardo Opazo.

ÍNDICE

1.- RESUMEN (abstract) 1
2.- INTRODUCCIÓN 1
3.- EL PROBLEMA TRIPULACIÓN ENLACE: 1
4.- RESOLVIENDO EL PROBLEMA TRIPULACIÓN ENLACE: 2
4.1.- GENERACIÓN DE ENLACES: 3
4.2 GENERACIONES DE FUNCIONES DE LAS ETAPAS: 4
4.3.- LA OPTIMIZACIÓN: 4
5.- RESULTADOSEXPERIMENTALES 7
6.- CONCLUSIÓN 9
7.- BIBLIOGRAFÍA 9

1.- RESUMEN (abstract)

El Problema de asignación de tripulación es complejo, y se ha divido en dos fases para su solución. siendo una de estas la generación de dotaciones y la segunda la optimización de aquellas, se muestran algunas de las restricciones que deben abordarse para resolver la problemática y se una pequeña parte del algoritmoutilizado y se realizan la conclusiones.

2.- INTRODUCCIÓN

El Problema de asignación de tripulación para las aerolíneas es de alta complejidad, debido a la gran cantidad de combinaciones y restricciones, que deben considerarse, para asignar una de tripulación a un determinado tramo de vuelo, las grandes compañías pueden llegar a realizar más de 1000 vuelos diarios, lo que aumenta lascombinaciones exponencialmente. Teniendo en cuenta que los segundos mayores costos de operación en los que incurren las aerolíneas, son los de las dotaciones asignadas a los tramos de vuelo, resulta crucial a la hora de querer disminuir los costos, que estas asignaciones sean realizadas lo mejor posible.
Para lo cual se propone trabajar con algoritmos genéticos que se aproximan a la meta u objetivo aalcanzar. La principal dificultad que se enfrenta es el gran tamaño de soluciones, en que se debe buscar, esta crece exponencialmente con el número de tramos de vuelo. Agregando más complejidad al problema, están las restricciones no lineales, como son las leyes de aeronáutica, regulaciones y otros.
Mucho se ha trabajado para intentar resolver el problema Ej. Explotar el paralelismo, usaralgoritmos genéticos y en algunos casos la combinación de ambos.
En este documento se presenta una descripción del problema “The crew pairing”, los resultados obtenidos y pruebas realizadas, y las conclusiones.

3.- EL PROBLEMA TRIPULACIÓN ENLACE:

El objetivo del problema Tripulación Enlace es minimizar los costos asociados con tripulaciones asignadas en etapas de los vuelos. Cada tripulacióntiene una base de operaciones y un enlace en una ruta de viaje, consistente de una secuencia de etapas de vuelo, las cuales comienzan y finalizan en la base de la tripulación. Cada enlace se compone de un número de días hábiles legales, llamados “Servicio” los cuales son separados por periodos de descanso.
El enlace de la tripulación busca encontrar un subconjunto de enlaces legales, de manera quecada etapa del vuelo sea cubierta, preferiblemente por un solo tripulante, y así el costo total de ese enlace sea mínimo. En términos legales, la construcción de un enlace debe tomar en cuenta un número de restricciones. Algunas de estas restricciones, como la restricción temporal y espacial siguen directamente desde la definición del problema, mientras otros son el resultado de leyes yregulaciones, específicamente, se pueden identificar los siguientes tipos de restricciones:

- Restricciones temporales: La salida de una etapa de un vuelo obviamente debiera suceder luego del arribo de la etapa previa del enlace. Adicionalmente, cierta cantidad de tiempo, llamado tiempo en transición, debe pasar entre el arribo de una etapa y la salida de la etapa siguiente.
- Restriccionesespaciales: Por cada dos etapas de vuelo consecutivas en un enlace, la segunda debe salir del aeropuerto al que llega primero. Además la primera etapa de un enlace legal debe salir desde la base de operaciones de la tripulación y la última etapa de cada enlace debe finalizar en la base de origen.
- Restricciones de flota: La cabina de mando es usualmente designada para operar sólo un tipo de...