Modelagem integrada para a programação de voos e a alocação de frotas: abordagens baseadas em... por Daniel Jorge Caetano - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub para obter uma versão completa.

DANIEL JORGE CAETANO

MODELAGEM INTEGRADA PARA A PROGRAMAÇÃO DE

VOOS E A ALOCAÇÃO DE FROTAS: ABORDAGENS

BASEADAS EM PROGRAMAÇÃO LINEAR INTEIRA E NA

META-HEURÍSTICA COLÔNIA DE FORMIGAS

Tese apresentada à Escola

Politécnica da Universidade

de São Paulo para

obtenção de Título de

Doutor em Engenharia.

Área de Concentração:

Engenharia de Transportes

Orientador:

Professor Doutor

Nicolau D. Fares Gualda

.

São Paulo

2011

Este exemplar foi revisado e alterado em relação à versão original, sob

responsabilidade única do autor e com a anuência de seu orientador.

São Paulo, 04 de julho de 2011

___________________________________

Autor: Daniel J. Caetano

___________________________________

Orientador: Nicolau D. F. Gualda

FICHA CATALOGRÁFICA

Caetano, Daniel Jorge

Modelagem integrada para a programação de vôos e aloca -

ção de frotas: abordagens baseadas em programação linear

inteira e na meta-heurística Colônia de Formigas / D.J. Caetano.

-- ed. Rev. -- São Paulo, 2011.

353 p.

Tese (Doutorado) - Escola Politécnica da Universidade de

São Paulo. Departamento de Engenharia de Transportes.

1. Transporte aéreo 2. Programação linear 3. Heurística

4. Pesquisa operacional I. Universidade de São Paulo. Escola

Politécnica. Departamento de Engenharia de Transportes II. t.

DEDICATÓRIA

Ao meu pai, Plínio Jorge Caetano, por me mostrar o quão maior

pode ser o mundo se estivermos dispostos a conhecê-lo.

AGRADECIMENTOS

Ao amigo e orientador Prof. Dr. Nicolau Dionísio Fares Gualda, pelo

auxílio na definição das diretrizes deste trabalho e constante apoio.

À CAPES, pelo apoio financeiro durante grande parte do tempo de

desenvolvimento deste trabalho.

Aos amigos MSc. Wágner de Paula Gomes, MSc. João Carlos Medau

e MSc. Antonio Martins Lima Filho, pela grande ajuda na compreensão do

problema tratado e pelas muitas discussões acerca de todas as etapas de

elaboração deste trabalho.

Aos amigos MSc. Ludmilson Abritta Mendes e Marcelo Beccaro

Bastos, dos quais o apoio técnico e emocional foi imprescindível para a

finalização deste trabalho.

A todos os professores que direta ou indiretamente orientaram,

transmitiram conhecimento e foram fonte de inspiração para o caminho

escolhido.

E, finalmente, aos meus pais Plínio ( in memoriam) e Dalva, aos quais

serei eternamente grato, por terem me possibilitado chegar até aqui.

RESUMO

Este trabalho propõe modelos matemáticos e heurísticas para a

definição da malha de voos de uma empresa aérea, como parte de seu

planejamento operacional, visando à maior eficiência de operação frente às

restrições relacionadas aos aeroportos, a equipamentos e à demanda. Em

especial, é proposta uma função objetivo, baseada no momento de

transporte, para a modelagem integrada dos problemas de Programação de

Voos e Alocação de Frotas que inclui elementos específicos para a

consideração de slots de pouso e decolagem.

A abordagem tem aplicação especialmente relevante no âmbito de

empresas aéreas de pequeno e médio porte atuando em mercados

regionais, cuja malha é composta principalmente por voos de curta duração,

em geral operando com aeronaves de pequeno e médio porte. Nestas

condições, tais empresas trabalham com margens de lucro limitadas e,

portanto, podem-se beneficiar sensivelmente da definição de uma malha

mais eficiente e eficaz.

Os modelos desenvolvidos, baseados em programação linear inteira

e na meta-heurística Ant Colony Optimization, foram aplicados com sucesso

ao caso de uma empresa aérea regional, com atuação no mercado

brasileiro, possibilitando a definição de malhas alternativas, bem como

fornecendo subsídos para a avaliação dos impactos na malha oriundos da

utilização de novas aeronaves.

ABSTRACT

This research proposes mathematical models and heuristics to define

the flight mesh of an airline, as part of its operational planning, considering

restrictions related to airports, equipment and demand. In particular, an

objective function is formulated, based on transport momentum, proposed

for the integrated modeling of Flight Scheduling and Fleet Assignment

problems that includes specific elements to consider landing and takeoff

slots at airports.

The approach is especially relevant for small and medium airlines

operating in regional markets, with short-haul flights, in general operating

with small or medium size aircraft. Accordingly, these companies work with

limited profit margins, and, therefore, they can take great benefit from a more

efficient and effective flight mesh.

The models proposed, based on integer linear programming and on

the Ant Colony Optimization meta-heuristic, were successfully applied to the

case of a regional airline with operations in Brazil, enabling the definition of

mesh alternatives as well as providing information for the assessment of

impacts in its flight network arising from the utilization of new aircraft.

SUMÁRIO

Capítulo 1 - Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.1. Objetivos, Metas e Contribuição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.2. Estrutura do texto

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Capítulo 2 - O Planejamento Operacional de Empresas Aéreas . . . . . 20

2.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2. Aspectos gerais do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3. Etapas Tradicionais de Solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.1. Definição de Voos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.1.1. Geração de Voos (Route Development) . . . . . . . . . . . . . . . . 26

2.3.1.2. Programação de Voos (Schedule Generation / Design) . . 28

2.3.2. Alocação de Aeronaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3.2.1. Alocação de Frotas (Fleet Assignment) . . . . . . . . . . . . . . . . . 31

2.3.2.2. Atribuição de Aeronaves (Maintenance Routing) . . . . . . . . 33

2.3.3. Alocação de Tripulantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.3.1. Definição de Viagens (Crew Pairing) . . . . . . . . . . . . . . . . . . . 36

2.3.3.2. Escala de Tripulantes (Crew Rostering) . . . . . . . . . . . . . . . . 37

2.4. Avanços Recentes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.6. Conclusões do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Capítulo 3 - Modelos Clássicos para a Alocação de Frotas

. . . . . . . . . 42

3.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2. Modelos para Alocação de Frotas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2.1. Modelo de Alocação de Frotas de Ferguson-Dantzig . . . . . . . . . 45

3.2.1.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 49

3.2.2. Modelo de Alocação de Aeronaves de Simpson . . . . . . . . . . . . . . 50

3.2.2.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.3. Modelo de Alocação usando Rede de Conexões . . . . . . . . . . . . . 53

3.2.3.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 60

3.2.4. Modelo de Alocação usando Rede Espaço-Tempo . . . . . . . . . . . 60

3.2.4.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 65

3.3. Modelos Integrados para Programação de Voos e Alocação de

Frotas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.3.1. Modelo Integrado Clássico

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.3.1.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 70

3.3.2. O Modelo Integrado de Soumis-Ferland-Rousseau . . . . . . . . . . . 70

3.3.2.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 72

3.3.3. O Modelo Integrado de Lohatepanont-Barnhart . . . . . . . . . . . . . . 72

3.3.3.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 81

