Lagos Carlos

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE INGENIERÍA
UN MODELO DE OPTIMIZACIÓN
DINÁMICA PARA LA PLANIFICACIÓN
EFICIENTE DE TAREAS DE
MANTENIMIENTO DE AVIONES
CARLOS ALBERTO LAGOS SALGADO
Tesis para optar al grado de

Magı́ster en Ciencias de la Ingenierı́a
Profesores Supervisores:
FELIPE DELGADO
MATHIAS KLAPP
Santiago de Chile, Marzo 2019
c MMXIX, C ARLOS A LBERTO L AGOS S ALGADO

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE INGENIERÍA
UN MODELO DE OPTIMIZACIÓN
DINÁMICA PARA LA PLANIFICACIÓN
EFICIENTE DE TAREAS DE
MANTENIMIENTO DE AVIONES
CARLOS ALBERTO LAGOS SALGADO
Miembros del Comité:

FELIPE DELGADO
MATHIAS KLAPP
GUSTAVO ANGULO
LUIS CADARSO
JULIO VERGARA
Tesis para optar al grado de

Magı́ster en Ciencias de la Ingenierı́a
Santiago de Chile, Marzo 2019
c MMXIX, C ARLOS A LBERTO L AGOS S ALGADO

A mi familia, amigos y profesores.
AGRADECIMIENTOS
En primer lugar, me gustarı́a agradecer a mi familia, por su apoyo incondicional en

todos los proyectos en que he estado involucrado durante mi vida. En especial quiero
darle las gracias a Lucı́a Latı́n por ayudarme a hacer de estos dos años un proceso más
fácil. Quiero reconocer a mis hermanas Andrea y Mariana por ser mi soporte en todas las
decisiones que durante los últimos años he tomado.
En segundo lugar, agradecer a Felipe y Mathias, mis profesores guı́as, por su pacien-
cia, apoyo y ayuda durante estos dos años. Gracias por compartir sus conocimientos y
experiencias, con su tutela he crecido como profesional y más aún como persona. A Juan
Enrique Coeymans le doy las gracias por siempre estar disponible para entregarme sus
consejos y ayuda. Extiendo este agradecimiento a todos los profesores que han sido parte
de mi proceso de formación, sin duda, todos han aportado a mi desarrollo.
También agradecer a mis compañeros de postgrado por recibirme y hacer del departa-
mento de transporte mi segunda casa. En particular, quiero darle las gracias a Cristóbal Sir-
han, Sebastián Gebhardt y José Tomás Marquinez quienes siempre me motivaron, acom-
pañaron y ayudaron a conseguir todo lo necesario para que estos años se convirtieran en
una muy grata experiencia. Mención especial a la ayuda inicial que Cristóbal me entregó,
sin él no hubiese podido embarcarme en este proyecto.
Agradezco a la Comisión Nacional de Investigación Cientı́fica y Tecnológica por el

financiamiento de mis estudios mediante la entrega de una Beca de Magı́ster Nacional
(CONICYT-PFCHA/Magı́sterNacional/2017-22171227).
Finalmente, a mis amigos más cercanos, les doy las gracias por estar siempre apoyándo-
me y compartiéndome sus conocimientos para hacer este trabajo aún mejor.
iv
ÍNDICE GENERAL
AGRADECIMIENTOS iv
ÍNDICE DE FIGURAS viii
ÍNDICE DE TABLAS x
RESUMEN xi
ABSTRACT xii
1. INTRODUCCIÓN 1
1.1. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Motivación del problema . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4. Alcances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5. Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2. REVISIÓN BIBLIOGRÁFICA 9
2.1. Planificación aérea a nivel estratégico-táctico . . . . . . . . . . . . . . . 9
2.1.1. Integración de etapas en la planificación de aerolı́neas . . . . . . . . 12
2.1.2. Proactividad con respecto a disrupciones . . . . . . . . . . . . . . . 15
2.2. Planificación aérea a nivel operacional . . . . . . . . . . . . . . . . . . . 17
2.2.1. Operational aircraft maintenance routing problem (OAMRP) y Tail
assignment problem (TAP) . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2. Manejo de disrupciones . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3. Planificación de recursos humanos - Asignación de tareas . . . . . . . 26
2.3. Programación dinámica aproximada (ADP) . . . . . . . . . . . . . . . . 26
2.4. Aporte a la literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3. METODOLOGÍA 32
3.1. Supuestos de modelación . . . . . . . . . . . . . . . . . . . . . . . . . 32
v
3.2. Formalización del problema como MDP . . . . . . . . . . . . . . . . . . 33
3.2.1. Proceso de arribo de tareas . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2. Estado y espacio de acciones factibles . . . . . . . . . . . . . . . . . 35
3.2.3. Costo diario de operación . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4. Transiciones de estado . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.5. MDP y ecuaciones de Bellman . . . . . . . . . . . . . . . . . . . . . 39
3.3. Modelo determinı́stico integrado de planificación de mantenimiento y TAP 41
3.4. Polı́ticas dinámicas de decisión . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1. Miope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.2. VFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.3. Horizonte rodante . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.4. Combinación de horizonte rodante con VFA . . . . . . . . . . . . . 52
3.5. Heurı́stica aerolı́nea . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4. CASO DE ESTUDIO Y RESULTADOS 55

4.1. Diseño de caso de estudio . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1. Caso base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.2. Caso 1: nuevas LOFs . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.3. Caso 2: reducción del plazo para realizar tareas . . . . . . . . . . . . 61
4.1.4. Caso 3: diferentes niveles de saturación . . . . . . . . . . . . . . . . 62
4.1.5. Caso 4: Planificación de mantenimiento sin integración con TAP . . . 62
4.1.6. Caso 5: Planificación de mantenimiento descentralizada . . . . . . . 63
4.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.1. Resultados caso base . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.2. Resultados caso 1: nuevas LOFs . . . . . . . . . . . . . . . . . . . . 67
4.2.3. Resultados caso 2: reducción del plazo para realizar tareas . . . . . . 69
4.2.4. Resultados caso 3: diferentes niveles de saturación . . . . . . . . . . 70
4.2.5. Resultados caso 4: planificación de mantenimiento sin integración con
TAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2.6. Resultados caso 5: planificación de mantenimiento descentralizada . . 74
vi
5. CONCLUSIONES 76
5.1. Principales resultados y lecciones . . . . . . . . . . . . . . . . . . . . . 76
5.2. Futuras lı́neas de investigación . . . . . . . . . . . . . . . . . . . . . . . 78
REFERENCIAS 80
GLOSARIO 95
ANEXOS 96
A. Modelos determinı́sticos equivalentes . . . . . . . . . . . . . . . . . . . . 97
A.1. Modelo determinı́stico adicional 1 . . . . . . . . . . . . . . . . . . . 97
B. Inclusión explı́cita de tareas periódicas . . . . . . . . . . . . . . . . . . . . 103
vii
ÍNDICE DE FIGURAS
1.1. Evolución de oferta y demanda de mecánicos de aviones en EEUU . . . . . . 2
1.2. Ejemplo problema simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Solución problema simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Solución problema simple re-asignando vuelos . . . . . . . . . . . . . . . . 5
2.1. Esquema de planificación aérea . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Esquema de planificación aérea operacional . . . . . . . . . . . . . . . . . . 19
3.1. Evolución del dı́a t para cada avión . . . . . . . . . . . . . . . . . . . . . . 34
3.2. Conservación de flujo avión a . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3. Conservación de flujo dı́a 1 para un avión cualquiera . . . . . . . . . . . . . 45
3.4. Conservación de flujo dı́a 2 para un avión cualquiera . . . . . . . . . . . . . 46
3.5. Conservación de flujo dı́a t para un avión cualquiera . . . . . . . . . . . . . 46
3.6. Ejemplo de horizonte rodante . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1. Número de aviones en mantenimiento por dı́a . . . . . . . . . . . . . . . . . 57
4.2. Función de probabilidad de HP por tarea . . . . . . . . . . . . . . . . . . . 58
4.3. Distribución horas de inicio y fin LOFs . . . . . . . . . . . . . . . . . . . . 59
4.4. Distribución vencimiento de tareas iniciales . . . . . . . . . . . . . . . . . . 60
4.5. Perfil de anticipación de tareas por polı́tica . . . . . . . . . . . . . . . . . . 66
4.6. Ponderadores VFA dependiendo de LOFs . . . . . . . . . . . . . . . . . . . 68
4.7. Perfil de anticipación de tareas por polı́tica caso más dinámico . . . . . . . . 70

viii
4.8. Comparación HR-VFA1 con PIM en diferentes niveles de saturación . . . . . 71
4.9. Perfil de anticipación de tareas en diferentes niveles de saturación . . . . . . 72
4.10. Perfil de anticipación de tareas desagregado por tamaño . . . . . . . . . . . 72
ix
ÍNDICE DE TABLAS
2.1. Trabajos revisados sobre FS-FA-CS . . . . . . . . . . . . . . . . . . . . . . 11
2.2. Trabajos revisados sobre ARP/AMRP . . . . . . . . . . . . . . . . . . . . . 13
2.3. Trabajos revisados sobre integración de etapas . . . . . . . . . . . . . . . . 15
2.4. Trabajos revisados sobre robustez . . . . . . . . . . . . . . . . . . . . . . . 18
2.5. Trabajos revisados sobre OAMRP/TAP . . . . . . . . . . . . . . . . . . . . 23
2.6. Trabajos revisados sobre manejo de disrupciones a nivel operacional . . . . . 25
2.7. Trabajos revisados sobre ADP . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1. Tamaño de flota doméstica principales aerolı́neas en Chile . . . . . . . . . . 56
4.2. Resultados caso base (50 réplicas) . . . . . . . . . . . . . . . . . . . . . . 64
4.3. Resultados caso nuevas LOFs (50 réplicas) . . . . . . . . . . . . . . . . . . 67
4.4. Resultados caso tareas más dinámicas (50 réplicas) . . . . . . . . . . . . . . 69
4.5. Resultados caso sin integración (50 réplicas) . . . . . . . . . . . . . . . . . 73
4.6. Resultados caso planificación descentralizada para HR-VFA1 (50 réplicas) . . 74
x
RESUMEN
Una aparición inesperada de tareas de mantenimiento puede producir cambios signi-

ficativos y costosos en la operación de una aerolı́nea. Cuando se trata de tareas crı́ticas,
incluso podrı́a ser necesario cancelar vuelos programados. A pesar de ello, el desafı́o de
planificar las operaciones de mantenimiento de aviones bajo incertidumbre ha recibido
limitada atención de parte de la literatura cientı́fica.
Se estudió un problema de planificación de mantenimiento de una aerolı́nea que in-

volucra decidir diariamente qué aeronaves mantener y seleccionar el conjunto de tareas
pendientes a ejecutar en cada aeronave. El objetivo del problema es minimizar el costo
total esperado por las tareas que expiran en el horizonte operativo. Para aumentar flexi-
bilidad y reducir costos, integramos la planificación de mantenimiento con la asignación
de LOFs a aviones. Formulamos el problema como un proceso de decisión markoviano y
diseñamos polı́ticas basadas en programación dinámica aproximada.
En un caso de estudio basado en una aerolı́nea latinoamericana, mostramos el valor de

la optimización dinámica al comparar el costo de nuestras polı́ticas contra el de una regla
de decisión simplificada de la aerolı́nea y una cota con información perfecta del proceso
de arribo de tareas. Nuestra polı́tica propuesta previene AOGs, alcanza una cobertura de
tareas del 97,57 % y muestra una reducción promedio en las tareas vencidas de 83,75 %
con respecto a la regla de la aerolı́nea. Además, nuestra polı́tica tiene un costo promedio
un 2,64 % mayor que la cota de información perfecta. Para aumentar la utilización de
la capacidad residual, nuestras polı́ticas adelantan el mantenimiento de tareas pendientes
que requieren un bajo consumo de recursos. También sugerimos que existen significativas
economı́as de escala cuando se comparten recursos de mantenimiento entre aerolı́neas.
Palabras Claves: Mantenimiento de aviones, Programación dinámica aproximada, Plani-

ficación de tareas, Asignación de aviones.
xi
ABSTRACT
The occurrence of unexpected aircraft maintenance tasks can produce expensive chan-
ges in an airline’s operation. When it comes to critical tasks, it might even end up cance-
lling programmed flights. Despite of it, the challenge of scheduling aircraft maintenance
operations under uncertainty has received limited attention in the scientific literature.
We studied a dynamic airline maintenance scheduling problem, which involve daily

decisions about the set of aircraft to maintain and the set of pending tasks to execute in
each aircraft. The objective is to minimize the total expected cost of expired maintenance
tasks over the operating horizon. In order to increase flexibility and to reduce costs, we
integrated maintenance scheduling with tail assignment decisions. We formulated our pro-
blem as a Markov Decision Process and design dynamic policies based on approximate
dynamic programming.
In a case study based on a Latin American airline, we showed the value of dynamic
optimization by testing our best policies against a simple airline decision rule and a de-
terministic relaxation with perfect information of the task arrival disclosure process. Our
proposed policy prevents AOGs, achieved a 97.57 % coverage of task requirements, and
showed an average reduction in tasks expired of 83.75 % against the airline decision rule.
Compared to the perfect information lower bound, our best policy had an average cost
increase of 2.64 %. To increase utilization of residual capacity at the maintenance base,
our policies scheduled ahead pending tasks requiring low consumption of resources first.
We also suggest that significant economies of scale are present when sharing maintenance
resources between multiple airlines.
Keywords: Airline maintenance, Approximate Dynamic Programming, Task Scheduling,

Tail Assignment.
xii
1
1. INTRODUCCIÓN
En este capı́tulo se introduce un estudio de planificación diaria de tareas de mante-

nimiento de aviones organizado en las siguientes secciones: en la sección 1.1 se contex-
tualiza el problema; en la sección 1.2 se presenta el problema y las motivaciones para
abordarlo; en la sección 1.3 se enuncian los objetivos del trabajo; en la sección 1.4 se
definen los alcances de la investigación; y en la sección 1.5 se describe la estructura del
documento.
1.1. Contexto
El transporte aéreo es fundamental para la economı́a mundial y su crecimiento ha cam-

biado la forma de transportar personas y mercancı́as. Esta evolución ha ido acompañada
de estrictos estándares de seguridad en la operación de aeronaves los cuales han posicio-
nado al transporte aéreo como el modo de transporte más seguro del mundo culminando
el año 2017 sin vı́ctimas fatales en vuelos comerciales (IATA, 2018b) y con un accidente
cada 740.000 vuelos en 2018 (IATA, 2019).
Dentro de una aerolı́nea, el área de mantenimiento es responsable de planificar y ejecu-

tar todas las acciones preventivas necesarias para cumplir con dichos estándares de seguri-
dad, incluyendo la ejecución de tareas de mantenimiento en cada avión. Para esto requiere
trabajadores con distintas habilidades como por ejemplo: mecánicos de aeronaves, exper-
tos en aviónica, electricistas y expertos en cabina, entre otros.
Desde un punto de vista económico, las aerolı́neas operan con bajos márgenes, con
un promedio anual de 1,8 % en la última década (IATA, 2018a), por lo que buscan un
mantenimiento costo-eficiente. De acuerdo a Bureau of Transportation Statistics (2017),
el mantenimiento representa cerca del 9 % de los costos de operación de una aerolı́nea y,
considerando solo a las 10 principales aerolı́neas de Estados Unidos, representa más de
12,5 billones de dólares anualmente en gastos.
2
Dentro de los costos de mantenimiento, la mano de obra calificada representa cerca

del 50 % de los gastos (IATA’s Maintenance Cost Task Force, 2013), y se espera que este
porcentaje aumente. Como se muestra en la Figura 1.1, la oferta de mecánicos capacitados
no crece a la par con las necesidades de la industria y para 2027 se espera que el número de
mecánicos de aviones en los Estados Unidos sea inferior a los requeridos por la industria de
aviación comercial (Prentice, Costanza, y Smiley, 2017). A medida que la disponibilidad
de mano de obra se vuelve escasa, realizar una eficiente programación de las operaciones
de mantenimiento se vuelve cada vez más importante.
92
Número de trabajadores
Demanda Oferta
90
(en miles)
88
86
84
82
80
15
16
17
18
19
20
21
22
23
24
25
26
27
20
20
20
20
20
20
20
20
20
20
20
20
20
Año
Figura 1.1. Evolución de oferta y demanda de mecánicos de aviones en

EEUU
Fuente: (Prentice et al., 2017)
Además de los costos, las actividades de mantenimiento pueden afectar negativamen-

te el nivel de servicio al cliente, retrasando los itinerarios o incluso cancelando vuelos.
Dado el costo de capital de cada avión, las aerolı́neas buscan continuamente aumentar la
utilización de este (IATA, 2017), reduciendo su tiempo en tierra. Como efecto secundario,
aumenta la probabilidad de que un ligero retraso en el mantenimiento pueda propagarse
severamente en la operación futura. Un estudio realizado por Cook, Tanner, y Anderson
(2004) estima que, para una aerolı́nea grande, los costos directos causados por vuelos atra-
sados debido a mantenimiento superaron los $20 millones de dólares anuales. Por lo tanto,
3
no solo se debe buscar planificar operaciones de mantenimiento costo-eficientes, sino que

también reducir al máximo los retrasos operacionales.
1.2. Motivación del problema
La planificación de tareas de mantenimiento consiste en determinar diariamente a qué

aviones realizar mantenimiento y qué tareas realizar en ellos para garantizar la operati-
vidad de la aeronave, teniendo recursos limitados. El objetivo es minimizar el costo total
esperado por tareas de mantenimiento vencidas en el horizonte de operación. Cada tarea se
pondera de manera diferente en la función objetivo de acuerdo a su importancia. Mientras
que el retraso de una tarea es levemente indeseable, el vencimiento de una tarea crı́tica
podrı́a cancelar vuelos programados y dejar a una aeronave inoperativa. Este tipo de pro-
blemas pertenece a la familia de problemas de Scheduling (Pinedo, 2016) y gran parte
de ellos pertenecen al conjunto de problemas N P-hard, lo que indica su complejidad de
resolución.
Además, el problema presenta una serie de caracterı́sticas que lo distinguen de una ca-
lendarización tradicional de tareas. En primer lugar, las tareas son reveladas al tomador de
decisiones dinámicamente en el tiempo por lo que al momento de planificar no se cuenta
con toda la información relevante para tomar decisiones eficientes. Normalmente se dis-
pone solo de información probabilı́stica sobre los acontecimientos futuros. En segundo
lugar, existe un número máximo de aeronaves que diariamente pueden recibir manteni-
miento debido a la capacidad de las instalaciones, que comúnmente, no pueden albergar a
toda la flota. En tercer lugar, cada tarea puede requerir múltiples tipos de recurso para ser
completada. Por ejemplo una tarea puede requerir tres horas-persona de trabajadores con
la habilidad de mécanico y dos horas-persona de aviónico. En cuarto lugar, las tareas de
mantenimiento solo se pueden realizar en aeropuertos con bases de mantenimiento dispo-
nibles de la aerolı́nea. En quinto lugar, es necesario modelar el detalle de mantenimiento
por hora del dı́a, pues cada avión ejecuta un conjunto de vuelos particular con diferentes
ventanas de tiempo en tierra disponibles para mantenimiento. Finalmente, las tareas tienen
4
fecha de vencimiento, la cual debe ser respetada y no hacerlo puede implicar que dicha
aeronave quede inoperativa.
Actualmente, en latinoamérica las aerolı́neas resuelven este complejo problema de

forma manual (H. Salazar, comunicación personal, 21 de abril, 2017). Para ello deben
descartar el detalle del problema, pues de lo contrario no podrı́an resolverlo, y seleccionar
las tareas a realizar cada dı́a guiándose únicamente por la fecha de vencimiento y con-
siderando la disponibilidad de recursos de manera agregada a nivel diario. Esto no solo
puede generar soluciones infactibles, sino que reduce la capacidad de anticipar el futuro.
Sumado a lo anterior, esta forma de afrontar el problema requiere planificar manualmente
la operación y aumenta el uso de recursos humanos calificados. De acuerdo a lo señalado
por el jefe de planificación de mantenimiento de LATAM Airlines, al automatizar la ope-
ración se podrı́a reducir cerca de 50 % de estas horas (H. Salazar, comunicación personal,
21 de abril, 2017).
Consideremos el ejemplo presentado en la Figura 1.2, que describe a tres aviones (A,
B, C) con cinco, tres y una tarea pendiente, respectivamente. Cada tarea consume una hora
del turno nocturno de mantenimiento que dura 9 horas y posee un técnico disponible.
Figura 1.2. Ejemplo problema simple
Al planificar de forma manual, se planificarı́an las nueve tareas, ya que hay nueve horas
de recurso disponibles. Sin embargo, al considerar el horario en tierra de cada aeronave se
podrı́a estar proponiendo una planificación infactible. Por ejemplo, consideremos la Figura
1.3, donde el avión A está disponible entre las horas 0 y 6, B entre 2 y 7, y C entre 3 y 9.
5
En este caso, la ejecución de las 9 tareas en un turno es infactible y, de forma obligatoria,

una tarea (A o B) debe quedar pendiente.
Figura 1.3. Solución problema simple
Adicionalmente, la planificación manual no considera reasignar los vuelos de cada

avión al momento de diseñar el plan, a pesar de que los vuelos son determinantes en
la factibilidad y eficiencia del proceso. Esto se ilustra con el ejemplo anterior, donde se
puede obtener una solución factible reasignando los vuelos entre aviones. Como se detalla
en la Figura 1.4, se podrı́a asignar el avión A al conjunto de vuelos del siguiente dı́a que
originalmente tenı́a el avión B, el avión B al que tenı́a C y el avión C al que tenı́a A.
Figura 1.4. Solución problema simple re-asignando vuelos
El ejemplo anterior ilustra lo importante que es considerar explı́citamente restriccio-

nes de capacidad de recursos de mantenimiento por hora y considerar re-asignar vuelos o
conjuntos de vuelos (tail assignment problem - TAP) al planificar tareas de mantenimiento
de aviones. Además, revela lo difı́cil que es afrontarlo manualmente, pues no considera
6
el detalle de restricciones y decisiones existentes. Considerando que lo anterior es solo

un ejemplo simplificado, que trabaja con un tipo de recurso, es aún más difı́cil abordar
problemas con múltiples tipos de recurso disponibles. Se hace indispensable diseñar he-
rramientas de investigación de operaciones para reducir el costo de planificación de mante-
nimiento actual satisfaciendo todas las restricciones al detalle. La hipótesis de este trabajo
es que es posible diseñar dichas herramientas y explotar toda la flexibilidad disponible en
el problema.
1.3. Objetivos
El objetivo general de esta tesis es utilizar técnicas de optimización entera mixta y

programación dinámica para modelar y resolver el problema de planificación diaria de
tareas de mantenimiento de aeronaves. Especı́ficamente se plantea:
i. Formular un modelo matemático determinı́stico que incorpore todas las restricciones

y decisiones relevantes del problema a estudiar.
ii. Implementar computacionalmente el modelo matemático determinı́stico correspon-
diente a la cota de información perfecta.
iii. Formular polı́ticas costo-eficientes utilizando técnicas de optimización dinámica para
resolver el problema con dinamismo e incertidumbre en el proceso estocástico de
arribo de tareas.
iv. Simular computacionalmente un conjunto de instancias a partir de datos reales que
representan la operación de la aerolı́nea.
v. Determinar empı́ricamente una polı́tica adecuada para planificar el mantenimiento de
la aerolı́nea.
vi. Estimar los beneficios de la polı́tica propuesta en comparación con una regla de pla-
nificación manual de referencia asociada a la actual gestión de la aerolı́nea.
vii. Estimar los beneficios asociados a la incorporación de la asignación de aviones a
secuencias de vuelo dentro del proceso de planificación de mantenimiento.
viii. Analizar la presencia de economı́as de escala en la planificación de mantenimiento.
7
ix. Analizar patrones comunes y caracterı́sticas relevantes en las soluciones que entregan
valiosa intuición para la toma de decisiones de mantenimiento.
1.4. Alcances
En esta tesis se estudia la planificación de mantenimiento de la flota doméstica de

una aerolı́nea con una única base de mantenimiento, con capacidad definida, en donde co-
mienzan y terminan diaramente las secuencias de vuelos de los aviones. Para simplificar el
problema, se considera una flota homogénea de aviones y que las tareas de mantenimiento
son ejecutadas en turnos nocturnos. También se asume que los vuelos no son cancelados
ni sufren retrasos, por lo que las secuencias de vuelos cumplen los horarios estipulados.
Además, se considera que una tarea planificada fue ejecutada sin perturbación al mo-
mento de planificar tareas posteriores. También, se asumen conocidos los recursos dispo-
nibles y las secuencias diarias de vuelos para todo el horizonte de operación al momento
de planificar.
1.5. Estructura de la tesis
Este trabajo se estructura de la siguiente manera: en el siguiente capı́tulo se presenta

una revisión bibliográfica que aborda la literatura relevante en planificación de manteni-
miento de aeronaves y optimización dinámica. Dentro de la planificación de mantenimien-
to, se profundiza en las investigaciones que incorporan esta materia en problemas de ruteo
o asignación de aviones. También, se detalla los aspectos del problema que han sido es-
tudiados y los trabajos relevantes en el ámbito operacional. Con respecto a optimización
dinámica, se expone algunas técnicas desarrolladas para resolver problemas dinámicos de
gran tamaño en base a approximate dynamic programming (ADP).
En el capı́tulo 3, se presenta la metodologı́a de estudio del problema. En particular, se

formula el modelo de programación dinámica que define el problema y un modelo deter-
minı́stico de optimización que planifica todo el horizonte de planificación. Este segundo
8
modelo supone que la información de tareas está disponible al comienzo de la operación

y por lo tanto, relaja los supuestos de información conocida al planificar. Posteriormente,
se propone polı́ticas dinámicas basadas en ADP.
En el capı́tulo 4, se describe el caso de estudio, la metodologı́a de generación de ins-

tancias, y se presentan los resultados obtenidos implementando las polı́ticas propuestas.
Se compara la solución obtenida contra la cota de información perfecta y contra un bench-
mark asociado a la actual gestión de la aerolı́nea.
Finalmente, en el capı́tulo 5, se concluye el trabajo, discutiendo posibles extensiones

