🚛 CVRP Solver - Heurística Computacional

Implementação de múltiplos algoritmos heurísticos e meta-heurísticos para resolução do Capacitated Vehicle Routing Problem (CVRP) - Problema de Roteamento de Veículos com Capacidade Limitada.

Escopo verificável: a branch main contém o solver Physarum base. Algoritmo genético, busca local e Tabu Search vivem em branches históricas separadas. Percentuais de melhoria citados abaixo são anotações experimentais do projeto e não resultados reproduzidos por uma suíte automatizada nesta branch.

📋 Visão Geral

Este repositório é fruto de um trabalho acadêmico explorando diferentes abordagens para solução de problemas de otimização combinatória NP-difíceis, especificamente o CVRP. O projeto demonstra evolução incremental de técnicas, desde algoritmos bio-inspirados até meta-heurísticas híbridas sofisticadas.

O Problema: CVRP

O Capacitated Vehicle Routing Problem consiste em:

Objetivo: Minimizar a distância total percorrida por uma frota de veículos
Restrições:
- Cada veículo possui capacidade máxima limitada
- Todos os veículos tem a mesma capacidade
- Todos os veículos partem e retornam ao depósito central
- Cada cliente deve ser visitado exatamente uma vez
- A demanda total de uma rota não pode exceder a capacidade do veículo

Dataset de Testes

Utilizamos as instâncias benchmark de Christofides et al. (1979) (CMT01-CMT14), referências padrão em pesquisas de roteamento de veículos:

Problemas com 50 a 200 clientes
Coordenadas euclidianas 2D
Demandas variadas por cliente
Capacidades de veículos específicas

🌳 Estrutura de Branches

O repositório está organizado em 4 branches que representam diferentes abordagens algorítmicas:

📍 `main` - PhysarumSolver (Base)

Implementação básica do algoritmo bio-inspirado Physarum polycephalum

Algoritmo: Inspirado no comportamento do mofo limoso (Physarum polycephalum) na busca por nutrientes
Técnica: Modelagem da rede de transporte biológico usando pressão, condutividade e fluxo
Características:
- 100 iterações para cálculo de pressões
- Atualização de condutividades baseada em fluxo (DELTA_T = 0.01)
- Construção gulosa de rotas usando scores de condutividade
- Seleção de nós por vizinho mais próximo ponderado
Arquivos principais:
- PhysarumSolver.h
- PhysarumSolver.cpp

📊 Performance: Baseline para comparação com outras abordagens

🧬 `feature/genetic-solver` - Algoritmo Genético Híbrido

Combinação de Physarum + Algoritmo Genético

Estratégia: Usa a solução do PhysarumSolver como semente inicial da população
Algoritmo Genético:
- População: 50 indivíduos
- Gerações: Até 200 iterações
- Seleção: Torneio de 3 indivíduos + Elitismo (10%)
- Crossover: Troca de rotas completas entre pais (taxa 85%)
- Mutação: 7 operadores especializados para CVRP (taxa 20%)
  1. Swap de nós dentro de rota (2-opt)
  2. Inserção de nó em nova posição
  3. Reversão de segmento (3-opt)
  4. Realocação entre rotas
  5. Swap entre rotas diferentes
  6. Merge de rotas (se capacidade permitir)
  7. Split de rota longa
Mecanismo de Reparo: Corrige soluções infactíveis (duplicatas, nós faltantes, violação de capacidade)
Convergência:
- Early stopping após 50 gerações sem melhoria
- Diversificação adaptativa (aumenta mutação para 80% se estagnado)
- Busca local 2-opt nas últimas 10 iterações
Arquivos adicionais:
- GeneticSolver.h - 93 linhas
- GeneticSolver.cpp - 1065 linhas

📊 Performance: Melhora típica de 5-15% sobre o Physarum base

🔍 `physarum-v2` - Local Search + Tabu Search

Physarum melhorado com busca local e tabu search

Introduz a classe PhysarumSolverV3 que adiciona meta-heurísticas ao algoritmo base:

Melhorias no PhysarumSolver Base:

Parâmetros otimizados:
- MAX_ITERATIONS: 100 → 75,000 (750x mais iterações)
- DELTA_T: 0.01 → 0.00005 (200x mais gradual)
- MIN_FLOW: 0.01 → 0.0005 (mantém mais caminhos alternativos)
- Novos parâmetros:
  - NETWORK_EVOLUTION_ITERATIONS = 15,000
  - GLOBAL_PRESSURE_WEIGHT = 0.95