3.3.4. O Modelo Aproximado de Lohatepanont-Barnhart . . . . . . . . . . . . 82

3.3.4.1. Considerações Sobre o Modelo . . . . . . . . . . . . . . . . . . . . . . . 86

3.4. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Capítulo 4 - Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.2. Origem da Otimização por Colônia de Formigas . . . . . . . . . . . . . . . . . . 90

4.3. A Heurística Simple Ant Colony Optimization (S-ACO) . . . . . . . . . . . . . 94

4.3.1. Formalização da Heurística S-ACO . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.4. A Meta-Heurística Ant Colony Optimization (ACO) . . . . . . . . . . . . . . . . 97

4.4.1. Representação de Problemas para ACO

. . . . . . . . . . . . . . . . . . . 98

4.4.2. Comportamento das Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.4.3. A Meta-Heurística

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.4.4. Critérios Heurísticos e o Papel das Melhorias Locais

. . . . . . . . 101

4.4.5. Aplicação a Problemas Dinâmicos . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.5. Variantes Comuns da ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.5.1. Ant System - Ant Cycle (AS-AC) . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.5.2. Elitist Ant System (EAS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.5.3. Ranked Ant System (ASrank) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.5.4. MAX-MIN Ant System (MMAS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.5.5. Ant Colony System (ACS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.5.6. Multiple Ant Colony System (MACS) . . . . . . . . . . . . . . . . . . . . . . . 110

4.5.7. Multiple Ant Colony Optimization (MACO) . . . . . . . . . . . . . . . . . . 111

4.6. Aplicação ao Planejamento Aéreo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.6.1. Roteirização de Aeronaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.6.2. Atribuição de Aeronaves

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.6.3. Definição de Viagens

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.7. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Capítulo 5 - Caracterização do Problema . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.2. Abordagem Adotada para a Programação de Voos Integrada à

Alocação de Frota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5.3. Considerações Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5.3.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5.3.2. Mercado Considerado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.3.3. Porte da Empresa Aérea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.3.4. Receita e Custos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.3.5. Seleção de Voos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

5.3.6. Tempos de Voo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.3.7. Demandas dos Voos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

5.3.8. Oferta de Voos, Assentos e Aeronaves . . . . . . . . . . . . . . . . . . . . 124

5.3.9. Restrições Aeroportuárias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Capítulo 6 - Momento de Transporte na Programação de Voos e

Alocação de Frotas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

6.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

6.2. Maximização de Lucro no Transporte Aéreo de Passageiros . . . . . . 126

6.3. O Momento de Transporte como Proxy de Custos e Receitas . . . . . 128

6.4. Função Objetivo Baseada em Momento de Transporte . . . . . . . . . . . 130

6.4.1. Ponto de Equilíbrio entre Oferta e Demanda . . . . . . . . . . . . . . . . 131

6.5. Proporcionalidade do Valor de Passagem por Voo . . . . . . . . . . . . . . . 136

6.6. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

Capítulo 7 - Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.2. Metas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

7.3. Procedimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7.4. Instâncias de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.5. Critérios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.6. Calibragem dos Parâmetros Básicos da Heurística ACO . . . . . . . . . . 145

7.6.1. Procedimento para Calibragem dos Parâmetros Básicos . . . . . 145

7.6.2. Seleção de Melhores Resultados pelo Critério de Ranking . . . 147

Capítulo 8 - Instâncias de Teste e Tratamento de Dados . . . . . . . . . . 149

8.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.2. Nomenclatura das Instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.2.1. Tipos de Malha Potencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

8.2.1.1. Malha Original . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

8.2.1.2. Malha Incluindo Congonhas . . . . . . . . . . . . . . . . . . . . . . . . . . 151

8.2.1.3. Malha Incluindo Congonhas e Guarulhos . . . . . . . . . . . . . . 152

8.2.2. Distribuições de Demanda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.2.2.1. Tipos de Faixa Horária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

8.2.2.2. Valores das Demandas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

8.2.3. Tipos de Frota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

8.2.4. Coeficientes da Função Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . 160

8.2.5. Tempos de Voo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

8.3. Instâncias Adotadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

8.3.1. Instâncias para Modelo Sem Realocação de Demanda . . . . . . 162

8.3.2. Instâncias para Modelo Com Realocação de Demanda e

Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

8.3.3. Instâncias para Calibragem de Parâmetros da Heurística . . . . 167

8.3.3.1. Calibragem do Feromônio Inicial . . . . . . . . . . . . . . . . . . . . . . 168

8.3.3.2. Definição de Processos de Heurística . . . . . . . . . . . . . . . . 168

8.3.3.3. Calibragem Final dos Modelos

. . . . . . . . . . . . . . . . . . . . . . . 169

8.4. Formatação de Dados de Entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

8.5. Construção da Rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

8.5.1. Voo Potenciais Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

8.5.2. Voos Alternativos e de Reposicionamento . . . . . . . . . . . . . . . . . . 172

8.5.3. Espera em Solo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

8.6. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

Capítulo 9 - Um Modelo Integrado para Programação de Voos e

Alocação de Frotas Sem Realocação de Demanda . . . . . . . . . . . . . . . . 176

9.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

9.2. Considerações Específicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

9.3. O Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

9.4. Implementação e Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

9.5. Aplicação à Malha de Uma Empresa Aérea Atuando no Mercado

Brasileiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

9.5.1. Instâncias Baseadas na Malha Original . . . . . . . . . . . . . . . . . . . . 185

9.5.2. Instâncias Adicionando Congonhas . . . . . . . . . . . . . . . . . . . . . . . . 189

9.6. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Capítulo 10 - Um Modelo Integrado para Programação de Voos e

Alocação de Frotas Com Realocação de Demanda e Janelas de

Tempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

10.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

10.2. Considerações Específicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

10.3. O Modelo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

10.4. Implementação e Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

10.5. Aplicação à Malha de Uma Empresa Aérea Atuando no Mercado

Brasileiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

10.5.1. Instâncias Baseadas na Malha Original . . . . . . . . . . . . . . . . . . . 204

10.5.2. Instâncias Adicionando Congonhas

. . . . . . . . . . . . . . . . . . . . . . 207

10.5.3. Instâncias com Congonhas e Demanda por Período

. . . . . . . 213

10.5.4. Mercado Compartilhado entre Congonhas e Guarulhos . . . . 224

10.6. Tempos de Execução e Níveis de Reposicionamento . . . . . . . . . . . 227

10.7. Consideração de Tempos de Voo por Frota . . . . . . . . . . . . . . . . . . . . 229

10.8. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

Capítulo 11 - Heurísticas Ant Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

11.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

11.2. Ant Group Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

11.2.1. O Procedimento Básico da AGO . . . . . . . . . . . . . . . . . . . . . . . . . 237

11.2.2. Construção da Solução na AGO . . . . . . . . . . . . . . . . . . . . . . . . . 238

11.2.3. Depósito de Feromônios na AGO . . . . . . . . . . . . . . . . . . . . . . . . 240

11.3. Modelagem de Rede para Aplicação da AGO ao Problema

Integrado da Programação de Voos e Alocação e Frotas . . . . . . . . . . . . . 241

11.3.1. Representação de Feromônios na Rede . . . . . . . . . . . . . . . . . . 243

11.4. Heurística Multiple Ant Group Optimization (MAGO) . . . . . . . . . . . . . 243

11.4.1. Inicialização de Feromônios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

11.4.2. Construção da Solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

11.4.2.1. Origem dos Valores Heurísticos . . . . . . . . . . . . . . . . . . . . . 249

11.4.3. Evaporação de Feromônios

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

11.4.4. Depósito de Feromônios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

11.4.5. Calibragem dos Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

11.4.6. Resultados da Aplicação da Heurística

. . . . . . . . . . . . . . . . . . . 254

11.5. Heurística Multiple Ant Group System (MAGS) . . . . . . . . . . . . . . . . . 256

11.5.1. Inicialização de Feromônios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

11.5.2. Construção da Solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

11.5.2.1. Origem do Uso de Feromônios como Informação

Heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

11.5.3. Depósito de Feromônios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

11.5.4. Calibragem dos Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

11.5.5. Resultados da Aplicação da Heurística

. . . . . . . . . . . . . . . . . . . 265

11.6. Melhorias Locais nas Heurísticas MAGO e MAGS . . . . . . . . . . . . . . 267

11.6.1. Melhoria Local LS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

11.6.2. Melhoria Local LS2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

11.6.2.1. Soluções Processadas pela LS2 . . . . . . . . . . . . . . . . . . . . 269

11.6.3 Heurística MAGO-LS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

11.6.4 Heurística MAGO-LS2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

11.6.5 Heurística MAGS-LS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

11.6.6 Heurística MAGS-LS2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

11.7. Análise Geral dos Resultados

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

11.8. Conclusões do Capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

Capítulo 12 - Conclusões e Recomendações . . . . . . . . . . . . . . . . . . . . . . 286

12.1. Recomendações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

Lista de Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Bibliografia Complementar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

Glossário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

Apêndice A - O Cenário Nacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

A.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

A.2. O Sistema Aeroportuário Brasileiro e a Demanda Doméstica de

Passageiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

A.2.1. Empresas Aéreas Atuando no Transporte Doméstico de

Passageiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

A.3. Condicionantes do Cenário Nacional . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

A.3.1. Informações Sobre a Demanda . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

A.3.2. Concentração da Demanda de Passageiros Domésticos . . . . . 313

A.3.3. Restrições Operacionais em Aeroportos Relevantes

. . . . . . . . 315

Apêndice B - Relação entre Coeficientes de Custo e Ocupação

Mínima de Aeronave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

B.1. Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

B.2. O Princípio do Equilíbrio de Operação . . . . . . . . . . . . . . . . . . . . . . . . . . 320

B.3. Relação entre Coeficientes de Custo e Ocupação Mínima . . . . . . . . 321

Apêndice C - Análise de Robustez do Modelo Integrado sem

Realocação de Demanda

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

C.1. Melhor Escolha de Frota para um Conjunto de Trilhos

. . . . . . . . . . . 324

C.2. Uso de Voos de Reposicionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

C.3. Uso de Voos de Reposicionamento Envolvendo Aeroportos de

Operação Restrita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

C.4. Conflito entre Número de Slots de Pouso e Decolagem . . . . . . . . . . 330

Apêndice D - Análise de Robustez do Modelo Integrado com

Realocação de Demanda

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

D.1. Alocação de Demanda Total e Disputa por Voos . . . . . . . . . . . . . . . . 333

D.2. Distribuição de Demanda entre Frotas Distintas . . . . . . . . . . . . . . . . . 337

D.3. Conflito na Escolha de Aeronaves e Voos Obrigatórios . . . . . . . . . . 341

Apêndice E - Tabelas de Calibragem de Parâmetros . . . . . . . . . . . . . . . 346

E.1. Calibragem da Heurística MAGO

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

E.2. Calibragem da Heurística MAGO-LS . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

E.3. Calibragem da Heurística MAGO-LS2 . . . . . . . . . . . . . . . . . . . . . . . . . . 348

E.4. Calibragem da Heurística MAGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

E.5. Calibragem da Heurística MAGS-LS

. . . . . . . . . . . . . . . . . . . . . . . . . . . 350

E.6. Calibragem da Heurística MAGS-LS2 . . . . . . . . . . . . . . . . . . . . . . . . . . 351

E.7. Ranking* de Conjuntos de Feromônio Inicial . . . . . . . . . . . . . . . . . . . . 352

E.8. Exemplo de Tabela de Testes para Depósito Inicial . . . . . . . . . . . . . . 353

15

Capítulo 1 - Introdução

A fim de atender ao crescimento da demanda de passageiros, o

movimento natural das empresas de transporte aéreo tem sido o aumento

da frequência dos voos, além da criação de novas rotas e, quando

justificável comercialmente, a adoção de voos diretos. Entretanto,

acompanhando este paulatino aumento de oferta ao longo dos anos,

torna-se visível também uma ligeira queda no número de assentos por voo

(SWAN, 2002).

Por outro lado, o aumento do número de voos decorrente da

evolução temporal da demanda pelo transporte aéreo, quando não

acompanhado do surgimento de novos aeroportos e pólos populacionais,

tem como decorrência direta uma maior taxa de utilização dos aeroportos já

existentes. Como consequência, alguns aeroportos podem passar a operar

abaixo de um nível de serviço aceitável, levando a medidas restritivas para

garantir a segurança da operação (MINISTÉRIO, 2008), possivelmente

afetando a viabilidade de voos que envolvam estes aeroportos. Tais fatos,

aliados à crescente competitividade advinda da desregulação do mercado

de transporte aéreo (IPEA, 2003; KLABJAN, 2004), podem ter graves

consequências para a saúde financeira das empresas que operam tais

voos, em especial aquelas de menor porte.

Uma vez que as medidas que mitigariam estes problemas, como as

expansões aeroportuárias e a criação de novos aeródromos, são de longo

prazo e pouco podem contribuir, no curto prazo, para reduzir os gargalos já

existentes (SWAN, 2002), torna-se fundamental para uma empresa a

possibilidade de remodelar sua malha aérea visando à manutenção da

viabilidade de suas operações. Tal remodelagem devem considerar as

mudanças das condições operacionais dos aeroportos e a evolução da

demanda, promovendo a redução de custos operacionais e melhorando as

16

condições competitivas da empresa (KLABJAN, 2004), levando a melhores

níveis de serviço oferecidos.

Não é uma situação específica do Brasil, mas também aqui os

gargalos supracitados se manifestam em alguns dos principais aeroportos

(CGNA, 2009; MAYO, 1999, MINISTÉRIO, 2008; CAETANO; GUALDA,

2008). Considerando que a maior parte do tráfego aéreo nacional, cerca de

65% em termos de receita (ANUÁRIO, 2007 apud OLIVEIRA, 2009), é

composto por tráfego de passageiros, tais restrições ganham ainda mais

relevância para as empresas aéreas operando neste mercado. A saída

adotada por algumas empresas é a adoção de aeroportos alternativos aos

saturados; entretanto, este tipo de medida torna-se complexo quando se

trata do transporte de pessoas, em especial para trajetos de curta distância,

como é o caso dos voos de grande parte das empresas atuando no

mercado brasileiro (ANAC, 2010a). Além disso, considerando-se a

manutenção da taxa média de crescimento da demanda de passageiros por

voos domésticos verificada nos últimos anos, na faixa dos 10% anuais

(INFRAERO, 2008), a situação pode-se agravar ainda mais no futuro, com

uma possível saturação de outros aeroportos.

Assim, tal contexto de crescente competitividade e significativas

limitações do sistema aéreo explicita a necessidade de otimizar as várias

etapas do planejamento operacional das empresas aéreas, que envolve

desde a definição das linhas aéreas a serem oferecidas, passado pela

determinação das frotas e aeronaves que serão usadas em cada voo, até a

atribuição de tripulação a cada um dos voos.

Este trabalho trata da definição de modelos matemáticos para a

otimização integrada de duas das etapas tradicionais do planejamento

operacional de uma empresa aérea: a Programação de Voos ( Schedule

Generation) e a Alocação de Frotas ( Fleet Assignment).

17

1.1. Objetivos, Metas e Contribuição

O objetivo central desta pesquisa de doutorado é modelar e resolver

o Problema de Alocação de Frotas ( Fleet Assignment Problem - FAP)

integrando elementos da etapa imediatamente anterior do processo, o

Problema da Programação de Voos ( Schedule Generation Problem - SGP).

Sem prejuízo da aplicação do modelo em outras situações, serão

consideradas especialmente as condições e restrições existentes no

panorama brasileiro, relativas a empresas de pequeno e médio porte

atuando no mercado regional. Especificamente, a partir de voos potenciais

propostos entre os diversos aeroportos e de demandas previstas, deve-se

determinar:

- Quais são os voos viáveis, com base na demanda de passageiros.

- Qual o tipo de aeronave a ser usado em cada um destes voos.

Nestes termos, a principal contribuição desta pesquisa é o

desenvolvimento de modelos para readequar a malha de empresas aéreas,

com foco em voos domésticos, visando à operação mais eficiente dos voos

como uma forma de melhorar a rentabilidade destas empresas, de forma

que os limites operacionais do espaço aéreo e aeroportuário sejam

respeitados e as demandas atendidas adequadamente.

1.2. Estrutura do texto

Esta tese está dividida em doze seções principais:

O Capítulo 1 introduz o problema e sua importância, apresenta

informações gerais sobre este trabalho, bem como seus objetivos e

contribuições.

18

A revisão bibliográfica é feita nos capítulos 2 a 4. O Capítulo 2

apresenta a caracterização do problema do Planejamento Operacional de

Empresas Aéreas, destacando as etapas clássicas de solução, bem como

os avanços recentes na área. O Capítulo 3 apresenta modelos clássicos

para a Alocação de Frota, seja de maneira isolada ou em conjunto com a

Programação de Voos. Finalmente, o Capítulo 4 apresenta a

meta-heurística Ant Colony Optimization e suas variantes mais comuns,

além de algumas aplicações específicas para o planejamento operacional

de empresas aéreas.

A caracterização do problema e a metodologia são apresentadas nos

capítulos 5 a 8. O Capítulo 5 apresenta a caracterização do problema

abordado neste trabalho, explicitando seus aspectos fundamentais e as

considerações gerais adotadas. O Capítulo 6 apresenta a estrutura básica

da função objetivo proposta por este trabalho, detalhando seus elementos e

seu significado. O Capítulo 7 apresenta a metodologia adotada para a

obtenção dos resultados apresentados neste trabalho. Finalmente, o

Capítulo 8 apresenta as instâncias consideradas para a aplicação dos

modelos desenvolvidos, bem como o processo de construção da rede

tomada como base para os mesmos.

As modelagens propostas são apresentadas nos capítulos 9 a 11,

incluindo em cada uma delas a aplicação ao caso de uma empresa aérea

regional atuando no mercado brasileiro. O Capítulo 9 apresenta um modelo

simplificado para solução do problema integrado de Programação de Voos e

Alocação de Frotas, sem realocação de demanda, com foco na validação do

comportamento do tipo de função objetivo proposta para a resolução do

problema em questão. O Capítulo 10 apresenta um modelo para solução do

problema integrado de Programação de Voos e Alocação de Frotas, com

realocação de demanda entre voos de aeroportos de um mesmo mercado

considerando janelas de tempo de atendimento, definição de ocupação

mínima e a possibilidade de uso de coeficientes de custo diferenciados para

19

frotas e voos específicos. Finalmente, o Capítulo 11 apresenta as

heurísticas do tipo Ant Group System, desenvolvidas neste trabalho com

base na meta-heurística Ant Colony Optimization.

O Capítulo 12 encerra este trabalho, com as conclusões e sugestões

para trabalhos futuros.

index-20_1.png

20

Capítulo 2 - O Planejamento Operacional de Empresas

Aéreas

2.1. Introdução

Segundo uma visão sistêmica, há basicamente cinco macrovariáveis

que explicam a dinâmica do sistema aéreo (FRYSZMAN, 1990):

a) Insumos Produtivos

b) Mercado

c) Fatores Exógenos