y futuras lı́neas de investigación en torno a esta problemática.
9
2. REVISIÓN BIBLIOGRÁFICA
En este capı́tulo se presenta una revisión bibliográfica de literatura relevante al tema de

estudio. En la sección 2.1, se revisa el proceso de planificación aérea a nivel estratégico-
táctico y cómo se ha abordado desde la investigación de operaciones. En particular, se
revisa las etapas clásicas de este proceso, cómo se han resuelto y cómo se ha introduci-
do robustez a la planificación para absorber de mejor manera disrupciones. En la sección
2.2, se presentan los problemas relacionados con la planificación de la operación aérea,
centrando la exposición en el manejo de disrupciones, el problema de ruteo de aviones,
el problema de asignación de aviones especı́ficos a dicho ruteo y la calendarización de
tareas de mantenimiento de aviones. En la sección 2.3, se presentan algunos métodos de
programación dinámica aproximada (ADP) utilizados para enfrentar problemas de progra-
mación dinámica de gran escala como el nuestro. Por último, en la sección 2.4 se presenta
la contribución de este trabajo al estado del arte.
2.1. Planificación aérea a nivel estratégico-táctico
La planificación aérea se divide en operaciones de corto, mediano y largo plazo. Es-

tas dos últimas comprenden el nivel estratégico-táctico del proceso y han sido amplia-
mente abordadas en la literatura mediante herramientas de investigación de operaciones
(OR). Debido a su complejidad, usualmente el proceso se divide en cuatro etapas que
son resueltas secuencialmente: generación de vuelos (flight scheduling), asignación de
flota (fleet assignment), calendarización de tripulaciones (crew scheduling-crew pairing)
y ruteo de aviones considerando mantenimiento (aircraft maintenance routing problem-
AMRP) (Haouari, Shao, y Sherali, 2013; Liang, Feng, Zhang, Wu, y Chaovalitwongse,
2015). La Figura 2.1 presenta una visión general del proceso. Una revisión de trabajos
relevantes se puede encontrar en Barnhart, Belobaba, y Odoni (2003) y Barnhart y Smith
(2012).
En la etapa de generación de vuelos se define qué rutas operar y cuándo hacerlo. Tra-
bajos relevantes enfocados en este problema se encuentran en Etschmaier y Mathaisel
10
Figura 2.1. Esquema de planificación aérea tradicional

Fuente: Adaptado de Lapp y Cohn (2012) y Liang et al. (2015)
(1985), Gopalan y Talluri (1998b) y Eltoukhy, Chan, y Chung (2017). Posteriormente, es

necesario definir con qué tipo de avión se llevará a cabo cada vuelo planificado, es decir,
se debe resolver el problema de asignación de flota. Lectores interesados en este problema
pueden consultar Sherali, Bish, y Zhu (2006) y Eltoukhy et al. (2017). Una vez definido
el tipo de avión que operará cada vuelo, es necesario definir la secuencia de vuelos y otras
actividades que ejecuta cada avión. Este problema es conocido como ruteo de aviones
(AMRP) y es el más relevante para este trabajo, pues involucra el mantenimiento. Por últi-
mo, está el proceso de calendarización de la tripulación que puede planificarse en forma
paralela al ruteo de aviones. El estudio de Deveci y Demirel (2018) revisa trabajos rela-
cionados y en la Tabla 2.1 se detalla ejemplos relevantes sobre flight scheduling (FS), fleet
assignment (FA) y crew scheduling-crew pairing (CS).
En particular, el AMRP consiste en determinar las rutas de vuelos para cada uno de los
aviones de la flota dada una secuencia de vuelos requerida y una flota de aviones conocida,
tal que se cubran todos los vuelos y se respete el requerimiento de mantenimiento (Liang
et al., 2015). Es inicialmente abordado por Feo y Bard (1989) al formular el problema de
localización del mı́nimo número de bases de mantenimiento que hace posible asignar los
11
Tabla 2.1. Trabajos revisados sobre FS-FA-CS
Trabajo FS FA CS
Etschmaier y Mathaisel (1985) X
Barnhart et al. (2003) X X X
Sherali et al. (2006) X
Barnhart y Smith (2012) X X X
Eltoukhy et al. (2017) X X X
Deveci y Demirel (2018) X
aviones al calendario de vuelos de cuatro dı́as. Ellos utilizan ruteos de un dı́a de duración
entre aeropuertos, pues consideran que las paradas intermedias durante el dı́a no impactan
en la planificación. De forma similar, Daskin y Panayotopoulos (1989) enumeran rutas y
plantean un enfoque que maximiza las ganancias de la asignación al considerar distintos
tipos de aviones.
Kabbani y Patty (1992) es el primer trabajo que aborda completamente el AMRP y

formulan un modelo de set-partition que asigna rutas a cada avión de una flota. Garantizan
que cada avión debe pasar por mantenimiento imponiendo que un avión debe pernoctar
cada tres dı́as en una estación de mantenimiento. Ellos resuelven este problema con un
método de dos etapas, primero construyen rutas de un dı́a de extensión compuestas por
una secuencia de vuelos, llamadas lı́neas de vuelo (lines of flight-LOF), y después las
unen.
Posteriormente, Clarke, Johnson, Nemhauser, y Zhu (1997) formulan el AMRP como

un problema del vendedor viajero asimétrico (ATSP). Dicha formulación busca encontrar
la asignación de aviones que maximiza el valor de las conexiones entre vuelos, es decir,
el beneficio asociado a que un mismo avión realice dos vuelos de forma consecutiva con-
siderando restricciones asociadas a un tiempo máximo sin mantenimiento. Resuelven el
problema mediante relajación lagrangeana. Dicho enfoque de ATSP también es utilizado
por Boland, Clarke, y Nemhauser (2000).
12
Gopalan y Talluri (1998a) utiliza el mismo concepto de lı́neas de vuelo de Kabbani y

Patty (1992) para formular el problema de AMRP donde cada avión debe recibir manteni-
miento nocturno cada k dı́as (k-AMRP) y desarrollan un algoritmo eficiente para encontrar
soluciones factibles para el caso de tres dı́as. Posteriormente, Talluri (1998) muestra que
el 4-AMRP agregando un tipo de mantenimiento que denominan balance-check es N P-
completo, pero si este mantenimiento adicional se elimina, incluso el 4-AMRP puede ser
resuelto en tiempo polinomial.
Por último, Liang, Chaovalitwongse, Huang, y Johnson (2012) presentan una nueva
representación de red compacta para el AMRP y formulan un modelo de programación
matemática entera (MIP) para resolverlo. Dicha formulación considera un número máxi-
mo de aviones que pueden recibir mantenimiento cada dı́a en cada estación y constituye
el estado del arte en cuanto a formulación del AMRP desde un punto de vista estratégico-
táctico sin integrar otras etapas de planificación. Es importante recalcar que todos los tra-
bajos sobre el AMRP desarrollados hasta el momento solo consideran el mantenimiento
de una forma general, es decir, que cada avión debe pasar cada k dı́as por una estación de
mantenimiento para que se le realice un conjunto de tareas definidas por la Check-A, sin
considerar el detalle de tiempos y tareas adicionales que cada avión requiere. Lo anterior,
se debe a que el AMRP es un problema táctico que permite garantizar la factibilidad de
una flota para cubrir los vuelos planificados y satisfacer los requisitos de mantenimiento
generales (Liang et al., 2015).
En la Tabla 2.2 se clasifica los trabajos revisados sobre AMRP tomando en cuenta las
siguientes categorı́as: inclusión explı́cita de mantenimiento en el AMRP; planificación de
mantenimiento considerando solo chequeos periódicos (CH); e inclusión de número de
aviones máximo que las instalaciones permiten o capacity constraint (CC).
2.1.1. Integración de etapas en la planificación de aerolı́neas
Otro forma de planificación aérea desarrollada en la literatura de los últimos 20 años

consiste en integrar etapas, es decir, resolver simúltaneamente dos o más etapas de las
13
Tabla 2.2. Trabajos revisados sobre ARP/AMRP
Trabajo AMRP CH CC
Feo y Bard (1989) X X X
Daskin y Panayotopoulos (1989)
Kabbani y Patty (1992) X X
Clarke et al. (1997) X X
Gopalan y Talluri (1998a) X X X
Talluri (1998) X X X
Boland et al. (2000) X X
Liang et al. (2012) X X X
definidas anteriormente buscando evitar potenciales soluciones subóptimas de un enfoque

secuencial y aprovechar las mejoras existentes en capacidad de cómputo (hardware) y
algoritmos de optimización (software). Desaulniers, Desrosiers, Dumas, Solomon, y Sou-
mis (1997) son los primeros en estudiar el problema de asignación de flota y ruteo de
aviones de manera conjunta. Posteriormente, Barnhart, Boland, et al. (1998) introduce el
concepto de string, que corresponde a una secuencia de vuelos conectados que empieza
y termina en una estación de mantenimiento por lo que respeta la conservación de flujo y
garantiza la factibilidad respecto al mantenimiento. Dicho concepto se utiliza para desarro-
llar un modelo que resuelve simúltaneamente el AMRP y la asignación de flota mediante
branch-and-price (Barnhart, Johnson, Nemhauser, Savelsbergh, y Vance, 1998). Ioachim,
Desrosiers, Soumis, y Bélanger (1999), Haouari, Aissaoui, y Mansour (2009), Haouari,
Sherali, Mansour, y Aissaoui (2011), Zeghal, Haouari, Sherali, y Aissaoui (2011) y Liang
y Chaovalitwongse (2013) también formulan diferentes modelos para integrar el problema
de flota y ruteo incorporando restricciones de mantenimiento de los aviones, a excepción
de Ioachim et al. (1999) que no considera el mantenimiento.
Otras etapas del proceso han sido integradas con el AMRP. Cordeau, Stojković, Sou-
mis, y Desrosiers (2001), Cohn y Barnhart (2003), Mercier, Cordeau, y Soumis (2005),
Mercier (2008), Dı́az-Ramı́rez, Huertas, y Trigos (2014) y Ben Ahmed, Zeghal Man-
sour, y Haouari (2018) estudian modelos integrados de AMRP con la calendarización
de tripulación buscando evitar que los tripulantes cambien de avión excesivamente. Estos
14
desarrollan una solución considerando aviones genéricos, a diferencia de Ruther, Boland,

Engineer, y Evans (2017) que genera las rutas para cada avión individualmente (matrı́cu-
la) respetando requerimiento de mantenimiento particulares. A su vez, Klabjan, Johnson,
Nemhauser, Gelman, y Ramaswamy (2002) y Mercier y Soumis (2007) incorporan la po-
sibilidad de cambiar el inicio de cada vuelo dentro de una ventana de tiempo. En tanto,
Dı́az-Ramı́rez, Huertas, y Trigos (2013) planifican conjuntamente la generación de vue-
los con el ruteo para una flota homogénea. S. Yan y Tseng (2002) consideran una flota
heterogénea, pero no incorporan restricciones asociadas al mantenimiento. Sherali, Bae,
y Haouari (2013) abordan el problema de asignación de flota y ruteo de aviones de forma
integrada, permitiendo, además, modificar la hora de cada vuelo.
Papadakos (2009) es el primero integra tres etapas del proceso. Dicho trabajo planifica
conjuntamente la asignación de flota, AMRP y los turnos de las tripulaciones. Cacchia-
ni y Salazar-González (2017) integra los mismos problemas en una nueva formulación
y propone dos métodos exactos de resolución, los cuales implementa para resolver una
instancia real de un operador regional.
Pita, Barnhart, y Antunes (2013) presentan un MIP que integra la generación de vuelos
con la asignación de flota buscando maximizar las ganancias tomando en cuenta los costos
asociados a las demoras tanto de los aviones como pasajeros. Por último, Sandhu y Klabjan
(2007) y Özener, Örmeci Matoğlu, Erdoğan, Haouari, y Sözer (2017) plantean el problema
integrado de asignación de flota y creación de turnos para las tripulaciones, garantizando
factibilidad en el ruteo sin considerar el mantenimiento.
En la Tabla 2.3 se detalla una clasificación de los trabajos sobre integración de etapas
tomando en cuenta las siguientes categorı́as: inclusión de FS; inclusión de FA; inclusión
de CS; inclusión del AMRP; planificación de mantenimiento considerando solo chequeos
periódicos (CH); planificación de mantenimiento considerando tareas de forma individual
(TK); e inclusión de número de aviones máximo que las instalaciones permiten o capacity
constraint (CC). El asterisco (*) representa que la categorı́a es abordada, pero de forma
parcial.
15
Tabla 2.3. Trabajos revisados sobre integración de etapas
Mantenimiento
Trabajo FS FA CS AMRP CC
CH TK
Desaulniers et al. (1997) X* X X
Barnhart, Boland, et al. (1998) X X X X
Ioachim et al. (1999) X X
Cordeau et al. (2001) X X X
Klabjan et al. (2002) X* X X
S. Yan y Tseng (2002) X X X
Cohn y Barnhart (2003) X X X
Mercier et al. (2005) X X X
Mercier y Soumis (2007) X* X X X
Sandhu y Klabjan (2007) X X
Mercier (2008) X X X
Haouari et al. (2009) X X X
Papadakos (2009) X X X X
Haouari et al. (2011) X X X
Zeghal et al. (2011) X X X
Dı́az-Ramı́rez et al. (2013) X X X
Liang y Chaovalitwongse (2013) X X X X
Pita et al. (2013) X X
Sherali et al. (2013) X* X X X
Dı́az-Ramı́rez et al. (2014) X X X
Cacchiani y Salazar-González (2017) X X X X
Özener et al. (2017) X X
Ruther et al. (2017) X X X
Ben Ahmed et al. (2018) X X X
2.1.2. Proactividad con respecto a disrupciones
La operación aérea está expuesta a múltiples disrupciones en la operación, y distintos

trabajos se han enfocado en realizar una planificación robusta preparada para absorber de
mejor forma estas contingencias. Rosenberger, Johnson, y Nemhauser (2004) formulan un
modelo de asignación de flota que aumenta el número de ciclos cortos, es decir, buscan
formar secuencias cortas de vuelos que comienzan y terminan en el mismo aeropuerto para
reducir el impacto en la red al cancelar un vuelo. Sin embargo, los enfoques más estudiados
para dar robustez a la planificación se han centrado en la programación de los vuelos
16
(Ahmadbeygi, Cohn, y Lapp, 2010; Dickson, 2013; Jiang y Barnhart, 2013; Lee, Lee, y
Tan, 2007; Schaefer y Nemhauser, 2006; Sohoni, Lee, y Klabjan, 2011) y la modificación
de los ruteos de los aviones para evitar la propagación de demoras (Borndörfer, Dovica,
Nowak, y Schickinger, 2010; Liang et al., 2015; Marla, Vaze, y Barnhart, 2018; C. Yan y
Kung, 2016), como también una combinación de ambas (Ben Ahmed, Ghroubi, Haouari,
y Sherali, 2017; Ben Ahmed, Zeghal Mansour, y Haouari, 2017; Burke et al., 2010; Lan,
Clarke, y Barnhart, 2006).
Shebalov y Klabjan (2006), Yen y Birge (2006), Tekiner, Birbil, y Bülbül (2009) y
Muter et al. (2013) proponen distintas formas de abordar el problema de crew scheduling-
crew pairing de forma robusta. Shebalov y Klabjan (2006) se enfoca en maximizar las
tripulaciones que pueden ser intercambiadas, Yen y Birge (2006) en minimizar las de-
moras propagadas por tripulaciones que deben cambiar de avión, Tekiner et al. (2009) y
Muter et al. (2013) buscan crear calendarios que pueden manejar de mejor manera vuelos
adicionales.
Otros trabajos integran más de una etapa de la planificación de forma robusta, buscan-
do realismo y reducir costos. Cadarso y Marı́n (2013), Kenan, Jebali, y Diabat (2017) y
Cadarso y de Celis (2017) integran las etapas de planificación de vuelos y asignación de
flota, Gao, Johnson, y Smith (2009) asignación de flota con calendarización de tripulacio-
nes, Weide, Ryan, y Ehrgott (2010) ruteo de aviones y calendarización de tripulaciones,
Dunbar, Froyland, y Wu (2014) ajusta la planificación de vuelos, ruteo de aviones y calen-
darización de tripulaciones, y Jamili (2017) integra planificación de vuelos, asignación de
flota y ruteo de aviones.
Por último, el único trabajo que aborda el ruteo y mantenimiento de forma robusta es
Lapp y Cohn (2012). Ellos aumentan la probabilidad de cumplir con el mantenimiento de
los aviones mediante la modificación de las secuencias de vuelo diarias (LOFs) ya gene-
radas para ser asignadas a cada avión. Este enfoque busca alterar las LOFs planificadas
para crear un ruteo que ante disrupciones en la operación pueda garantizar, mediante deci-
siones menores, el mantenimiento a cada avión. Para esto, solo considera que el requisito
17
de mantenimiento es similar a exigir que cada avión debe pernoctar en una estación de
mantenimiento cada siete dı́as, sin considerar el tiempo de ejecución del mantenimiento
ni tareas adicionales que cada avión requiere.
En la Tabla 2.4 se muestra la clasificación de los trabajos sobre robustez tomando en

cuenta las siguientes categorı́as: inclusión de FS; inclusión de FA; inclusión de CS; inclu-
sión del AMRP; planificación de mantenimiento considerando solo chequeos periódicos
(CH); e inclusión de número de aviones máximo que las instalaciones permiten (CC). El
asterisco (*) representa que la categorı́a es abordada, pero de forma parcial.
2.2. Planificación aérea a nivel operacional
El AMRP es resuelto con varios meses de anticipación por lo que ignora el detalle de
los requerimientos de mantenimiento y considera solo uno o dos de los mantenimientos
primarios que se deben realizar periódicamente; estos corresponden a Check-A y Check-B
del manual de mantenimiento de cada avión. Como resultado, esos planes frecuentemente
son modificados por el personal encargado de las operaciones, quienes se ven obligados a
desarrollar rápidos métodos de resolución diaria para planificar los requerimientos detalla-
dos de mantenimiento (Sarac, Batta, y Rump, 2006). Esta planificación de mantenimiento
de corto plazo desagregada en tareas, comúnmente recibe el nombre de mantenimiento en
lı́nea (Van den Bergh, De Bruecker, Beliën, y Peeters, 2013) e interactúa con el proceso
de asignación de aviones (matrı́culas) a los vuelos dentro del nivel operacional, tal como
lo muestra la Figura 2.2
La consideración de restricciones de mantenimiento es crı́tica dentro de la planifica-

ción operativa de una aerolı́nea, ya que prescindir de ellas puede provocar costosas can-
celaciones de vuelos y fuertes alteraciones a la operación (Biró, Simon, y Tánczos, 1992;
Sriram y Haghani, 2003). Por lo anterior, es relevante modelar la interacción existente en-
tre la planificación de mantenimiento y la asignación de aviones o matrı́culas a un nivel
operacional para obtener soluciones compatibles con la operación diaria. El trabajo de El
18
Tabla 2.4. Trabajos revisados sobre robustez
Trabajo FS FA CS AMRP CH TK CC
Rosenberger et al. (2004) X
Schaefer y Nemhauser (2006) X
Lan et al. (2006) X X X
Shebalov y Klabjan (2006) X
Yen y Birge (2006) X
Lee et al. (2007) X
Tekiner et al. (2009) X
Gao et al. (2009) X X
Ahmadbeygi et al. (2010) X
Borndörfer et al. (2010) X X X
Burke et al. (2010) X X X
Weide et al. (2010) X X X
Sohoni et al. (2011) X
Lapp y Cohn (2012) X X
Dickson (2013) X
Jiang y Barnhart (2013) X
Muter et al. (2013) X
Cadarso y Marı́n (2013) X X
Dunbar et al. (2014) X* X X X
Liang et al. (2015) X X X
C. Yan y Kung (2016) X X
Ben Ahmed, Zeghal Mansour, y Haouari (2017) X X*
Ben Ahmed, Ghroubi, et al. (2017) X X X
Kenan et al. (2017) X X
Cadarso y de Celis (2017) X X
Jamili (2017) X X X*
Marla et al. (2018) X X
Moudani y Mora-Camino (2000) es el primero en explorar una interacción de este tipo y

ratifica la necesidad de avanzar en literatura al respecto.
2.2.1. Operational aircraft maintenance routing problem (OAMRP) y Tail assignment

problem (TAP)
Sriram y Haghani (2003) es el primer trabajo que, además de abordar el AMRP, formu-
la un modelo operacional de re-ruteo de aviones junto con planificación de mantenimiento
19
Figura 2.2. Esquema de planificación aérea operacional

Fuente: Adaptado de Lapp y Cohn (2012) y Liang et al. (2015)
considerando las Checks (A y B) en términos de las horas de vuelo acumuladas. Para esto
considera LOFs de un dı́a de duración y el mantenimiento como la necesidad de pernoctar
en una estación de mantenimiento, pero no proporciona un método eficiente de solución
para el problema operacional dada su dificultad.
Sarac et al. (2006) define y aborda por primera vez el Operational aircraft routing
problem-OAMRP. Este problema corresponde a determinar un ruteo de aviones válido
desde un punto de vista operacional, es decir, a nivel diario considerando las caracterı́sticas
de cada avión a nivel individual e incorporando que algunos aviones deben terminar en una
estación de mantenimiento al final de dicho dı́a. En particular, el objetivo es minimizar las
horas de vuelo no utilizadas antes de un mantenimiento sujeto a restricciones de capacidad
(recursos y número de aviones) por estación-dı́a. El problema es formulado como set-
partition y resuelto mediante branch-and-price.
En paralelo, Grönkvist (2005) formula el Tail assignment problem-TAP, que es prácti-

camente idéntico al OAMRP siempre y cuando el OAMRP identifique explı́citamente a
cada avión y no considere un avión genérico. Por lo anterior, en la literatura se utiliza
indistintamente los conceptos de OAMRP y TAP. El TAP es un problema entero de flujo
20
en redes multi-commodity a mı́nimo costo con restricciones de recursos y es N P-hard

(Grönkvist, 2006). Otten, Grönkvist, y Dubhashi (2006) y Gabteni y Grönkvist (2009)
desarrollan métodos como depth-first backtrack search, generación de columnas y cons-
traint programming para resolver el TAP.
Murat Afsar, Espinouse, y Penz (2007) y Murat Afsar, Espinouse, y Penz (2009) ex-
tienden el OAMRP a una operación dinámica bajo un esquema de horizonte rodante de
una semana con el mismo objetivo de Sarac et al. (2006). Para esto, considera máximo
un mantenimiento por avión por semana y no considera restricciones de recursos, solo un
número máximo de aviones a mantener cada noche. Desarrollan heurı́sticas de dos etapas
en que primero rutean los aviones que deben recibir mantenimiento esa semana (crı́ticos)
y posteriormente distribuyen de forma balanceada los vuelos restantes entre los aviones
no crı́ticos. Este enfoque posteriormente es extendido por Orhan, Kapanoglu, y Karakoc
(2011), pero no es proactivo con respecto a los potenciales mantenimientos de las semanas
futuras por lo que es miope.
Haouari et al. (2013) presentan una formulación compacta para el OAMRP diario,
considerando que los vuelos se repiten todos los dı́as y que los aviones deben visitar una
estación de mantenimiento antes de cumplir un máximo de horas de vuelo, despegues y
dı́as desde el mantenimiento anterior. Además, incluye que cada mantenimiento (Check-
A) tiene un tiempo de ejecución (fijo) y un número máximo de aviones que pueden recibir
mantenimiento diariamente.
Basdere y Bilge (2014) estudian el OAMRP con y sin restricciones de capacidad en

el mantenimiento. Ellos proponen un modelo de flujo multi-commodity semanal con el
mismo objetivo de Sarac et al. (2006) y teniendo en cuenta únicamente Check-A. Al igual
que Haouari et al. (2013) considera un tiempo fijo de mantenimiento, ocho horas en este
caso, un lı́mite en los aviones que simultáneamente pueden recibir mantenimiento por dı́a
y construye las LOFs mediante la asignación de conexiones entre vuelos a los aviones.
Ajusta dinámicamente las horas de vuelo acumuladas dı́a a dı́a mediante un enfoque de
horizonte rodante.
21
Al-Thani, Ben Ahmed, y Haouari (2016) proponen un modelo de programación entera

mixta (MIP) que maximiza la utilización de las horas de vuelo antes de mantenimien-
to. Para resolver el problema, desarrollan una meta-heurı́stica del tipo very large-scale
neighborhood search (VLNS). Khaled, Minoux, Mousseau, Michel, y Ceugniet (2018)
desarrollan un modelo compacto para el TAP incorporando restricciones máximas de ho-
ras de vuelo, ciclos y dı́as asociadas al mantenimiento nocturno del tipo Check-A, como
también restricciones de capacidad de aviones por estación. Este modelo permite resolver
eficientemente instancias de tamaño real a optimalidad por medio de los solvers comer-
ciales.
Otra opción para satisfacer requerimientos de mantenimiento en un enfoque opera-

cional es hacerlo implı́citamente a través de restricciones que miran al futuro (look-ahead
maintenance constraints). Maher, Desaulniers, y Soumis (2018) asignan aviones (matrı́cu-
las) a rutas de un dı́a de extensión con el objetivo de cumplir las restricciones de mante-
nimiento explı́citamente para el dı́a actual e implı́citamente para los dos dı́as siguienes.
Para el dı́a actual, busca asignar cada avión que requiere mantenimiento (avión crı́tico) a
una LOF que termina en una estación de mantenimiento (MLOF). Para los siguientes dos
dı́as, busca asegurar que cada dı́a desde cada estación existan tantas MLOFs como avio-
nes crı́ticos comienzan el dı́a allı́. Como regularmente existen perturbaciones que afectan
la operación y un avión puede terminar en un lugar diferente al planificado originalmen-
te, incorporan un conjunto adicional de LOFs para reducir el número de mantenimientos
incumplidos. Para resolver lo anterior, utilizaron branch-and-price.
Últimamente se ha estudiado cómo planificar el mantenimiento en términos de tareas

