Presentación de PowerPoint · 2020-01-20 · Modelo MIP determinístico Decisiones del modelo...

Un modelo de optimización dinámica para la

planificación eficiente de tareas de mantenimiento

de aviones

Carlos Lagos Salgado

Felipe Delgado

Mathias Klapp

Escuela de Ingeniería

Departamento de Ingeniería de

Transporte y Logística

CCIT19

Santiago, Chile

9 de octubre, 2019

1

Motivación

• El mayor grupo de aerolíneas de Latinoamérica

• Flota: 315 aviones

Chile

• Flota: 26 A320 FAM

• 8,2 MM pax anuales

• Participación de mercado: 61%

• Hub: Santiago

Fuente: LATAM y Junta Aeronáutica Civil (JAC)

2

94% de los vuelos

domésticos tienen

origen/destino Santiago

Fuente: Junta Aeronáutica Civil (JAC)

3

Motivación

Base de mantenimiento

• Única base de la aerolínea en Chile

• Capacidad30 aviones de un pasillo (A320 FAM) o 10 aviones de doble pasillo (B767 – B787)

• Turno noche dedicado a la flota doméstica

Hub: Santiago

4

Fuente: Oliver Wyman 5

6Fuente: Oliver Wyman

Agenda

1. El problema

2. Proceso de Decisión Markoviano

3. Modelo MIP determinístico

4. Políticas o heurísticas

5. Experimento

6. Resultados

7. Conclusiones

7

1. El problema

8

El problema

Aircraft 1 Aircraft NAircraft 2

Flota

Flota doméstica homogénea

9

El problemaCapacidad de la base

Flota doméstica homogénea

10

El problema

Avión 1 Avión N

….

Cada tarea tiene:• Fecha de aparición (release date)• Fecha de vencimiento (due date)• Requerimiento de recursos• Requerimiento de tiempo de procesamiento

Avión 2

Tareas

….

11

El problemaTareas

Tarea crítica• Si no se realiza antes del vencimiento, el avión queda fuera de operación dicho día• No importa cuantas tareas críticas no venzan, una es suficiente para dejar el avión

en tierra (aircraft on ground - AOG)

Tarea normal• Si no se realiza antes del vencimiento, el avión continúa su operación normal

dicho día y se externaliza la realización de la tarea

12

El problemaLíneas de vuelo de un día (LOFs)

Día 0 Día 1 Día 2

13

El problemaLíneas de vuelo de un día (LOFs)

Día 0 Día 1 Día 2

Varios vuelos

14

El problemaPlanificación

Día 0 Día 1

Mantenimiento Mantenimiento

Día 2

15

El problemaPlanificación

Día 0 Día 1 Día 2

16

El problemaPlanificación

Día 0 Día 1 Día 2

Mantenimiento 1

17

El problemaPlanificación

Día 0 Día 1 Día 2

Mantenimiento 1

Nuevas tareas disponibles

Tareas abiertas no realizadas

18

El problemaPlanificación

Día 0 Día 1 Día 2

Mantenimiento 1 Mantenimiento 2

19

El problemaAsignación de aviones a LOFs

Avión saludable

Avión enfermizo

5 tareas pequeñas

10 tareas medianas

20

El problemaAsignación de aviones a LOFs

Día 0 Día 1 Día 2

21

El problemaAsignación de aviones a LOFs

M

M M

M

Día 0 Día 1 Día 2

22

El problemaAsignación de aviones a LOFs

M

M M

M

Día 0 Día 1 Día 2

23

El problemaAsignación de aviones a LOFs

M

M M

M

Día 0 Día 1 Día 2

24

El problemaAsignación de aviones a LOFs

M

M M

M

Día 0 Día 1 Día 2

25

El problemaRestricción de capacidad por hora

26

A

B

C

A A A A A

B B B

C

tiempo

El problemaRestricción de capacidad por hora

27

A

B

C

A A A A A

B B B

C

9

9

tiempo

El problemaRestricción de capacidad por hora

28

A

B

C

A A A A A

B B B

C

9

9

tiempo

El problemaRestricción de capacidad por hora

29

A

B

C

A A A A A

B B B

C

0 1 2 3 4 5 6 7 8 9

tiempo

El problemaRestricción de capacidad por hora

30

A

B

C

A A A A A

B B B

C

A A A A B B B C -

A B C A C