d) Desempenho da Empresa

e) Malha Aérea

A inter-relação entre eles pode ser representada por um diagrama de

causa e efeito, como o representado na Figura 2.1 (FRYSZMAN, 1990).

Figura 2.1 - Visão Sistêmica do Planejamento de Linhas de Empresa Aérea

(fonte: FRYSZMAN, 1990)

21

Os insumos produtivos são os elementos que a empresa dispõe para

exercer sua atividade fim, como pessoal e equipamento, como suas frotas

de aeronaves. O mercado é o ambiente comercial, o que inclui a demanda,

os modos de transporte concorrentes, a estratégia de marketing, dentre

outros. Os fatores exógenos são os condicionantes sobre os quais a

empresa não tem controle, como os custos de alguns insumos e

regulamentações, como as tarifárias (FRYSZMAN, 1990) e/ou de operação

de aeroportos (ANAC 2006, 2007, 2010a). O desempenho da empresa é

medido por variáveis que representam sua lucratividade e podem ser

usadas para a definição de metas de participação no mercado. Finalmente,

a malha aérea é o núcleo das operações de uma empresa, constituindo o

" mix de produtos" que direciona todas as outras áreas funcionais da

companhia aérea, para o cumprimento dos voos programados. Sua

definição depende dos insumos disponíveis, do mercado e dos fatores