individuales y no paquetes de tareas como las Check-A (Ruther et al., 2017). Papakos-
tas, Papachatzakis, Xanthakis, Mourtzis, y Chryssolouris (2010) desarrolla una metodo-
logı́a para planificar las actividades de mantenimiento en lı́nea durante el turn-around
time (TAT) entre vuelos de un dı́a, que consiste en un análisis multicriterio de un conjunto
de planes de mantenimiento alternativos, generados para distribuir las tareas de mante-
nimiento acorde a los recursos de los aeropuertos, que tienen una capacidad en término
22
de horas-persona por periodo o turno. Safaei y Jardine (2018) también abordan el man-
tenimiento de cada avión considerando tareas de manera individual, con un tiempo de
ejecución fijo, y mediante restricciones de mantenimiento generalizadas buscan asegurar
que las rutas asignadas entreguen las suficientes oportunidades de mantenimiento para
satisfacer la demanda por mantenimiento. Al no poder asegurar la factibilidad de dicho
problema, se minimiza el grado de infactibilidad del mantenimiento, es decir, minimizar
la demanda insatisfecha.
Diversos objetivos se han considerado para el TAP. Lapp y Wikenhauser (2012) buscan
minimizar el consumo de combustible y emisiones. Gavranis y Kozanidis (2015) adaptan
el problema para una operación de aviones de combate que decide qué avión vuela y por
cuánto tiempo, y qué aviones reciben mantenimiento. Keysan, Nemhauser, y Savelsbergh
(2010) incorporan estocasticidad en el OAMRP para una compañı́a que solo realiza vuelos
chárter, es decir, conoce sus vuelos con poca anticipación. Para lo anterior, utiliza un
horizonte rodante de 10 dı́as en que los vuelos son revelados con un dı́a de anticipación.
En dı́as futuros se asume que cada avión volará un número de horas promedio. Buscan
minimizar las horas de vuelo inutilizadas antes de mantenimiento, deciden qué avión opera
cada uno de los vuelos del primer dı́a y qué dı́a pasará por mantenimiento nocturno cada
avión que lo requiera en los próximos 10 dı́as a través de un MIP.
Por último, Ruther et al. (2017) integran el TAP con el ruteo de aviones y calendari-
zación de tripulaciones para su aplicación diaria bajo un horizonte rodante de siete dı́as.
Esto implica tomar decisiones, que tradicionalmente se toman con meses de anticipación,
pocos dı́as antes de la operación. Además, consideran todos los requerimientos de mante-
nimiento de cada avión dentro del horizonte.
En la Tabla 2.5 se detalla la clasificación de los trabajos sobre OAMRP/TAP toman-

do en cuenta las siguientes categorı́as: planificación de mantenimiento considerando solo
chequeos periódicos (CH); planificación de mantenimiento considerando tareas de forma
individual (TK); inclusión de número de aviones máximo que las instalaciones permiten
(CC); inclusión de restricciones de recursos por dı́a (RCD); inclusión de restricciones de
23
recursos por hora (RCH); e inclusión de aparición dinámica de tareas (DT). En ella tam-
bién se incluye este trabajo, cuya contribución se detallará en la sección 2.4.
Tabla 2.5. Trabajos revisados sobre OAMRP/TAP
Mantenimiento Restricciones
Trabajo DT
CH TK CC RCD RCH
El Moudani y Mora-Camino (2000) X
Sriram y Haghani (2003) X X
Grönkvist (2005) X X
Sarac et al. (2006) X X X
Otten et al. (2006) X
Murat Afsar et al. (2007) X X
Murat Afsar et al. (2009) X X
Gabteni y Grönkvist (2009) X
Papakostas et al. (2010) X X
Keysan et al. (2010) X X
Orhan et al. (2011) X
Lapp y Wikenhauser (2012)
Haouari et al. (2013) X X
Basdere y Bilge (2014) X X
Gavranis y Kozanidis (2015) X X X
Al-Thani et al. (2016) X
Ruther et al. (2017) X
Khaled et al. (2018) X X
Maher et al. (2018) X X
Safaei y Jardine (2018) X X
Este trabajo X X X X
2.2.2. Manejo de disrupciones
Las disrupciones en el ámbito operacional son frecuentes, por lo que se han desarrolla-
do trabajos que buscan reducir el efecto de estas disrupciones a través de dos enfoques: el
primero, busca resolver los problemas operacionales anticipando esas disrupciones de mo-
do de planificar de forma robusta; el segundo, una vez que la disrupción sucede, resuelve
algún tipo de problema de recovery (Ball, Barnhart, Nemhauser, y Odoni, 2007).
24
En cuanto a la planificación operacional robusta, Borndörfer et al. (2010) presenta un

TAP de resolución diaria con el objetivo de minimizar la probabilidad de propagación de
demoras durante el ruteo de los aviones, incluyendo las necesidades de mantenimiento de
algunos aviones al final de dicho dı́a. Maher, Desaulniers, y Soumis (2014) desarrollan el
OAMRP para un dı́a de operación buscando minimizar el costo de recuperación en caso
de disrupción. Para ello, plantean un problema estocástico de dos etapas: en la primera
se rutea los aviones de manera de minimizar los costos de ruteo y el número esperado de
mantenimientos incumplidos, es decir, aviones asignados a LOFs que no terminan en una
estación de mantenimiento; en la segunda, para cada uno de los posibles escenarios de
disrupción se busca minimizar los costos de dicha recuperación y el número de cambios
efectuados a la planificación de la primera etapa. Para resolverlo utilizan descomposición
de Benders y generación de columnas, entre otras técnicas. Un enfoque similar para el
mismo problema desarrollan Froyland, Maher, y Wu (2014), pero no consideran el mante-
nimiento dentro de su formulación. Por último, Liang et al. (2015) presenta una extensión
de su planificación robusta táctica, mencionada en la sección 2.1.2, para ser aplicada en
un enfoque operacional mediante el TAP buscando minimizar las demoras propagadas y
los cambios efectuados a la planificación táctica original.
Por más de que la planificación sea robusta, las disrupciones de igual forma pueden
suceder y para enfrentarlas es necesario el recovery. Como ya se mencionó, Maher et al.
(2014) y Froyland et al. (2014) plantean problemas de recuperación como segunda etapa
de modelos estocásticos de dos etapas en que se busca generar ruteos que anticipen las
disrupciones. Argüello, Bard, y Yu (1997) y Eggenberg, Salani, y Bierlaire (2010) tam-
bién se centran en el ruteo de aviones ante disrupciones, pero solo Eggenberg et al. (2010)
considera restricciones de mantenimiento. Rosenberger, Johnson, y Nemhauser (2003) y
Vos, Santos, y Omondi (2015) además de modificar ruteos, deciden los horarios de los
vuelos para mejorar la solución. Santos, Wormer, Achola, y Curran (2017) proponen ges-
tionar el atraso de los vuelos en un hub considerando las conexiones de los pasajeros, los
costos para la aerolı́nea y la capacidad del aeropuerto. Sin embargo, el foco principal en
la literatura de manejo de disrupciones en la operación aérea ha sido integrar los distintos
25
recursos que sufren las disrupciones al análisis (aviones, pasajeros y tripulaciones) en un

mismo problema buscando tomar las decisiones más adecuadas para el sistema completo
(Dickson, 2013; Hu, Song, Zhao, y Xu, 2016; Jozefowiez, Mancel, y Mora-Camino, 2013;
Maher, 2016; Petersen, Sölveling, Clarke, Johnson, y Shebalov, 2012; Sinclair, Cordeau,
y Laporte, 2016; Teodorović y Stojković, 1995; Zhang, Henry Lau, y Yu, 2015; Zhang,
Yu, Desai, y Lau, 2016).
En la Tabla 2.6 se muestra la clasificación de los trabajos sobre manejo de disrupciones

a nivel operacional tomando en cuenta las siguientes categorı́as: inclusión de FS; inclu-
sión de CS; inclusión del OAMRP/TAP; problema robusto (RB); problema de recovery
(REC); planificación de mantenimiento considerando solo chequeos periódicos (CH); pla-
nificación de mantenimiento considerando tareas de forma individual (TK); e inclusión de
número de aviones máximo que las instalaciones permiten (CC). El asterisco (*) represen-
ta que la categorı́a es abordada, pero de forma parcial.
Tabla 2.6. Trabajos revisados sobre manejo de disrupciones a nivel operacional
Mantenimiento
Trabajo FS CS TAP RB REC CC
CH TK
Teodorović y Stojković (1995) X* X X* X
Argüello et al. (1997) X* X
Rosenberger et al. (2003) X X X X
Borndörfer et al. (2010) X X X X
Eggenberg et al. (2010) X X X
Petersen et al. (2012) X* X X X X
Dickson (2013) X* X X X X
Jozefowiez et al. (2013) X* X X X X
Maher et al. (2014) X X X X
Froyland et al. (2014) X* X X
Liang et al. (2015) X X X X
Vos et al. (2015) X X X X
Zhang et al. (2015) X* X X X X
Zhang et al. (2016) X* X X X X
Maher (2016) X* X X X X
Hu et al. (2016) X* X X X X
Sinclair et al. (2016) X* X X X X
26
2.2.3. Planificación de recursos humanos - Asignación de tareas
Dos aspectos relevantes para planificar el mantenimiento de una aerolı́nea son los re-
cursos humanos dedicados a tareas de mantenimiento y la calendarización detallada de
los trabajos. Ası́, se requiere asignar trabajos a cada uno de los técnicos disponibles. Sin
embargo, estos dos aspectos del proceso quedan fuera de los alcances de este trabajo por-
que la contratación de mano de obra se decide con meses de anticipación de manera que
no es posible modificarla diariamente, y la calendarización detallada de los trabajos im-
plica un nivel de desagregación de los recursos que vuelve el problema inmanejable por
lo que no serán revisados. En caso de lectores interesados en estos problemas, Defraeye
y Van Nieuwenhuyse (2016) presentan los trabajos relevantes en la planificación de mano
de obra, Van den Bergh et al. (2013) realizan una revisión que incluye ambos problemas y
Bertsimas, Gupta, y Lulli (2014) presentan un trabajo reciente enfocado en la asginación
de recursos y calendarización de tareas.
En base a la revisión anterior, se identificó que existe una necesidad no satisfecha en

la literatura de integrar a nivel operacional el TAP con el mantenimiento considerando
todos los requerimientos de tareas de manera desagregada y dinámica. Esta contribución
se detalla en la sección 2.4.
2.3. Programación dinámica aproximada (ADP)
Los problemas dinámicos se caracterizan por su dificultad de resolución asociada, prin-

cipalmente, a la gran cantidad de etapas, estados del sistema y decisiones disponibles. Sin
embargo, no considerar dicho dinamismo aumenta los costos y puede generar una solu-
ción infactible. En un problema dinámico, la información relevante para tomar decisiones
es conocida de forma parcial al momento de comenzar a ejecutar una solución y la in-
formación restante es revelada de forma incremental durante la operación. Por ello, una
solución eficiente debe ajustarse periódicamente frente a nueva información revelada, es
decir, debe ser reactiva, y, además ser proactiva frente a potenciales estados de decisión y
27
arribos de información futura. En el caso particular del mantenimiento de aviones, el arri-

bo de tareas obedece a un proceso de llegada estocástico a lo largo del tiempo con fuerte
dinamismo.
Un modelo estándar para representar una toma de decisión dinámica es un proceso

de decisión Markoviano de horizonte finito (Markov decision process-MDP), un modelo
de árbol de decisión para problemas de optimización dinámicos y estocásticos (Bertsekas,
2005). Resolver un MDP de forma exacta es difı́cil por lo que se han desarrollado métodos
de programación dinámica aproximada (Approximate dynamic programming-ADP) para
obtener polı́ticas de solución de alta calidad a un menor esfuerzo analı́tico y computacional
(Powell, 2011).
Dentro de ADP existen distintos tipos de polı́tica, dependiendo del tipo de estrategia a
utilizar. Powell (2011) las clasifica en cuatro grandes categorı́as: Miopes; Lookahead po-
licies; Policy function approximations (PFA); Value function approximations (VFA). Las
polı́ticas miopes son las más simples y consisten en planificar la operación descartando
toda información disponible del futuro. Las polı́ticas de lookahead planifican decisio-
nes del presente optimizando explı́citamente sobre un horizonte truncado que incorpora
información y acciones futuras. Las aproximaciones de polı́ticas (PFA) simplifican el es-
pacio de búsqueda de polı́ticas factibles y optimizan el problema mediante optimización-
simulación. Las aproximaciones a las funciones de valor (VFA) generan una aproximación
del “value-to-go”, o valor futuro resultante al dejar disponible un determinado vector de
recursos para el futuro, por lo que el impacto futuro de una decisión tomada en el periodo
actual que consume recursos se considera mediante una función que valoriza el estado del
sistema posterior a la decisión (Powell, 2011).
Tı́picamente, en problemas combinatoriales de gran tamaño, los tipos de polı́ticas más

utilizadas corresponden a lookahead y VFA por su efectividad y calidad. Novoa y Storer
(2009) utiliza un tipo de polı́tica lookahead llamada rollout, que consiste en reemplazar la
enumeración explı́cita del árbol completo de estados por algún tipo de heurı́stica y utilizar-
la para evaluar el futuro una vez alcanzado un estado. Li y Womer (2015) también utilizan
28
rollout junto a programación de restricciones para mejorar el desempeño de polı́tica basa-

da en una heurı́stica de reglas de priorización al resolver un problema de calendarización
de tareas con estocasticidad en su duración y restricción de recursos. Además, combina
esta polı́tica lookahead con VFA no paramétrico, es decir, que no asume una forma fun-
cional para el valor futuro. En particular, incorporan lookup table para hacer más simple y
eficiente la aproximación.
Yang y Strauss (2017) investiga el problema de la gestión de los despachos a domicilio

y estima el costo de oportunidad asociado a tener agendado el despacho a un cliente de un
área especı́fica en un espacio de tiempo determinado. Para ello utiliza VFA y calcula los
valores a través de un modelo paramétrico que utiliza parte de la información del estado.
Ulmer, Soeffker, y Mattfeld (2018) también utilizan esta técnica para ser proactivo ante el
futuro en un problema de ruteo vehicular con clientes estocásticos. En el mismo problema,
Ulmer, Goodson, Mattfeld, y Hennig (2018) va más allá y combinan esta idea de VFA con
algoritmos rollout obteniendo una polı́tica hı́brida de alta calidad y computacionalmente
manejable que brinda anticipación tanto espacial como temporal a los pedidos y rutas.
En cuanto a las técnicas de ADP en problemas relacionados con planificación aérea, la

literatura es escasa y consiste, principalmente, en el uso de una polı́tica lookahead como
horizonte rodante (HR) (Haouari et al., 2013; Keysan et al., 2010; Murat Afsar et al., 2007,
2009; Ruther et al., 2017). Por lo anterior, existe la oportunidad de contribuir a la literatura
con la incorporación de métodos de mejora al horizonte rodante tradicional y métodos de
ADP hı́bridos para abordar el dinamismo en un problema de planificación aérea.
En la Tabla 2.7 se muestra la clasificación de los trabajos sobre ADP revisados en base
al tipo de polı́tica lookahead considerada y el tipo de VFA considerada. En ella también
se incluye este trabajo, cuya contribución se detallará en la sección 2.4.
29
Tabla 2.7. Trabajos revisados sobre ADP
Lookahead VFA
Trabajo
Rollout HR Paramétrico No paramétrico
Murat Afsar et al. (2007) X
Murat Afsar et al. (2009) X
Novoa y Storer (2009) X
Keysan et al. (2010) X
Haouari et al. (2013) X
Li y Womer (2015) X X
Yang y Strauss (2017) X
Ruther et al. (2017) X
Ulmer, Soeffker, y Mattfeld (2018) X
Ulmer, Goodson, et al. (2018) X X
Este trabajo X X
2.4. Aporte a la literatura
El presente trabajo contribuye a la literatura abordando un problema que dı́a a dı́a de-
ben resolver las aerolı́neas, para esto se incorporan conceptos y técnicas de programación
dinámica en su modelación y resolución. En particular, se busca extender el OAMRP/TAP
presentado originalmente por Sarac et al. (2006) y Grönkvist (2005) e incorporar tareas
de forma individual tal como se mostró en la Tabla 2.5. Esto responde a que el uso de
la clasificación tradicional de mantenimientos (Check A, B, C y D) va en retirada y las
aerolı́neas han adoptado un enfoque de tareas de mantenimiento (Ruther et al., 2017). A
pesar de esto, Safaei y Jardine (2018) señalan que no existen estudios previos que se hayan
enfocado en integrar el TAP con mantenimiento considerando todos los requerimientos de
manera desagregada.
Adicionalmente, para flexibilizar la programación y la utilización de los recursos, este

trabajo permite realizar tareas con diferentes niveles de consumo de recursos por unidad
de tiempo. Por ejemplo, una tarea que requiere seis horas-persona puede ejecutarse en
tres horas por dos técnicos o en seis horas por uno. Todos los trabajos anteriores utilizan
tiempos fijos de procesamiento de tareas.
30
En contraste con Safaei y Jardine (2018), en este trabajo se modela la disponibilidad

de recursos de mantenimiento considerando que los aviones terminan su operación diaria
en distintos horarios y comparten dichos recursos en ciertos periodos. Para lo anterior, se
desagrega los recursos por hora en el caso de la mano de obra y por dı́a para el número
de aviones máximo que las instalaciones permiten. Al igual que en la literatura, se aborda
únicamente el mantenimiento nocturno de manera de reflejar una operación doméstica
tradicional.
Además, en esta tesis se estudia el problema de planificación de mantenimiento de for-

ma dinámica como lo sugieren Murat Afsar et al. (2009) y Safaei y Jardine (2018). Para
ello, se considera que las tareas de mantenimiento son conocidas una vez que son reveladas
por lo que existe incertidumbre respecto a las tareas que deberán ser realizadas a futuro,
aspecto que será incorporado mediante técnicas de ADP. Tal como Ulmer, Goodson, et al.
(2018), se utiliza una combinación de técnicas online (horizonte rodante) y offline (VFA),
para desarrollar una serie de polı́ticas de alta calidad, pero computacionalmente compati-
bles con la operación.
En resumen, las principales contribuciones de este trabajo a la literatura son:
i. Integrar el TAP con la planificación de mantenimiento a un nivel operacional consi-

derando las tareas de mantenimiento de forma desagregada.
ii. Modelar las restricciones de recursos de mantenimiento explı́citamente por hora de
manera de proponer una planificación de mantenimiento factible de realizar.
iii. Desarrollar un método de ADP hı́brido que permite incorporar el dinamismo y la esto-
casticidad del problema para tomar decisiones reactivas frente a la nueva información
revelada y proactivas frente a potenciales estados posteriores del sistema y arribos de
información futura.
iv. Valorar y validar la utilidad de las polı́ticas desarrolladas mediante un caso de estudio
basado en la operación de una aerolı́nea latinoamericana.
v. Obtener lecciones para los tomadores de decisiones con respecto a la anticipación
requerida al realizar tareas, el tipo de tareas que deben ser anticipadas primero, la
31
conveniencia de aumentar los recursos disponibles, el impacto de la integración del

TAP con la planificación de mantenimiento y las economı́as de escala existentes.
32
3. METODOLOGÍA
En esta sección del trabajo se expone una formulación matemática para resolver el
problema expuesto en los capı́tulos anteriores que consiste en integrar la planificación de
mantenimiento con el ruteo de aviones a un nivel operativo considerando tareas de mante-
nimiento de forma desagregada. Consiste en decidir diariamente qué tareas realizar y qué
lineas de vuelo cubrir con cada avión. Se busca minimizar el costo adicional de manteni-
miento, dado por dejar aviones fuera de operación (aircraft on ground-AOG) y por tener
que externalizar ciertas tareas de mantenimiento que no se pudo realizar con recursos pro-
pios. Se considera que las tareas van apareciendo dinámicamente cada dı́a y que existe
incertidumbre respecto al requerimiento de recursos y plazo de ejecución de estas. Para
resolver el problema, se plantean polı́ticas basadas en programación dinámica aproximada
que buscan anticipar esta incertidumbre y trabajar eficazmente con el dinamismo. Estas
polı́ticas son comparadas con un modelo de programación matemática que asume infor-
mación perfecta sobre el arribo de tareas y sus caracterı́sticas para todo el horizonte de
planificación, y con un algoritmo que recrea la polı́tica actual de una aerolı́nea.
En la sección 3.1 se señalan los supuestos planteados y las polı́ticas que buscan dar
solución al problema. En la sección 3.2 se presenta un modelo de programación dinámica
genérico que describe el problema. En la sección 3.3 se formula el modelo de programa-
ción matemática que asume información perfecta. En la sección 3.4 se define una serie
de polı́ticas que permiten resolver el problema dinámico y que serán comparadas con la
polı́tica actual de una aerolı́nea y con el modelo que asume información perfecta. Final-
mente, en la sección 3.5 se presenta el algoritmo de planificación que recrea la polı́tica
actual de una aerolı́nea latinoamericana.
3.1. Supuestos de modelación
A continuación se detallan los supuestos realizados para modelar el problema:

33
i) Toda LOF comienza y termina a una hora en punto, es decir, a las 20:00, 21:00, etc.
Esto permite trabajar con las horas como periodo relevante más pequeño.
ii) Se considera que transcurre un tiempo fijo de una hora entre la base de mantenimiento
y el comienzo o término de una LOF. Este tiempo corresponde al traslado del avión
hasta la base de mantenimiento y es descontado extendiendo las LOFs.
iii) Cada dı́a existe un momento en que todos los aviones están en tierra con sus vuelos
diarios terminados, lo que permite separar las operaciones entre dı́as y que todas las
LOFs puedan ser realizadas por cualquier avión.
iv) El término de un dı́a está dado por la primera LOF que termina su operación dicho
dı́a. Esto permite definir el problema de manera más sencilla.
v) Una tarea planificada siempre es realizada, es decir, desaparece del sistema para el
siguiente dı́a. Esto obedece a que la planificación elaborda es factible de ejecutar con
los recursos disponibles por lo que no debiesen quedar tareas sin ser realizadas.
3.2. Formalización del problema como MDP
El problema estudiado es dinámico y estocástico por lo que es necesario definir es-

te formalmente. Para ello, se considera una aerolı́nea que opera una flota definida por un
conjunto homogéneo de aviones A, donde cada uno ejecuta diarimente LOFs, desde un ae-
ropuerto central (hub) a lo largo de un horizonte de planificación de H dı́as consecutivos
definido por el conjunto T := {1, 2, . . . H}. El horizonte también es dividido en un con-
junto J de periodos más pequeños, tı́picamente horas, en particular J := {1, 2, . . . , 24·H}.
Se asume conocida la información de los horarios de las LOFs con anticipación. Sea It
el conjunto de LOFs del dı́a t ∈ T , donde la aerolı́nea asigna una LOF i ∈ It a cada avión
a ∈ A (asumiendo |A| = |It |). Cada LOF i ∈ It comienza en el hub en la mañana a las
fi ∈ J y termina, en el hub, en la noche a las ei ∈ J. Las operaciones de mantenimiento
de los aviones ocurren en la base de mantenimiento durante el turno nocturno, previo a la
operación del dı́a t.
34
En el dı́a t, se considera un turno de mantenimiento Jt = {θt , . . . , ρt } ⊆ J que em-

pieza cuando termina la LOF más temprana del dı́a t − 1 (θt := mini∈It−1 {ei }) y que
termina cuando comienza la LOF más tarde del dı́a t (ρt := maxi∈It {fi }). Además, defi-
nimos los conjuntos auxiliares de LOFs que comienzan y terminan en una hora especı́fica
+ −
j ∈ J como It,j := {i ∈ It : fi = j} y It,j := {i ∈ It : ei = j}, respectivamente.
Las horas en que terminan las LOFs del dı́a anterior se describen en el conjunto auxiliar
Jt− := {j ∈ Jt : It−1,j
−
6= ∅}, mientras que las horas en que comienzan LOFs se describen
en Jt+ := {j ∈ Jt : It,j
+
6= ∅}. Las horas en que no comienzan ni terminan LOFs, pero se
+ −
puede realizar mantenimiento, se agrupan en Jt0 := {j ∈ Jt : It,j = ∅, It−1,j = ∅}.
Como detalla la Figura 3.1, asignar el avión a ∈ A a las LOFs i1 ∈ It−1 e i2 ∈ It define
su ventana de tiempo en tierra (GTW) {ei1 , . . . , fi2 }, disponible para mantenimiento. Cada
dı́a t, la base tiene una capacidad para trabajar en n < |A| aviones y tiene cp,j ≥ 0
trabajadores disponibles del tipo p ∈ P en la hora j ∈ Jt .
medianoche
Ayer (t − 1) Hoy (t)
tiempo
LOF i1 ei1 mantenimiento dı́a t fi LOF i2 ei2

2
Figura 3.1. Evolución del dı́a t para cada avión
3.2.1. Proceso de arribo de tareas
Las tareas de mantenimiento requeridas para cada aeronave se revelan de la siguiente

