OPT301 - Otimização de Rotas e Grafos

Código: OPT301
Nível: Avançado
Pré-requisitos: ANA201

Objetivos de Aprendizagem

Ao final desta matéria, o aluno deverá ser capaz de:

1. Compreender os conceitos básicos de grafos (vértices, arestas, pesos) sem formalismo matemático.

2. Modelar problemas de distribuição como redes de transporte.

3. Aplicar o algoritmo de Dijkstra (intuitivamente) para encontrar caminhos mínimos.

4. Resolver problemas de roteirização usando Excel Solver e Google Sheets.

5. Analisar trade-offs entre distância, tempo e custo em rotas.

6. Aplicar conceitos de grafos em casos reais da logística militar.

Tópicos Abordados

Fundamentos de Grafos

• O Problema das Pontes de Königsberg: A origem histórica da teoria dos grafos. Como Euler provou a impossibilidade de atravessar todas as 7 pontes sem repetir nenhuma, criando o conceito de caminhos eulerianos.
• O que é um grafo: Representação visual de conexões.
• Tipos de grafos:
  • Direcionados vs. não-direcionados.
  • Ponderados vs. não-ponderados.
• Terminologia básica:
  • Vértice (nó): Localização (base, depósito, unidade).
  • Aresta (link): Conexão entre localizações.
  • Peso: Distância, tempo ou custo.

Note

Esta matéria foca na intuição e aplicação prática. Não há demonstrações formais ou provas matemáticas.

Representação de Redes

Matriz de Adjacência

• Como representar conexões em uma tabela.
• Facilidade de implementação em planilhas.

Matriz de Distâncias

• Construindo uma matriz de custos (km, R$, tempo).
• Lidando com conexões inexistentes (infinito).

Problema do Caminho Mínimo

Algoritmo de Dijkstra (Visão Intuitiva)

1. Começar no ponto de origem.

2. Explorar vizinhos mais próximos.

3. Atualizar distâncias acumuladas.

4. Repetir até chegar ao destino.

Exemplo Prático: Encontrar a rota mais curta entre Base Aérea de Brasília e Base Aérea de Manaus, considerando paradas intermediárias.

Implementação em Planilhas

• Uso de fórmulas para calcular distâncias acumuladas.
• Formatação condicional para destacar caminho ótimo.

Problema de Roteirização de Veículos (VRP)

Vehicle Routing Problem Simplificado

• Cenário: Um caminhão deve entregar suprimentos em múltiplas unidades.
• Objetivo: Minimizar distância total percorrida.
• Restrições: Capacidade do veículo, janelas de tempo.

O Problema do Caixeiro Viajante (TSP)

O VRP é uma generalização do famoso Travelling Salesperson Problem (TSP). É fundamental entender que este é um problema NP-Completo, o que significa que, computacionalmente, não existe (ainda) uma fórmula mágica para encontrar a solução perfeita instantaneamente para muitos pontos.

• Relevância Prática: A diferença entre uma rota “no olho” e uma rota otimizada pode representar milhões em economia de combustível anualmente.
• Complexidade: Com poucos pontos é fácil, mas a dificuldade cresce exponencialmente. Por isso usamos heurísticas e Solvers.

Uso do Excel Solver

• Configurando variáveis de decisão.
• Definindo função objetivo (minimizar distância).
• Adicionando restrições.
• Interpretando resultados.

Algoritmos Gulosos (Greedy Algorithms)

A Armadilha do 'Vizinho Mais Próximo'

Um algoritmo guloso sempre escolhe a opção que parece melhor agora, sem olhar à frente.

Exemplo Clássico: No TSP, começar pelo destino mais próximo parece lógico, mas frequentemente resulta em rotas piores que abordagens mais sofisticadas.

Lição para Gestores: Decisões que parecem ótimas no curto prazo podem ser ruins estrategicamente. Planejamento logístico exige visão de longo prazo.

Aplicações Militares

Distribuição de Suprimentos

• Otimização de rotas de abastecimento entre bases.
• Priorização de entregas em situações de emergência.

Planejamento Logístico

• Alocação de recursos em múltiplas unidades.
• Balanceamento de carga entre rotas.

Análise de Vulnerabilidade

• Identificação de pontos críticos na rede.
• Planejamento de rotas alternativas.

Ferramentas Práticas

Excel Solver

• Add-in nativo para problemas de otimização.
• Configuração passo a passo.
• Análise de sensibilidade.

Google Sheets

• Solver alternativo via extensões (Solver for Google Sheets).
• Compartilhamento de modelos com equipe.

Visualização

• Criação de diagramas de rede usando formas e conectores.
• Mapas geográficos com rotas destacadas.

Materiais de Consulta

• CORMEN, Thomas H. et al. Introdução aos Algoritmos. 3ª ed. Campus, 2012.
  • Capítulo 22: Algoritmos Elementares em Grafos (representação, busca em largura, busca em profundidade)
  • Capítulo 24: Caminhos Mínimos de Fonte Única (Algoritmo de Dijkstra)
  • PDF disponível
• Vídeo: “Introduction to Graph Theory” - Khan Academy (legendado em português).
• Artigo: “Practical Applications of Dijkstra’s Algorithm” - GeeksforGeeks.
• Tutorial: “Using Excel Solver for Route Optimization” - Microsoft Support.
• Dataset: Matriz de distâncias entre 20 bases da FAB.
• Planilha Modelo: OPT301_Solver_Rotas.xlsx.

Casos de Estudo

Caso 1: Distribuição de Vacinas

Cenário: Durante uma campanha de vacinação, é necessário distribuir doses para 10 unidades da FAB em 2 dias.

Desafios:

• Restrição de temperatura (transporte rápido).
• Capacidade limitada de veículos.
• Priorização de unidades remotas.

Entrega: Propor roteirização otimizada usando Solver.

Caso 2: Evacuação Médica

Cenário: Transferência urgente de paciente entre hospitais militares.

Análise:

• Modelar rede de hospitais como grafo.
• Encontrar caminho mais rápido (não necessariamente o mais curto).
• Considerar helicópteros vs. ambulâncias.

Caso 3: Cadeia de Suprimento em Exercício Militar

Cenário: Abastecer 5 posições avançadas durante exercício de campo.

Complexidade:

• Rotas podem ficar temporariamente indisponíveis.
• Necessidade de rotas alternativas.
• Sincronização com outras operações.

Avaliação

Projeto Prático

Desenvolver um modelo de otimização de rotas para um cenário real da sua unidade:

1. Mapear a rede de distribuição.

2. Coletar dados de distâncias/custos.

3. Implementar modelo no Excel Solver.

4. Apresentar resultados e economia estimada.

Critérios de Avaliação

• Corretude do modelo (30%).
• Qualidade da apresentação visual (20%).
• Viabilidade prática da solução (30%).
• Análise de sensibilidade (20%).