exógenos, e influencia diretamente o desempenho financeiro da empresa

(FRYSZMAN, 1990).

Uma vez que o principal componente da malha aérea são os voos

oferecidos pela empresa, a determinação de quais serão estes voos,

respeitando a disponibilidade de aeronaves e tripulações, dentre uma

grande gama de possibilidades, constitui a base do problema denominado

Planejamento Operacional de Empresas Aéreas. Devido à complexidade

computacional e outros fatores de ordem organizacional, tradicionalmente

este planejamento é feito em etapas, sendo decomposto em subproblemas

(BARNHART et al., 2003; KLABJAN, 2004). A resolução integrada de

diferentes etapas, visando a resultados mais próximos do ótimo global, vem

sendo estudada com mais ênfase desde o final da década de 1990, mas em

geral os resultados não são aplicáveis a problemas de grande escala

(KLABJAN, 2004).

Com o objetivo de apresentar o contexto no qual se insere este

trabalho, esta seção apresenta uma visão geral sobre o processo do

index-22_1.png

22

Planejamento Operacional de Empresas aéreas, detalha as etapas em que

é tradicionalmente dividido e, finalmente, as recentes evoluções propostas

na literatura.

2.2. Aspectos gerais do problema

Embora cada empresa tenha o seu próprio processo para realizar as