manera. En cada dı́a t ∈ T , un conjunto aleatorio Na,t de nuevas tareas para cada avión
a ∈ A es revelado. Cada tarea k ∈ Na,t puede ejecutarse desde el dı́a t hasta el dı́a bk
(inclusive), tiene un tiempo de procesamiento mı́nimo de `k horas y requiere βk,p ≥ 0
horas-persona de cada tipo p ∈ P . Se desconoce la llegada de tareas futuras, pero se
supone que es posible simular realizaciones aleatorias del proceso estocástico.
35
Cada tarea k es crı́tica (γk = 1) o normal (γk = 0). Cuando una tarea crı́tica k queda
pendiente después del turno de mantenimiento del dı́a t = bk , la aeronave relacionada a se
ve forzada a permanecer en tierra (AOG) en el dı́a bk a un costo de cancelación de $α. Una
cancelación permite realizar todas las tareas crı́ticas pendientes en la aeronave a sin gastar
recursos del turno de mantenimiento nocturno. Por el contrario, cuando una tarea normal
vence, la aeronave continúa su operación y la tarea es externalizada a un costo $δk . En
nuestros experimentos asumimos que δk es igual al total de horas de recursos requeridos
P
multiplicado por un costo por hora externalizada δ, es decir, δk := δ · p∈P βk,p .
3.2.2. Estado y espacio de acciones factibles
La dinámica de las decisiones del problema es la siguiente. Cada dı́a t ∈ T , el sistema

se encuentra en el estado St = (mt , Ot ) ∈ St , donde St representa el espacio de estados
factibles. El vector mt := (m1,t , . . . , ma,t , . . . , m|A|,t ) entrega información con respecto al
periodo de inicio del GTW de cada avión, que define la primera hora disponible para man-
tenimiento en el dı́a t por avión. El vector de conjuntos Ot := (O1,t , . . . , Oa,t , . . . , O|A|,t )
modela las tareas abiertas (reveladas y pendientes) para cada avión a antes del manteni-
miento en el dı́a t; se cumple que Oa,t ⊆ ∪tt0 =1 Na,t0 .
El estado inicial del sistema es S1 = (m1 , O1 ), el vector m1 = (d1 ; . . . ; da , . . . ; d|A| )

contiene las horas en que cada avión a termina su operación el dı́a anterior a la planifica-
ción y el conjunto O1 contiene las tareas pendientes conocidas previamente. La factibilidad
de este problema está garantizada, pues en el peor de los casos todos los aviones quedan
fuera de operación y se externalizan todas las tareas.
En el estado St ∈ St y dı́a t ∈ T , el tomador de decisiones ejecuta tres decisiones:
Primero, asigna las LOFs a cada avión, es decir, realiza el tail assignment. De-
finimos la variable binaria xa,i,t ∈ {0, 1} para cada dı́a t, avión a ∈ A y LOF
i ∈ It , la cual es igual a 1 cuando a es asignado a i en el dı́a t y 0, si no. Un
36
AOG ocurre cuando a no es asignado; esta decisión es capturada por la variable

P
ua,t := 1 − i∈It xa,i,t .
Segundo, escoge cuáles aviones reciben mantenimiento. Definimos la variable bi-
naria za,t ∈ {0, 1}, que es igual a 1 cuando a recibe mantenimiento el dı́a t y 0, si
no.
Finalmente, escoge un subconjunto de tareas de mantenimiento abiertas para rea-
lizar en cada avión a asignado a mantenimiento. Definimos yk,t ∈ {0, 1} una
variable binaria, que es igual a 1 si la tarea k ∈ Oa,t es realizada y 0, si no; esta
decisión define si una tarea k vence el dı́a t, capturado en la variable qk ∈ {0, 1}.
El espacio factible de acciones Xt (St ) en el estado St está formalmente definido por

(3.1)-(3.19) como un conjunto de soluciones Xt = (xt , yt , zt , q, ut ) al polı́topo con res-
tricciones de integralidad
n
Xt (St ) := (xt , yt , zt , q, ut ) : ∃ r, w tal que:
X
xa,i,t ≤ 1 ∀i ∈ It (3.1)
a∈A
X
ua,t + xa,i,t = 1 ∀a ∈ A (3.2)
i∈It
qk + yk,t ≥ 1 ∀k ∈ ∪a∈A Oa,t : bk = t (3.3)
ua,t ≥ qk ∀a ∈ A, ∀k ∈ Oa,t : γk = 1 (3.4)
yk,t ≤ za,t ∀a ∈ A, ∀k ∈ Oa,t (3.5)

X
za,t ≤ n (3.6)
a∈A
X
`k · yk,t ≤ wa,j ∀a ∈ A, ∀k ∈ Oa,t (3.7)
j∈Jt
X X
βk,p · yk,t = ra,p,j ∀a ∈ A, ∀p ∈ P (3.8)
k∈Oa,t j∈Jt
37
X
ra,p,j ≤ cp,j ∀p ∈ P, ∀j ∈ Jt (3.9)
a∈A
ra,p,j ≤ wa,j · cp,j ∀p ∈ P, ∀j ∈ Jt , ∀a ∈ A (3.10)
1 = wa,ma,t +1 + ua,t ∀a ∈ A (3.11)

X
wa,j = wa,j+1 + xa,i,t ∀a ∈ A, ∀j ∈ Jt+ \ {ρt } (3.12)
+
i∈It,j
X
wa,ρt = xa,i,t ∀a ∈ A (3.13)
+
i∈It,ρ t
wa,j = wa,j+1 ∀a ∈ A, ∀j ∈ Jt0 (3.14)
xa,i,t ∈ {0, 1} ∀a ∈ A, ∀i ∈ It (3.15)
yk,t , qk ∈ {0, 1} ∀k ∈ ∪a∈A Oa,t (3.16)
ua,t , za,t ∈ {0, 1} ∀a ∈ A (3.17)
ra,p,j ≥ 0 ∀a ∈ A, ∀p ∈ P, ∀j ∈ Jt (3.18)
o
wa,j ∈ {0, 1} ∀a ∈ A, ∀j ∈ Jt . (3.19)
La variable auxiliar binaria wa,j indica si el avión a se encuentra disponible para recibir
mantenimiento en la hora j y la variable auxiliar ra,p,j indica el consumo del recurso p en
la hora j para mantenimiento del avión a.
El conjunto de restricciones (3.1) asegura que ninguna LOF es asignada a más de un

avión. Las restricciones (3.2) aseguran asignar una LOF a cada avión cada dı́a siempre y
cuando no esté fuera de operación dicho dı́a. El conjunto de restricciones (3.3) impone
que todas las tareas que vencen el dı́a t deben ser realizadas o marcadas como vencidas.
El conjunto de restricciones (3.4) impone que si una tarea crı́tica no es realizada, entonces
el avión queda fuera de operación y todas las tareas crı́ticas disponibles ese dı́a para ese
avión son realizadas fuera de operación.
El conjunto de restricciones (3.5) impone que solo se puede ejecutar tareas en avio-
nes asignados a mantenimiento. El conjunto de restricciones (3.6) asegura que se respete
38
la capacidad fı́sica de la base de mantenimiento. El conjunto de restricciones (3.7) ase-

gura que solo se realicen tareas con largo mı́nimo menor o igual al largo del bloque de
mantenimiento.
El conjunto de restricciones (3.8) asegura que la carga de trabajo de tareas planificadas

a cada avión para cada dı́a sea igual a la capacidad total asignada por recurso para ese
avión-dı́a. Las restricciones (3.7) y (3.8) permiten realizar tareas en diferentes niveles de
consumo de recursos por hora. El conjunto de restricciones (3.9) impone que la capacidad
total asignada a los aviones por recurso para cada hora sea menor o igual a la capacidad
disponible en la estación. El conjunto de restricciones (3.10) asegura que a un avión no se
le asigne más capacidad de la disponible y que no se le asigne capacidad en caso de no
estar en mantenimiento.
Las restricciones (3.11)-(3.14) definen el bloque de mantenimiento asignado a cada

avión y son explicadas en detalle en los siguientes párrafos. Por último, las restricciones
(3.15)-(3.19) corresponden a la naturaleza de las variables.
Las restricciones (3.11)-(3.14) fueron modeladas como restricciones de balance de

flujo por avión. La conservación de flujo se ilustra en la Figura 3.2 y en ella cada nodo
representa una hora del GTW del avión a el dı́a t. Los arcos representan las variables que
determinan el bloque de mantenimiento, es decir, el inicio de una LOF o el inicio de un
avión fuera de operación. Las restricciones (3.11) corresponden al balance de flujo en la
hora de inicio del GTW (ma,t ) de cada avión a. Las restricciones (3.12) son el balance de
flujo para cada avión en horas en que comienzan LOFs, a excepción del balance de flujo
para el último nodo de cada dı́a que está modelado en las restricciones (3.13). Por último,
las restricciones (3.14) aseguran la conservación de flujo en los nodos en que es posible
realizar mantenimiento pero no comienzan ni terminan LOFs. Por lo que cada dı́a un avión
puede quedar fuera de operación o estar disponible para operar. Un avión disponible para
operar, puede recibir mantenimiento algunas horas y operar después, o solo esperar en
tierra algunas horas para luego iniciar una LOF.
39
Figura 3.2. Conservación de flujo avión a
3.2.3. Costo diario de operación
El costo incurrido por el sistema en el dı́a t ∈ T esta definido por

X X
C(St , Xt ) = α ua,t + δk · q k . (3.20)
a∈A k∈Oa,t :γk =0
El primer término en el lado derecho de la ecuación (3.20) modela el costo relacionado

con AOGs (vuelos cancelados), mientras que el segundo término modela el costo incurrido
por tareas normales vencidas y externalizadas.
3.2.4. Transiciones de estado
Cuando se toma la acción diaria Xt ∈ Xt (St ) en el estado St = (mt , Ot ), el siguiente

momento de decisión ocurre en el dı́a t + 1 y estado St+1 = (mt+1 , Ot+1 ). Para cada avión
a, su conjunto de tareas pendientes Oa,t+1 := {k ∈ Oa,t : yk,t = 0, bk > t} ∪ Na,t+1 es
actualizado eliminando todas las tareas realizadas o vencidas el dı́a anterior e incluyendo
las nuevas tareas reveladas. Para cada avión a, se actualiza la hora en que está disponible
P
para mantenimiento ma,t+1 := máx{θt+1 ; i∈It ei · xa,i,t } la cual está definida como el fin
de la LOF anteriormente realizada o el inicio del turno en caso de haber estado en tierra.
3.2.5. MDP y ecuaciones de Bellman
Ahora, definimos el problema como un Proceso de Decisión Markoviano (MDP) (Pu-

terman, 2014). El objetivo es encontrar una polı́tica π ∗ = {X1∗ , X2∗ , . . . , XH
∗
} ∈ Π dentro
del conjunto de todas las polı́ticas markovianas y determinı́sticas factibles Π, tal que el
40
costo total esperado sobre todo el horizonte de operación sea el mı́nimo. Formalmente,
nuestro problema es modelado como
" H
#
X
C ∗ (S1 ) = mı́n E C(St , Xtπ (St ))|S1 , (3.21)
π∈Π
t=1
donde S1 es el estado inicial del sistema y la esperanza es con respecto al proceso aleatorio
de arribo de tareas.
Dicha polı́tica óptima resuelve las ecuaciones de Bellman para cada t ∈ T y St ∈ S

definidas como
Vt (St ) = mı́n {C(St , Xt ) + E [Vt+1 (St+1 )|St , Xt ]} , (3.22)

Xt ∈Xt (St )
hP i
H
donde Vt (St ) = E t0 =t C(St0 , Xt∗0 (St0 ))|St es el mı́nimo costo esperado del sistema
con respecto al proceso aleatorio de arribo de tareas a partir del dı́a t en adelante. Este valor
se conoce como cost-to-go. El costo esperado óptimo satisface que C ∗ (S1 ) = V1 (S1 ).
La ecuación (3.22) se resuelve de manera exacta mediante recursión. Sin embargo,

para ello es necesario expandir todo el árbol de decisiones y el problema estudiado sufre de
la maldición de la dimensionalidad (curse of dimensionality). Esto se debe principalmente
a cuatro motivos: la cardinalidad del espacio de estados crece exponencialmente con el
número de tareas y el tamaño de la flota; el espacio de acciones es un conjunto lineal
entero con un número exponencial de puntos factibles; la asignación de las tareas es un
problema de scheduling y este es un problema combinatorial de compleja resolución; y las
expresiones de esperanza son difı́ciles de calcular ya que el número de escenarios crece
de forma exponencial con el número de tareas potenciales por dı́a. De hecho, simplemente
evaluar una polı́tica dada requiere hacer un número exponencial de operaciones en función
del conjunto potencial de tareas. Dadas estas dificultades, esta tesis se enfoca en diseñar
polı́ticas basadas en Approximate Dynamic Programming (ADP).
41
3.3. Modelo determinı́stico integrado de planificación de mantenimiento y TAP
A pesar de que el problema estudiado es dinámico y, por ende, estocástico, es posible

y útil plantear un modelo matemático que planifica con información perfecta, es decir,
se relaja la restricción de acceso a información futura que posee el problema original (a
perfect information relaxation-PIR) (Brown, Smith, y Sun, 2010).
En este caso, cada conjunto Na,t de tareas de mantenimiento reveladas el dı́a t ∈ T y

avión a ∈ A es información conocida al planificar en t = 1. Sea C P IR (N, S1 ) el mı́nimo
costo del problema determinı́stico para una realización N := {Na,t : ∀a ∈ A, ∀t ∈ T } de
las tareas de mantenimiento de los aviones y un estado inicial S1 . Este valor es una cota
inferior (potencialmente inalcanzable) del mı́nimo costo del sistema dinámico-estocástico
ejecutado sobre la realización N . Por lo tanto, se cumple que
C ∗ (S1 ) ≥ EN [C P IR (N, S1 )], ∀S1 ∈ S. (3.23)
En la práctica, se calcula C P IR (N, S1 ) resolviendo el modelo de programación entera-

mixta (MIP) definido por (3.24)-(3.50). Una cota inferior a C ∗ (S1 ) se puede aproximar a
través de simulación de Monte Carlo sobre una muestra Ω de realizaciones del proceso
1
de arribo de tareas, es decir, EN [C P IR (N, S1 )] ≈ |Ω| P IR
P
ω∈Ω C (N (ω), S1 ). Esta cota
entrega un benchmark que permite analizar la calidad de las soluciones obtenidas en el
problema dinámico.
Para formular el MIP, se define el conjunto auxiliar de tareas que se pueden realizar el
dı́a t ∈ T sobre cada avión a ∈ A como Ka,t := {k ∈ ∪tv=1 Na,v : t ≤ bk }; el conjunto de
todas las tareas relacionadas con a como Ka = ∪H
v=1 Na,v ; el conjunto de todas las tareas
K = ∪a∈A Ka ; y el conjunto de dı́as en que es factible realizar la tarea k ∈ Na,t como

