IEFA — CPAINT

Código: ROUT301
Nível: Avançado
Pré-requisitos: DATA201

Objetivos de Aprendizagem

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

Compreender os conceitos básicos de grafos (vértices, arestas, pesos) sem formalismo matemático.
Modelar problemas de distribuição como redes de transporte.
Aplicar o algoritmo de Dijkstra (intuitivamente) para encontrar caminhos mínimos.
Resolver problemas de roteirização usando Excel Solver e Google Sheets.
Analisar trade-offs entre distância, tempo e custo em rotas.
Aplicar conceitos de grafos em casos reais da logística militar.

Cobertura no Cronograma

Módulo	Tópico	Tipo
Módulo 14	Teoria dos Grafos e Redes Logísticas	Teoria
Módulo 14	Modelando problemas reais como grafos	Prática
Módulo 14	Matrizes de Adjacência e Custos	Lab
Módulo 15	Algoritmo de Dijkstra (Intuição)	Teoria
Módulo 15	Dijkstra passo-a-passo (Manual)	Prática
Módulo 16	Vehicle Routing Problem (VRP)	Teoria
Módulo 16	Restrições de Capacidade e Tempo	Prática
Módulo 16	VRP com Múltiplos Veículos	Prática
Módulo 17	Casos de Uso Militar (Vacinas, Emergência)	Teoria

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.

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)

Começar no ponto de origem.
Explorar vizinhos mais próximos.
Atualizar distâncias acumuladas.
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
- 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: ROUT301_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:

Mapear a rede de distribuição.
Coletar dados de distâncias/custos.
Implementar modelo no Excel Solver.
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%).

ROUT301 - Otimização de Rotas e Grafos