tarefas do planejamento operacional, a maioria deles envolve etapas

similares, apresentadas na Figura 2.2 (KLABJAN, 2004).

Figura 2.2 - Processos do Planejamento Operacional de Empresa Aérea

(baseada em KLABJAN, 2004)

O momento em que cada um destes processos ocorre é variado. O

planejamento da frota e de tripulação é composto por decisões estratégicas,

23

de longo prazo, e usualmente refletem a missão da empresa aérea, como

ela pretende operar, combinação de carga/passageiros pretendida, dentre

outros (KLABJAN, 2004). O desenvolvimento da programação de voos, que

define o plano de serviços da empresa, ocorre, normalmente, com uma

antecedência de um ano e leva em consideração um grande número de

fatores, desde interesse mercadológico, previsões de demanda, capacidade

das aeronaves disponíveis, dentre outros (KLABJAN, 2004; RABETANETY;

CALMET; SCHOEN, 2006).

A atribuição de aeronaves e tripulantes, envolvendo aspectos de

manutenção, legislação, preferências dos tripulantes, rentabilidade, dentre

outros, ocorre preliminarmente desde que a programação de voos é

definida. Em geral, a atribuição de tripulação é iniciada cerca de 3 meses

antes do voo, sofrendo alterações até algumas semanas antes do voo

ocorrer. Com relação às aeronaves selecionadas para cumprir determinados

voos, apenas pequenas modificações são feitas, nas últimas semanas, para

adequar melhor o tipo de aeronave à demanda real, usualmente com um

modelo do tipo Demand Driven Dispatch (BERGE; HOPPERSTAD, 19931

apud KLABJAN, 2004; SHERALI; BISH; ZHU, 2006).

O processo do planejamento estratégico está ligado, também, ao

gerenciamento de receita (yield management) , preço e rentabilidade,

determinando a melhor política de preços e vendas para aumentar a

lucratividade. Os modelos usados para estas determinações são

substancialmente distintos daqueles envolvidos nos processos

anteriormente mencionados (KLABJAN, 2004); uma visão geral sobre tais

modelos pode ser encontrada na literatura (VAN RYZIN; TALLURI, 20022

apud KLABJAN, 2004), envolvendo detalhes sobre a definição de preços

1 BERGE, M; HOPPERSTAD, C. Demand driven dispatch: A method for dynamic aircraft

capacity assignment, models and algorithms. Operations Research, n.41, p.153-168.

2 VAN RYZIN, G; TALLURI, K. Revenue management. In: R. Hall, ed., Handbook of

Transportation Science. Kluwer Academic Publishers. p.559-661, 2002.

24

(MAYO, 1999) e distribuição de demanda (DUMAS; SOUMIS, 2008;

RABETANETY; CALMET; SCHOEN, 2006), por exemplo.

Finalmente, no dia da execução da operação, ocorrem ajustes finais

para a programação de voos, de maneira a considerar problemas (disruption

management) como atrasos, manutenções não previstas, dentre outros

(BISAILLON et al., 2010). Esse processo envolve uma nova definição de

trilhos, ou seja, da sequência de voos de cada aeronave ( aircraft recovery),

realocação de tripulantes ( crew recovery) e reacomodação dos passageiros

( passenger reaccommodation) (KLABJAN, 2004).

A solução para este problema como um todo é complexa, envolvendo

um número de variáveis e restrições que tornam o problema intratável

matematicamente quando considerado no todo, para problemas práticos

(HANE et al. , 1995; KLABJAN, 2004).

2.3. Etapas Tradicionais de Solução

Tradicionalmente, o Planejamento Operacional de Empresas Aéreas

é dividido em vários subproblemas. Alguns autores propõem um modelo em

quatro etapas (BARNHART et al. , 2003) e outros subdividem algumas

destas quatro etapas, formando modelos de cinco etapas

(GOPALAKRISHNAN; JOHNSON, 20053 apud GOMES, 2009; KLABJAN,

2004; LOHATEPANONT; BARNHART, 2004; RABETANETY; CALMET;

SCHOEN, 2006).

Uma combinação de todas estas subdivisões leva a um modelo com

três grandes etapas: a Definição de Voos, em que são definidos quais voos

serão oferecidos, a Alocação de Aeronaves, em que são definidas quais

aeronaves executam cada voo, e a Alocação de Tripulantes, em que são

3 GOPALAKRISHNAN, B.; JOHNSON, E. L. Airline crew scheduling: State-of-

the-art. Annals of Operations Research n.140, p. 305-337, 2005.

index-25_1.png

25

definidos quais os tripulantes de cada voo. Cada uma destas etapas pode

ser subdividida em duas subetapas, compondo um total de seis etapas

(CAETANO; GUALDA, 2009), apresentadas na Figura 2.3.

Figura 2.3 - Etapas de Modelagem do Planejamento Operacional de Empresa Aérea

Esta divisão em etapas reduz a complexidade de solução, embora os

modelos para algumas das subetapas permaneçam complexos o suficiente

para exigir tratamento por metodologias específicas (HANE et al., 1995).

Cada uma destas etapas é descrita nas próximas seções.

2.3.1. Definição de Voos

A Definição de Voos tem como objetivo a geração da programação

final de voos, isto é, quais voos serão executados e em que horário.

Usualmente sua solução é dividida em dois passos: a Geração de Voos, em

que se define os voos de interesse, e a Programação de Voos, em que se

determina quais deles ocorrerão, na prática, e em que horário. Para a

concretização desta etapa, é fundamental o conhecimento da demanda que,

no caso de voos de passageiros, é definida pela quantidade de pessoas -

passageiros potenciais - que desejam voar de uma cidade a outra, em um

período de tempo. Ao conjunto formado pelo número de passageiros

potenciais, sua origem, seu destino e faixa horária dá-se o nome de

mercado (LOHATEPANONT; BARNHART, 2004).

26

A demanda de um dado voo depende de diversos fatores, como, por

exemplo, a estrutura da malha aérea e a capacidade da aeronave utilizada

em cada voo; se não houver lugar em um dado voo, o passageiro daquele

voo pode optar por outro. À demanda total, que independe das limitações da

empresa aérea em atendê-la, dá-se o nome de "demanda não restrita"

(LOHATEPANONT; BARNHART, 2004).

As sub-etapas Geração de Voos e Programação de Voos são

descritas a seguir.

2.3.1.1. Geração de Voos (Route Development)

A Geração Voos é um dos pontos de partida do planejamento

operacional de uma empresa aérea. O objetivo desta etapa é definir quais

são os voos de interesse da empresa aérea, criando subsídios para uma

futura escolha dos melhores voos a serem oferecidos. O resultado de todo

este processo é um conjunto de voos de interesse que estejam de acordo

com as regras de operação dos diversos aeroportos e órgãos de controle do

espaço aéreo (KLABJAN, 2004; RABETANETY; CALMET; SCHOEN, 2006).

O estudo é iniciado com a definição das rotas ( trips) para cada

mercado de interesse. As rotas são inicialmente identificadas como pares de

cidades entre as quais há interesse em oferecer voos, sendo cada um

destes pares denominado par origem-destino. Esta determinação se inicia

cerca de 12 meses antes do início das operações daquela linha aérea

(RABETANETY; CALMET; SCHOEN, 2006) e, usualmente, sofre alterações

