ALOCAÇÃO DE AERONAVES
A UM ESQUEMA DE VÔOS
SEMINÁRIO: OTIMIZAÇÃO COMBINATÓRIA E
PROGRAMAÇÃO LINEAR
ALOCAÇÃO DE AERONAVES A UM ESQUEMA DE VÔOS
UNIVERSIDADE FEDERAL DE ALAGOAS - UFAL
CIÊNCIAS EXATAS E TECNOLOGIA
MESTRADO EM MODELAGEM COMPUTACIONAL DE CONHECIMENTO
Prof. Dr. Henrique Pacca L. Luna
Prof. Dr. João Soletti
ALLAN GOMES DOS SANTOS
[email protected]
www.mcc007allangomes.cjb.net
Maceió, 2004.
ROTEIRO









MOTIVAÇÃO
OBJETIVOS
INTRODUÇÃO
APRESENTAÇÃO DO PROBLEMA
PROBLEMA DA ATRIBUIÇÃO
MODELO DE ATRIBUIÇÃO E SUA SOLUÇÃO
MODELO DE PROGRAMA LINEAR
COMENTÁRIOS FINAIS
REFERÊNCIAS BIBLIOGRÁFICAS
Motivação 1
ROTAER
AIP - BRASIL
MANUAL AUXILIAR DE
ROTAS AÉREAS
PUBLICACÒES DE
INFORMAÇÕES AERONÁUTICAS
Motivação 2
Maceió / Zumbi dos Palmares, MO SBMO
09 31 02S / 035 47 01W
PUB 20N UTC-3 VFR IFR L21,23,26 INFRAERO
12 - L6 (1) (2), 12 - (2600 X 45 46/F/A/X/T L14,15) - L12 - 30
CMB - QUEROSENE / GASOLINA
COM - TORRE 118.25
MET - CMA (1 A 10)
RDONAV - ILS/DME 12 IMO (1) 109.30
VOR/DME MCE 115.10
NDB COM 340
AIS - (4) (82) 322-1773 R 320
RMK - a. OBS VAC para entrada ou saída do cicuito de tráfego
b. Quando em aproximação visual, tomar cuidado para não confundir com a
RWY 14/32 do Aeroclube de Alagoas, situado a SE, a 7NM (13Km).
c. OBS concentração de urubus na aproximação final RWY 12.
d. AD habilitado para o TFC AÉREO INTL. As solicitações de FLT INTL
deverão ser encaminhadas ao DAC.
(4) Aceita plano de vôo e notificação por telefone (82) 322-3000
Obs.:RWY 46 - Número de classificação do pavimento (número que indica a resistência
de um pavimento para operações sem restrições)
F - Pavimento flexivel (asfalto)
A - Categoria de Resistência do Subleito (alta)
X - Categoria de pressão máxima admissível dos pneus (média)
T - Métodos de avaliação (técnica)
OBJETIVOS
 Tecer algumas considerações sobre o significado
prático da otimização no campo transporte aéreo;
 Determinar através da proposta de um problema o
número necessário de aviões para realizar um
serviço, identificando também a seqüência de
vôos que cada avião deve cumprir.
INTRODUÇÃO
 O estabelecimento
dos horários de aviões
comerciais
depende,
de
um
lado,
da
disponibilidade de aeronaves e de suas
características de operação e desempenho e, de
outro, dos aspectos ligados à demanda do
transporte;
 O problema de otimizar o uso da frota é
normalmente complexo, pois envolve um número
de parâmetros bastante amplo, além de estar
sujeito a condicionantes de ordem qualitativa ou
de difícil quantificação.
APRESENTAÇÃO DO PROBLEMA



Otimizar uma frota homogênea de aviões comerciais a partir de um esquema
de horários de vôo pré-fixado;
Uma empresa aérea de pequeno porte serve as cidades A, B e C de acordo
com o esquema de vôos apresentados no quadro 1;
Deseja-se determinar o número necessário de aviões para realizar um
circuito completo, identificando a melhor seqüência que cada avião deve
realizar.