0 1 2 3 4 5 6 7 8 9

tiempo

B

El problemaRestricción de capacidad por hora

31

A

B

C

A A A A A

B B B

C

A A A A B B B C -

A B C A C

0 1 2 3 4 5 6 7 8 9

tiempo

B

El problemaRestricción de capacidad por hora

32

A

B

C

A A A A A

B B B

C

A A A A A C B B B

A B C C A B

0 1 2 3 4 5 6 7 8 9

tiempo

El problemaRestricción de capacidad por hora

33

A A A A A C B B B

A B C C A B

0 1 2 3 4 5 6 7 8 9

tiempo

A A A A B B B C -

A B C A B C

0 1 2 3 4 5 6 7 8 9

tiempo

Antes

Después

2. Proceso de Decisión Markoviano

34

Proceso de Decisión MarkovianoMDP

• Etapas: Una por día

• Estado en cada etapa:

• Decisiones:• LOF que cada avión operará el día

• Qué aviones pasan por mantenimiento

• Qué tareas de mantenimiento de las disponibles se realizan en ellos

35

Proceso de Decisión MarkovianoMDP

• Espacio factible de acciones en el estado

36

1-2. Una LOF-avión o fuera de operación3. Tarea es realizada o no4. Tarea crítica vencida AOG5. Tarea planificada cuando avión está en mantenimiento6. Capacidad de la base7. Duración mínima de una tarea8-10. Restricciones de recursos por hora11-14. Construcción de bloques de mantenimiento a partir de LOFs15-19. Naturaleza de variables

Proceso de Decisión MarkovianoMDP

• Costo decisión en estado

37

AOG Externalización

Proceso de Decisión MarkovianoMDP

• Transición de estado

38

Tareas reveladas

Tareas pendientes

Proceso de Decisión MarkovianoMDP

• Política óptima

39

cost-to-go

Proceso de Decisión MarkovianoMDP

• Política óptima

40

cost-to-go

3. Modelo MIP determinístico

41

Modelo MIP determinísticoDecisiones del modelo

Supone información perfecta de tareas futuras al comienzo delhorizonte de planificación

Decisión óptima se puede determinar al comienzo del horizonte

Perfect Information Relaxation - PIR (Brown, Smith, y Sun, 2010)

42

4. Políticas o heurísticas

43

Políticas o heurísticasResumen

• Política 1: Miope

• Política 2a: VFA1

• Política 2b: VFA2

• Política 3: HR

• Política 4a: HR-VFA1

• Política 4b: HR-VFA2

44

Políticas o heurísticasPolítica 1: Miope

1 2 3 4 5 6 7 8

Hoy

9 10

45

Políticas o heurísticasPolítica 1: Miope

2 3 4 5 6 7 8

Hoy

9 10

46

Políticas o heurísticasPolítica 1: Miope

3 4 5 6 7 8

Hoy

9 10

47

Políticas o heurísticasPolítica 2: VFA

1 2 3 4 5 6 7 8

Hoy

9 10

48

VFA

Carga de trabajo que se deja pendiente con vencimiento en cada

uno de los próximos cuatro días

Políticas o heurísticasPolítica 2: VFA

1 2 3 4 5 6 7 8

Hoy

9 10

• Dos opciones para VFA:1. Valores criterio experto Política 2a: VFA1

2. Valores calibrados Política 2b: VFA2

49

VFA

Políticas o heurísticasPolítica 2: VFA

2 3 4 5 6 7 8

Hoy

9 10

50

Políticas o heurísticasPolítica 2: VFA

3 4 5 6 7 8

Hoy

9 10

51

Políticas o heurísticasPolítica 3: HR

1 2 3 4 5 6 7 8

Hoy

9 10

Incorpora pronóstico de tareas futuras

52

Políticas o heurísticasPolítica 3: HR

2 3 4 5 6 7 8

Hoy

9 10

53

Políticas o heurísticasPolítica 3: HR

3 4 5 6 7 8

Hoy

9 10

54

Políticas o heurísticasPolítica 4: HR-VFA

1 2 3 4 5 6 7 8

Hoy

9 10

55

VFAIncorpora pronóstico de tareas futuras

Políticas o heurísticasPolítica 4: HR-VFA

1 2 3 4 5 6 7 8

Hoy

9 10

VFA