até cerca de 3 meses antes do início das operações (KLABJAN, 2004).

A determinação das rotas é feita, em geral, com base em critérios

mercadológicos aprovados pela direção da empresa, considerando diversas

questões que vão da demanda potencial em cada mercado até o

cumprimento de interesses específicos da empresa, como entrar no

27

mercado de uma concorrente ou mesmo criar um novo mercado (KLABJAN,

2004). Isto significa que esta determinação não segue diretamente critérios

financeiros, sendo possível que uma rota financeiramente inadequada seja

definida como prioritária por possibilitar a abertura de um novo mercado

para a empresa. Uma vez selecionadas as rotas, são definidos os voos

potenciais, ou seja, entre quais aeroportos serão realizados voos para o

cumprimento das rotas. Uma rota pode ser atendida por diversos conjuntos

diferentes de voos ( legs) , ou seja, ela pode ser atendida por um único voo

direto ou pelas mais variadas combinações de voos com escalas e/ou

conexões (SHERALI; BISH; ZHU, 2006).

Ao definir os voos potenciais, é fundamental identificar as demandas

para cada trecho específico, pois elas farão parte da seleção dos voos

financeiramente interessantes nas etapas posteriores. Uma vez que uma

rota pode ser composta por vários voos e que um trecho pode ser

compartilhado por mais de uma rota, a determinação da demanda

específica de cada trecho pode não ser trivial, sendo este assunto tópico de

pesquisas específicas (DUMAS; SOUMIS, 2008), envolvendo, por exemplo,

modelos de preferência e análise conjunta de custo e tempo de viagem

(RABETANETY; CALMET; SCHOEN, 2006).

Também é relevante identificar restrições específicas ainda nesta

etapa, como as limitações de operação em aeroportos restritos, uma vez

que não faz sentido definir um voo se a operação aeroportuária não é

permitida no horário em que o voo é interessante. Seria inadequado, por

exemplo, determinar um voo partindo ou chegando ao aeroporto de

Congonhas, na cidade de São Paulo, durante a madrugada, visto que, por

estar situado dentro da área urbana, próximo a áreas residenciais, não há

operação neste aeroporto nesse período do dia (ANAC, 2007).

28

Uma outra razão para que um voo não seja possível é a política de

operação dos aeroportos. Cada aeroporto possui uma capacidade de

pousos e decolagens que podem ser executados com segurança. Alguns

aeroportos, entretanto, operam próximos deste limite (conforme dados

apresentados no Apêncice A) e, para organizar o tráfego, a autoridade

aeroportuária define horários específicos em que uma companhia aérea

pode decolar ou pousar naquele aeroporto. Estes horários fixos são

chamados de slots (ANAC, 2006; MAYO, 1999).

2.3.1.2. Programação de Voos (Schedule Generation / Design)

A Programação de Voos é a etapa que seleciona os voos que serão

efetivamente ofertados e executados, tendo como base os resultados da

etapa de Geração de Voos. O resultado final desta etapa é a definição de

todos os voos a serem cumpridos, com a especificação de horário de cada

um deles, de maneira que maximizem a receita (KLABJAN, 2004) ou

minimizem o custo das operações. O resultado da Programação de Voos,

uma tabela com os horários dos voos (BARNHART et al. , 2003), servirá de

base para todas as outras etapas do planejamento (RABETANETY;

CALMET; SCHOEN, 2006).

Os voos potenciais definidos na Geração de Voos atendem, a priori,

às necessidades mercadológicas da empresa, às restrições operacionais

dos aeroportos e às regulamentações oficiais. Entretanto, eles não atendem

necessariamente a todas as restrições da empresa aérea, como número de

aeronaves disponíveis, tamanho das aeronaves, disponibilidade de

tripulantes, necessidade de manutenção etc. (RABETANETY; CALMET;

SCHOEN, 2006), o que pode levar a custos adicionais, atrasos ou

cancelamentos em algumas circunstâncias, devido à impossibilidade de

cumprir a programação. Por essa razão, é adequado que a seleção final dos

voos a serem executados leve em conta pelo menos algumas destas

restrições, em especial o número total de aeronaves disponíveis e, em certo

29

nível, a demanda de cada voo. Os critérios mais comuns são as já citadas

maximização da receita (KLABJAN, 2004) e minimização do custo

operacional (RABETANETY; CALMET; SCHOEN, 2006), também sendo

adotado o critério da maximização dos lucros (KIM; BARNHART, 2007).

A determinação de valores adequados de custo e receita, entretanto,

é bastante prejudicada no momento em que este planejamento é feito, pois

a determinação destes valores depende de uma série de decisões que

serão tomadas em etapas posteriores do processo.

Do ponto de vista dos custos, o tipo de aeronave alocado a cada voo,

assim como a alocação de tripulantes pode modificar significativamente os

custos operacionais (GOMES, 2009; SHERALI; BISH; ZHU, 2006). Do ponto

de vista das receitas, também há indefinições. Por exemplo, se em uma

etapa posterior for alocada uma aeronave com um menor número de

assentos do que a demanda existente, haverá perda de passageiros,

levando a uma perda de receita pelo não atendimento da demanda

disponível. Por outro lado, se uma aeronave maior que o necessário for

usada, haverá assentos ociosos, implicando outro tipo de perda, já que o

transporte do assento está ocorrendo, mas não gera qualquer tipo de receita

(SHERALI; BISH; ZHU, 2006). Além do número de passageiros

transportados, também a política de preços para os assentos tem influência

sobre a receita (MAYO, 1999) e, como consequência de todos estes fatores,

a determinação do lucro também é afetada.

Devido à dificuldade em determinar demandas, custos e receitas com

boa precisão, quando esta etapa é considerada isoladamente prevalecem,

muitas vezes, os critérios mercadológicos (KLABJAN, 2004) e de cobertura,

respeitando a restrição do número total de aeronaves (RABETANETY;

CALMET; SCHOEN, 2006).

30

Independentemente dos critérios utilizados para sua criação, é usual

que a tabela de programação de voos seja definida para períodos que

variam de um dia a uma semana, programação esta que deve ser repetida

consecutivamente (RABETANETY; CALMET; SCHOEN, 2006), embora

nada impeça que ela seja determinada para períodos mais longos. O

planejamento de voos domésticos é, usualmente, diário, enquanto que o

planejamento para voos internacionais, com um número menor de voos,

costuma ser semanal (KLABJAN, 2004).

Alguns autores dividem o problema da Programação de Voos em

outras duas etapas: Planejamento da Frequência de Voos ( Frequency

Planning), onde são definidas a quantidade de vezes que um voo é

executado em dado período de tempo para atender à demanda, e a Seleção

de Rota ( Timetable Development ou Route Selection), em que é definido

quando cada voo de uma rota será oferecido e incluído na programação

(RABETANETY; CALMET; SCHOEN, 2006).

2.3.2. Alocação de Aeronaves

A Alocação de Aeronaves tem como objetivo a determinação de qual

das aeronaves da empresa cumprirá cada um dos voos. Usualmente sua

solução é dividida em dois passos: a Alocação de Frotas, em que é definido

o melhor tipo de aeronave para cumprir um determinado voo, e a Atribuição

de Aeronaves, em que se define exatamente qual é a sequência de voos

que serão cumpridos por uma aeronave específica, considerando detalhes

