💻 computer science

Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

Este artigo apresenta uma metaheurística de Busca de Vizinhança Variável reduzida (rVNS) cooperativa para otimizar o complexo Problema de Roteamento e Escalonamento de Veículos com Capacidade e Múltiplas Viagens com Janelas de Tempo e Intervalos de Refeição (MTCVRSPTW-MB) para operações de catering aeroportuário, demonstrando sua eficiência superior e redução de quilometragem em relação a métodos exatos em instâncias da vida real no Aeroporto Internacional de San Francisco.

Autores originais: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Publicado 2026-07-07

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um aeroporto movimentado como um quebra-cabeça gigante de alto risco. De um lado, você tem centenas de aviões chegando e partindo, cada um precisando de comida carregada ou descarregada. Do outro lado, você tem uma frota de caminhões e motoristas, cada um com habilidades específicas, tempo limitado e regras rigorosas sobre quando podem fazer uma pausa para o almoço.

O objetivo é simples: alimentar cada avião no prazo usando o menor número de milhas percorridas pelos caminhões. Mas a matemática por trás disso é incrivelmente complexa. Se você tentar resolver isso com um programa de computador padrão, é como tentar encontrar um grão de areia específico em uma praia verificando cada grão um por um — leva tempo demais.

Este artigo apresenta uma maneira mais inteligente e rápida de resolver este quebra-cabeça usando um método chamado rVNS (Variable Neighbourhood Search reduzida). Veja como ele funciona, detalhado através de conceitos do cotidiano:

1. O Problema: O "Tetris" da Comida de Aeroporto

Pense na equipe de solo do aeroporto jogando um jogo de Tetris de alta velocidade.

Os Blocos: São as tarefas (carregar um avião, descarregar um avião).
As Vagas: São os motoristas e caminhões.
As Regras: Um motorista só pode dirigir um caminhão específico; um caminhão só pode carregar certa quantidade de comida; um motorista deve fazer uma pausa de 30 minutos para o almoço entre 4 e 5 horas após o início; e um avião deve ser alimentado dentro de uma janela de tempo específica.

No passado, os pesquisadores tentaram duas formas de resolver isso:

A Maneira "Perfeita" (Método Exato): Tentar calcular todas as possibilidades para encontrar a solução absoluta. Isso é como tentar ler todos os livros de uma biblioteca para encontrar a melhor história. É preciso, mas demora muito.
A Maneira "Rápida" (Heurística Gananciosa/Greedy): Fazer a melhor escolha disponível no momento exato. Isso é como pegar o livro mais próximo sem olhar os outros. É rápido, mas frequentemente leva a um resultado medíocre.

2. A Solução: O "Embaralhamento Inteligente" (rVNS)

O novo método, rVNS, é como um mestre de quebra-cabeças que sabe que, às vezes, você precisa quebrar um bom arranjo para criar um melhor.

Em vez de tentar construir o quebra-cabeça perfeito do zero, o algoritmo começa com um arranjo decente e então joga um jogo de "Embaralhar e Trocar".

O Embaralhamento: Ele escolhe aleatoriamente algumas tarefas (blocos) e as remove do cronograma, colocando-as de volta em uma "sala de espera".
A Troca: Ele então tenta colocar essas tarefas de volta, mas desta vez, tenta encaixá-las em lugares diferentes ou trocá-las com outras tarefas para ver se o quadro geral fica melhor.

Por que "Reduzida"?
Normalmente, esses algoritmos tentam embaralhar grandes blocos do quebra-cabeça, o que é lento. Este novo método embaralha pequenos blocos, mas faz isso de forma muito rápida e repetitiva. É como um chef provando uma sopa e adicionando uma pitada de sal, e provando novamente, em vez de tentar reescrever toda a receita a cada vez.

3. O Ingrediente Secreto: Duas Estratégias Diferentes

O algoritmo é inteligente o suficiente para saber quando focar no que importa. Ele possui dois modos:

Modo A (O "Preenchedor"): Seu principal objetivo é garantir que nenhuma tarefa seja deixada para trás. Ele embaralha o cronograma para garantir que cada avião seja alimentado.
Modo B (O "Economizador de Milhas"): Uma vez que a maioria das tarefas é atribuída, ele muda o foco para economizar combustível. Ele procura maneiras de rearranjar os caminhões para que dirijam menos milhas entre os aviões.

4. O "Reunião de Equipe" (Paralelização)

Para tornar isso ainda mais rápido, os pesquisadores não usaram apenas um cérebro de computador; eles usaram uma equipe. Imagine um grupo de detetives tentando resolver um crime. Em vez de uma pessoa verificar cada pista, eles dividem o trabalho:

Equipe de Detetives 1 trabalha no cronograma do turno da manhã.
Equipe de Detetives 2 trabalha no cronograma do turno da tarde.
A cada 10 segundos, eles se reúnem, compartilham suas melhores ideias e combinam suas descobertas.

Isso garante que eles não fiquem presos em um "beco sem saída" (um ótimo local) onde pensam ter encontrado a melhor solução, mas na verdade perderam uma melhor.

5. Os Resultados: Mais Rápido, Melhor e Mais Suave

Quando testaram este novo método com dados reais do Aeroporto Internacional de San Francisco (SFO):

Taxa de Sucesso: Os métodos antigos consegravam atribuir cerca de 80–89% das tarefas. O novo método rVNS atribuiu de 99% a 99,8% das tarefas. Ele quase nunca deixa um avião sem comida.
Economia de Combustível: Como ele rearranja o cronograma de forma mais eficiente, os caminhões percorreram cerca de 20% a 30% menos milhas do que antes.
Velocidade: Ele encontrou essas soluções quase perfeitas em menos de um minuto, o que é rápido o suficiente para ser usado em operações em tempo real.

Resumo

Em suma, este artigo apresenta um novo algoritmo de "embaralhamento inteligente" que ajuda os gestores de aeroportos a atribuir tarefas de entrega de comida a motoristas e caminhões. Ao dividir o problema em partes menores, embaralhando-as aleatoriamente para encontrar melhores encaixes e usando uma equipe de computadores para trabalhar juntos, o sistema garante que quase todos os aviões sejam alimentados, enquanto dirige significativamente menos milhas do que os métodos anteriores. Ele transforma um quebra-cabeça caótico e impossível de resolver em uma rotina diária gerenciável e eficiente.

Resumo Técnico: Atribuição e Otimização de Operações de Handling Aeroportuário via rVNS

Definição do Problema
O estudo aborda a complexa otimização combinatória das operações de handling (serviços de solo) aeroportuários, focando especificamente nos serviços de catering. O problema central é modelado como o Problema de Roteamento e Escalonamento de Veículos com Múltiplas Viagens, Capacidade Limitada, Janelas de Tempo e Intervalos de Refeição (MTCVRSPTW-MB), estendido para acomodar uma frota heterogênea de caminhões e motoristas com diferentes qualificações e padrões de carga.

O objetivo é duplo:

Primário: Maximizar o número de tarefas de catering (carga/descarga de aeronaves) atribuídas aos motoristas e caminhões disponíveis.
Secundário: Minimizar a quilometragem total necessária para executar essas tarefas.

O problema é limitado por regras operacionais rigorosas, incluindo:

Restrições de Motoristas: Escalas de turno, intervalos obrigatórios de 30 minutos para refeição (ocorrendo 4 a 5 horas após o início do turno) e requisitos de qualificação para tipos específicos de aeronaves e companhias aéreas.
Restrições de Caminhões: Limites de capacidade, tipos específicos de caminhão (14FT, 16FT, 22FT) e disponibilidade diária limitada.
Restrições de Tarefas: Janelas de tempo para execução, compatibilidade entre caminhão/motorista e o voo/companhia aérea específica, e requisitos de volume.
Restrições de Missão: Regras que regem missões de múltiplas tarefas, tais como a proibição de descargas domésticas após cargas internacionais na mesma missão, garantia de tempo de viagem suficiente entre tarefas e exigência de que todas as missões comecem e terminem na unidade principal de catering.

O estudo utiliza dados reais do Aeroporto Internacional de San Francisco (SFO) de março de 2023, envolvendo aproximadamente 350 tarefas diárias, 80 motoristas e 40 caminhões. Um requisito crítico é que as soluções sejam geradas em um minuto para serem operacionalmente viáveis.

Metodologia
Os autores propõem uma metaheurística de Busca de Vizinhança Variável reduzida cooperativa (rVNS). Esta abordagem foi selecionada em vez da Busca de Vizinhança Variável (VNS) tradicional e da Busca de Vizinhança Grande Adaptativa (ALNS) para equilibrar eficiência computacional com qualidade de solução.

Os principais componentes da metodologia incluem:

Estrutura de VNS Reduzida (rVNS):
- Diferente da VNS clássica, que varia os tamanhos dos passos, a rVNS emprega um tamanho de passo pequeno e fixo.
- O algoritmo opera através de um ciclo de desconstrução e reconstrução: ele desatribui um número fixo de tarefas ( $n$ ) da solução atual e tenta reatribuí-las aleatoriamente.
- Para compensar o tamanho de passo fixo, o algoritmo aproveita a alta simetria do problema de escalonamento. Ao explorar soluções "equivalentes" (diferentes cronogramas com pontuações idênticas) através de trocas aleatórias, a busca diversifica sem a necessidade de passos grandes e computacionalmente caros.
Estrutura Algorítmica:
- Decomposição (Dicotomia do Problema): O cronograma diário é dividido em dois subproblemas (Manhã e Tarde) baseados nas sobreposições de turno dos motoristas, permitindo o processamento paralelo.
- Heurística de Warm-Start: A rVNS é inicializada com uma solução gerada por uma heurística gulosa que prioriza tarefas com menos motoristas qualificados e intervalos de refeição obrigatórios. Isso evita que a busca comece em um ótimo local pobre.
- Randomização de Objetivo Duplo: O algoritmo alterna entre duas estratégias de randomização baseadas na convergência do objetivo:
  - Foco Primário: Desatribui tarefas com posições temporais semelhantes para criar espaço para tarefas não atribuídas.
  - Foco Secundário: Desatribui tarefas que contribuem mais significativamente para a quilometragem total.
- Heurística de Sequenciamento: Uma heurística rápida (Algoritmo 3) verifica se uma tarefa pode ser inserida na sequência de um motorista sem violar restrições, o que é crucial para manter a velocidade durante a fase de reconstrução.
- Paralelização Cooperativa: Uma estratégia de multi-início roda em 8 núcleos (4 por subproblema). A cada 10 segundos, as unidades paralelas compartilham resultados e reiniciam a partir da melhor solução atual para reduzir a variância e evitar ótimos locais.
Função Objetivo:
A função objetivo total $F$ é uma soma ponderada que prioriza a atribuição de tarefas, seguida pela redução de quilometragem e, finalmente, pela eficiência da missão:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Onde $a_i$ representa tarefas não atribuídas, $x_i$ e $y_i$ representam distâncias de viagem, e $e_i$ conta os inícios de missão.

Principais Resultados
O estudo compara a rVNS proposta contra uma Heurística Gulosa e uma Matheurística (desenvolvida anteriormente em [1]) usando dois conjuntos de dados (S1: tarefas menos numerosas e mais restritas; S2: tarefas numerosas e menos restritas).

Atribuição de Tarefas: A rVNS supera significativamente os métodos anteriores. Enquanto as abordagens Gulosa e Matheurística atribuíram cerca de 80–89% das tarefas, a rVNS alcançou taxas de atribuição de 99,0% a 99,8% em ambos os conjuntos de dados.
Redução de Quilometragem: A rVNS reduziu a quilometragem total da frota em aproximadamente 30% para o conjunto de dados S1 e 20% para o S2 em comparação com a Matheurística.
Estabilidade e Convergência:
- A rVNS paralelizada demonstrou maior consistência do que a versão sequencial, com um desvio padrão na quilometragem de 2–3% comparado a 4–6% para a abordagem sequencial.
- Velocidade de Convergência: Para o conjunto de dados menor (S1), o objetivo primário (contagem de tarefas) convergiu rapidamente (dentro de ~1 segundo), enquanto a otimização da quilometragem continuou a melhorar até um minuto. Para o conjunto de dados maior (S2), o objetivo primário exigiu ~10 segundos para convergir, com retornos decrescentes após um minuto.
Tempo de Execução: Todas as soluções foram geradas dentro da janela de um minuto exigida (especificamente ~55–60 segundos, incluindo o overhead).

Significância e Alegações
O artigo afirma que a metaheurística rVNS oferece uma solução robusta e flexível para o handling aeroportuário que supera as bases exatas e heurísticas anteriores. Sua principal significância reside em:

Viabilidade Operacional: Resolve um problema altamente restrito e multiobjetivo dentro do rigoroso prazo de um minuto necessário para o despacho em tempo real.
Otimização Dupla: Consegue equilibrar com sucesso a maximização da conclusão de tarefas com a minimização dos custos operacionais (quilometragem), um recurso não totalmente otimizado em trabalhos anteriores.
Flexibilidade: Os autores observam que a estrutura do algoritmo permite a integração de novas restrições ou objetivos, como o gerenciamento de carregamento de veículos elétricos ou operações de múltiplos depósitos.
Aplicação no Mundo Real: O estudo demonstra que o algoritmo pode lidar com a complexidade de dados do mundo real (incluindo janelas de tempo deslizantes e frotas heterogêneas) melhor do que modelos anteriores, fornecendo uma ferramenta que os agentes de handling podem usar para atribuir automaticamente centenas de tarefas diárias.

Os autores mantêm-se modestos quanto à otimalidade absoluta, reconhecendo que, embora o algoritmo não garanta um ótimo global, ele converge consistentemente para soluções que são superiores aos métodos existentes tanto em velocidade quanto em qualidade. Eles destacam o potencial para aplicação futura em cenários de reatribuição em tempo real, onde tarefas atrasadas devem ser reescalonadas dinamicamente.