Tk = {t, . . . , bk }. Además, se define, en reemplazo de la variable ua,t , la variable binaria
ua,t,j que es igual a 1 cuando a es dejado en tierra (AOG) en el dı́a t a partir de la hora j y
0, si no, pues en este caso es necesario considerar la hora en que el avión queda fuera de
42
operación para mantener la conservación de flujo. Todos los otros parámetros y variables
son definidos de igual manera que en la sección 3.2.
La función objetivo del modelo presentada en la ecuación (3.24) considera las mismas
dos componentes que el problema dinámico, pero expandidas para todo el horizonte de
planificación que se asumira mayor a dos dı́as. En primer lugar, busca minimizar el costo
de dejar fuera de operación aviones y, en segundo lugar, minimizar la carga de trabajo
externalizada, es decir los recursos extra requeridos por tareas normales no realizadas.
Tı́picamente, dejar fuera de operación aviones tiene un costo mucho mayor que cada uni-
dad de recurso extra (α δ).
XX X XX X
mı́n α ua,t,j + δk · q k . (3.24)
q,r,u,w,x,y,z
a∈A t∈T − a∈A t∈T k∈Oa,t :γk =0
j∈Jt−1
Las restricciones del modelo son similares a las del modelo dinámico con la diferencia
de que se debe relacionar el balance de flujo por avión entre dı́as consecutivos y el conjunto
de tareas es conocido para todo el horizonte de operación. Las restricciones del modelo de
información perfecta se presentan en las ecuaciones (3.25)-(3.50).
X
xa,i,t ≤ 1 ∀i ∈ It , ∀t ∈ T (3.25)
a∈A
X
ua,1,da + xa,i,1 = 1 ∀a ∈ A (3.26)
i∈I1
X X
ua,t,j + xa,i,t = 1 ∀a ∈ A, ∀t ∈ T \ {1} (3.27)
− i∈It
j∈Jt−1
X
qk + yk,t ≥ 1 ∀k ∈ K (3.28)
t∈Tk
X X
ua,t,j ≥ qk ∀a ∈ A, k ∈ Ka : γk = 1 (3.29)
t∈Tk j∈J −
t−1
yk,t ≤ za,t ∀a ∈ A, ∀k ∈ Ka , ∀t ∈ Tk
(3.30)
X
za,t ≤ n ∀t ∈ T (3.31)
a∈A
43
X
`k · yk,t ≤ wa,j ∀a ∈ A, ∀k ∈ Ka , ∀t ∈ Tk
j∈Jt
(3.32)
X X
βk,p · yk,t = ra,p,j ∀a ∈ A, ∀p ∈ P, ∀t ∈ T (3.33)
k∈Ka,t j∈Jt
X
ra,p,j ≤ cp,j ∀p ∈ P, ∀t ∈ T, ∀j ∈ Jt (3.34)
a∈A
ra,p,j ≤ wa,j · cp,j ∀a ∈ A, ∀p ∈ P, ∀t ∈ T, ∀j ∈ Jt

(3.35)
1 = wa,da +1 + ua,1,da ∀a ∈ A (3.36)

X
xa,i,1 + ua,1,da = wa,θ2 +1 + ua,2,θ2 ∀a ∈ A (3.37)
−
i∈I1,θ
2
X X
xa,i,t−1 + ua,t−1,j = wa,θt +1 + ua,t,θt ∀a ∈ A, ∀t ∈ T \ {1, 2} (3.38)
− −
i∈It−1,θ j∈Jt−2
t
X
xa,i,t−1 + wa,j = wa,j+1 + ua,t,j ∀a ∈ A, ∀t ∈ T \ {1},
−
i∈It−1,j
−
∀j ∈ Jt−1 \ {θt } (3.39)
X
wa,j = wa,j+1 + xa,i,t ∀a ∈ A, ∀t ∈ T, ∀j ∈ Jt+ \ {ρt }
+
i∈It,j
(3.40)
X
wa,ρt = xa,i,t ∀a ∈ A, ∀t ∈ T (3.41)
+
i∈It,ρ t
wa,j = wa,j+1 ∀a ∈ A, ∀t ∈ T, ∀j ∈ Jt0 (3.42)
xa,i,t ∈ {0, 1} ∀a ∈ A, ∀t ∈ T, ∀i ∈ It (3.43)
yk,t ∈ {0, 1} ∀a ∈ A, ∀k ∈ Ka , ∀t ∈ Tk ,
∀a ∈ A (3.44)
qk ∈ {0, 1} ∀k ∈ K (3.45)
44
ua,t,j ∈ {0, 1} ∀a ∈ A, ∀t ∈ T \ {1},

−
∀j ∈ Jt−1 (3.46)
ua,1,da ≥ 0 ∀a ∈ A (3.47)
za,t ∈ {0, 1} ∀a ∈ A, ∀t ∈ T (3.48)
ra,p,j ≥ 0 ∀a ∈ A, ∀p ∈ P, ∀t ∈ T,
∀j ∈ Jt (3.49)
wa,j ∈ {0, 1} ∀a ∈ A, ∀t ∈ T, ∀j ∈ Jt (3.50)
El conjunto de restricciones (3.25) asegura que ninguna LOF es asignada a más de un

avión. Las restricciones (3.26) y (3.27) aseguran asignar una LOF a cada avión cada dı́a
siempre y cuando no esté fuera de operación dicho dı́a. El conjunto de restricciones (3.28)
impone que todas las tareas deben ser realizadas o marcadas como no realizadas (qk ). El
conjunto de restricciones (3.29) impone que si una tarea crı́tica no es realizada, el avión
queda fuera de operación y todas las tareas crı́ticas disponibles ese dı́a para ese avión son
realizadas.
El conjunto de restricciones (3.30) impone que solo se pueden realizar tareas en avio-
nes que están en mantenimiento. El conjunto de restricciones (3.31) asegura que todos los
dı́as se respete la capacidad fı́sica de la estación de mantenimiento. El conjunto de restric-
ciones (3.32) asegura que solo se realicen tareas con largo mı́nimo menor o igual al largo
del bloque de mantenimiento.
El conjunto de restricciones (3.33) asegura que la carga de trabajo de tareas planifi-

cadas a cada avión para cada dı́a sea igual a la capacidad total asignada por recurso para
ese avión-dı́a. El conjunto de restricciones (3.34) impone que la capacidad total asignada
a los aviones por recurso para cada hora sea menor o igual a la capacidad disponible en la
estación. El conjunto de restricciones (3.35) asegura que a un avión no se le asigne más
45
capacidad de la disponible y en caso de que en esa hora no esté en mantenimiento, no se

le asigne capacidad.
Las restricciones (3.36)-(3.42) definen el bloque de mantenimiento asignado a cada

avión y son explicadas en detalle en los siguientes párrafos. Por último, las restricciones
(3.43)-(3.50) corresponden a la naturaleza de las variables. La variables ua,1,da pueden
declararse como continuas en las restricciones (3.47) porque las restricciones (3.26) las
obligarán a ser binarias.
Las restricciones (3.36)-(3.42) fueron modeladas como un balance de flujo por avión.
Para esto se debe diferenciar el primer y segundo dı́a respecto del resto de los dı́as de
planificación, debido a que cada avión ya tiene asignada una LOF para el dı́a anterior al
comienzo de la planificación. De esta manera, el primero es el único dı́a del horizonte de
planificación en que se conoce la hora de inicio del GTW para cada avión, lo que provoca
que solo existe una variable u para cada avión el primer dı́a. Como el primer dı́a es el
único con una variable u por avión, el balance de flujo en el primer nodo del segundo dı́a
es distinto al de los restantes dı́as por lo que también se debe diferenciar.
Figura 3.3. Conservación de flujo dı́a 1 para un avión cualquiera
La conservación de flujo se ilustra en las Figuras 3.3, 3.4 y 3.5. En ellas, los nodos
representan las horas del turno de mantenimiento de cada dı́a y los arcos representan las
variables de flujo. Todo arco saliente hacia arriba a la derecha de un nodo representa un
comienzo de LOF o avión fuera de operación por lo que dicho arco termina en el siguiente
dı́a. Todo arco entrante desde abajo a la izquierda a un nodo representa un fin de LOF
o avión fuera de operación por lo que dicho arco viene desde el dı́a anterior. Dadas las
46
Figura 3.4. Conservación de flujo dı́a 2 para un avión cualquiera
Figura 3.5. Conservación de flujo dı́a t para un avión cualquiera
caracterı́sticas del problema, siempre se traspasa una unidad de flujo al siguiente dı́a para
cada avión.
Las restricciones (3.36) corresponden al balance del primer nodo del primer dı́a para
cada avión. Las restricciones (3.37) corresponden al balance de flujo en el primer nodo del
segundo dı́a para cada avión. Las restricciones (3.38) corresponden al balance de flujo en
el primer nodo para cada avión a partir del tercer dı́a.
Las restricciones (3.39) son el balance de flujo para cada avión en los nodos en que
terminan LOFs a partir del segundo dı́a, a excepción del primer nodo de cada dı́a que son
abarcados por las restricciones (3.37)-(3.38). Las restricciones (3.40) son el balance de
flujo para cada avión en las horas en que comienzan LOFs, a excepción del balance de
flujo para el último nodo de cada dı́a que se realiza en las restricciones (3.41). Por último,
las restricciones (3.42) aseguran la conservación de flujo en los nodos en que es posible
realizar mantenimiento pero no comienzan ni terminan LOFs.
47
Durante el desarrollo de este trabajo se formularon tres modelos equivalentes al ex-

puesto, pero que fueron desechados en experimentos preliminares por un peor desempeño
computacional. Estos están detallados en el Anexo A.
3.4. Polı́ticas dinámicas de decisión
Dado que no es posible resolver el problema dinámico a optimalidad y que en la reali-

dad tampoco se cuenta con información perfecta, se aplican herramientas de ADP para
obtener polı́ticas heurı́sticas para resolver de forma aproximada la ecuación (3.22).
3.4.1. Miope
En cada dı́a t en el estado St , se obtiene una polı́tica Miope al tomar decisiones con-
siderando la acción óptima Xt para las ecuaciones de Bellman (3.22) asumiendo que el
costo futuro esperado es cero. Es decir, se descarta el cost-to-go y se enfoca únicamente
en minimizar los costos del periodo actual como se detalla a continuación
Vt (St ) = mı́n {C(St , Xt )} . (3.51)

Xt ∈Xt (St )
Una ventaja de una polı́tica miope es que solo requiere resolver un pequeño MIP deter-
minı́stico para cada dı́a y, por lo tanto, su ejecución es relativamente rápida en comparación
con las soluciones proactivas con la planificación futura. Se utiliza esta polı́tica como un
benchmark.
3.4.2. VFA
En vez de simplemente no tener en cuenta el costo futuro esperado de las decisiones

de hoy en (3.22) dado por Qt (St , Xt ) := E[Vt+1 (St+1 )|St , Xt ], un enfoque alternativo es
estimar su valor mediante una función lineal paramétrica dependiente de caracterı́sticas del
48
estado St y de la acción Xt . Formalmente, se utiliza QVt F A (St , Xt ) ≈ Qt (St , Xt ) descrita

en la ecuación (3.52):
X
QVt F A (St , Xt ) = λf · φf (St , Xt ). (3.52)
f ∈F
Cada φf (St , Xt ) modela una caracterı́stica seleccionada f ∈ F del par estado-decisión

(St , Xt ). El vector de caracterı́sticas (F ) se construye de forma que tenga una dimensión
muy inferior al espacio de estados.
En experimentos preliminares, se estudió múltiples conjuntos de caracterı́sticas y ob-

tuvimos los mejores resultados con la carga total de trabajo en tareas normales pendientes
{k ∈ ∪a∈A Oa,t : γk = 0, yk,t = 0} en el dı́a t después de que la decisión Xt es tomada en
el estado St . Lo anterior debido a que una forma de ser proactivos en el problema estudia-
do es realizar tareas con anterioridad a su vencimiento, de manera de anticipar trabajo y
liberar capacidad para tareas que aparecerán en el futuro. En particular, las caracterı́sticas
que se seleccionaron corresponden a la carga de trabajo que se decidió no atender en el
periodo t con vencimiento en cada uno de los cuatro periodos siguientes. Esta función se
ilustra en la ecuación (3.53):
XX X
φf := I(bk − t = f ) · (1 − yk,t ) · βk,p ∀f ∈ {1, 2, 3, 4}. (3.53)
p∈P a∈A k∈Oa,t :γk =0
Se determinó utilizar cuatro periodos debido a que en experimentos preliminares del

modelo determinı́stico con información perfecta se observó que la anticipación al realizar
las tareas era de cuatro periodos o menos en más de un 95 % de los casos.
En cuanto a los parámetros λf , se utilizaron dos estrategias para calibrarlos las que
serán comparadas en el caso de estudio de la sección 4. La primera consiste en determinar
los valores de λf como un porcentaje del costo de una unidad de recurso externalizada (δ);
49
para esto se observó que mientras menos distancia al vencimiento existe, más importante
es la tarea. De esta manera, basándonos en los resultados de los experimentos preliminares
con el modelo determinı́stico y la anticipación con que se realizan las tareas en él, se
determinó utilizar λ = (0, 5·δ; 0, 3·δ; 0, 2·δ; 0, 1·δ) para asimilar un perfil de anticipación
ideal. Se abreviará esta polı́tica como VFA1.
La segunda estrategia para determinar el valor del vector λ consiste en calibrarlo me-
diante regresiones lineales sobre escenarios simulados con la distribución de probabilida-
des de la instancia a resolver. Este proceso se basa en Approximate Value Iteration (AVI)
planteado por Powell (2011). Se comienza con los valores de la primera estrategia y se van
ajustando iterativamente de manera que se minimice el error cuadrático medio con respec-
to al valor estimado mediante simulación de Qt (St , Xt ) para las etapas, estados y acciones
visitadas en cada uno de los escenarios simulados. En particular, el proceso de calibración
consiste en simular R escenarios de la instacia y en cada uno de ellos aplicar diariamente
la polı́tica con el valor de λ obtenido en la iteración anterior. Para esto se considera que
Xtπ (St ) es la decisión en el periodo t basada en la polı́tica π a implementar al encontrarse
en el estado St . A través de la ejecución de la polı́tica se obtiene el costo simulado de
operación Ĉtn de cada dı́a t ∈ T en el escenario n y con ellos se calcula V̂tn , para cada
etapa y escenario, el valor estimado mediante simulación de Qt (St , Xt ). Posteriormente,
se ajustan nuevos valores de λ mediante regresión lineal utilizando la secuencia de pares
estado-valor (Stn , V̂tn ) de todas las etapas y escenarios. Este proceso de calibración se des-
cribe en el Algoritmo 1 y para este trabajo se utilizó R = 50 con un criterio de parada de
mejora menor a 1 % de la función objetivo. Se abreviará esta polı́tica como VFA2.
Un aspecto importante de los métodos de VFA es que tienen carácter de offline ya que
los parámetros de la función que aproxima el cost-to-go están determinados a priori, es
decir, antes de que la ejecución del proceso suceda (Ulmer, Goodson, et al., 2018). Por lo
tanto, los tiempos de cómputo son comparables con la polı́tica miope.
50
Algoritmo 1 Calibración de parámetros VFA

1: Generar R escenarios o réplicas de la instancia a calibrar
2: Inicializar λ0 de acuerdo a criterio experto
3: n ← 1
4: Stop ← F alse
5: i ← 1
6: while Stop == F alse do
7: while n ≤ R do
8: Elegir el escenario n
9: for all t ∈ T do
10: X̄tn = Xtπ (Stn )
11: Ĉtn = C(Stn , X̄tn )
12: end for
13: for all t ∈PTH do n
n
14: V̂t = j=t Ĉj
15: end for
16: n←n+1
17: end while
18: Utilizar la secuencia de pares estado-valor (Stn , V̂tn ) con t ∈ {1, . . . , H} y n ∈
{1, . . . , R} para ajustar nuevos valores de λi mediante regresión lineal
19: if cumple criterio de parada then
20: Stop = T rue
21: else
22: i←i+1
23: end if
24: end while
3.4.3. Horizonte rodante
Una polı́tica de decisión del tipo lookahead alternativa a VFA, es un horizonte ro-
dante (HR) (Powell, 2011). Esta consiste en que en el dı́a t y estado St , se estima un
pronóstico (deterministic forecast) N̄a,t0 para cada conjunto estocástico Na,t0 sobre un ho-
rizonte truncado de R dı́as a futuro comenzando desde el dı́a t + 1. Posteriormente, se
resuelve un problema de horizonte rodante determinı́stico (PHRD) desde el dı́a t a t + R
con Oa,t , N̄a,t+1 , . . . , N̄a,t+R y el estado actual del sistema St como inputs. La acción Xt
planificada para el dı́a t se obtiene de la solución óptima del PHRD, mientras que las
planificaciones para dı́as futuros pronosticados ayudan a estimar costos futuros, pero son
51
descartadas. Finalmente, el sistema avanza al dı́a t+1 y se repite la polı́tica. De esta mane-
ra, una polı́tica HR aproxima el valor de Qt (St , Xt ) con el costo determinı́stico generado
por la solución del PHRD entre los dı́as t + 1 y t + R. La Figura 3.6 ilustra un ejemplo de
horizonte rodante de siete dı́as (R = 6).
tiempo
1 2 3 4 5 6 7 8 9 10
tiempo
2 3 4 5 6 7 8 9 10
tiempo
3 4 5 6 7 8 9 10
Figura 3.6. Ejemplo de horizonte rodante
En el PHRD se resuelve un problema determinı́stico similar al de un tomador de de-

cisiones con información perfecta, pero considerando solo una parte del horizonte de pla-
nificación. Se utilizó un largo de siete dı́as para el horizonte rodante (R = 6), pues las
planificaciones de LOFs en la industria se realizan de manera semanal y cada siete dı́as se
repiten los vuelos a efectuar (Basdere y Bilge, 2014; Ruther et al., 2017). Además, dado
los resultados preliminares del modelo con información perfecta, con un horizonte de una
semana se puede anticipar más de un 99 % de las tareas realizadas.
A diferencia de los métodos de VFA, horizonte rodante es online ya que recalcula su

estimación del costo futuro en cada punto de decisión dependiendo del avance del proceso
estocástico. Sin embargo, es miope frente a potenciales acciones correctivas futuras que
el tomador de decisiones podrı́a ejecutar al observar una realización de incertidumbre
distante del promedio, y aumenta los costos computacionales.
52
3.4.4. Combinación de horizonte rodante con VFA
Dado que VFA es offline y horizonte rodante es online se adoptó lo recomendado

por Ulmer, Goodson, et al. (2018) y Powell (2011) al combinar las dos herramientas de
ADP antes descritas y con ello se obtiene una polı́tica hı́brida que se espera entregue una
solución de mayor calidad que cada una por si sola, sin incrementar en deması́a el costo
de cómputo.
Por una parte, una desventaja de VFA es que impone artificialmente una forma fun-
cional en los costos futuros esperados en función de las caracterı́sticas seleccionadas. Por
otra parte, HR trunca la estimación de los costos futuros esperados en R dı́as y agrupa
realizaciones futuras en un promedio. Por lo tanto, al agregar al PHRD una aproximación
de la función de cost-to-go QVt+R
FA
para estimar los costos futuros esperados a partir del dı́a
t + R + 1 se tienen en cuenta ambos inconvenientes. De esta forma, se estimó los costos
futuros de forma detallada entre t + 1 y t + R, y se aproximó los costos de largo plazo de
forma lineal a través de VFA.
Al igual que en las polı́ticas anteriores, se utilizó siete dı́as para el horizonte rodante
(R = 6) y cuatro dı́as adicionales para la forma funcional del VFA. Además, se conside-
raron los dos métodos propuestos en la sección 3.4.2 para obtener los parámetros de VFA.
El valor de agregar VFA al utilizar un horizonte rodante de siete dı́as debiese ser menor
que agregarlo directamente a un modelo miope como en la polı́tica descrita en la sección
3.4.2. Más aún, el proceso de calibración para los valores de los parámetros de VFA podrı́a
no ser satisfactorio debido a la variabilidad incorporada entre los periodos t + 1 y t + 6.
3.5. Heurı́stica aerolı́nea
Por último, se desarrolló un algoritmo que recrea el proceso de toma de decisiones de

un planificador de mantenimiento en la actualidad con el objetivo de comparar las polı́ticas
anteriormente propuestas con el mecanismo actual de planificación manual.
53
En la actualidad no se considera la asignación simultánea de los aviones a las LOFs y la

planificación del mantenimiento y las decisiones se toman de forma secuencial. Primero se
asignan las matrı́culas a los vuelos y después se planifica el mantenimiento. Sin embargo,
la aerolı́nea busca priorizar a los aviones con mayor carga de trabajos crı́ticos pendientes
por lo que en el algoritmo se asignan los aviones a las LOFs buscando que los aviones más
problemáticos tengan mayor tiempo en tierra.
En cuanto a la planificación de tareas de mantenimiento, esto se realiza desde las tareas

más importantes a las menos y desde los aviones con mayor carga de trabajos a los con
menos. Al planificar el mantenimiento del dı́a t, primero se busca planificar las tareas
crı́ticas que vencen este dı́a pues en caso de que un avión no pueda cumplir con ellas
quedará fuera de operación. En segundo lugar, se planifican las tareas normales que vencen
el dı́a t. En tercer lugar, las tareas crı́ticas prontas a vencer (tres dı́as o menos). Por último,
se planifican tareas normales prontas a vencer. Todo lo anterior se realiza respetando todas
las restricciones de capacidad, tanto en recursos por hora como en número de aviones
por dı́a para asegurar la factibilidad de la solución. El pseudocódigo se encuentra en el
Algoritmo 2.
54
Algoritmo 2 Adaptación de polı́tica aerolı́nea

Entrada: Conjuntos Kt , It y el vector d = (d1 , . . . , da , . . . , d|A| ).
Salida: Asignación de aviones a LOFs y planificación de mantenimiento dı́a t.
1: Ordenar LOFs del dı́a t de acuerdo a su hora de comienzo, de más tarde a más tem-
prano (Iordenados );
2: Ordenar aviones de acuerdo a la criticidad y carga total de tareas que vencen en t, de
más crı́tico a menos crı́tico (Aordenados );
3: Asignar aviones a LOFs de forma ordenada;
4: for all a ∈ Aordenados do
5: if es posible realizar todas las tareas crı́ticas del avión a que vencen en t then
6: Planificar tareas crı́ticas con vencimiento en t y actualizar recursos remanentes;
7: else
8: Avion a fuera de operación en t;
9: end if
10: end for
12: for all k ∈ Oa,t : γk = 0 do
13: if es posible realizar la tarea normal k del avión a que vence en t then
14: Planificar tarea k en el dı́a t y actualizar recursos remanentes;
15: end if
16: end for
17: end for
20: if es posible realizar la tarea crı́tica k del avión a que vence en próximos tres dı́as
then
22: end if
23: end for
24: end for
27: if es posible realizar la tarea normal k del avión a que vence en próximos tres
dı́as then
29: end if
30: end for
31: end for
55
4. CASO DE ESTUDIO Y RESULTADOS
En este capı́tulo, se presenta el caso de estudio y un resumen de los resultados obteni-

dos implementando las polı́ticas propuestas. En la sección 4.1 describimos el proceso de
diseño del caso de estudio y se presenta la metodologı́a de generación de escenarios para
cada instancia del caso de estudio. En la sección 4.2 se presentan los principales resultados
obtenidos para las instancias del caso de estudio.
4.1. Diseño de caso de estudio
Para decidir cuál es la polı́tica más adecuada para planificar el mantenimiento junto a
la asignación de LOFs y probar la calidad de dicha polı́tica es necesario realizar un caso
de estudio que incorpore las caracterı́sticas del proceso de manera adecuada. Para esto se
diseñó un caso base y se modificaron algunos parámetros o caracterı́sitcas de este para
realizar análisis de los resultados y obtener lecciones para el tomador de decisiones.
Un caso corresponde a una configuración de costos, LOFs diarias, número de aviones,

capacidad de base de mantenimiento, recursos y distribución del proceso de arribo de
tareas, mientras que una réplica o escenario corresponde a una realización particular del
proceso estocástico de arribo de tareas de un caso determinado. Para cada uno de los cuatro
casos analizados se generaron 50 réplicas para estimar el costo esperado de cada polı́tica
mediante simulación de Monte Carlo.
Además, impusimos un tiempo lı́mite de 180 segundos para la toma de decisión diaria
de planificación. Esto busca entregar una respuesta rápida y compatible con el horizonte
de planificación operativo. Por último, para todos los análisis se definió un horizonte de
evaluación de 30 dı́as.
56
4.1.1. Caso base
Santiago concentra la operación aérea en Chile, ya que cerca del 94 % de los vuelos
nacionales tienen origen o destino en esta ciudad (Junta Aeronáutica Civil, 2018). Por lo
anterior, el caso o instancia base representa la simulación de la operación y la planificación
de mantenimiento de la flota doméstica de una aerolı́nea basada en Santiago de Chile, para
lo cual se utilizó como base la información de una aerolı́nea real.
4.1.1.1. Número de aviones
Para determinar el número de aviones (|A|) del caso base se utilizó la información
del tamaño de flota doméstica para las principales aerolı́neas que operan dentro de Chile
(JetSmart Airlines, 2018; LATAM Airlines, 2018; SKY Airlines, 2018). Esta informa-
ción es pública y se encuentra resumida en la Tabla 4.1. Debido al crecimiento del tráfico
doméstico en Chile por sobre el 10 % anual (Junta Aeronáutica Civil, 2018) y los requeri-
mientos de la aerolı́nea con la que se trabajó, se decidió utilizar un tamaño de flota de 30
aviones.
Tabla 4.1. Tamaño de flota doméstica aerolı́neas en Chile
Aerolı́nea Tipo de aeronave Número de aviones

LATAM Airlines A320FAM 26
SKY Airlines A320FAM 15
JetSmart Airlines A320FAM 5
4.1.1.2. Capacidad base de mantenimiento
Para determinar el número de aviones máximo que la base de mantenimiento puede

atender cada dı́a, se consultó a la aerolı́nea y se analizó la información de mantenimiento
disponible. Decidimos definir la capacidad de la base de mantenimiento como un porcen-
taje del tamaño de la flota utilizada por la aerolı́nea actualmente.
57
90
Porcentaje de aviones en mantenimiento
80 Capacidad base de mantenimiento
70
Porcentaje de la flota
60
50
40
30
20
10
0
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53
Dı́a
Figura 4.1. Número de aviones en mantenimiento por dı́a
La aerolı́nea informó que la capacidad de la base de mantenimiento es de un 66 % de

su flota, es decir, dos tercios de la flota doméstica puede recibir mantenimiento cada noche.
La Figura 4.1 muestra el porcentaje real de la flota en mantenimiento cada noche para un
periodo de dos meses y en ella se observa que la capacidad ha sido superada en algunas
ocasiones debido a que se han estacionado aviones fuera de las instalaciones propias. Estos
hechos buscan ser evitados y nuestro modelo considera la capacidad de diseño declarada.
4.1.1.3. Recursos
Para cada tipo de recursos la oferta es por hora, la demanda es en horas-persona y

cada tarea declara su duración mı́nima. A partir de lo señalado por la aerolı́nea, se utilizó
dos tipos de recursos medidos en horas-persona (HP): mecánico y aviónico. Lo anterior,
radica en que tı́picamente estos dos tipos de recursos limitan las labores de mantenimiento.
Para definir la disponibilidad de cada uno de ellos, establecimos que el número de horas-
persona disponibles por dı́a es igual a la demanda diaria esperada por cada recurso. En
otras palabras, cada dı́a debe existir un número de horas-persona igual al número de tareas
58
promedio que se generan por avión por dı́a (µ) multiplicado por el número de aviones y
por las horas-persona promedio que demanda una tarea, tal como lo muestra la ecuación
(4.1).
X
cp,j = µ · |A| · Ek [βk,p ] ∀p ∈ P (4.1)
j∈Jt
Tı́picamente, durante un turno la cantidad de trabajadores es constante por lo que la

oferta diaria se reparte equitativamente entre las horas del turno.
En cuanto a las horas-persona por recurso que demanda una tarea, se utilizó una dis-
tribución discreta obtenida a partir de los datos de la aerolı́nea. Esta fue desescalada para
conservar la confidencialidad de la información y su función de probabilidad se muestra
en la Figura 4.2. Como actualmente la aerolı́nea no cuenta con información referente al
tiempo mı́nimo necesario para la realización de cada tarea (`k ), asumimos que una tarea
promedio se puede realizar
en una
hora (H. Salazar, comunicación personal, 21 de abril,
βk,p
2017), por lo que `k = Ek [βk,p ]
.
0,4
Probabilidad
0,3
0,2
0,1
0
1 3 5 7 9 11 13 15 17 19 21 23
HP por tarea
Figura 4.2. Función de probabilidad de HP por tarea
4.1.1.4. LOFs diarias
Para definir la distribución de los horarios de comienzo y fin de las LOFs diarias, se
utilizó la información de todos los aterrizajes y despegues de vuelos domésticos del año
2017 en el aeropuerto de Santiago de Chile. Ambas distribuciones se muestran en la Figura
59
4.3 y a partir de ellas se obtuvieron horarios para todo el horizonte de evaluación. En la

Figura 4.3 se presentan las horas 25, 26 y 27 debido a que existen aviones que terminan
su operación en las primeras horas del siguiente dı́a.
0,3
Inicio
0,25 Fin
Probabilidad
0,2
0,15
0,1
0,05
0
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Hora
Figura 4.3. Distribución horas de inicio y fin LOFs
4.1.1.5. Tareas
Se caracterizó el proceso de arribo de tareas como un proceso Poisson con una media µ
tareas diarias por avión. A partir del análisis de la información de la aerolı́nea se determinó
utilizar µ = 3. Sumado a esto, es necesario definir la criticidad de las tareas para lo que
se definió una probabilidad de 40 % que una tarea sea crı́tica, independiente al proceso de
arribo y basada en los datos de la aerolı́nea.
Además, toda tarea tiene un plazo para ser realizada, este se mide en dı́as y, a partir de
la información de la aerolı́nea, se generaron realizaciones de una variable aleatoria (vk ) con
distribución triangular con parámetros 1, 10 y 30. De esta forma la fecha de vencimiento
de la tarea k que aparece el dı́a t esta dada por la ecuación (4.2):
bk = t + bvk c ∀k ∈ K. (4.2)
60
Debido a que el sistema debe comenzar con tareas reveladas en dı́as anteriores y aún
no realizadas, decidimos iniciar la planificación después de un mes de warm-up en que
las tareas aparecen y solo se realizan el dı́a de su vencimiento. Ası́ al finalizar el periodo
de 30 dı́as, el sistema se encuentra cargado con tareas cuyos vencimientos en su mayorı́a
corresponden a los primeros dı́as tal como se aprecia en la distribución esperada que se
muestra en la Figura 4.4.
8
7
Porcentaje de tareas
6
5
4
3
2
1
0
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Dı́a de vencimiento
Figura 4.4. Distribución vencimiento de tareas iniciales
Además, el valor esperado del número de tareas disponibles al comienzo de la ope-

ración corresponde al valor esperado de vk más 0,5 por utilizar la parte entera de vk en
la definición de bk , multiplicado por el tamaño de la flota y el número esperado de tareas
generadas por dı́a por avión, tal como se detalla en la ecuación (4.3). En ella, η1 , η2 y η3
corresponden a los parámetros de la distribución triangular para el plazo de ejecución de
una tarea (vk ):

η1 + η2 + η3 1
E [Ot=0 ] = + · |A| · µ. (4.3)
3 2
61
4.1.1.6. Costos
Existen dos costos relevantes para el problema: el costo por dejar fuera de operación
un dı́a un avión (α); y el costo por unidad de recurso externalizada (δ). Como se señaló
anteriormente, en la realidad α es varias veces mayor a δ. En particular, nosotros definimos
α = $100.000 y δ = $75.
4.1.1.7. Resumen configuración caso base
En resumen, nuestro caso base considera una flota de 30 aviones, con una base de
mantenimiento capaz de atender 20 aviones por noche, dos tipos de recursos con una
disponibilidad diaria igual a la demanda esperada, LOFs basadas en la operación del aero-
puerto de Santiago de Chile y tareas que arriban de acuerdo a un proceso Poisson con tasa
de 3 tareas diarias por avión. Además, las tareas tienen un plazo de ejecución dado por
una distribución triangular con parámetros 1, 10 y 30; un 40 % de ellas son tareas crı́ticas.
4.1.2. Caso 1: nuevas LOFs
A partir del caso base, se generó un nuevo conjunto de LOFs a partir de la misma
distribución del caso base. Con lo anterior, se modificó la información de LOFs de las 50
réplicas manteniendo todo el resto igual al caso base.
Con este caso se buscó analizar el efecto que tiene en el desempeño de las polı́ticas
un cambio en las LOFs a operar y la sensibilidad de los ponderadores del método de VFA
ante una modificación en las LOFs.
4.1.3. Caso 2: reducción del plazo para realizar tareas
A partir del caso base, se modifica la distribución del plazo para realizar una tarea (vk )
y a partir de ella se genera una nueva realización del proceso de arribo de tareas para cada
una de los 50 réplicas. En particular, se disminuyó el plazo de vencimiento de tareas a la
mitad, es decir, η = (0, 5; 5; 15).
62
Con este caso se buscó determinar el impacto de un menor plazo para la realización de
tareas. Además, esto implica que la planificación de mantenimiento se realiza con menor
información de los dı́as siguientes.
4.1.4. Caso 3: diferentes niveles de saturación
A partir del caso base, solo se modifica la disponibilidad de recursos para comparar
los resultados bajo distintos niveles de saturación del sistema. Como el caso base corres-
ponde a un estado de congestión (saturación de 100 %), se aumenta la oferta para alcanzar
distintos niveles de saturación. En particular se utilizó una saturación de 97, 5 %, 95 %,
92, 5 % y 90 %.
Con este caso se buscó determinar a partir de qué nivel de congestión debiese ser
necesario externalizar trabajos, cómo se comporta la polı́tica propuesta bajo diferentes
niveles de congestión y cuánto mejora el sistema por cada aumento en la oferta.
4.1.5. Caso 4: Planificación de mantenimiento sin integración con TAP
En las mismas réplicas del caso base, se limitan ciertas flexibilidades del problema para
analizar el comportamiento de la polı́tica y los beneficios que se obtienen al considerar
dichas flexibilidades. En particular, se analizaron los beneficios de integrar la planificación
de mantenimiento con el TAP y de resolver el problema de manera centralizada para toda
la flota.
A partir del caso base, se elimina la posibilidad de asignar las LOFs al momento de
planificar, es decir, se fija anticipadamente la LOF que cada avión opera cada dı́a. Para
esto, primero se asignan LOFs (TAP) bajo un escenario promedio de llegada de tareas y
posteriormente se planifica el mantenimiento en cada uno de los réplicas con las LOFs ya
asignadas.
Con este caso se buscó determinar el valor de integrar el TAP a la planificación de

mantenimiento comparado con resolverlo de forma secuencial.
63
4.1.6. Caso 5: Planificación de mantenimiento descentralizada
A partir del caso base, se divide la flota en dos grupos y se limita la posibilidad de
compartir los recursos e intercambiar LOFs con toda flota. Esto es análogo a tener dos
planificadores cada uno encargado de una mitad de la flota y que los recursos sean divi-
didos en un 50 % para cada uno y solo puedan intercambiar las LOFs entre su grupo de
aviones. Además, se analiza cada una de estas limitaciones por si sola (recursos y LOFs).
4.2. Resultados
En esta sección se presentan los resultados de nuestros experimentos computacionales.

En primer lugar se presenta el caso base y el caso 1 con nuevas LOFs para definir la mejor
polı́tica de las propuestas. Posteriormente, se muestran los resultados de los casos 2, 3, 4
y 5.
Para resolver todos los escenarios generados se utilizó el solver Gurobi v7.5.1, en el
lenguaje de programación Python v3.6.3. Se utilizó un notebook con un procesador Intel
Core i7-7500U 2.9Ghz, 16GB de memoria RAM y sistema operativo Windows 10.
4.2.1. Resultados caso base
Para el caso base se generaron en promedio 2.678 tareas que demandaron 26.314 uni-
dades de recurso por réplica. De esta manera obtuvimos los resultados al aplicar cada
una de las polı́ticas descritas en la sección 3.4. Los principales resultados corresponden
al número de aviones fuera de operación promedio (AOG) y las tareas (recursos) venci-
das. Para cuantificar la externalización de tareas, se utilizó el porcentaje de las tareas que

Vencidas
no fueron realizadas y por lo tanto externalizadas, es decir, Realizadas+Vencidas . De
manera análoga se calculó el porcentaje de recursos externalizados teniendo en cuenta los
recursos que las tareas vencidas demandan. Tı́picamente se utiliza únicamente el porcen-
taje de tareas como resultado relevante. Sin embargo, dado que el objetivo es disminuir
64
los costos y estos son proporcionales a los recursos externalizados, se muestran ambos
indicadores.
Una forma de medir la calidad de las polı́ticas propuestas es compararlas con la cota
inferior dada por el modelo de información perfecta (PIM). Dicha comparación se realizó
a través de la diferencia relativa o gap que existe con los resultados de la función objetivo

(3.24) al aplicar las polı́ticas, de manera que gap = Polı́tica PIM
−PIM
. Al modelo de in-
formación perfecta se le impuso un tiempo lı́mite de 10.800 segundos y solo un 30 % de
las réplicas se lograron resolver a optimalidad bajo dicho lı́mite. Sin embargo, se tomó la
última cota inferior en caso de que esto sucediera para mantener su carácter de cota infe-
rior para las polı́ticas. Considerando que puede existir un gap ineludible de información,
se puede estar sobrestimando la diferencia entre las polı́ticas propuestas y la óptima, tal
como se señaló en la sección 3.3.
Tabla 4.2. Resultados caso base (50 réplicas)
Externalizados ( %) Tiempo de cómputo

Polı́tica AOG gap ( %)
Tareas Recursos por dı́a (s)
Miope 12,16 20,97 19,44 3.147,00 0,12
Aerolı́nea 0,02 15,95 14,67 531,52 0,04
VFA1 1,74 4,16 3,67 389,39 0,61
VFA2 0 5,65 5,31 126,32 0,52
HR 0 2,57 2,52 6,66 50,47
HR-VFA1 0 2,44 2,43 2,64 121,66
HR-VFA2 0 2,43 2,45 3,71 116,14
PIM 0 2,33 2,33 0 -
La Tabla 4.2 sugiere que la polı́tica actual de la aerolı́nea descrita en la sección 3.5
presenta un desempeño empı́ricamente superior a la polı́tica miope, pero inferior a todas
las otras polı́ticas en términos de gap. Al utilizar la polı́tica de la aerolı́nea en el caso base
se obtuvo una réplica con un avión fuera de operación. Más aún, el nivel de externalización
alcanzado es de 15,95 % en tareas y 14,67 % en recursos, es decir, una polı́tica intermedia
entre Miope y VFA que se encuentra muy por debajo de las polı́ticas de horizonte rodante
65
o hı́bridas propuestas. Bajo la polı́tica de la aerolı́nea se externaliza un 83 % más de carga

de trabajo que al utilizar una polı́tica hı́brida.
Al aplicar las polı́tica miope y VFA con ponderadores bajo criterio experto (VFA1)
se obtienen aviones fuera de operación, esto sugiere que no debiesen ser consideradas. Al
efectuar el proceso de calibración de ponderadores en VFA2 se evita dejar aviones fuera de
operación y disminuye el gap a 126 %. Comparado con la polı́tica miope, VFA2 reduce el
gap en 24 veces y disminuye el nivel de externalización en más de 3,7 veces, manteniendo
el tiempo de cómputo por decisión bajo un segundo.
Los resultados también señalan que las polı́ticas que incorporan horizonte rodante son
empı́ricamente superiores, pues alcanzan las mayores coberturas de tareas con valores
sobre el 97 % y obtienen resultados cercanos al PIM con gaps inferiores al 4 % en el caso
de las polı́ticas combinadas con VFA. Para dimensionar la eficiencia alcanzada por HR-
VFA1, es necesario mencionar que su diferencia contra PIM representa solo un 1,2 % del
costo de un AOG, es decir, de un avión fuera de operación un dı́a.
Ambas polı́ticas hı́bridas que combinan horizonte rodante con VFA (HR-VFA) son
estadı́sticamente superiores a la polı́tica HR con 95 % de confianza, lo que ratifica la uti-
lidad de aproximar el cost-to-go de dı́as posteriores al HR mediante funciones lineales.
Sin embargo, en este caso el proceso de calibración de los ponderadores de VFA no per-
mite obtener un resultado superior que los valores provenientes del criterio experto. Esto
radica en el hecho de que se busca anticipar el costo futuro de siete periodos más adelante
por lo que existe excesiva variabilidad en dichos periodos que provoca un alto error en la
estimación de las regresiones lineales de la calibración.
Todas las polı́ticas de la Tabla 4.2 toman, en promedio, menos de dos minutos para
planificar el mantenimiento diario. Esto sugiere que son compatibles con la toma de deci-
siones operacionales y, tal como se esperaba, los tiempos de cómputo aumentan a medida
66
que la complejidad de la polı́tica aumenta. Por lo tanto, si la aerolı́nea requiere una de-
cisión instantánea, la polı́tica VFA2 puede ser una excelente candidata. En otro caso, se
recomienda seleccionar HR-VFA1.
Otro aspecto a analizar de la calidad de las polı́ticas formuladas es observar la antici-

pación con que se realizan las tareas. Por anticipación nos referimos a la diferencia entre
el dı́a en que se realiza una tarea y su vencimiento.
80
VFA1
70 VFA2
HR
60 HR-VFA1
HR-VFA2
50 PIM
40
30
20
10
0
0 1 2 3 4 5 6 7
Anticipación (dı́as)
Figura 4.5. Perfil de anticipación de tareas por polı́tica
La Figura 4.5 que muestra el perfil de anticipación de tareas por polı́tica indica que
las polı́ticas que utilizan horizonte rodante logran obtener la proactividad necesaria para
alcanzar una anticipación similar al PIM. Además, la combinación con VFA no altera
fuertemente la anticipación lo que ratifica los resultados anteriores y muestra que un 63 %
de las tareas se realiza el dı́a de su vencimiento, 23 % con un dı́a de anticipación y 8 % con
dos dı́as de anticipación.
67
Sumado a esto, la Figura 4.5 muestra el efecto que tiene calibrar los ponderadores en
las polı́ticas VFA, dismuyendo el porcentaje de tareas que se realiza el dı́a de su venci-
miento desde un 42 % a un 8 % y aumentando las que se realizan con uno, dos o tres dı́as
de anticipación desde 45 %, 11 % y 2 % a 64 %, 22 % y 6 % respectivamente. Esto indi-
ca que la calibración de lo ponderadores en VFA provoca que la planificación el sistema
opere de forma similar a las polı́ticas de horizonte rodante pero con un dı́a de anticipación
para evitar dejar aviones fuera de operación dada la menor información con la que trabaja.
Por último, se ratifica que es marginal el valor de anticipar tareas más allá de una semana,
lo que explica los buenos resultados de una polı́tica de HR considerando 7 dı́as.
4.2.2. Resultados caso 1: nuevas LOFs
La Tabla 4.3 detalla que los resultados obtenidos para el caso 1 siguen las mismas
tendencias que en el caso base. Nuevamente, las mejores polı́ticas son las hı́bridas de
horizonte rodante combinadas con VFA y sus resultados son estadı́sticamente superiores
a una polı́tica de horizonte rodante, al 95 % de confianza. Sumado a esto, los resultados
de ambas polı́ticas hı́bridas no son estadı́sticamente diferentes ni al 80 % de confianza por
lo que se puede señalar que son equivalentes. A pesar de esto, el calibrar los ponderadores
de la polı́tica VFA tiene un alto valor cuando ésta se utiliza aisladamente y no combinada.
Por último, recalcar que el gap obtenido en las mejores polı́ticas es menos de un 2 % del
costo de AOG.
Tabla 4.3. Resultados caso nuevas LOFs (50 réplicas)
Externalizados ( %)
Polı́tica AOG gap vs PIM ( %)
Tareas Recursos
Miope 11,86 20,86 19,30 3.616,84
Aerolı́nea 0,12 16,46 14,97 679,41
VFA1 1,74 4,02 3,52 469,71
VFA2 0 5,64 5,25 163,04
HR 0 2,21 2,22 10,16
HR-VFA1 0 2,04 2,10 4,20
HR-VFA2 0 2,09 2,11 4,86
68
En cuanto a la calibración de los ponderadores utilizados tanto en VFA2 como HR-

VFA2 la Figura 4.6 indica que existen diferencias dependiendo de las LOFs utilizadas.
Sin embargo, la forma de la curva es similar en ambos casos por lo que se mantiene la
lógica de que mientras más alejado se encuentra el vencimiento de la tarea, menor impacto
debiese tener el ponderador. A pesar de esto, en el caso de HR-VFA2 en el caso base esto
no es tan claro y esta curva es prácticamente plana lo que refuerza el hecho de que al
estar aproximando el valor de futuro de un estado tan alejado pueden no tener efecto los
distintos vencimientos de las tareas.
200 80
Caso base HR-VFA2-base
180 Nuevas LOFs HR-VFA2-nuevos
70
160
60
140
Ponderador (λf )
Ponderador (λf )
50
120
100 40
80
30
60
20
40
10
20
0 0
1 2 3 4 1 2 3 4
Dı́as para el vencimiento (f ) Dı́as para el vencimiento (f )
(a) VFA2 (b) HR-VFA2
Figura 4.6. Ponderadores VFA dependiendo de LOFs
A partir de los resultados del caso 1, se ratifica empı́ricamente que las mejores polı́ticas
corresponden a las que consideran horizonte rodante junto a VFA. A pesar de no existir
diferencia estadı́stica entre los resultados de estas dos polı́ticas al 90 %, tanto en el caso
base como caso 1, por mayor facilidad de implementación y menor complejidad decidi-
mos que la mejor polı́tica es utilizar un horizonte rodante de siete dı́as junto a VFA con
69
ponderadores determinados por criterio experto (HR-VFA1). Ésta será la polı́tica utilizada
para obtener los resultados para el caso 3, 4 y 5 expuestos más adelante en este trabajo.
4.2.3. Resultados caso 2: reducción del plazo para realizar tareas
La Tabla 4.4 muestra empı́ricamente que reducir el plazo para realizar tareas baja el
desempeño de las polı́ticas diseñadas, con un aumento del gap con respecto al PIM com-
parado con el caso base para todas las polı́ticas y un aumento de 4 % en el porcentaje de
tareas externalizadas para la polı́tica HR-VFA1. Sin embargo, el nivel de externalización
del PIM también aumenta, a 2,44 %, a pesar de resolver un número similar de réplicas a
optimalidad, por lo que sugiere que la planificación también se vuelve más compleja pa-
ra un tomador de decisiones con información perfecta y el menor desempeño no es solo
atribuible a las polı́ticas propuestas. Además, los métodos más sofisticados (VFA2, HR,
HR-VFA1, HR-VFA2) obtienen menores diferencias en sus resultados lo que sugiere una
menor ganancia al construir herramientas más complejas ya que todas las polı́ticas dispo-
nen de menor información del futuro. Más aún, se mantiene la equivalencia estadı́stica de
las polı́ticas combinadas (HR-VFA). Sin embargo, la superioridad estadı́stica de las polı́ti-
cas combinadas de HR con VFA por sobre el HR por si solo continúa y el gap se mantiene
bajo 8 % para la mejor polı́tica.
Tabla 4.4. Resultados caso tareas más dinámicas (50 réplicas)
Externalizados ( %)
Polı́tica AOG gap vs PIM ( %)
Tareas Recursos
Miope 15,5 20,05 18,92 3.734,22
Aerolı́nea 1,14 11,34 10,66 552,52
VFA1 1,92 4,16 3,68 424,95
VFA2 0 6,04 5,57 126,50
HR 0 2,59 2,78 12,02
HR-VFA1 0 2,53 2,67 7,54
HR-VFA2 0 2,55 2,72 9,58
70
Si a este análisis también se incorpora el comportamiento de la anticipación de tareas

bajo este mayor dinamismo, la Figura 4.7 indica que se obtienen perfiles similares a los
del caso base para cada polı́tica a pesar del mayor dinamismo existente.
80
VFA1
70 VFA2
HR
60 HR-VFA1
HR-VFA2
50 PIM
40
30
20
10
0
0 1 2 3 4 5 6 7
Figura 4.7. Perfil de anticipación de tareas por polı́tica caso más dinámico
4.2.4. Resultados caso 3: diferentes niveles de saturación
Utilizando distintos niveles de saturación la Figura 4.8 (a) indica que, como era de es-
perar, a menor saturación menos recursos deben ser externalizados. Además, la pendiente
de esta curva es más pronunciada a medida que se aumenta la saturación, lo que indica que
el beneficio marginal de aumentar los recursos es mayor cuando más saturado se encuen-
tra el sistema. Por ejemplo, al aumentar los recursos para bajar la saturación de 100 % a
97, 5 % el beneficio es una disminución de 242 HP externalizas. En cambio, cuando se pa-
sa de 92, 5 % a 90 % el beneficio es de 52 HP, a pesar de que el aumento de oferta necesario
para bajar la saturación en este caso es levemente mayor. Lo anterior, permite planificar
recursos de acuerdo a su beneficio. Sumado a esto, al utilizar la polı́tica HR-VFA1 se ob-
tienen resultados cercanos al PIM independiente del nivel de saturación del sistema. Esto
71
se ve reforzado al observar la Figura 4.8 (b) que indica que a pesar del aumento en el gap
absoluto a medida que el sistema se satura, el gap relativo cae consistentemente.
700 20 12
HR-VFA1 gap absoluto
600 PIM gap relativo %
10
Carga externalizada (HP)
15
Gap absoluto (HP)

500
Gap relativo ( %)
8
400
10 6
300
4
200
5
100 2
0 0 0
90 92,5 95 97,5 100 90 92,5 95 97,5 100
Saturación ( %) Saturación ( %)
(a) HP externalizadas vs saturación (b) Gap vs saturación
Figura 4.8. Comparación HR-VFA1 con PIM en diferentes niveles de saturación
Al extender estos resultados y analizar la anticipación de tareas bajo los distintos ni-
veles de saturación se obtiene que a menor nivel de saturación el sistema presente una
mayor capacidad de anticipación disminuyendo el porcentaje de tareas ejecutadas el dı́a
de su vencimiento. Tal como lo indica la Figura 4.9 se baja de más de un 60 % a un 40 %
de tareas realizadas en su vencimiento al disminuir la saturación del sistema. En contraste,
el porcentaje de tareas que se realizan con un dı́a de anticipación se mantiene práctica-
mente constante para todos los niveles de saturación. Además, nuevamente el porcentaje
de tareas realizadas con más de una semana de anticipación es marginal.
Un aspecto interesante de los resultados obtenidos es que la anticipación con que se

realizan las tareas depende del tamaño de estas. En particular, la Figura 4.10 indica que,
independiente del nivel de saturación del sistema, las tareas pequeñas (consumo menor o
igual a 6 HP en total) presentan una anticipación claramente mayor que tareas medianas
(consumo mayor a 6 y menor o igual a 25 HP en total) y grandes (consumo mayor a 25 HP
72
70
Saturación = 90 %
60
Saturación = 92,5 %
Saturación = 95 %
50
Saturación = 97,5 %
Saturación = 100 %
40
30
20
10
0
0 1 2 3 4 5 6 7 8
Figura 4.9. Perfil de anticipación de tareas en diferentes niveles de saturación
70
Pequeñas 70
Pequeñas
Medianas Medianas
60
Grandes 60
Grandes
50 50
40 40
30 30
20 20
10 10
0 0
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
Anticipación (dı́as) Anticipación (dı́as)
(a) Saturación 100 % (b) Saturación 90 %
Figura 4.10. Perfil de anticipación de tareas desagregado por tamaño

73
en total). Además, no resulta relevante diferenciar tareas medianas de grandes en cuanto a

anticipación de trabajo por lo que en caso de contar con capacidad para anticipar trabajo
ésta se debe utilizar preferentemente en tareas pequeñas. Esto se debe a que los excesos de
capacidad que permiten adelantar trabajo son de un tamaño muy reducido y que considerar
las ventanas de tiempo de mantenimiento de cada avión provoca que estos excesos de
capacidad sean aún menores al mirarlos individualmente por avión, lo que implica que las
tareas anticipadas sean en su mayorı́a pequeñas. Por ejemplo, pueden sobrar ocho HP de
un recurso, lo que bajo una mirada diaria permitirı́a anticipar una tarea de dicho tamaño;
sin embargo, si dos aviones que están en mantenimiento solamente tienen acceso a cuatro
HP (de los ocho) cada uno, solo se puede acomodar dos tareas de cuatro HP cada una.
4.2.5. Resultados caso 4: planificación de mantenimiento sin integración con TAP
Al utilizar una asignación de aviones a LOFs basada en un modelo a priori con un

escenario futuro y no permitir la reasignación en la etapa de planificación de manteni-
miento se toma un enfoque secuencial por lo que se obtienen peores resultados tal como
lo demuestra la Tabla 4.5. Es relevante mencionar que el gap en el caso del modelo no in-
tegrado se obtiene con respecto al PIM bajo la misma asignación de LOFs para no incluir
la pérdida por el hecho de que las LOFs están fijas y hacer pareja la comparación.
Tabla 4.5. Resultados caso sin integración (50 réplicas)
Externalizados
Decisiones integradas AOG gap vs PIM ( %)
Tareas Recursos
Sı́ 0 65,28 638,90 2,64
No 0,02 75,12 720,68 2,26
En particular, aumentan 15 % las tareas no realizadas y 13 % los recursos externali-

zados producto de ellas. Además, producto del enfoque secuencial se obtiene un caso de
un avión fuera de operación en una réplica, riesgo asociado a la pérdida de flexibilidad
que puede aumentar fuertemente los costos y ser perjudicial para la operación aérea. Sin
embargo, es importante recalcar que el gap se mantiene en un bajo nivel independiente de
74
si el enfoque es integrado o secuencial. Lo anterior demuestra que la polı́tica es recomen-

dable independiente del enfoque utilizado, pero se sugiere integrar ambos problemas para
bajar la externalización de trabajos.
4.2.6. Resultados caso 5: planificación de mantenimiento descentralizada
Al descentralizar la planificación se consideró dividir en dos grupos la flota para el TAP

y dividir en dos grupos los recursos. La Tabla 4.6 muestra empı́ricamente que separar la
flota en dos grupos solo en lo referente al TAP (2da fila de la Tabla) no afecta los resultados
de la planificación de mantenimiento al utilizar la polı́tica propuesta (HR-VFA1). A pesar
de esto, el gap disminuye levemente producto de que la cota inferior (PIM) aumenta al
agregarle restricciones al modelo original, pero el resultado de la polı́tica se mantiene
igual.
Tabla 4.6. Resultados caso planificación descentralizada para HR-VFA1

(50 réplicas)
Descentralizado Externalizados
AOG gap vs PIM ( %)
TAP Recursos Tareas Recursos
No No 0 65,28 638,90 2,64
Sı́ No 0 63,16 638,36 2,47
No Sı́ 0 115,46 1.110,60 7,32
Sı́ Sı́ 0 180,60 1.743,34 1,67
Además, dividir la flota en dos grupos no afecta, por si sola, a la planificación conser-
vando un nivel de servicio de recursos en 97,57 % e inclusive disminuyendo la externali-
zación levemente. En cambio, separar los recursos disponibles en dos grupos (3ra fila de
la Tabla), con un 50 % cada uno, provoca una caı́da de casi 2 % en el nivel de servicio, lo
que implica un aumento de un 74 % en los recursos externalizados respecto al caso con la
planificación completamente centralizada. Esto muestra que lo relevante en cuanto a cen-
tralización de decisiones en la planificación de mantenimiento es el hecho de compartir
los recursos.
75
Sin embargo, si la división de la flota se realiza en conjunto con la de los recursos

disponibles (4ta fila de la Tabla), la caı́da del nivel de servicio es superior al 4 %. Lo
que implica un aumento de 173 % en los recursos externalizados respecto al caso con la
planificación completamente centralizada y un 57 % más que cuando solo se dividen los
recursos. A pesar de esto, la polı́tica sigue siendo muy cercana al PIM ya que presenta
un gap de solo 1,67 % por lo que la caı́da en los niveles de servicio son producto de la
descentralización impuesta al problema y no de la polı́tica.
Lo anterior evidencia la existencia de economı́as de escala en la planificación de man-

tenimiento, aspecto muy relevante para las aerolı́neas pequeñas ya que deben compartir los
recursos de mantenimiento con otras aerolı́neas para aprovecharlas. Además, se comprobó
que estas sinergias se mantienen a pesar de que cada aerolı́nea decida las asignaciones de
aviones a LOFs de forma independiente.
76
5. CONCLUSIONES
En este capı́tulo se presentan, en la sección 5.1, las conclusiones respecto al objetivo

general de esta tesis y las lecciones obtenidas. En la sección 5.2, se describen futuras lı́neas
de investigación que exploren más allá de los alcances que tuvo nuestra investigación.
5.1. Principales resultados y lecciones
En este trabajo, se presentó un problema de planificación dinámica de tareas de man-

tenimiento de aviones y se verificó que mediante la implementación de técnicas de opti-
mización entera y programación dinámica es posible modelar y resolver el problema obte-
niendo una planificación que usa eficientemente los recursos disponibles y con ello mejora
la fiabilidad de la operación. Además, entrega soluciones en tiempos breves y automatiza
un proceso que demanda gran cantidad de horas-persona.
En vez de los enfoques tradicionales de optimización estática que construyen planes de

mantenimiento agregados, nuestro problema modela una toma de decisión dinámica con
arribo estocástico de tareas individuales a lo largo del tiempo. Además, en las decisiones
incluimos la asignación de aviones a LOFs y permitimos realizar tareas con diferentes
niveles de consumo de recursos por hora. En particular, se formuló el problema como
MDP y se diseñaron polı́ticas dinámicas basadas en técnicas ADP, tales como horizonte
rodante y aproximación de la función de valor futuro (VFA). Se probaron estas polı́ticas
empı́ricamente sobre un conjunto de instancias simuladas computacionalmente basadas en
la información de una aerolı́nea latinoamericana.
En nuestros experimentos, la incorporación de VFA permite obtener mejores resulta-

dos que la polı́tica actual de la aerolı́nea y la calibración de los ponderadores usados en
VFA permite evitar aviones fuera de operación. Además, la polı́tica de horizonte rodante
para este problema empı́ricamente es superior a las polı́ticas de VFA. Se sugiere combi-
nar ambas polı́ticas en polı́ticas hı́bridas que permiten aumentar en un 14 % el nivel de
77
servicio respecto a la polı́tica actual de la aerolı́nea y disminuir en 83 % los recursos ex-

ternalizados. Los tiempos de ejecución de estas polı́ticas, y de las otras, son compatibles
con la operación diaria.
La anticipación de tareas lograda por la polı́tica propuesta se asemeja a un tomador de

decisiones con información perfecta y alcanza un 3 % de gap. Estos resultados se man-
tienen para distintos niveles de saturación del sistema y muestran que la polı́tica funciona
eficientemente independiente del nivel de congestión del sistema.
Además, se mostró empı́ricamente que la integración de la asignación de aviones a

LOFs (TAP) contribuye a realizar una mejor planificación del mantenimiento. En particu-
lar, se obtuvo un aumento de 14 % en los recursos externalizados y un escenario con un
avión fuera de operación al utilizar un enfoque secuencial de resolución.
Respecto a las lecciones relevantes para los tomadores de decisiones, nuestros experi-
mentos sugieren que un alto porcentaje de las tareas deben ser realizadas en su vencimiento
y que si se cuenta con capacidad ociosa para anticipar trabajo ésta debe ser preferentemen-
te usada en tareas de bajo consumo de recursos. Lo anterior es válido sin importar el nivel
de saturación existente en el sistema. Además, a través de un análisis de sensibilidad en los
recursos disponibles se mostró que es posible estimar el beneficio marginal de una unidad
porcentual de recursos extra, en términos de externalización de trabajo, permitiendo eva-
luar las ampliaciones o reducciones de capacidad en función del efecto real en el sistema
comparado con el costo o beneficio de estas.
Adicionalmente, se mostró que una reducción del plazo para realizar tareas de man-
tenimiento afecta negativamente los resultados de todas las polı́ticas producto de la dis-
minución en la información del futuro con la que se cuenta al planificar. Sin embargo, no
cambia la elección de polı́tica óptima entre nuestras candidatas.
Por último, se comprobó la existencia de economı́as de escala en la planificación de

mantenimiento, por lo que se sugiere que las aerolı́neas relativamente pequeñas compar-
tan los recursos de mantenimiento y mantengan de forma independiente la asignación de
78
aviones a LOFs pues el efecto de centralizar dicha asignación es prácticamente nulo una
vez que se cuenta con la flexibilidad de compartir los recursos de mantenimiento. A pesar
de esto, independiente del tamaño de la operación, la polı́tica propuesta produce resultados
cercanos al modelo de información perfecta.
5.2. Futuras lı́neas de investigación
Este trabajo es el primero que considera la planificación de mantenimiento de aviones

integrada con el TAP tomando en cuenta tareas que llegan dinámicamente a nivel indivi-
dual y existe una serie de posibles extensiones.
En primer lugar, se identificó la necesidad de determinar el largo del horizonte rodante

más adecuado para la planificación de mantenimiento. En este trabajo se utilizó siete dı́as
basado en la periodicidad de los vuelos y trabajos anteriores. Sin embargo, a la luz de
los resultados de anticipación, puede que considerar un horizonte cercano a cinco dı́as
permita obtener niveles de servicio similares o mejores a un menor costo computacional.
En general, depende de las caracterı́sticas particulares de la operación.
En segundo lugar, dado que existen economı́as de escala, resulta interesante determinar
el tamaño de flota óptimo para la planificación de mantenimiento, es decir, hasta qué ta-
maño de flota las economı́as de escala son suficientes y cuándo los costos de coordinación
son mayores a los potenciales ahorros. Además, esto permitirı́a probar la escalabilidad de
la metodologı́a propuesta.
En tercer lugar, en este trabajo se utilizó un modelo determinı́stico de información

perfecta como cota inferior para comparar la calidad de los resultados de las polı́ticas
diseñadas. Sin embargo, este costo puede ser inalcanzable por la existencia de costos de
información. Para solucionar lo anterior, es posible explorar la opción de desarrollar un
modelo estocástico de múltiples etapas para obtener una cota inferior mayor.
79
En cuarto lugar, se puede estudiar como rediseñar las LOFs utilizadas y tal como Lapp
y Cohn (2012) se puede comenzar con las LOFs ya diseñadas e ir agregando nuevas LOFs
para mejorar aún más la planificación de mantenimiento. Para lo anterior, se tendrı́a que
desagregar las LOFs en los vuelos que las componen para generar nuevas secuencias a
partir de ellos. Esto se puede realizar mediante técnicas de branch-and-price (Barnhart,
Johnson, et al., 1998). Además, un rediseño de las LOFs afectarı́a a las tripulaciones por
lo que también se deberı́a considerar dicho impacto. En caso de que las LOFs tengan dema-
siada variabilidad también se puede considerar hacer los plazos de las tareas dependientes
de las horas de vuelo o ciclos.
En quinto lugar, dada la realidad de Chile y de la mayorı́a de los paı́ses sudamericanos,

se consideró un solo hub y una única estación de mantenimiento. Para extender este trabajo
a operaciones mayores se debe considerar múltiples aeropuertos donde terminen las LOFs
e incluir múltiples estaciones de mantenimiento. Sumado a esto, debido al crecimiento
que esta industria presenta en la región, se podrı́a incorporar aviones del mismo tipo, pero
con cabinas diferentes (ya sea distinto número de asientos o configuraciones de estos).
Para esto, se podrı́a considerar un costo de asignar cada avión a cada LOF que incluya los
difentes ingresos y costos de spill asociados a cada asignación, como también se podrı́a
considerar una matriz de compatibilidad entre aviones de manera de intercambiar LOFs
solo entre aviones idénticos.
Por último, se podrı́a distinguir entre la fecha de conocimiento (disclosure) de una

tarea y el primer dı́a en que puede ser ejecutada, para medir el costo de los diferentes
niveles de anticipación en el proceso de llegada de tareas. También se pueden incorporar
disrupciones en las LOFs y/o incertidumbre en los recursos consumidos en la ejecución de
las tareas de mantenimiento para hacer aún más realista la planificación de mantenimiento.
Además, se pueden incorporar recursos con más de una habilidad de manera de agregar
flexibilidad a la planificación.
80
REFERENCIAS
Ahmadbeygi, S., Cohn, A., y Lapp, M. (2010). Decreasing airline delay propagation by
re-allocating scheduled slack. IIE Transactions (Institute of Industrial Engineers), 42(7),
478–489. doi: 10.1080/07408170903468605
Al-Thani, N. A., Ben Ahmed, M., y Haouari, M. (2016). A model and optimization-
based heuristic for the operational aircraft maintenance routing problem. Transportation
Research Part C: Emerging Technologies, 72, 29–44. Descargado de http://dx.doi
.org/10.1016/j.trc.2016.09.004 doi: 10.1016/j.trc.2016.09.004
Argüello, M. F., Bard, J. F., y Yu, G. (1997). A GRASP for aircraft routing in response
to groundings and delays. Journal of Combinatorial Optimization, 1(3), 211–228. doi:
10.1023/A:1009772208981
Ball, M., Barnhart, C., Nemhauser, G., y Odoni, A. (2007). Chapter 1 Air Transportation:
Irregular Operations and Control. En Handbooks in operations research and management
science (Vol. 14, pp. 1–67). doi: 10.1016/S0927-0507(06)14001-3
Barnhart, C., Belobaba, P., y Odoni, A. R. (2003). Applications of Operations Re-
search in the Air Transport Industry. Transportation Science, 37(4), 368–391. Descarga-
do de http://pubsonline.informs.org/doi/10.1287/trsc.37.4.368
.23276 doi: 10.1287/trsc.37.4.368.23276
Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., y Shenoi,
R. G. (1998). Flight String Models for Aircraft Fleeting and Routing. Transportation
Science, 32(3), 208–220. Descargado de http://pubsonline.informs.org/
doi/abs/10.1287/trsc.32.3.208 doi: 10.1287/trsc.32.3.208
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., y Vance, P. H.
(1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Ope-
rations Research, 46(3), 316–329. Descargado de http://pubsonline.informs
.org/doi/abs/10.1287/opre.46.3.316 doi: 10.1287/opre.46.3.316
Barnhart, C., y Smith, B. (Eds.). (2012). Quantitative Problem Solving Methods
81
in the Airline Industry (1.a ed., Vol. 169). Springer US. Descargado de http://
link.springer.com/10.1007/978-1-4614-1608-1 doi: 10.1007/978-1-
4614-1608-1
Basdere, M., y Bilge, Ü. (2014). Operational aircraft maintenance routing problem with
remaining time consideration. European Journal of Operational Research, 235(1), 315–
328. doi: 10.1016/j.ejor.2013.10.066
Ben Ahmed, M., Ghroubi, W., Haouari, M., y Sherali, H. D. (2017). A hybrid
optimization-simulation approach for robust weekly aircraft routing and retiming. Trans-
portation Research Part C: Emerging Technologies, 84, 1–20. Descargado de http://
dx.doi.org/10.1016/j.trc.2017.07.010 doi: 10.1016/j.trc.2017.07.010
Ben Ahmed, M., Zeghal Mansour, F., y Haouari, M. (2017). A two-level optimization
approach for robust aircraft routing and retiming. Computers and Industrial Engineering,
112, 586–594. Descargado de http://dx.doi.org/10.1016/j.cie.2016.09
.021 doi: 10.1016/j.cie.2016.09.021
Ben Ahmed, M., Zeghal Mansour, F., y Haouari, M. (2018). Robust integrated mainte-
nance aircraft routing and crew pairing. Journal of Air Transport Management, 73(July),
15–31. Descargado de https://doi.org/10.1016/j.jairtraman.2018.07
.007 doi: 10.1016/j.jairtraman.2018.07.007
Bertsekas, D. (2005). Dynamic programming and optimal control. Belmont, MA: Athena
scientific.
Bertsimas, D., Gupta, S., y Lulli, G. (2014). Dynamic resource allocation: A flexible
and tractable modeling framework. European Journal of Operational Research, 236(1),
14–26. Descargado de http://dx.doi.org/10.1016/j.ejor.2013.10.063
doi: 10.1016/j.ejor.2013.10.063
Biró, M., Simon, I., y Tánczos, C. (1992). Aircraft and maintenance scheduling support,
mathematical insights and a proposed interactive system. Journal of Advanced Transpor-
tation, 26(2), 121–130. doi: 10.1002/atr.5670260204
Boland, N. L., Clarke, L. W., y Nemhauser, G. L. (2000). The asymmetric traveling
salesman problem with replenishment arcs. European Journal of Operational Research,
82
123(2), 408–427. doi: 10.1016/S0377-2217(99)00266-0

Borndörfer, R., Dovica, I., Nowak, I., y Schickinger, T. (2010, may). Robust Tail Assign-
ment. En Proceedings of the fiftieth annual symposium of agifors.
Brown, D. B., Smith, J. E., y Sun, P. (2010, aug). Information Relaxations and Dua-
lity in Stochastic Dynamic Programs. Operations Research, 58(4-part-1), 785–801. doi:
10.1287/opre.1090.0796
Bureau of Transportation Statistics. (2017). Form 41: Air Carrier Financial Reports.
Descargado de https://www.transtats.bts.gov/
Burke, E. K., De Causmaecker, P., De Maere, G., Mulder, J., Paelinck, M., y Vanden
Berghe, G. (2010). A multi-objective approach for robust airline scheduling. Computers
and Operations Research, 37(5), 822–832. Descargado de http://dx.doi.org/
10.1016/j.cor.2009.03.026 doi: 10.1016/j.cor.2009.03.026
Cacchiani, V., y Salazar-González, J.-J. (2017). Optimal Solutions to a Real-World
Integrated Airline Scheduling Problem. Transportation Science, 51(1), 250–268. Des-
cargado de http://pubsonline.informs.org/doi/10.1287/trsc.2015
.0655 doi: 10.1287/trsc.2015.0655
Cadarso, L., y de Celis, R. (2017). Integrated airline planning: Robust update of sche-
duling and fleet balancing under demand uncertainty. Transportation Research Part C:
Emerging Technologies, 81, 227–245. doi: 10.1016/j.trc.2017.06.003
Cadarso, L., y Marı́n, Á. (2013). Robust passenger oriented timetable and fleet assignment
integration in airline planning. Journal of Air Transport Management, 26, 44–49. Descar-
gado de http://dx.doi.org/10.1016/j.jairtraman.2012.10.004 doi:
10.1016/j.jairtraman.2012.10.004
Clarke, L., Johnson, E., Nemhauser, G., y Zhu, Z. (1997). The aircraft rotation problem.
Annals of Operations Research, 69, 33–46. Descargado de http://linkinghub
.elsevier.com/retrieve/pii/0965856496810950 doi: 10.1016/0965-
8564(96)81095-0
Cohn, A. M., y Barnhart, C. (2003). Improving Crew Scheduling by Incorpora-
ting Key Maintenance Routing Decisions. Operations Research, 51(3), 387–396. doi:
83
10.1287/opre.51.3.387.14959
Cook, A. J., Tanner, G., y Anderson, S. (2004). Evaluating the True Cost To Airlines of
One Minute of Airborne or Ground Delay (Inf. Téc.). University of Westminster.
Cordeau, J.-F., Stojković, G., Soumis, F., y Desrosiers, J. (2001). Benders Decompo-
sition for Simultaneous Aircraft Routing and Crew Scheduling. Transportation Science,
35(4), 375–388. Descargado de http://pubsonline.informs.org/doi/abs/
10.1287/trsc.35.4.375.10432 doi: 10.1287/trsc.35.4.375.10432
Daskin, M. S., y Panayotopoulos, N. D. (1989). A Lagrangian Relaxation Approach to
Assigning Aircraft to Routes in Hub and Spoke Networks. Transportation Science, 23(2),
91–99. doi: 10.1287/trsc.23.2.91
Defraeye, M., y Van Nieuwenhuyse, I. (2016). Staffing and scheduling under nonstatio-
nary demand for service: A literature review (Vol. 58). doi: 10.1016/j.omega.2015.04.002
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., y Soumis, F. (1997). Daily
Aircraft Routing and Scheduling. Management Science, 43(6), 841–855. doi: 10.1057/pal-
grave.jors.2601352
Deveci, M., y Demirel, N. Ç. (2018). A survey of the literature on airline crew sche-
duling. Engineering Applications of Artificial Intelligence, 74(March), 54–69. Des-
cargado de https://doi.org/10.1016/j.engappai.2018.05.008 doi:
10.1016/j.engappai.2018.05.008
Dı́az-Ramı́rez, J., Huertas, J., y Trigos, F. (2013). Simultaneous schedule design & routing
with maintenance constraints for single fleet airlines. International Journal of Engineering
and Applied Sciences, 2(2), 23–35.
Dı́az-Ramı́rez, J., Huertas, J. I., y Trigos, F. (2014). Aircraft maintenance, rou-
ting, and crew scheduling planning for airlines with a single fleet and a single main-
tenance and crew base. Computers and Industrial Engineering, 75(1), 68–78. doi:
10.1016/j.cie.2014.05.027
Dickson, S. K. (2013). Robust airline scheduling and disruption management, PhD Thesis
(Tesis Doctoral, The University of Melbourne). Descargado de http://hdl.handle
.net/11343/40764
84
Dunbar, M., Froyland, G., y Wu, C. L. (2014). An integrated scenario-based approach

for robust aircraft routing, crew pairing and re-timing. Computers and Operations Re-
search, 45, 68–86. Descargado de http://dx.doi.org/10.1016/j.cor.2013
.12.003 doi: 10.1016/j.cor.2013.12.003
Eggenberg, N., Salani, M., y Bierlaire, M. (2010). Constraint-specific recovery network
for solving airline recovery problems. Computers and Operations Research, 37(6), 1014–
1026. Descargado de http://dx.doi.org/10.1016/j.cor.2009.08.006
doi: 10.1016/j.cor.2009.08.006
El Moudani, W., y Mora-Camino, F. (2000). A dynamic approach for aircraft assignment
and maintenance scheduling by airlines. Journal of Air Transport Management, 6(4),
233–237. doi: 10.1016/S0969-6997(00)00011-9
Eltoukhy, A. E., Chan, F. T., y Chung, S. (2017). Airline schedule planning: a review and
future directions. Industrial Management & Data Systems, 117(6), 1201–1243. Descar-
gado de http://www.emeraldinsight.com/doi/10.1108/IMDS-09-2016
-0358 doi: 10.1108/IMDS-09-2016-0358
Etschmaier, M. M., y Mathaisel, D. F. X. (1985). Airline Scheduling: An Overview. Trans-
portation Science, 19(2), 127–138. Descargado de http://pubsonline.informs
.org/doi/abs/10.1287/trsc.19.2.127 doi: 10.1287/trsc.19.2.127
Feo, T. A., y Bard, J. F. (1989). Flight Scheduling and Maintenance Base Planning.
Management Science, 35(12), 1415–1432. Descargado de http://www.jstor.org/
stable/2632228 doi: 10.1287/mnsc.35.12.1415
Froyland, G., Maher, S. J., y Wu, C.-L. (2014). The Recoverable Robust Tail As-
signment Problem. Transportation Science, 48(3), 351–372. Descargado de http://
pubsonline.informs.org/doi/abs/10.1287/trsc.2013.0463 doi:
10.1287/trsc.2013.0463
Gabteni, S., y Grönkvist, M. (2009). Combining column generation and constraint pro-
gramming to solve the tail assignment problem. Annals of Operations Research, 171(1),
61–76. doi: 10.1007/s10479-008-0379-1
Gao, C., Johnson, E., y Smith, B. (2009). Integrated Airline Fleet and Crew
85
Robust Planning. Transportation Science, 43(1), 2–16. Descargado de http://

10.1287/trsc.1080.0257
Gavranis, A., y Kozanidis, G. (2015). An exact solution algorithm for maximizing the fleet
availability of a unit of aircraft subject to flight and maintenance requirements. European
Journal of Operational Research, 242(2), 631–643. doi: 10.1016/j.ejor.2014.10.016
Gopalan, R., y Talluri, K. T. (1998a). The aircraft maintenance routing problem. Ope-
rations Research, 46(2), 260–271. Descargado de http://dx.doi.org/10.1287/
opre.46.2.260
Gopalan, R., y Talluri, K. T. (1998b). Mathematical models in airline schedule planning :
A survey. Annals of Operations Research, 76, 155–185. doi: 10.1023/A:1018988203220
Grönkvist, M. (2005). The tail assignment problem, PhD Thesis (Doctor of Philosophy,
Chalmers University of Technology and Göteborg University). doi: ISSN: 0346-718X
Grönkvist, M. (2006). Accelerating column generation for aircraft scheduling using
constraint propagation. Computers and Operations Research, 33(10), 2918–2934. doi:
10.1016/j.cor.2005.01.017
Haouari, M., Aissaoui, N., y Mansour, F. Z. (2009). Network flow-based approaches
for integrated aircraft fleeting and routing. European Journal of Operational Research,
193(2), 591–599. Descargado de http://dx.doi.org/10.1016/j.ejor.2007
.11.042 doi: 10.1016/j.ejor.2007.11.042
Haouari, M., Shao, S., y Sherali, H. D. (2013). A Lifted Compact Formulation for
the Daily Aircraft Maintenance Routing Problem. Transportation Science, 47(4), 508–
525. Descargado de http://pubsonline.informs.org/doi/abs/10.1287/
trsc.1120.0433 doi: 10.1287/trsc.1120.0433
Haouari, M., Sherali, H. D., Mansour, F. Z., y Aissaoui, N. (2011). Exact approaches
for integrated aircraft fleeting and routing at TunisAir. Computational Optimization and
Applications, 49(2), 213–239. doi: 10.1007/s10589-009-9292-z
86
Hu, Y., Song, Y., Zhao, K., y Xu, B. (2016, mar). Integrated recovery of air-
craft and passengers after airline operation disruption based on a GRASP algo-
rithm. Transportation Research Part E: Logistics and Transportation Review, 87, 97–
112. Descargado de http://linkinghub.elsevier.com/retrieve/pii/
S1366554516000028 doi: 10.1016/j.tre.2016.01.002
IATA. (2017). Economic performance of the airline industry (Inf. Téc.). Descar-
gado de https://www.iata.org/whatwedo/Documents/economics/
IATA-Economic-Performance-of-the-Industry-mid-year-2017
-report.pdf
IATA. (2018a). Economic performance of the airline industry (Inf. Téc.).
IATA. (2018b). Safety Report 2017 (Inf. Téc.).
IATA. (2019). Safety Report 2018 (Inf. Téc.).
IATA’s Maintenance Cost Task Force. (2013). Labour rate and productivity calculations
for commercial aircraft maintenance (Inf. Téc.).
Ioachim, I., Desrosiers, J., Soumis, F., y Bélanger, N. (1999). Fleet assignment and routing
with schedule synchronization constraints. European Journal of Operational Research,
119(1), 75–90. doi: 10.1016/S0377-2217(98)00343-9
Jamili, A. (2017). A robust mathematical model and heuristic algorithms for integrated
aircraft routing and scheduling, with consideration of fleet assignment problem. Journal
of Air Transport Management, 58, 21–30. Descargado de http://dx.doi.org/10
.1016/j.jairtraman.2016.08.008 doi: 10.1016/j.jairtraman.2016.08.008
JetSmart Airlines. (2018). Quiénes Somos. Descargado 2018-10-09, de https://
jetsmart.com/cl/es/quienes-somos
Jiang, H., y Barnhart, C. (2013). Robust airline schedule design in a dyna-
mic scheduling environment. Computers and Operations Research, 40(3), 831–840.
Descargado de http://dx.doi.org/10.1016/j.cor.2011.06.018 doi:
10.1016/j.cor.2011.06.018
Jozefowiez, N., Mancel, C., y Mora-Camino, F. (2013). A heuristic approach based
87
on shortest path problems for integrated flight, aircraft, and passenger rescheduling un-
der disruptions. Journal of the Operational Research Society, 64(3), 384–395. doi:
10.1057/jors.2012.20
Junta Aeronáutica Civil. (2018). Informe estadı́stico de Tráfico Aéreo 2017 (Inf. Téc.).
Santiago de Chile.
Kabbani, N. M., y Patty, B. W. (1992). Aircraft Routing at American Airlines. En
Proceedings of the thirty-second annual symposium of agifors. Descargado de https://
trid.trb.org/view/535718
Kenan, N., Jebali, A., y Diabat, A. (2017). An integrated flight scheduling and fleet
assignment problem under uncertainty. Computers and Operations Research, 0, 1–
10. Descargado de https://doi.org/10.1016/j.cor.2017.08.014 doi:
10.1016/j.cor.2017.08.014
Keysan, G., Nemhauser, G. L., y Savelsbergh, M. W. P. (2010). Tactical and Operational
Planning of Scheduled Maintenance for Per-Seat, On-Demand Air Transportation. Trans-
.org/doi/abs/10.1287/trsc.1090.0311 doi: 10.1287/trsc.1090.0311
Khaled, O., Minoux, M., Mousseau, V., Michel, S., y Ceugniet, X. (2018). A com-
pact optimization model for the tail assignment problem. European Journal of Opera-
tional Research, 264(2), 548–557. Descargado de http://dx.doi.org/10.1016/
j.ejor.2017.06.045 doi: 10.1016/j.ejor.2017.06.045
Klabjan, D., Johnson, E. L., Nemhauser, G. L., Gelman, E., y Ramaswamy, S. (2002). Air-
line Crew Scheduling with Time Windows and Plane-Count Constraints. Transportation
doi/abs/10.1287/trsc.36.3.337.7831 doi: 10.1287/trsc.36.3.337.7831
Lan, S., Clarke, J.-P., y Barnhart, C. (2006). Planning for Robust Airline Opera-
tions: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passen-
ger Disruptions. Transportation Science, 40(1), 15–28. Descargado de http://
10.1287/trsc.1050.0134
88
Lapp, M., y Cohn, A. (2012). Modifying lines-of-flight in the planning process for
improved maintenance robustness. Computers and Operations Research, 39(9), 2051–
2062. Descargado de http://dx.doi.org/10.1016/j.cor.2011.08.024
doi: 10.1016/j.cor.2011.08.024
Lapp, M., y Wikenhauser, F. (2012). Incorporating aircraft efficiency measures into the
tail assignment problem. Journal of Air Transport Management, 19(1), 25–30. Descar-
gado de http://dx.doi.org/10.1016/j.jairtraman.2011.12.006 doi:
10.1016/j.jairtraman.2011.12.006
LATAM Airlines. (2018). Memoria Anual 2017 (Inf. Téc.). Santiago de Chile: LATAM
Airlines. Descargado de http://memoria2017.marketinglatam.net/es/
Lee, L. H., Lee, C. U., y Tan, Y. P. (2007). A multi-objective genetic algorithm for robust
flight scheduling using simulation. European Journal of Operational Research, 177(3),
1948–1968. doi: 10.1016/j.ejor.2005.12.014
Li, H., y Womer, N. K. (2015). Solving stochastic resource-constrained project schedu-
ling problems by closed-loop approximate dynamic programming. European Journal of
Operational Research, 246(1), 20–33. doi: 10.1016/j.ejor.2015.04.015
Liang, Z., y Chaovalitwongse, W. A. (2013). A Network-Based Model for the Integrated
Weekly Aircraft Maintenance Routing and Fleet Assignment Problem. Transportation
doi/abs/10.1287/trsc.1120.0434 doi: 10.1287/trsc.1120.0434
Liang, Z., Chaovalitwongse, W. A., Huang, H. C., y Johnson, E. L. (2012). On a New
Rotation Tour Network Model for Aircraft Maintenance Routing Problem. Transportation
Science, 45(1), 109–120. doi: 10.1287/trsc.
Liang, Z., Feng, Y., Zhang, X., Wu, T., y Chaovalitwongse, W. A. (2015). Ro-
bust weekly aircraft maintenance routing problem and the extension to the tail as-
signment problem. Transportation Research Part B: Methodological, 78(2015), 238–
259. Descargado de http://dx.doi.org/10.1016/j.trb.2015.03.013 doi:
10.1016/j.trb.2015.03.013
Maher, S. J. (2016, feb). Solving the Integrated Airline Recovery Problem Using
89
Column-and-Row Generation. Transportation Science, 50(1), 216–239. Descargado de

http://pubsonline.informs.org/doi/10.1287/trsc.2014.0552 doi:
10.1287/trsc.2014.0552
Maher, S. J., Desaulniers, G., y Soumis, F. (2014). Recoverable robust single day
aircraft maintenance routing problem. Computers and Operations Research, 51, 130–
145. Descargado de http://dx.doi.org/10.1016/j.cor.2014.03.007 doi:
10.1016/j.cor.2014.03.007
Maher, S. J., Desaulniers, G., y Soumis, F. (2018). The daily tail assignment problem
under operational uncertainty using look-ahead maintenance constraints. European Jour-
nal of Operational Research, 264(2), 534–547. Descargado de http://dx.doi.org/
10.1016/j.ejor.2017.06.041 doi: 10.1016/j.ejor.2017.06.041
Marla, L., Vaze, V., y Barnhart, C. (2018). Robust optimization: Lessons learned
from aircraft routing. Computers and Operations Research, 98(January), 165–184. doi:
10.1016/j.cor.2018.04.011
Mercier, A. (2008). A Theoretical Comparison of Feasibility Cuts for the Integra-
ted Aircraft-Routing and Crew-Pairing Problem. Transportation Science, 42(1), 87–
trsc.1070.0197 doi: 10.1287/trsc.1070.0197
Mercier, A., Cordeau, J. F., y Soumis, F. (2005). A computational study of Benders
decomposition for the integrated aircraft routing and crew scheduling problem. Computers
and Operations Research, 32(6), 1451–1476. doi: 10.1016/j.cor.2003.11.013
Mercier, A., y Soumis, F. (2007). An integrated aircraft routing, crew scheduling and
flight retiming model. Computers and Operations Research, 34(8), 2251–2265. doi:
10.1016/j.cor.2005.09.001
Murat Afsar, H., Espinouse, M. L., y Penz, B. (2007). A two-step heuristic to build
flight and maintenance planning in a rolling-horizon. Proceedings - ICSSSM’06: 2006
International Conference on Service Systems and Service Management, 2, 1251–1256.
doi: 10.1109/ICSSSM.2006.320688
Murat Afsar, H., Espinouse, M. L., y Penz, B. (2009). Building flight planning for an
90
airline company under maintenance constraints. Journal of Quality in Maintenance Engi-

neering, 15(4), 430–443. doi: 10.1108/13552510910997788
Muter, I., Ilker Birbil, ., Bülbül, K., Şahin, G., Yenigün, H., Taş, D., y Tüzün, D. (2013).
Solving a robust airline crew pairing problem with column generation. Computers and
Operations Research, 40(3), 815–830. doi: 10.1016/j.cor.2010.11.005
Novoa, C., y Storer, R. (2009). An approximate dynamic programming approach for
the vehicle routing problem with stochastic demands. European Journal of Operatio-
nal Research, 196(2), 509–515. Descargado de http://dx.doi.org/10.1016/
j.ejor.2008.03.023 doi: 10.1016/j.ejor.2008.03.023
Orhan, I., Kapanoglu, M., y Karakoc, t. H. (2011). Concurrent Aircraft and Maintenance
Scheduling. Journal of Aeronautics and Space Tecnologies, 5(1), 73–79.
Otten, L., Grönkvist, M., y Dubhashi, D. (2006). Randomization in Constraint Program-
ming for Airline Planning. En F. Benhamou (Ed.), Principles and practice of constraint
programming - cp (pp. 406–420). Springer, Berlin, Heidelberg.
Özener, O. Ö., Örmeci Matoğlu, M., Erdoğan, G., Haouari, M., y Sözer, H. (2017). Solving
a large-scale integrated fleet assignment and crew pairing problem. Annals of Operations
Research, 253(1), 477–500. doi: 10.1007/s10479-016-2319-9
Papadakos, N. (2009). Integrated airline scheduling. Computers & Operations Research,
36(1), 176–195.
Papakostas, N., Papachatzakis, P., Xanthakis, V., Mourtzis, D., y Chryssolouris, G. (2010).
An approach to operational aircraft maintenance planning. Decision Support Systems,
48(4), 604–612. Descargado de http://dx.doi.org/10.1016/j.dss.2009
.11.010 doi: 10.1016/j.dss.2009.11.010
Petersen, J. D., Sölveling, G., Clarke, J.-p., Johnson, E. L., y Shebalov, S. (2012). An Op-
timization Approach to Airline Integrated Recovery. Transportation Science, 46(4), 482–
trsc.1120.0414 doi: 10.1287/trsc.1120.0414
Pinedo, M. L. (2016). Scheduling. Springer. doi: 10.1007/978-3-319-26580-3
91
Pita, J. P., Barnhart, C., y Antunes, A. P. (2013). Integrated Flight Scheduling and Fleet As-
signment Under Airport Congestion. Transportation Science, 47(4), 477–492. Descarga-
do de http://pubsonline.informs.org/doi/abs/10.1287/trsc.1120
.0442 doi: 10.1287/trsc.1120.0442
Powell, W. B. (2011). Approximate Dynamic Programming: Solving the Cur-
ses of Dimensionality: Second Edition. Hoboken, NJ, USA: John Wiley & Sons,
Inc. Descargado de http://doi.wiley.com/10.1002/9781118029176 doi:
10.1002/9781118029176
Prentice, B., Costanza, D., y Smiley, J. (2017). Not enough mechanics (Inf. Téc.). Oliver
Wyman.
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dy-
namic programming. John Wiley & Sons. Descargado de https://books
.google.com/books?hl=en{&}lr={&}id=VvBjBAAAQBAJ{&}pgis=1 doi:
10.15713/ins.mmj.3
Rosenberger, J. M., Johnson, E. L., y Nemhauser, G. L. (2003). Rerouting
Aircraft for Airline Recovery. Transportation Science, 37(4), 408–421. doi:
10.1287/trsc.37.4.408.23271
Rosenberger, J. M., Johnson, E. L., y Nemhauser, G. L. (2004). A Robust Fleet-
Assignment Model with Hub Isolation and Short Cycles. Transportation Science,
38(3), 357–368. Descargado de http://pubsonline.informs.org/doi/abs/
10.1287/trsc.1030.0038 doi: 10.1287/trsc.1030.0038
Ruther, S., Boland, N., Engineer, F. G., y Evans, I. (2017). Integrated aircraft routing,
crew pairing, and tail assignment: branch-and-price with many pricing problems. Trans-
portation Science, 51(1), 177–195. doi: 10.1287/trsc.2015.0664
Safaei, N., y Jardine, A. K. (2018). Aircraft routing with generalized maintenance cons-
traints. Omega (United Kingdom), 80, 111–122. Descargado de https://doi.org/
10.1016/j.omega.2017.08.013 doi: 10.1016/j.omega.2017.08.013
Sandhu, R., y Klabjan, D. (2007). Integrated Airline Fleeting and Crew-Pairing
Decisions. Operations Research, 55(3), 439–456. Descargado de http://
92
pubsonline.informs.org/doi/abs/10.1287/opre.1070.0395 doi:
10.1287/opre.1070.0395
Santos, B. F., Wormer, M. M., Achola, T. A., y Curran, R. (2017). Airline delay
management problem with airport capacity constraints and priority decisions. Journal
of Air Transport Management, 63, 34–44. Descargado de http://dx.doi.org/
10.1016/j.jairtraman.2017.05.003 doi: 10.1016/j.jairtraman.2017.05.003
Sarac, A., Batta, R., y Rump, C. M. (2006). A branch-and-price approach for operational
aircraft maintenance routing. European Journal of Operational Research, 175(3), 1850–
1869. doi: 10.1016/j.ejor.2004.10.033
Schaefer, A. J., y Nemhauser, G. L. (2006). Improving airline operational performan-
ce through schedule perturbation. Annals of Operations Research, 144(1), 3–16. doi:
10.1007/s10479-006-0003-1
Shebalov, S., y Klabjan, D. (2006). Robust Airline Crew Pairing: Move-up Crews. Trans-
.org/doi/abs/10.1287/trsc.1050.0131 doi: 10.1287/trsc.1050.0131
Sherali, H. D., Bae, K.-H., y Haouari, M. (2013). An Integrated Approach for Airline
Flight Selection and Timing, Fleet Assignment, and Aircraft Routing. Transportation
doi/abs/10.1287/trsc.2013.0460 doi: 10.1287/trsc.2013.0460
Sherali, H. D., Bish, E. K., y Zhu, X. (2006). Airline fleet assignment concepts, mo-
dels, and algorithms. European Journal of Operational Research, 172(1), 1–30. doi:
10.1016/j.ejor.2005.01.056
Sinclair, K., Cordeau, J. F., y Laporte, G. (2016). A column generation post-optimization
heuristic for the integrated aircraft and passenger recovery problem. Computers and Ope-
rations Research, 65, 42–52. doi: 10.1016/j.cor.2015.06.014
SKY Airlines. (2018). Nuestra Historia. Descargado 2018-10-09, de https://www
.skyairline.com/chile/about{ }us/learn{ }more
93
Sohoni, M., Lee, Y.-c., y Klabjan, D. (2011). Robust Airline Scheduling Un-
der Block-Time Uncertainty. Transportation Science, 45(4), 451–464. Descarga-
.0361 doi: 10.1287/trsc.1100.0361
Sriram, C., y Haghani, A. (2003). An optimization model for aircraft maintenance sche-
duling and re-assignment. Transportation Research Part A: Policy and Practice, 37(1),
29–48. doi: 10.1016/S0965-8564(02)00004-6
Talluri, K. T. (1998). The Four-Day Aircraft Maintenance Routing Problem. Transporta-
tion Science, 32(1), 43–53. Descargado de http://pubsonline.informs.org/
doi/abs/10.1287/trsc.32.1.43 doi: 10.1287/trsc.32.1.43
Tekiner, H., Birbil, . I., y Bülbül, K. (2009). Robust crew pairing for mana-
ging extra flights. Computers and Operations Research, 36(6), 2031–2048. doi:
10.1016/j.cor.2008.07.005
Teodorović, D., y Stojković, G. (1995). Model to Reduce Airline Schedule Disturban-
ces. Journal of Transportation Engineering, 121(4), 324–331. doi: 10.1061/(ASCE)0733-
947X(1995)121:4(324)
Ulmer, M. W., Goodson, J. C., Mattfeld, D. C., y Hennig, M. (2018). Offline-Online
Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Re-
quests. Transportation Science. Descargado de https://doi.org/10.1287/
trsc.2017.0767
Ulmer, M. W., Soeffker, N., y Mattfeld, D. C. (2018). Value function approximation for
dynamic multi-period vehicle routing. European Journal of Operational Research, 269(3),
883–899. Descargado de https://doi.org/10.1016/j.ejor.2018.02.038
doi: 10.1016/j.ejor.2018.02.038
Van den Bergh, J., De Bruecker, P., Beliën, J., y Peeters, J. (2013). Aircraft maintenance
operations: state of the art. FEB@HUBRUSSEL RESEARCH PAPER, 9, 34. Descargado
de https://lirias.kuleuven.be/bitstream/123456789/426843/1/
Vos, H. W. M., Santos, B. F., y Omondi, T. (2015). Aircraft schedule recovery problem - A
dynamic modeling framework for daily operations. En Transportation research procedia
94
(Vol. 10, pp. 931–940). doi: 10.1016/j.trpro.2015.09.047

Weide, O., Ryan, D., y Ehrgott, M. (2010). An iterative approach to robust and integrated
aircraft routing and crew scheduling. Computers and Operations Research, 37(5), 833–
844. Descargado de http://dx.doi.org/10.1016/j.cor.2009.03.024 doi:
10.1016/j.cor.2009.03.024
Yan, C., y Kung, J. (2016). Robust Aircraft Routing. Transportation Science, 52(1). doi:
10.2139/ssrn.2518028
Yan, S., y Tseng, C. H. (2002). A passenger demand model for airline flight schedu-
ling and fleet routing. Computers and Operations Research, 29(11), 1559–1581. doi:
10.1016/S0305-0548(01)00046-6
Yang, X., y Strauss, A. K. (2017). An approximate dynamic programming approach
to attended home delivery management. European Journal of Operational Research,
263(3), 935–945. Descargado de http://dx.doi.org/10.1016/j.ejor.2017
.06.034 doi: 10.1016/j.ejor.2017.06.034
Yen, J. W., y Birge, J. R. (2006). A Stochastic Programming Approach to the
Airline Crew Scheduling Problem. Transportation Science, 40(1), 3–14. Descarga-
.0138 doi: 10.1287/trsc.1050.0138
Zeghal, F. M., Haouari, M., Sherali, H. D., y Aissaoui, N. (2011). Flexible aircraft fleeting
and routing at TunisAir. Journal of the Operational Research Society, 62(2), 368–380. doi:
10.1057/jors.2010.100
Zhang, D., Henry Lau, H. Y., y Yu, C. (2015). A two stage heuristic algorithm for the
integrated aircraft and crew schedule recovery problems. Computers and Industrial Engi-
neering, 87, 436–453. doi: 10.1016/j.cie.2015.05.033
Zhang, D., Yu, C., Desai, J., y Lau, H. Y. (2016). A math-heuristic algorithm for the
integrated air service recovery. Transportation Research Part B: Methodological, 84, 211–
236. Descargado de http://dx.doi.org/10.1016/j.trb.2015.11.016 doi:
10.1016/j.trb.2015.11.016
95
GLOSARIO
AOG: del inglés aircraft on ground, es cuando un avión se encuentra en tierra fuera de
operación.
LOF: del inglés line of flights, es una ruta de un dı́a de extensión compuesta por una
secuencia de vuelos.
ADP: del inglés approximate dynamic programming, es un conjunto de técnicas de pro-
gramación dinámica aproximada.
VFA: del inglés value function approximation, es una técnica de ADP que consiste en
aproximaciones a las funciones de valor. Se utiliza para estimar el costo futuro de una
decisión en un sistema dinámico.
AMRP: del inglés aircraft maintenance routing problem, es un problema de ruteo de
aviones con restricciones de mantenimiento.
TAP: del inglés tail assignment problem, es el problema de asignación de aviones es-
pecı́ficos a vuelos. Cuando incorpora restricciones de mantenimiento es similar al AMRP.
MIP: del inglés mixed integer programming, es un modelo de programación entero mixto.
GTW: del inglés ground time window, es la ventana de tiempo en tierra de un avión entre
terminar la operación de un dı́a y comenzar la del siguiente.
PIR: del inglés perfect information relaxation, es la relajación de información perfecta
de un problema dinámico.
PHRD: es el problema de horizonte rodante determinı́stico resultante de tomar un pronósti-
co para los eventos estocásticos de los dı́as futuros.
96
ANEXOS
97
A. MODELOS DETERMINÍSTICOS EQUIVALENTES
Se desarrollaron tres modelos determinı́sticos equivalentes al expuesto en la sección

3.3, pero que fueron descartados por un peor desempeño computacional debido al mayor
número de variables que utilizaban y/o la peor estructura del modelo.
A.1. Modelo determinı́stico adicional 1
Este modelo es similar al expuesto en (3.24)-(3.50), pero en vez de considerar la va-

riable para aviones fuera de operación a partir de una hora (ua,t,j ), considera una única
variable por dı́a (ua,t ). Producto de lo anterior, no es posible utilizar restricciones de flujo
en redes y es necesario definir dos parámetros adicionales para formular el modelo, ηa,j
que toma valor 1 si el avión a termina de volar el dı́a cero antes de la hora j y νi, j que
toma valor 1 si al realizar la LOF i es posible hacer mantenimiento en la hora j.
La función objetivo es presentada en la ecuación (A.1). De forma similar, las restric-

ciones se detallan en las ecuaciones (A.2)-(A.21).
XX XX X
mı́n α ua,t + δk · qk (A.1)
a∈A t∈T a∈A t∈T k∈Oa,t :γk =0
X
xa,i,t ≤ 1 ∀i ∈ It , ∀t ∈ T (A.2)
a∈A
X
ua,t + xa,i,t = 1 ∀a ∈ A, ∀t ∈ T (A.3)
i∈It
X
qk + yk,t ≥ 1 ∀k ∈ Ka , ∀a ∈ A (A.4)
t∈Tk
X
ua,t ≥ qk ∀k ∈ Ka : γk = 1, ∀a ∈ A (A.5)
t∈Tk
yk,t ≤ za,t ∀k ∈ Ka,t , ∀t ∈ T, ∀a ∈ A (A.6)

98
X
za,t ≤ n ∀t ∈ T (A.7)
a∈A
X
`k · yk,t ≤ wa,j ∀k ∈ Ka,t , ∀a ∈ A, ∀t ∈ T (A.8)
j∈Jt
X X
βk,p · yk,t ≤ ra,p,j ∀a ∈ A, ∀p ∈ P, ∀t ∈ T (A.9)
k∈Ka,t j∈Jt
X
ra,p,j ≤ cp,j ∀p ∈ P, ∀j ∈ Jt , ∀t ∈ T (A.10)
a∈A
ra,p,j ≤ wa,j · cp,j ∀p ∈ P, ∀j ∈ Jt , ∀t ∈ T, ∀a ∈ A (A.11)
wa,j ≤ ηa,j ∀j ∈ J1 , ∀a ∈ A (A.12)