específicos de manutenção. Estas duas sub-etapas são apresentadas a

seguir.

31

2.3.2.1. Alocação de Frotas (Fleet Assignment)

A Alocação de Frotas é a etapa que seleciona o melhor tipo de

aeronave para cumprir cada um dos voos selecionados na etapa de

Programação de Voos, considerando o melhor atendimento da demanda

(BARNHART et al., 2003), possivelmente usando o menor número de

aeronaves, preferivelmente com o uso balanceado das aeronaves (ABARA,

1989). O objetivo principal desta etapa é a maximização da lucratividade,

envolvendo estimativas das receitas e dos custos (HANE et al., 2004;

KLABJAN, 2004; SHERALI; BISH; ZHU, 2006) ou, simplesmente, buscando

a minimização do custo operacional, em um modelo de cobertura

(RABETANETY; CALMET; SCHOEN, 2006).

A maximização dos lucros é mais frequente, sendo a minimização de

custos indicada apenas para casos em que a quantidade de passageiros é

tão baixa que o tráfego de passageiros não se altere com variações nas

capacidades das aeronaves escolhidas para cada voo (ABARA, 1989). Em

outras palavras, se a demanda é menor que a capacidade da menor

aeronave da empresa, em princípio a receita de um voo não se altera em

função da aeronave escolhida para executá-lo.

Independente do tipo de função objetivo, a alocação deve ser feita

considerando diferentes tipos de restrições, como o atendimento da

demanda, a disponibilidade de aeronaves, a continuidade do fluxo de

aeronaves, tempo mínimo de permanência em solo de aeronaves de um

determinado tipo etc. (ABARA, 1989; KLABJAN, 2004; RABETANETY;

CALMET; SCHOEN, 2006). A consideração de outros fatores como

tripulação disponível, consumo de combustível, gates dos aeroportos e

barulho das aeronaves também pode ser feita (KLABJAN, 2004).

32

Não é necessário que o modelo tome a demanda como cativa de um

determinado voo, permitindo a existência de voos concorrentes e

redistribuição da demanda entre os voos que atendem a um dado mercado.

Essa redistribuição pode ser considerada com ou sem escalas/conexões no

modelo (HANE et al., 1994) e também é possível considerar recaptura de

demanda, que é o efeito de perder um passageiro para outra empresa em

um dado voo de sua rota com conexão, mas recuperá-lo em um voo

subsequente (RABETANETY; CALMET; SCHOEN, 2006).

Considerando a influência da demanda na alocação de frota, um

aspecto fundamental a ser considerado é a perecibilidade dos assentos, isto

é, o fato de que assentos que não foram vendidos no momento do voo são

desperdiçados (MAYO, 1999; SHERALI; BISH; ZHU, 2006). Essa

característica tem, como consequência direta, uma preocupação em não

alocar aeronaves com capacidade muito superior à demanda prevista para

um dado voo, além de indicar a necessidade de uma política de preços

adequada (MAYO, 1999; SHERALI; BISH; ZHU, 2006), sendo interessante

vender passagens abaixo do preço médio para um certo número de

assentos que, de outra forma, não seriam vendidos e voariam vazios,

usando-se do conceito de yield management, ou seja, de gestão de receitas

(CROSS, 1998a4 apud MAYO, 1999).

Por outro lado, a perda de passageiros por insuficiência de oferta

constitui uma perda de receita, ainda que seja uma perda de consideração

mais complexa devido aos possíveis efeitos de recaptura de demanda e

também ao efeito de propagação da redução de demanda para os trechos

seguintes de uma mesma rota (KLABJAN, 2004; SHERALI; BISH; ZHU,

2006); adicionalmente, esta perda de receita pode ser considerada variável

e crescente à medida que a incerteza da demanda de um voo aumenta

(FERGUSON; DANTZIG, 1956).

4 CROSS, R.G. Revenue Management - Maximização de receitas: táticas radicais para

dominar o mercado. Rio de Janeiro, Campus, 1998a.

33

Uma maneira alternativa de considerar os custos de voo, já que estes

são de determinação complexa nesta fase do planejamento, é o uso de

variáveis proxy, como o momento de transporte, que é obtido com a

multiplicação do número de assentos de uma aeronave pela duração de

cada voo que ela realiza (SWAN; ADLER, 2006).

2.3.2.2. Atribuição de Aeronaves (Maintenance Routing)

A Atribuição de Aeronaves é a etapa em que se define, para cada

frota, qual será o trilho de cada aeronave, ou seja, qual a sequência de voos

que cada aeronave específica irá executar. Essa atribuição deve ser feita de

maneira a assegurar que cada aeronave fique tempo suficiente nos

aeroportos, nos momentos adequados, para que sejam executadas todas as

tarefas de manutenção (BARNHART et al., 2003; KLABJAN, 2004).

As sequências de voos executados por uma aeronave, denominadas

trilhos, são tradicionalmente determinados de maneira cíclica, isto é, de

modo que uma aeronave parta de um dado aeroporto e, ao fim da

sequência, volte ao mesmo aeroporto inicial, já posicionada para executar

os mesmos voos novamente. Quando são usados modelos de fluxo em

rede, a necessidade de tempo para manutenção pode ser implementada de

maneira simplificada, fazendo com que cada aeronave passe pelo menos

uma noite do período de planejamento em um aeroporto específico

(RABETANETY; CALMET; SCHOEN, 2006).

Uma das dificuldades da modelagem desta etapa é a definição da

função objetivo, já que a determinação de um custo diferenciado para cada

aeronave pode ser complexa: como são da mesma frota, todas possuem

características muito similares. Assim, é comum que este problema seja

resolvido simplesmente buscando uma solução de cobertura viável ou,

ainda, implementando um fator multiplicador que privilegie atribuições que

34

garantam que rotas específicas sejam cumpridas com escalas, mas sem

conexões (KLABJAN, 2004).

Em geral, as modelagens utilizadas para a representação e solução

deste problema são do tipo fluxo em rede multicommodity ou partição de

conjuntos. A solução é comumente encontrada usando-se programação

linear inteira ou outros algoritmos exatos, bem como heurísticas específicas

(KLABJAN, 2004). Algumas modelagens bastante diferenciadas também

podem ser encontradas na literatura, como uma em que cada trilho é

considerado um tour-euleriano, recaindo em um Problema do Caixeiro

Viajante (TALLURI, 19965 apud KLABJAN, 2004). Em alguns problemas de

atribuição, com regras de manutenção bastante simplificadas, é até mesmo

possível encontrar a solução através do algoritmo húngaro (NOVAES,

1978).

2.3.3. Alocação de Tripulantes

A Alocação de Tripulantes tem como objetivo a geração da

programação dos tripulantes que executarão cada um dos voos

(RABETANETY; CALMET; SCHOEN, 2006; KLABJAN, 2004). Usualmente

sua solução é dividida em dois passos: a Definição de Viagens e a Escala

de Tripulantes (GOMES, 2009).

Na Definição de Viagens são, primeiramente, definidos grupos de

voos que poderão ser atribuídos a um tripulante e devem atender aos

critérios legais locais, denominados jornadas. Posteriormente são definidas

as viagens, que são sequências de jornadas que partem de uma base

domiciliar e voltam para esta mesma base (GOMES, 2009). A Escala de