Arquitetura de duas fases:
1. Fase 1 - Evolução de Rede: 15,000 iterações para criar estrutura global robusta
2. Fase 2 - Construção de Rotas: Seleção gulosa combinando perspectiva global (95%) e local (5%)

PhysarumSolverV3 - Meta-heurísticas:

Busca Local:

findBestInterRouteSwap(): Troca de nós entre rotas diferentes
findBestNodeReallocation(): Realocação de nós
applyLocalSearch(): Loop principal com estratégias first improvement e best improvement

Tabu Search:

Lista Tabu: Memória de movimentos recentes para evitar ciclos
Critério de Aspiração: Aceita movimentos tabu se melhoram o melhor conhecido
Tenure Adaptativo:
- Aumenta quando estagnado (max=30) para escapar de ótimos locais
- Diminui quando melhorando (min=10) para explorar vizinhança
Limite: 100 iterações sem melhoria

Pipeline de Otimização:

PhysarumSolver (inicial)
  → 4 variantes de busca local paralelas
    → Seleciona melhor solução
      → Tabu search (refinamento final)

Arquivos novos:
- PhysarumSolverV3.h - 80 linhas
- PhysarumSolverV3.cpp - 515 linhas

📊 Performance: Melhora significativa sobre Physarum base (10-25% em instâncias médias)

🛡️ `physarum-v3` - Versão Robusta e Produção

Hardening e segurança do PhysarumSolverV3

Esta branch NÃO muda a lógica algorítmica, mas torna o código robusto e pronto para produção:

Melhorias de Robustez:

1. Validação Defensiva em isMoveFeasible():

Validação de tamanho de rotas (mínimo 3 nós: depósito + cliente + depósito)
Verificação de índices negativos antes de conversão de tipo
Lookup seguro de demandas com .find() ao invés de .at()
Validação de demandas não-negativas
Margem de capacidade: 0.999x (previne erros de precisão de ponto flutuante)
Try-catch abrangente para prevenir crashes

2. Segurança em calculateMoveCost():

Verificação de índices negativos
Conversão segura de tipos (int → size_t) em estágios
Bounds checking para todos os acessos a arrays
Retorna std::numeric_limits<double>::max() em caso de erro
Validações separadas para movimentos intra-rota e inter-rota

3. Configuração de Build:

Address Sanitizer habilitado (-fsanitize=address)
Detecção de memory leaks e buffer overflows em tempo de desenvolvimento
Frame pointers preservados para melhor debugging

Impacto:

isMoveFeasible(): 18 → 58 linhas (3x mais código defensivo)
calculateMoveCost(): 42 → 135 linhas (3x mais validações)
Zero crashes em testes extensivos com dados malformados

📊 Performance: Idêntica à v2, mas com estabilidade produtiva

🏗️ Estrutura do Projeto

tec_heuristica/
├── README.md                          # Este arquivo
├── .gitignore
├── CMakeLists.txt                     # Configuração de build
├── Makefile                           # Build alternativo
│
├── include/                           # Headers (.h)
│   ├── Types.h                        # Definições de tipos (Point, XMLProblemData)
│   ├── Edge.h                         # Estrutura de aresta
│   ├── Route.h                        # Estrutura de rota
│   ├── PhysarumSolver.h               # Solver bio-inspirado
│   ├── PhysarumSolverV3.h             # Solver + busca local (branches v2/v3)
│   ├── GeneticSolver.h                # Algoritmo genético (branch genetic-solver)
│   ├── Interface.h                    # I/O e parsing XML
│   └── SolutionValidator.h            # Validação de soluções
│
├── src/                               # Implementações (.cpp)
│   ├── main.cpp                       # Programa principal com menu
│   ├── PhysarumSolver.cpp             # Implementação do Physarum
│   ├── PhysarumSolverV3.cpp           # Implementação busca local (branches v2/v3)
│   ├── GeneticSolver.cpp              # Implementação genética (branch genetic-solver)
│   ├── Interface.cpp                  # Implementação I/O
│   ├── SolutionValidator.cpp          # Implementação validador
│   ├── Route.cpp                      # Implementação de rotas
│   └── Edge.cpp                       # Implementação de arestas
│
├── entradas/                          # Datasets de teste
│   └── CMT01.xml ... CMT14.xml        # Instâncias Christofides
│
├── resultados/                        # Saídas do programa
│
└── lab/                               # Bibliotecas externas
    └── tinyxml2/                      # Parser XML

