Scien5fic sphere
4- Retailers distribution i) Big Distribution
Para avaliar o comportamento de uma função objetivo baseada no momento de transporte, algumas considerações adicionais foram feitas. É importante frisar, entretanto, que tais restrições, apresentadas a seguir, não modificam a essência do problema, que permanece um problema de Programação de Voos integrada à Alocação de Frotas:
y Demanda: considerada fixa por voo, sem redistribuição entre voos. y Voos opcionais: este modelo, simplificadamente, não considera a
existência de voos obrigatórios.
y Custos dos Voos: associados ao momento de transporte perdido, seja por conta de passageiros que não foram transportados, seja por assentos vazios em voos. Para facilitar a verificação da validade dos resultados, será considerada uma ocupação média mínima de 50%, ou seja, que passageiros não transportados e assentos vazios devem ser minimizados na mesma proporção. Em outras palavras, neste modelo, um passageiro não atendido tem, proporcionalmente, o mesmo custo de um assento ocioso.
9.3. O Modelo
O modelo desenvolvido para atender aos requisitos especificados é um modelo de minimização de custo de circulação em rede, tendo como base um grafo direcionado. Tal modelo foi baseado no Modelo de Rede Espaço-Tempo, e tem como principal objetivo definir o tipo de aeronave que será utilizado em cada voo (BERGE, HOPPERSTAD, 19931 apud KLABJAN, 2004), buscando a minimização das perdas totais - assentos vazios e demanda não atendida. Para tanto, será adotada uma função objetivo do tipo proposto no Capítulo 6, baseada no conceito de proporcionalidade entre custos de um voo e seu respectivo momento de transporte (SWAN; ADLER, 2006).
No modelo clássico, apresentado na seção 3.2.4, os nós são definidos por uma tríade: frota, instante de tempo e aeroporto. Neste modelo, entretanto, há dois tipos de nós: nós de pouso e nós de
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, 1993.
espera/decolagem. Esta diferenciação existe para permitir a consideração explícita dos slots e arcos de manutenção básica no modelo.
Interligando os pares de nós, existem arcos que podem ser de quatro tipos: os três dos modelos tradicionais e um quarto que representa o tempo de manutenção básica mínima após o voo, ou seja:
a. Arcos de Voo, que interligam um nó de decolagem em um aeroporto a um nó de pouso em outro aeroporto, representando um voo que pode ser um arco de voo potencial (com demanda) ou de reposicionamento (sem demanda).
b. Arcos de Manutenção Básica, que interligam um nó de pouso de um aeroporto a um nó de espera/decolagem neste mesmo aeroporto, indicando o tempo de manutenção mínima a considerar após cada arco de voo.
c. Arcos de Espera em Solo, que interligam um nó de espera/decolagem de um aeroporto a outro nó de espera/decolagem no mesmo aeroporto, indicando o tempo que a aeronave permanece esperando em solo, com disponibilidade para voar.
d. Arcos de Ciclo, que interligam o último nó de um aeroporto com o primeiro nó deste mesmo aeroporto, permitindo uma solução periódica (usualmente períodos diários ou semanais).
Além da maior flexibilidade que traz ao modelo, a diferenciação entre nós de pouso e espera/decolagem e entre os arcos de voo e seus respectivos arcos de manutenção básica é interessante, porque permite a consideração de slots de horário fixo - como adotados nos aeroportos nacionais, em que há um horário pré-definido para cada empresa realizar os pousos e as decolagens. Como os slots de pouso possuem um horário específico para o pouso, caso fosse considerado o tempo de manutenção como parte do tempo de voo - conforme a abordagem tradicional -, o horário
de chegada de um arco de voo não seria equivalente ao do nó que representa o slot de chegada, com uma representação temporal incoerente: o horário final do arco de voo seria diferente do horário do nó no qual ele termina. Ainda que tal incoerência pudesse ser aceita, ela tornaria mais complexa a definição das restrições que dependem do tempo, como a que limita o número de aeronaves utilizadas por frota.
A adoção de arcos de manutenção independentes dos arcos de voo aumenta a dimensão da rede, mas permite a correção dessa incoerência, além de permitir tempos de manutenção básica diferenciados para frotas diferentes e considerações dos custos desta manutenção básica na função objetivo, ainda que estas características não sejam exploradas neste instante.
A Figura 9.1 apresenta parte da rede usada no modelo, em um aeroporto com quatro voos chegando e quatro saindo, para uma aeronave.
Figura 9.1 - Representação em Rede Espaço-Tempo Adotada
O fluxo nos arcos desta rede significa a quantidade de aeronaves que passam por tais arcos, sendo um valor binário para cada arco de voo com
demanda associada e um valor inteiro não negativo em cada um dos demais arcos.
A estrutura básica do modelo é composta por uma função objetivo, que visa à minimização do momento de transporte perdido, e cinco grupos de restrições básicas, construídas em torno de duas variáveis de decisão. Para a descrição do modelo são considerados as seguintes variáveis, conjuntos e parâmetros:
Variáveis:
xijf : indica o número de aeronaves da frota f que fluem por cada um
dos arcos (i,j) ∈ L.
yij : vale 1 quando o voo (i,j) não é atendido e 0 caso contrário.
Conjuntos:
F : conjunto de frotas disponível para alocação, indexadas por f. Nf : conjunto dos nós que são atendidos por uma aeronave da frota f
∈ F. Cada nó representa um horário em um aeroporto para uma frota específica.
Nrd : conjunto dos nós cuja operação de decolagem é limitada (slots). Nra : conjunto dos nós cuja operação de aterrissagem é limitada
(slots).
L : conjunto dos arcos que unem os nós da rede, cada um deles sendo representado por um par de nós (i,j).
Lv : subconjunto de L, contendo apenas os arcos que representam movimentos de voo.
Lvd : subconjunto de Lv, contendo apenas os arcos que representam movimentos de voo com demanda.
Lt : subconjunto de L quem contém todos os arcos da rede que
incluem o instante t.
Parâmetros:
Dij : demanda do arco (i,j).
Tij : tempo do voo representado pelo arco (i,j).
Cf : capacidade, em passageiros de cada aeronave da frota f.
A partir dessas definições, descreve-se o modelo:
(9.1)
[min]
fcF(i,j)cLv(D
ij− C
f)
2.T
ij.x
ijf+
(i,j)cLvdD
ij2.T
ij.y
ij (9.2) fcFx
ij f+ y
ij= 1
≤(i, j) c Lvd
(9.3) o|(o,k)cLx
ok f−
d|(k,d)cLx
kd f= 0
≤k c N
f,≤f c F
(9.4) (i,j)cLtx
ijf[ A
f≤f c F
(9.5) fcFd|(i,d)cLvx
id f[ 1
≤i c Nrd
(9.6) fcFo|(o,j)cLvx
oj f[ 1
≤j c Nra
Variáveis Binárias: (9.7)x
ijfc
{0, 1}para ≤(i, j) c Lvd
(9.8)y
ijc
{0, 1}para ≤(i, j) c Lvd
Variáveis Inteiras: (9.9)x
ijfm 0 para ≤(i, j) c L\Lvd
A função objetivo, representada na Eq. 9.1, minimiza a soma dos momentos de transporte não aproveitados pelo transporte de assentos vazios e pelo não atendimento completo da demanda, com uma estrutura similar à já apresentada nas Eqs. 6.2 e 6.3. O primeiro termo da Eq. 9.1 representa o momento de transporte não aproveitado, devido aos assentos vazios ou à demanda não atendida. O segundo termo representa o
momento de transporte que não ocorreu devido ao não atendimento da demanda em voos não realizados.
Note-se que os termos que representam assentos vazios e passageiros perdidos são quadráticos, evitando que o primeiro termo tivesse sinal negativo quando algum voo fosse executado com uma frota de capacidade superior à demanda. Apenas inverter os sinais não resolveria este problema, porque a demanda também pode ser maior que a capacidade, repetindo o problema: a demanda perdida deve penalizar a função objetivo, ao invés de bonificá-la.
O primeiro conjunto de restrições, representado na Eq. 9.2, garante a cobertura dos voos, indicando que cada voo pode ser alocado a uma e apenas a uma aeronave, considerando todas as frotas. Como xijf representa
o fluxo de aeronaves da frota f no arco (i,j), o primeiro termo da Eq. 9.2 representa o número de aeronaves que atendem a um determinado voo - no caso, uma ou nenhuma aeronave. O segundo termo da Eq. 9.2, yij é a
variável de controle, que terá seu valor definido como 1 se e somente se o primeiro termo tiver valor zero, isto é, se este voo (i,j) não for atendido por nenhuma aeronave. Quando yij = 1, a demanda deste voo será considerada
totalmente perdida, gerando penalidade na função objetivo conforme o segundo termo da Eq. 9.1.
O segundo conjunto de restrições, representado na Eq. 9.3, garante a continuidade dos equipamentos, por meio do equilíbrio nos nós, isto é, o número de aeronaves que chegam em um dado nó deve ser exatamente igual ao número de aeronaves que partem daquele nó, para todos os nós da rede. O primeiro termo da Eq. 9.3 indica o número de aeronaves da frota f que chegam ao nó k e o segundo termo indica o número de aeronaves desta mesma frota que deixam o nó k. Note-se que não há distinção entre os nós da rede, sendo tais restrições válidas inclusive para os nós inicial e final, visto que não há fontes e sorvedouros de aeronaves.
O terceiro conjunto de restrições, representado na Eq. 9.4, garante o respeito à disponibilidade de aeronaves, isto é, que o número de aeronaves utilizadas de uma frota não supera o número de aeronaves disponíveis naquela frota. Considerando que a rede é cíclica e fechada, o número de aeronaves de uma frota é constante em qualquer instante t, uma vez que elas não surgem nem desaparecem em nenhum nó ou arco. Assim, é suficiente garantir que o número de aeronaves máximo de cada frota seja respeitado em um único instante t.
Assim como no modelo clássico da seção 3.2.4, considera-se que um arco "inclui o instante t" quando o instante representado pelo nó de origem deste arco for menor ou igual a t e o instante representado pelo nó de destino deste arco for maior que t. O valor de t para as restrições da Eq. 9.4 deve ser definido para um horário válido de acordo com o problema, isto é, dentro do período de programação voos. Por exemplo: se os horários de voo variam das 9:00 do dia 1, às 23:00 do dia 7, qualquer horário entre estes dois é considerado um horário válido para o instante t.
O quarto grupo de restrições, representado na Eq. 9.5, garante o respeito à capacidade de decolagens, isto é, o respeito às limitações de decolagens em aeroportos de operação restrita. Esse efeito é obtido limitando a 1 o fluxo de aeronaves em todos os arcos de voo que partem de um nó cujas decolagens são restritas, permitindo que apenas uma aeronave passe pelo nó que representa o slot.
O quinto grupo de restrições, representado na Eq. 9.6, é análogo ao quarto, garantindo o respeito à capacidade de pousos, isto é, o respeito às limitações de pousos em aeroportos de operação restrita.
As variáveis xijf e yij são binárias para os voos com demanda,
conforme representado pelas Eqs. 9.7 e 9.8. As variáveis xijf são inteiras e
não negativas quando representam os demais arcos da rede, conforme indicado pela Eq. 9.9.