Tripulantes, por sua vez, é a etapa em que se define qual tripulante irá

cumprir cada viagem, considerando critérios legais e técnicos, definindo a

5 TALLURI, K. Swapping applications in a daily airline fleet assignment. Transportation

Science, n.30, 1996.

35

programação de cada tripulante e, por consequência, qual será a tripulação

de cada voo. O objetivo da alocação de tripulantes é, em geral, a

minimização dos custos com tripulação (BARNHART et al., 2003;

GERSHKOFF, 19896 apud GOMES, 2009), podendo ou não considerar os

interesses e desejos dos tripulantes (KLABJAN, 2004).

Ainda que a lógica básica da atribuição de tripulantes seja sempre a

mesma, cada problema tem características específicas. Por exemplo,

dependendo do tipo de voo tratado, pode haver diferenças significativas na

alocação da tripulação. Nos EUA, os voos internacionais são relativamente

esparsos com relação aos voos domésticos daquele mesmo país

(BARNHART et al., 2003), o que leva a uma programação diária para os

voos nacionais e semanal para os voos internacionais (KLABJAN, 2004),

similar ao que acontece com a atribuição de aeronaves.

Além do período da programação, as condições operacionais

também costumam ser diferentes entre voos domésticos e internacionais.

Em voos domésticos é comum a ocorrência de operações de deadhead, isto

é, um tripulante ter de viajar como passageiro em um voo para ser

reposicionado, de acordo com as necessidades da empresa, algo que não

ocorre em voos internacionais (BARNHART et al., 19957 apud BARNHART

et al., 2003). Há também diferenças significativas na alocação dos

tripulantes, de acordo com suas atribuições na operação da aeronave. Os

membros da tripulação de cockpit, como piloto e copiloto, em geral são

mantidos unidos e sua alocação é, geralmente, limitada a alguns tipos de

aeronave. A tripulação de cabine, como comissários de bordo, por sua vez,

tem sua composição mais variada, sendo comumente alocados

individualmente e, normalmente, o tipo de aeronave não é uma restrição a

6 GERSHKOFF, I. Optimizing flight crew schedules. Interfaces 19, nº 4, p. 29-43, 1989.

7 BARNHART, C; HATAY, L; JOHNSON, E. Deadhead selection for the long-haul crew

pairing problem. Operations Research, n.43, p.491-499, 1995.

36

ser considerada (BARNHART et al., 2003; RABETANETY; CALMET;

SCHOEN, 2006).

Maiores detalhes sobre cada uma das sub-etapas da Alocação de

Tripulantes são descritas a seguir.

2.3.3.1. Definição de Viagens (Crew Pairing)

A Definição de Viagens é a etapa que, em linhas gerais, agrupa os

voos em jornadas e, posteriormente, estas jornadas são agrupadas em

viagens (GOMES, 2009). As jornadas são sequências de voos que devem

respeitar uma série de critérios, regras e regulamentações como duração

máxima, intervalo mínimo entre voos de um tripulante, sequência temporal

dos voos, limite das horas de voo e do número de pousos por tripulante,

entre outras (GOMES, 2009; KLABJAN, 2004).

As jornadas podem ter seu início e seu final em aeroportos distintos,

o que na maioria das vezes impede um tripulante de estar sempre em sua

base domiciliar. Como, em geral, há um limite para o número máximo de

dias que o tripulante pode ficar distante de sua base domiciliar, existe a

necessidade de agrupar as jornadas em viagens que iniciem e terminem na

base domiciliar dos tripulantes, dentro do limite de tempo regulamentar

(GOMES, 2009; KLABJAN, 2004). A Figura 2.4 mostra a relação entre voos,

jornadas e viagens, com início e fim em uma mesma base domiciliar.

De maneira geral, o objetivo dos modelos desenvolvidos para esta

etapa é a determinação de viagens que cubram todos os voos necessários

e, ao mesmo tempo, respeitem a todos os critérios legais e regulamentares

que regem o trabalho dos tripulantes. O resultado desta etapa é composto

por diversas viagens atribuídas a bases domiciliares específicas,

respeitando a todas as restrições impostas. Tais resultados serão usados na

index-37_1.png

37

etapa posterior, a Escala de Tripulantes, quando cada viagem será atribuída

a um determinado tripulante (GOMES, 2009).

Figura 2.4 - Relação entre voos, jornadas e viagens (GOMES, 2009)

A Definição de Viagens é, normalmente, formulada como um

problema de particionamento de conjuntos (KLABJAN, 2004), sendo que

cada linha da matriz de restrições define um voo programado e cada coluna

representa uma tripulação válida para o voo (RABETANETY; CALMET;

SCHOEN, 2006).

2.3.3.2. Escala de Tripulantes (Crew Rostering)

Nesta etapa são definidas as escalas de cada tripulante, compostas

por sequências de viagens. As escalas de cada tripulante devem atender a

vários requisitos, como a qualificação do tripulante para operar um dado tipo

de aeronave, além de sua disponibilidade (GOMES, 2009; KLABJAN, 2004).

A escala deve incluir as folgas, sobreavisos, reservas, treinamentos e

férias dos tripulantes, com o objetivo clássico de minimizar os custos

38

(BARNHART et al., 2003), além de buscar a satisfação dos tripulantes

(KLABJAN, 2004; KOHL e KARISCH, 20048 apud GOMES, 2009). Neste

último caso, quando são levadas em consideração as preferências dos

tripulantes em sua escala (usualmente considerando o tempo de serviço do

tripulante como critério para determinar a importância de suas requisições),

esta etapa passa também a ser denominada Preferential Bidding

(KLABJAN, 2004).

A Escala de Tripulantes é usualmente modelada como um problema

de cobertura (KLABJAN, 2004), geralmente solucionado com programação

linear inteira, adotando a técnica de geração de colunas (KLABJAN, 2004).

2.4. Avanços Recentes

Embora os problemas envolvidos no planejamento operacional de

empresas aéreas estejam sendo estudados desde a década de 1950

(DANTZIG; FULKERSON, 1954; FERGUSON; DANTZIG, 19559 apud

FERGUSON; DANTZIG, 1956; FERGUSON; DANTZIG, 1956; DANTZIG,

1963), foi a partir da década de 1970, com o " Airline Deregulation Act of

1978", nos Estados Unidos da América, que tais estudos passaram a ter

fundamental importância, dada a crescente competição entre as empresas,

que passaram a definir suas próprias linhas aéreas e estratégias de voo

(KLABJAN, 2005; SWAN, 2002). Segundo Richter (1989), foi nessa época

que os estudos acerca da definição de rotas e voos tiveram seu ápice,

assim como o estudo da demanda, com os trabalhos mais interessantes

sobre alocação de frota e aeronaves surgindo no início da década de 1980.

Ainda hoje, muitos dos problemas iniciais estão em aberto; além disso,

novos problemas ganharam relevância, devido ao crescimento e às

8 KOHL, N; KARISCH, S. Airline crew rostering: Problem types, modeling and optimization.

Annals of Operations Research n.127, p. 223-257, 2004.

9 FERGUSON, A. R; DANTZIG, G.B. The problem of routing aircraft. Aeronautical

Engineering Review, April, 1955, v.14, n.4, 1955.

39

mudanças na operação dos sistemas de transporte aéreo, bem como ao

surgimento de empresas aéreas concorrentes com diferentes filosofias