🚀 Compilação e Execução

Requisitos

Compilador: GCC/Clang com suporte a C++17
Build System: CMake 3.10+
Plataforma: macOS 10.15+ (adaptável para Linux/Windows)

Compilar

cd tec_heuristica
mkdir build && cd build
cmake ..
make

Executar

./bin/tec_heuristica_pj1

Menu Interativo

O programa apresenta um menu com opções:

Criar arquivo exemplo (não implementado)
Resolver a partir de arquivo texto
- Carrega problema de arquivo customizado
- Executa solver
- Exibe resultados
- Opção de salvar em arquivo
Resolver a partir de XML Christofides
- Seleciona uma das 14 instâncias (CMT01-CMT14)
- Executa solver(s) configurado(s)
- Valida solução
- Compara resultados (se múltiplos solvers)
- Salva resultados em arquivos
Sair

📊 Resultados e Validação

Validação de Soluções

O sistema valida automaticamente:

✅ Todas as rotas começam e terminam no depósito
✅ Nenhum cliente visitado mais de uma vez (exceto depósito)
✅ Todos os clientes visitados exatamente uma vez
✅ Capacidade de veículos respeitada em todas as rotas
✅ Cálculo correto de distâncias (Euclidiana)

Formato de Saída

Cada solução gera arquivo com:

Sequência de nós em cada rota
Demanda total por rota
Distância total por rota
Distância total da solução
Número de veículos utilizados

🧪 Comparação de Abordagens

Branch	Algoritmo Principal	Técnicas Adicionais	Complexidade Temporal	Qualidade Esperada
main	Physarum básico	-	O(n² × iterations)	Baseline
genetic-solver	Algoritmo Genético	7 operadores de mutação, elitismo, reparo	O(popSize × generations × n²)	+5-15% vs main
physarum-v2	Physarum evoluído	Local search, Tabu search, 4 estratégias	O(n² × 75k + n³ × LS)	+10-25% vs main
physarum-v3	Mesmo que v2	Mesmas + validações defensivas	Igual a v2	Igual a v2, mais robusto

Recomendação:

Protótipo rápido: main
Melhor qualidade: physarum-v3 (robustez + performance)
Pesquisa evolutiva: genetic-solver
Base para extensões: physarum-v2

🔬 Fundamentos Teóricos

Physarum polycephalum Algorithm

Inspirado no comportamento do mofo limoso ao encontrar caminhos ótimos:

Modelagem de Rede:
- Nós = junções biológicas
- Arestas = tubos com condutividade (capacidade de fluxo)
- Pressão = força motriz do fluxo

Dinâmica:

Fluxo(i,j) = Condutividade(i,j) × |Pressão(i) - Pressão(j)|

Nova_Condutividade = (1 + Δt) × atual × (fluxo + fluxo_mínimo)

Emergência de Caminhos Ótimos:
- Caminhos com alto fluxo aumentam condutividade (reforço positivo)
- Caminhos com baixo fluxo enfraquecem (poda natural)
- Converge para estrutura eficiente de transporte

Algoritmo Genético

Simula evolução natural através de:

População: Conjunto de soluções candidatas
Seleção: Indivíduos mais aptos têm maior probabilidade de reprodução
Crossover: Combinação de características de dois pais
Mutação: Introdução de variabilidade aleatória
Elitismo: Preservação das melhores soluções
Convergência: População evolui para região ótima do espaço de busca

Tabu Search

Meta-heurística que usa memória para guiar busca:

Lista Tabu: Memória de movimentos recentes (proibidos temporariamente)
Tenure: Tempo que um movimento permanece tabu
Critério de Aspiração: Exceção para movimentos tabu muito promissores
Intensificação/Diversificação: Balance entre explorar regiões conhecidas e novas
Adaptive Tenure: Ajuste dinâmico baseado em progresso

📚 Referências

Artigos Fundamentais

Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. In Combinatorial optimization (pp. 315-338). Wiley.
Tero, A., Kobayashi, R., & Nakagaki, T. (2007). A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology, 244(4), 553-564.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.
Glover, F. (1989). Tabu Search—Part I. ORSA Journal on Computing, 1(3), 190-206.

Benchmarks

Christofides et al. Benchmark Set: http://vrp.galgos.inf.puc-rio.br/index.php/en/

👨‍💻 Desenvolvimento

Para Estender o Projeto