• Dos opciones para VFA:1. Valores criterio experto Política 3a: HR-VFA1

2. Valores calibrados Política 3b: HR-VFA2

56

Incorpora pronóstico de tareas futuras

Políticas o heurísticasPolítica 4: HR-VFA

2 3 4 5 6 7 8

Hoy

9 10

57

Políticas o heurísticasPolítica 4: HR-VFA

3 4 5 6 7 8

Hoy

9 10

58

Políticas o heurísticasResumen

• Política 1: Miope

• Política 2a: VFA1

• Política 2b: VFA2

• Política 3: HR

• Política 4a: HR-VFA1

• Política 4b: HR-VFA2

59

Políticas o heurísticasResumen

• Política 1: Miope

• Política 2a: VFA1

• Política 2b: VFA2

• Política 3: HR

• Política 4a: HR-VFA1

• Política 4b: HR-VFA2

• Política aerolínea

• Cota inferior: Información perfecta (PIM)

60

5. Caso de estudio

61

Caso de estudioDescripción

Simulado a partir de información de operación doméstica de LATAM

• Aviones: 30

• Días: 30

• Recursos: 2 tipos

• Capacidad base: 20

• LOFs: Operación SCL

• Oferta: Necesaria para satisfacer demanda esperada (𝜌 = 1)

• Réplicas: 50

• Tiempo límite para resolver problema de cada día: 180 segundos

62

6. Resultados

63

ResultadosCaso base (50 réplicas)

64

• Política aerolínea externaliza un 83% más de carga de trabajo que política híbrida

• VFA2 evita AOG y reduce el gap a un tercio de VFA1, manteniendo tiempo de cómputo

• Políticas con HR alcanzan las mayores coberturas de tareas con valores sobre el 97% ycombinadas con VFA obtienen resultados cercanos al PIM con gaps inferiores al 4%

ResultadosCaso base - Anticipación

65

ResultadosCaso 2: Diferentes niveles de saturación HR-VFA1 – Anticipación por tipo de tarea

66

ResultadosCaso 3: Planificación de mantenimiento sin integración con asignación de LOFs para HR-VFA1

67

• Con un enfoque secuencial aumenta 15% las tareas no realizadas y 13% los recursosexternalizados producto de ellas

ResultadosCaso 4: Planificación de mantenimiento descentralizada para HR-VFA1

68

Recursos de mantenimientoTAP

Centralizado Centralizado

ResultadosCaso 4: Planificación de mantenimiento descentralizada para HR-VFA1

69

Descentralizado Centralizado

TAP Recursos de mantenimiento

ResultadosCaso 4: Planificación de mantenimiento descentralizada para HR-VFA1

70

Centralizado Descentralizado

TAP Recursos de mantenimiento

ResultadosCaso 4: Planificación de mantenimiento descentralizada para HR-VFA1

71

TAP

Descentralizado Descentralizado

Recursos de mantenimiento

ResultadosCaso 5: Planificación de mantenimiento descentralizada para HR-VFA1

72

• El sistema incurre en importantes costos cuando los recursos son descentralizados

7. Conclusiones

73

Conclusiones

• Modelamos un proceso de decisión dinámico que incluye la llegada de tareasestocástico durante el horizonte de planificación.

• En nuestros experimentos el incorporar VFA permite obtener mejores resultadosque la política de la aerolínea.

• La política de horizonte rodante es superior, empíricamente, a las políticas deVFA, y se sugiere combinar ambas políticas para aumentar en un 14% el nivel deservicio respecto a la política actual de la aerolínea

74

Conclusiones

• Un alto porcentaje de las tareas deben ser realizadas en su vencimiento

• Las tareas que deben ser utilizadas para anticipar trabajo deben ser pequeñas

• Es posible estimar el beneficio marginal de una unidad porcentual de recursos extra,en términos de externalización de trabajo

• Se comprobó la existencia de economías de escala en la planificación demantenimiento por lo que se recomienda que las aerolíneas relativamentepequeñas compartan los recursos de mantenimiento

Lecciones

75

Gracias

Carlos Lagos Salgado (cblagos@uc.cl)

Felipe Delgado (fdb@ing.puc.cl)

Mathias Klapp (maklapp@ing.puc.cl)

Escuela de Ingeniería

Departamento de Ingeniería de

Transporte y Logística

CCIT19

Santiago, Chile

9 de octubre, 2019

76