X
wa,j ≤ νi,j · xa,i,t−1 + ua,t−1 ∀j ∈ Jt , ∀t ∈ T \ {1}, ∀a ∈ A (A.13)
i∈It−1
X
wa,j ≤ νi,j · xa,i,t ∀j ∈ Jt , ∀t ∈ T, ∀a ∈ A (A.14)
i∈It
xa,i,t ∈ {0, 1} ∀a ∈ A, ∀i ∈ It , ∀t ∈ T (A.15)
yk,t ∈ {0, 1} ∀t ∈ Tk , ∀k ∈ K
fa , ∀a ∈ A (A.16)
qk ∈ {0, 1} ∀k ∈ K (A.17)
ua,t ≥ 0 ∀a ∈ A, ∀t ∈ T (A.18)
za,t ∈ {0, 1} ∀a ∈ A, ∀t ∈ T (A.19)
ra,p,j ≥ 0 ∀a ∈ A, ∀p ∈ P, ∀j ∈ Jt , ∀t ∈ T (A.20)
wa,j ∈ {0, 1} ∀a ∈ A, ∀j ∈ Jt , ∀t ∈ T (A.21)
Las restricciones (A.2)-(A.11) son prácticamente idénticas a las restricciones (3.25)-

(3.35) y las restricciones (A.12)-(A.14) equivalen a las restricciones (3.36)-(3.42). Por
último, las restricciones (A.15)-(A.21) corresponden a la naturaleza de variables.
Las restricciones (A.12) permiten activar las variables wa,j del primer dı́a si y solo si el
avión termina de operar la LOF del dı́a anterior antes de la hora j. Las restricciones (A.13)
permiten activar las variables wa,j a partir del segundo dı́a si y solo si el avión realiza el
99
dı́a anterior una LOF que termina antes de la hora j o se encuentra fuera de operación.
Las restricciones (A.14) permiten activar las variables wa,j de cada dı́a si y solo si el avión
realiza dicho dı́a una LOF que comienza después de la hora j.
Este modelo es similar al A.1, pero en vez de considerar la variable para la dispo-
nibilidad de mantenimiento por hora (wa,j ), considera una variable por cada ventana de
tiempo de mantenimiento (wa,j1 ,j2 ). Tampoco presenta restricciones de flujo en redes, pero
permite definir la restricción referente al largo mı́nimo del bloque de mantenimiento para
realizar una tarea de forma directa.
La función objetivo del modelo es la misma del modelo anterior presentada en la ecua-
ción (A.1). De forma similar, las restricciones (A.2)-(A.7), (A.9)-(A.10) y (A.15)-(A.20)
también son parte de este modelo junto a las nuevas restricciones (A.22)-(A.32).
X X
yk,t ≤ wa,j1 ,j2 ∀k ∈ Ka,t , ∀a ∈ A, ∀t ∈ T \ {1}
−
j1 ∈Jt−1 j2 ∈Jt+ :
j2 −j1 ≥`k
(A.22)
X
yk,1 ≤ wa,da ,j2 ∀k ∈ Ka,1 , ∀a ∈ A (A.23)
j2 ∈J1+ :
j2 ≥da +`k
X X
ra,p,j ≤ cp,j · wa,j1 ,j2 ∀p ∈ P, ∀j ∈ Jt , ∀t ∈ T \ {1},
−
j1 ∈Jt−1 : j2 ∈Jt+ :
j1 <j j2 ≥j
∀a ∈ A (A.24)
X
ra,p,j ≤ ηa,j · cp,j · wa,da ,j2 ∀p ∈ P, ∀j ∈ J1 , ∀a ∈ A (A.25)
j2 ∈J1+ :
j2 ≥j
100
X X
−
wa,j,j2 ≤ xa,i,t−1 + ua,t−1 ∀j ∈ Jt−1 , ∀t ∈ T \ {1}, ∀a ∈ A
−
j2 ∈Jt+ i∈It−1,j
(A.26)
X X
wa,j1 ,j = xa,i,t ∀j ∈ Jt+ , ∀t ∈ T \ {1}, ∀a ∈ A
− +
j1 ∈Jt−1 i∈It,j
(A.27)
X
wa,da ,j = xa,i,1 ∀j ∈ J1+ , ∀a ∈ A (A.28)
+
i∈I1,j
X X
wa,j1 ,j2 ≤ 1 ∀t ∈ T \ {1}, ∀a ∈ A (A.29)
−
j1 ∈Jt−1 j2 ∈Jt+
X
wa,da ,j2 ≤ 1 ∀a ∈ A (A.30)
j2 ∈J1+
wa,da ,j2 ∈ {0, 1} ∀j2 ∈ J1+ , ∀a ∈ A (A.31)