QUADRO 1:
Esquema de vôos a ser cumprido
Vôo nº
Da cidade
Para cidade
Horário de
Partida
Horário de
Chegada
1
A
B
9:00h
12:00h
2
A
B
10:00h
13:00h
3
A
B
15:00h
18:00h
4
A
C
20:00h
24:00h
5
A
C
22:00h
2:00h
6
B
A
4:00h
7:00h
7
B
A
11:00h
14:00h
8
B
A
15:00h
18:00h
9
C
A
7:00h
11:00h
10
C
A
15:00h
19:00h
PROBLEMA DA ATRIBUIÇÃO
 O problema da atribuição é um caso especial do
Problema de Transporte onde cada unidade a ser
alocada a partir de uma origem para um
determinado
destino
é
considerada
individualmente, havendo igual número de origens
e destinos;
 A formulação clássica do problema da atribuição é
a seguinte: existem n indivíduos e n tarefas: são
conhecidos os custos Cij correspondentes a todas
as combinações de indivíduos e tarefas: trata-se
de atribuir as tarefas a esses indivíduos, de modo
que o custo total seja mínimo. (formar matrizes);
PROBLEMA DA ATRIBUIÇÃO
 A formulação matemática do problema da atribuição é a
seguinte:
n
n
min Z   Cij xij
i 1 j 1
sujeito a:
n
x
i 1
ij
n
x
com:
j 1
ij
1
(j = 1, 2, ..., n)
1
(i = 1, 2, ..., n)
xij  0
 O modelo matemático mostra que o problema da
atribuição é um caso especial de Programação Linear;
 Assim, xij será igual a 1, se o elemento i for designado
para a tarefa j, e xij = 0, no caso contrário.
MODELO DE ATRIBUIÇÃO E SUA SOLUÇÃO




O problema pode ser resolvido por meio de um modelo de atribuição, em que se
minimiza o tempo morto global das aeronaves;
Define-se a matriz A, cujo elemento aij representa o tempo morto dispendido pela
aeronave, onde “i” instante de chegada e “j” instante de partida;
Faz-se aij = α, indica a inviabilidade física da seqüência de vôos ij (chegada e
partida diferentes);
Exemplos:
– a10,1 é igual a 14 horas (vôo nº 10 = 19:00h/cidade A - vôo nº 1 = 9:00h/cidade A);
– a5,1 é infinito (α, ) ( vôo nº 5 = cidade C - vôo nº 1 = cidade A )
QUADRO 2: Matriz A analisando todas as sequências
MODELO DE ATRIBUIÇÃO E SUA SOLUÇÃO
Aplicando o algoritmo a cada uma das submatrizes, de acordo com a
sistemática do Problema de atribuição, chega-se à seguinte matriz reduzida
final:
Quadro 3: Matriz A’ solução do algoritmo de atribuição
Células assinaladas indicam uma solução ótima, no entanto outras soluções
ótimas possíveis podem ser analisadas através do posicionamento dos zeros.
1 - 8 - 4 - 10 - 5 - 9 - 3 - 6 - 2 - 7 - 1
(uma das soluções ótimas)
CÁLCULO DO NÚMERO MÍNIMO DE
AERONAVES



Uma aeronave, efetuando o circuito completo, gastará um tempo total que é
múltiplo de 24 horas;
O cálculo do tempo “T” = tempo de vôo + tempo de espera;
Uma vez que o programa de vôo da empresa aérea é diário, divide-se o valor de
T por 24, resultando assim o número de aviões necessários. No exemplo
exposto, temos: N = 120/24 = 5 aviões necessários;
Quadro 4: Cálculo do tempo T para uma aeronave realizar um circuito completo.
Nº do Nº do Vôo
Vôo
Seguinte
Tempo de
Vôo (horas)
Tempo de espera até o
próximo Vôo (horas)
Tempo decorrido entre
partidas sucessivas
(horas)
1
8
3
3
6
8
4
3
2
5
4
10
4
15
19
10
5
4
3
7
5
9
4
5
9
9
3
4
4
8
3
6
3
10
13
6
2
3
3
6
2
7
3
22
25
7
1
3
19
22
Total
-
34
86
T=120
MODELO DE PROGRAMAÇÃO LINEAR
 O objetivo do modelo é alocar as aeronaves às diversas rotas, de forma a minimizar os
