O Modelo de Redes de Conexões é baseado no princípio de definir para qual voo será direcionada a aeronave de uma frota que pousou em um determinado aeroporto.
Neste modelo, os nós representam os possíveis momentos em que os voos chegam e partem de cada aeroporto, em uma escala temporal. Um nó fictício faz a função de "início do dia" - fonte mestra - e outro a de "fim do dia" - sorvedouro mestre (ABARA, 1989; SHERALI; BISH; ZHU, 2006).
São definidos três tipos de arcos (ABARA, 1989):
a. Arcos de Conexão, que interligam um nó de pouso com um de decolagem, cada um indicando uma conexão que pode ocorrer no aeroporto.
b. Arcos de Término, que interligam cada nó de pouso ao nó de "fim do dia" de um dado aeroporto, com o objetivo de indicar as aeronaves que permanecem no aeroporto ao final do dia.
c. Arcos de Origem, que interligam o nó de "início do dia" de um aeroporto com cada nó de decolagem, indicando as aeronaves que se encontram no aeroporto no início do dia.
É imprescindível, neste modelo, que todos os arcos de conexões sejam viáveis, ocorram as conexões no mesmo dia ou em dias diferentes. Isso significa que devem respeitar a disponibilidade de aeronaves no início e no fim do dia, além de que todas as conexões precisam respeitar o tempo mínimo de manutenção básica (turn-time) de cada aeronave (ABARA, 1989; SHERALI; BISH; ZHU, 2006).
A Figura 3.1 apresenta a estrutura da rede utilizada no modelo, em um aeroporto com 12 conexões: seis conexões de voo possíveis, três de origem e três de término (ABARA, 1989). Apesar de representados na figura, os "arcos" relativos aos voos não são criados, assim como os nós de "início do dia" e "fim do dia" (ABARA, 1989; SHERALI; BISH; ZHU, 2006).
Considerando que a rede tenha sido construída de maneira que cada voo que chegue a uma conexão possa se conectar a qualquer outro, desde que o horário de partida permita um tempo mínimo para inspeção e a conexão não seja proibida, a estrutura básica do modelo é composta por uma função objetivo e quatro grupos de restrições principais. O modelo pode ser descrito como se segue (ABARA, 1989).
Figura 3.1 - Modelo de Rede de Conexões. Xijf representa se aeronave do tipo f que veio do
voo i irá para o voo j (baseado em ABARA, 1989)
A função objetivo deste modelo, representada de maneira resumida na Eq. 3.17, visa à maximização do benefício de cada voo, Bv, descontados dos seguintes custos: custo pelo uso de aeronaves, Ca; custo pelo uso de aeronaves extras, Ce; custo pela falta de aeronaves em um aeroporto (desequilíbrio da rede / falta de continuidade), Cd; e o custo servir aos aeroportos com determinadas aeronaves, Cs, sendo que este último pode ser negativo, situação na qual passa a ser um estímulo para a alocação de uma frota a um dado aeroporto.
(3.17)
[max] Bv − (Ca + Ce + Cd + Cs)
Para descrever o modelo em detalhe, tome-se como base a variável de decisão Xijk, binária, que tem valor 1 apenas se a conexão do voo i para o
voo j está sendo feita com uma aeronave da frota k. Com essa proposição, uma sequência de valores Xijk iguais a 1 significa que estes arcos serão
usados como trilho de uma frota. Por exemplo, se as variáveis X0,1,9, X1,2,9,
trilho com os voos 1, 2, 3, 5 e 7, para a frota 9. Nestas variáveis, o índice i = 0 significa tratar-se de um voo inicial - isto é, a aeronave para estes voos já se encontrava no aeroporto - e o índice j = 0 significa tratar-se de um voo terminal - ou seja, a aeronave permanece no aeroporto ao final do dia.
Considerando F voos e K frotas e, ainda, que Pjk indica o benefício de
operar o voo j com uma aeronave da frota k, o benefício dos voos Bv pode ser calculado como a soma do benefício de cada voo que irá ocorrer, ou seja, para o qual há uma conexão, o que pode ser descrito conforme a Eq. 3.18. (3.18)
Bv
=
F i=0 F j=0 K k=1P
jkX
ijkO custo por se utilizar as frotas, Ca, pode ser calculado multiplicando-se um custo C1 devido à alocação da frota - em geral um valor
próximo de 1 -, multiplicado pela variável que indica o uso daquela frota em arcos de voo inicial, conforme representado na Eq. 3.19.
(3.19)
Ca
= C
1.
F j=0 K k=1X0jk
O custo pelo uso de aeronaves extras, Ce, pode ser calculado multiplicando-se um custo C2 - um valor alto pelo uso de cada aeronave
adicional, normalmente cerca de 800.000 -, multiplicado pelo número de aeronaves extra da frota k, indicado pela variável ek, conforme representado
na Eq. 3.20. (3.20)
Ce
= C
2.
k=1 Ke
kO custo pelo desequilíbrio da rede, isto é, da necessidade de uma aeronave em um aeroporto em que ela não se encontra, Cd, pode ser calculado multiplicando-se um custo C3 - um valor alto pela falta de
aeronaves, normalmente cerca de 500.000 -, multiplicado pela soma do número de aeronaves faltantes de cada frota em cada aeroporto. Considerando S o conjunto de todos os aeroportos, Osk o número de
aeronaves faltantes da frota k necessárias para iniciar voo no aeroporto s e Tsk o número de aeronaves faltantes da frota k necessárias para finalizar voo
no aeroporto s, esta restrição pode ser descrita conforme a Eq. 3.21.
(3.21)
Cd
= C
3.
S s=1k=1 K(O
sk+ T
sk)
O custo de servir a um dado aeroporto com uma determinada frota pode ser calculado multiplicando-se o custo de alocação desta frota k a um aeroporto, CSk, pelo número de aeroportos que foram servidos por aquela
frota; o custo de alocação total, Cs, é a soma do custo de alocação de cada frota. Considerando a variável Ysk, que indica se a frota k serve o aeroporto
s, o valor Cs pode ser calculado conforme a Eq. 3.22.
(3.22)
Cs=
k=1 K(CS
k.
s=1 SY
sk)
O primeiro grupo de restrições, relativo à cobertura de voo, garante que, no máximo, uma aeronave será alocada a cada voo, possibilitando apenas uma única conexão por voo j, conforme representado pela Eq. 3.23.
(3.23) F i=0 K k=1
X
ijkñ 1
j
= 0, 1, ..., F
O segundo grupo de restrições garante a continuidade dos equipamentos, isto é, garante que, se uma aeronave da frota k fez uma conexão para o voo l, então esta mesma frota deve ser usada na conexão
do voo l para o próximo voo. Em outras palavras, o objetivo é garantir que a frota que inicia um voo é a mesma que finaliza este voo, assegurando a viabilidade da solução prática. Esta restrição pode ser representada conforme a Eq. 3.24. (3.24) F i=0
X
ilk=
F j=0X
ljkl
= 0, 1, ..., F; k = 1, 2, ..., K
O terceiro grupo de restrições garante o equilíbrio da programação, ou seja, garante que o número de aeronaves de cada frota em um dado aeroporto seja o mesmo no início e no fim do dia. Isso é feito através do equilíbrio entre o número de chegadas e partidas de cada aeroporto, já que diferenças nestes valores indicam falta de aeronaves em cada aeroporto. Considerando Ds o conjunto de partidas do aeroporto s e As o conjunto de
chegadas ao aeroporto s, esta restrição pode ser representada conforme indicado na Eq. 3.25. Observando que os termos Osk e Tsk aparecem nesta
restrição, ela não é uma restrição estrita; entretanto, como há uma grande penalidade na função objetivo pelo desequilíbrio, boas soluções tenderão a manter o equilíbrio. (3.25) icDs
X
0ik+ O
sk=
icAsX
i0k+ T
sks= 1, 2, ..., S;k = 1, 2, ..., K
O quarto grupo de restrições impõe um limite para o número de aeronaves de cada frota, permitindo a construção de uma programação factível, evitando a alocação de mais aeronaves do que as disponíveis. Considerando Mk o número de aeronaves disponíveis na frota k, esta
restrição pode ser representada como indicado na Eq. 3.26.
(3.26)
F
Lembrando que a variável ek indica o número de aeronaves extra da
frota k, esta também não é uma restrição estrita, permitindo o uso de aeronaves extra; por outro lado, como ek aparece na função objetivo com
uma alta penalidade, boas soluções tenderão a não usar aeronaves extras.
Além destas restrições clássicas, como uma maneira de demonstrar a flexibilidade do modelo, o autor apresenta restrições adicionais - classificadas como extrínsecas -, para situações operacionais específicas, incluindo número de pernoites mínimos de cada frota em cada aeroporto, limitação no número de aeronaves por aeroporto, limitação do número de conexões por faixa horária - uma implementação similar à de slots - e a obrigatoriedade de um tipo de aeronave usar um dado aeroporto. A única limitação explicitada pelo autor, quanto as restrições que podem ser criadas, é a necessidade de que as variáveis sejam aditivas, isto é, o valor associado a um conjunto de voos precisa ser igual à soma dos valores dos voos individuais (ABARA, 1989).
A inclusão de algumas destas restrições pode fazer com que os tempos computacionais cresçam demasiadamente, impedindo soluções para casos práticos. Sem estas restrições adicionais, um problema com 400 voos programados, 60 aeroportos e três tipos de aeronaves envolve aproximadamente 6300 colunas e 1800 linhas, crescendo ainda se for considerado o processo de branch and bound para sua solução, dado que a maioria das variáveis precisa ser inteira. Pela concepção do modelo, é suficiente que apenas as variáveis de conexão sejam inteiras, mas elas são a grande maioria (ABARA, 1989).
Este modelo foi aplicado pela American Airlines para auxílio na solução de diversos problemas como a análise de alocação de bases de tripulação, redução de custos na alocação de aeronaves, ampliação dos lucros com limitação de pernoites em determinados aeroportos,
maximização do uso de determinados tipos de aeronave etc. (ABARA, 1989).
3.2.3.1. Considerações Sobre o Modelo
Os pontos fortes deste modelo são a consideração da dimensão tempo de maneira explícita, que permite uma grande flexibilidade para definir diversos tipos de restrições operacionais específicas. Um outro ponto forte é a idéia de penalização na função objetivo por conta de desequilíbrios na rede, o que também revela o primeiro ponto fraco: não garantir o fluxo contínuo de aeronaves, permitindo a ocorrência de aeronaves em excesso ou em falta nos aeroportos.
Adicionalmente, este modelo requer que todas as conexões possíveis sejam calculadas a priori, já que são representadas explicitamente pelos arcos; como o número de conexões possíveis tende a ser muito maior que o número de arcos de voo, o tamanho do modelo cresce demasiadamente com cada ampliação do número de voos possíveis em uma malha. Também este modelo se refere a diversos custos de operação, cujo valor nem sempre pode ser adequadamente determinado, dificultando sua aplicação prática.