−
wa,j1 ,j2 ∈ {0, 1} ∀j1 ∈ Jt−1 , ∀j2 ∈ Jt+ ,
∀t ∈ T \ {1}, ∀a ∈ A (A.32)
Las restricciones (A.22)-(A.23) aseguran el cumplimiento del largo del bloque de man-
tenimiento mı́nimo para realizar una tarea. El conjunto de restricciones (A.24)-(A.25) im-
ponen que la capacidad total asignada a los aviones por recurso para cada hora sea menor
o igual a la capacidad disponible en la estación siempre y cuando dicha hora el avión esté
disponible para mantenimiento. Las restricciones (A.26)-(A.28) aseguran que solo se ac-
tive la ventana de mantenimiento entre las LOFs asignadas, a excepción del caso en que
el avión está fuera de operación en que solo se fija la hora de término de la ventana. Las
restricciones (A.29)-(A.30) aseguran que solo se active una ventana de mantenimiento por
dı́a. Finalmente, (A.31)-(A.32) corresponden a la naturaleza de las variables wa,j1 ,j2 .
101
Este modelo es similar al en A.2, pero en vez de considerar una única variable por dı́a
para aviones fuera de operación (ua,t ), considera la variable para avión fuera de operación
a partir de una hora (ua,t,j ). Como consecuencia de esto, posee tanto la estructura de flujo
en redes como las ventanas de mantenimiento dadas por wa,j1 ,j2 .
La función objetivo del modelo se detalla en la ecuación (3.24). De forma similar, las
restricciones (3.25)-(3.31), (3.33)-(3.34) y (3.43)-(3.49) también son parte de este modelo
junto a las restricciones (A.22)-(A.25) y (A.31)-(A.32) del modelo presentado en la sec-
ción A.2. Para completar la formulación se deben plantear las restricciones (A.33)-(A.38).
X
1= wa,da ,j + ua,1,da ∀a ∈ A (A.33)
j∈J1+
X X
xa,i,1 + ua,1,da = wa,θ2 ,j + ua,2,θ2 ∀a ∈ A (A.34)
−
i∈I1,θ j∈J2+
2
X X X
xa,i,t−1 + ua,t−1,j = wa,θt ,j + ua,t,θt ∀a ∈ A, ∀t ∈ T \ {1, 2}
− −
i∈It−1,θt j∈Jt−2 j∈Jt+
(A.35)
X X
xa,i,t−1 = wa,j,j2 + ua,t,j ∀a ∈ A, ∀t ∈ T \ {1},
−
i∈It−1,j j2 ∈Jt+
−
∀j ∈ Jt−1 \ {θt } (A.36)
X
wa,da ,j = xa,i,1 ∀a ∈ A, ∀j ∈ J1+ (A.37)
+
i∈I1,j
X X
wa,j1 ,j = xa,i,t ∀a ∈ A, ∀t ∈ T \ {1},
− +
j1 ∈Jt−1 i∈It,j
∀j ∈ Jt+ (A.38)
102
Las restricciones (A.33) corresponden al balance del primer nodo del primer dı́a para
cada avión. Las restricciones (A.34) corresponden al balance de flujo en el primer nodo
del segundo dı́a para cada avión. Las restricciones (A.35) corresponden al balance de flujo
en el primer nodo para cada avión a partir del tercer dı́a. Estos tres grupos de restricciones
son similares a (3.36)-(3.38).
Las restricciones (A.36) son el balance de flujo para cada avión en los nodos en que
terminan LOFs a partir del segundo dı́a, a excepción del primer nodo de cada dı́a que son
abarcados por las restricciones (A.34)-(A.35). Las restricciones (A.37) son el balance de
flujo para cada avión en las horas en que comienzan LOFs del primer dı́a y las restricciones
(A.38) son para horas en que comienzan LOFs a partir del segundo dı́a. Como en este caso
las ventanas de mantenimiento son definidas directamente en la variable, no es necesario
trabajar la conservación de flujo en las horas de transbordo y tampoco tratar especialmente
la hora final del turno.
103
B. INCLUSIÓN EXPLÍCITA DE TAREAS PERIÓDICAS
A pesar de que las periodicidades de las tareas no fueron incluidas explı́citamente, los
resultados de anticipación señalan que no es totalmente necesario hacerlo, ya que al aplicar
la polı́tica propuesta la anticipación promedio con que se realiza una tarea es menor a un
dı́a (0,63) en el caso base. Esto se mantiene para todos los casos analizados, a excepción
de los casos con baja saturación (saturación menor a 95 %) en que alcanza un dı́a y medio.
Como consecuencia de lo anterior, no se estarı́an realizando tareas de forma tan anticipada,
que en caso de ser periódicas, implicarı́an repetirlas muchas más veces que las deseadas
ya que el plazo promedio para ejecutar una tarea se encuentra cercano a los 14 dı́as en el
caso base.
En caso de que, a pesar de lo señalado, se quiera incluir tareas periódicas es posible