custos; atendendo, por outro lado, a demanda e respeitando certas restrições operacionais.
C   DCijanija
ij
a
onde C é o custo global a ser minimizado , DCija representa o custo operacional direto
da aeronave a operando na rota ij e nija o número diário de vôos diretos na rota que
ligam i e j.
 As restrições do modelo são dadas:
a) A demanda, em cada rota, deve ser atendida, ou seja,
 LF
ija
 Sa  nija  Pij
(para cada rota ij)
a
onde:
LFija = fator de utilização médio (load factor)
Sa
= capacidade de assentos ofertados
Pij
= demanda média diária de passageiros
b) A disponibilidade de aviões não deve ser excedida, ou seja,
TB
ija
 nija  U a  N a
(para cada tipo de aeronave a)
ij
onde:
TBija = representa o tempo de vôo
Ua
= utilização média diária
Na
= número de aparelhos disponíveis
MODELO DE PROGRAMAÇÃO LINEAR (Cont.)
c) Equação de continuidade: em cada cidade atendida o número de chegadas
diárias de um certo tipo de aeronave deve ser igual ao número de partidas,ou seja,
n
ija
  n jia  0
j
(para cada cidade i e para
cada tipo de aeronave a)
j
d) Um número diário mínimo de frequências deve ser oferecido em cada rota, ou
seja,
n
ija
 NFij
(para cada rota ij)
a
onde:
NFij = número diário mínimo de frequência oferecida na rota ij
e) O número máximo de decolagens a partir de uma cidade
 n
ija
a
j
 NVi
(para cada aeroporto i)
onde:
NVi = é o número máximo diário de decolagens no aeroporto i
 As dimensões máximas do Problema de Programação Linear podem ser estimadas
como:
i) número de variáveis  E . a , onde E é o número de rotas (incluindo cada
sentido separadamente) e “a“
é o número de tipos de aeronaves
ii) número de restrições  2. E + a + Q. a + Q , onde Q é o número de cidades
atendidas
Exemplo, ligando as principais capitais brasileiras:
Q = 12 cidades
E = 24 rotas = 2 x 24 = 48 ligações
a = 3 ( tipos aeronaves: B737, B727, E120)
Assim, teremos: 144 variáveis e 147 restrições
CONSIDERAÇÕES FINAIS
 A ESTRUTURAÇÃO DO ESQUEMA
CONSTITUI UM PROCESSO CONTÍNUO.
DE
VÔOS
 FATORES POLÍTICOS E DE COMPETIÇÃO ENTRE AS
EMPRESAS TÊM SIDO DOMINANTES NA DEFINIÇÃO
DOS ESQUEMAS DE VÔO.
 DEVIDO AOS AUTOS CUSTOS OPERACIONAIS DO
TRANSPORTE AÉREO, MINIMIZAR O TEMPO MORTO
GLOBAL DAS AERONAVES TORNA-SE UM FATOR
ATUAL DE SOBREVIVÊNCIA DAS EMPRESAS.
 OTIMIZAÇÃO MUITAS VEZES NÃO É UM PROCESSO
DE BUSCA DO MELHOR ABSOLUTO MAS A PROCURA
SISTEMÁTICA DO MELHOR PRÁTICO.
REFERÊNCIAS BIBLIOGRÁFICAS
 NOVAES, Antonio Galvão. Métodos de otimização,
aplicações aos transportes: São Paulo. Ed. Edgard
Blucher ltda, 1978.
 SIMPSON, R. W. Scheduling and Routing Models for
Airline Systems. Publicações R68-3. Institute of
Technology, 1969.
 LUNA, Henrique Pacca L., GOLDBARG, Marco Cesar.
Otimização Combinatória e Programação Linear: Rio de
JAneiro. Ed. Campus, 2000.