Adicionar novo solver:
- Crie classe em include/ e src/
- Implemente método findRoutes() retornando vector<Route>
- Integre ao menu em main.cpp
Novos operadores genéticos:
- Adicione método em GeneticSolver.cpp
- Chame em mutate() com probabilidade apropriada
Modificar parâmetros:
- Headers contêm constantes ajustáveis
- Experimente com diferentes valores de MU, DELTA_T, tamanho de população, etc.

Debug

Com Address Sanitizer (branch physarum-v3):

cmake -DCMAKE_BUILD_TYPE=Debug ..
make
./bin/tec_heuristica_pj1

Memory leaks e buffer overflows serão detectados automaticamente.

📄 Licença

Projeto acadêmico - uso livre para fins educacionais.

🤝 Contato

Para dúvidas ou sugestões sobre este trabalho, abra uma issue no repositório.

⭐ Destaques Técnicos

✨ 4 implementações algorítmicas completas e funcionais
🧬 Algoritmo genético com 7 operadores especializados para CVRP
🔬 Bio-inspiração (Physarum) com modelagem física realista
🎯 Meta-heurísticas avançadas (Tabu Search com tenure adaptativo)
🛡️ Código robusto com validações defensivas extensivas
📊 Benchmarks padrão (Christofides) para comparação científica
🏗️ Arquitetura extensível para adicionar novos solvers
✅ Validação automática de restrições CVRP

Desenvolvido como parte da disciplina de Técnicas em Heurística 🎓

Auditoria técnica da branch `main`

Heurística realmente executada

O solver atual mantém matrizes de pressão, fluxo e condutividade inspiradas em Physarum. Entretanto, em findRoutes, os candidatos viáveis são ordenados pela distância ao nó atual e o próximo cliente é o primeiro da lista. Portanto, a decisão de rota observável na branch principal é vizinho mais próximo com restrição de capacidade; a condutividade é atualizada, mas não participa diretamente do ranking final.

Essa diferença entre intenção e implementação deve ser tratada antes de atribuir ganhos ao modelo bio-inspirado. Uma forma de verificar o efeito é comparar, com a mesma seed e instâncias, a versão atual contra um baseline explícito de nearest-neighbor.

Complexidade e memória

Para n nós e v veículos:

a matriz de adjacência ocupa O(n²);
caches de pressão/condutividade por veículo podem chegar a O(v × n²);
matrizes de fluxo temporárias também ocupam O(n²);
a construção ordena candidatos a cada passo, aproximadamente O(v × n² log n) no pior arranjo;
o CVRP é NP-difícil; a heurística não garante ótimo global.

Os contêineres STL gerenciam sua própria memória e não há new/delete manual no núcleo analisado. O risco principal é pressão de memória quadrática, não um vazamento evidente.

Correção, portabilidade e robustez

src/main.cpp contém caminho absoluto do computador original para entradas; em outro ambiente, a execução falha;
CMakeLists.txt força arquitetura macOS x86_64, dificultando Apple Silicon, Linux e Windows;
o Makefile versionado é um artefato gerado pelo CMake e também contém caminhos absolutos;
acessos demands[node] inserem demanda zero quando a chave não existe; find/at torna dado ausente um erro explícito;
se o limite de veículos for alcançado, clientes podem permanecer sem visita; o validador detecta a solução incompleta, mas o solver ainda a retorna;
o parser XML pressupõe elementos obrigatórios e precisa validar ponteiros antes de desreferenciá-los;
a regra de atualização de condutividade merece testes de estabilidade numérica, limite de iterações e critério de convergência;
não há benchmark automatizado que registre distância, factibilidade, seed, tempo e consumo de memória por instância.

Verificação recomendada

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build
./build/bin/tec_heuristica_pj1

Antes disso, remova o caminho absoluto, aceite --input/--output e não force CMAKE_OSX_ARCHITECTURES. Para diagnóstico, compile com -fsanitize=address,undefined.

Próximos passos prioritários

conectar condutividade/fluxo à função de seleção ou renomear honestamente o baseline;
parametrizar arquivos, seed, frota e limites;
falhar explicitamente quando houver cliente não atendido;
incluir testes de parser e validador com XML malformado;
criar benchmark reproduzível contra nearest-neighbor e melhores valores conhecidos;
remover builds gerados e caminhos locais do versionamento.

Name		Name	Last commit message	Last commit date
.vscode		.vscode
entradas		entradas
include		include
lab		lab
src		src
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
Makefile		Makefile
README.md		README.md

Latest commit

History

Folders and files

Repository files navigation