bajo el modelo y polı́ticas actuales a través de una de las siguientes opciones:
1. Inclusión explı́cita en el modelo, es decir, diferenciarlas de manera que cuando se

realice una tarea periódica, aparezca una nueva.
2. Introducir penalidades adicionales en la función objetivo asociadas a la anticipa-
ción con que se realiza cada tarea periódica para incentivar la realización de estas
el dı́a más cercano al vencimiento posible. Estas penalidades tendrı́an la forma de
P
t∈Tk (bk − t) · yk,t por lo que serı́a necesario escalarlas para que interactúen de
forma adecuada con las componentes actuales de la función objetivo.

3. Modificar la disponibilidad de las tareas periódicas de forma que no puedan ser
planificadas al momento de ser reveladas. Esto implica que estas tareas son co-
nocidas desde el momento en que arriban al sistema, pero que solo pueden ser
planificadas una vez que superan un porcentaje dado de su plazo. Es decir, si di-
cho porcentaje se fija en 75 % y una tarea periódica que arriba en el dı́a 6 vence
el dı́a 25, entonces para el sistema dicha tarea se encuentra disponible para ser
planificada a partir del dı́a 21.

Lagos Carlos

Cargado por

Copyright:

Formatos disponibles

Lagos Carlos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lagos Carlos

Cargado por

Copyright:

Formatos disponibles

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE

CARLOS ALBERTO LAGOS SALGADO

Tesis para optar al grado de

Santiago de Chile, Marzo 2019

c MMXIX, C ARLOS A LBERTO L AGOS S ALGADO

CARLOS ALBERTO LAGOS SALGADO

Miembros del Comité:

Tesis para optar al grado de

Santiago de Chile, Marzo 2019

c MMXIX, C ARLOS A LBERTO L AGOS S ALGADO

En primer lugar, me gustarı́a agradecer a mi familia, por su apoyo incondicional en

Agradezco a la Comisión Nacional de Investigación Cientı́fica y Tecnológica por el

ÍNDICE DE FIGURAS viii

4. CASO DE ESTUDIO Y RESULTADOS 55

1.1. Evolución de oferta y demanda de mecánicos de aviones en EEUU . . . . . . 2

1.2. Ejemplo problema simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Solución problema simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4. Solución problema simple re-asignando vuelos . . . . . . . . . . . . . . . . 5

2.1. Esquema de planificación aérea . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2. Esquema de planificación aérea operacional . . . . . . . . . . . . . . . . . . 19

3.1. Evolución del dı́a t para cada avión . . . . . . . . . . . . . . . . . . . . . . 34

3.2. Conservación de flujo avión a . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.3. Conservación de flujo dı́a 1 para un avión cualquiera . . . . . . . . . . . . . 45

3.4. Conservación de flujo dı́a 2 para un avión cualquiera . . . . . . . . . . . . . 46

3.5. Conservación de flujo dı́a t para un avión cualquiera . . . . . . . . . . . . . 46

3.6. Ejemplo de horizonte rodante . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.1. Número de aviones en mantenimiento por dı́a . . . . . . . . . . . . . . . . . 57

4.2. Función de probabilidad de HP por tarea . . . . . . . . . . . . . . . . . . . 58

4.3. Distribución horas de inicio y fin LOFs . . . . . . . . . . . . . . . . . . . . 59

4.4. Distribución vencimiento de tareas iniciales . . . . . . . . . . . . . . . . . . 60

4.5. Perfil de anticipación de tareas por polı́tica . . . . . . . . . . . . . . . . . . 66

4.6. Ponderadores VFA dependiendo de LOFs . . . . . . . . . . . . . . . . . . . 68

4.7. Perfil de anticipación de tareas por polı́tica caso más dinámico . . . . . . . . 70

4.9. Perfil de anticipación de tareas en diferentes niveles de saturación . . . . . . 72

4.10. Perfil de anticipación de tareas desagregado por tamaño . . . . . . . . . . . 72

2.1. Trabajos revisados sobre FS-FA-CS . . . . . . . . . . . . . . . . . . . . . . 11

2.2. Trabajos revisados sobre ARP/AMRP . . . . . . . . . . . . . . . . . . . . . 13

2.3. Trabajos revisados sobre integración de etapas . . . . . . . . . . . . . . . . 15

2.4. Trabajos revisados sobre robustez . . . . . . . . . . . . . . . . . . . . . . . 18

2.5. Trabajos revisados sobre OAMRP/TAP . . . . . . . . . . . . . . . . . . . . 23

2.6. Trabajos revisados sobre manejo de disrupciones a nivel operacional . . . . . 25

2.7. Trabajos revisados sobre ADP . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1. Tamaño de flota doméstica principales aerolı́neas en Chile . . . . . . . . . . 56

4.2. Resultados caso base (50 réplicas) . . . . . . . . . . . . . . . . . . . . . . 64

4.3. Resultados caso nuevas LOFs (50 réplicas) . . . . . . . . . . . . . . . . . . 67

4.4. Resultados caso tareas más dinámicas (50 réplicas) . . . . . . . . . . . . . . 69

4.5. Resultados caso sin integración (50 réplicas) . . . . . . . . . . . . . . . . . 73

4.6. Resultados caso planificación descentralizada para HR-VFA1 (50 réplicas) . . 74

Una aparición inesperada de tareas de mantenimiento puede producir cambios signi-

Se estudió un problema de planificación de mantenimiento de una aerolı́nea que in-

En un caso de estudio basado en una aerolı́nea latinoamericana, mostramos el valor de

Palabras Claves: Mantenimiento de aviones, Programación dinámica aproximada, Plani-

We studied a dynamic airline maintenance scheduling problem, which involve daily

Keywords: Airline maintenance, Approximate Dynamic Programming, Task Scheduling,

En este capı́tulo se introduce un estudio de planificación diaria de tareas de mante-

El transporte aéreo es fundamental para la economı́a mundial y su crecimiento ha cam-

Dentro de una aerolı́nea, el área de mantenimiento es responsable de planificar y ejecu-

Dentro de los costos de mantenimiento, la mano de obra calificada representa cerca

Figura 1.1. Evolución de oferta y demanda de mecánicos de aviones en

Además de los costos, las actividades de mantenimiento pueden afectar negativamen-