In English, briefly. A solver and a simulator for the Multi-Depot Vehicle Routing Problem under disruption. Routes are built cluster-first (constrained capacitated k-means over vehicle-level slots), then route-second (a per-depot genetic algorithm over permutations, with Prins's local search as mutation and Vidal's linear split turning each giant tour into vehicle routes). The interesting half is what happens next: an event-driven simulator runs the fleet minute by minute and blocks roads while vehicles are already moving, forcing a three-stage contingency cascade — repair inside the route, then inside the depot's cluster, then across depots. Failures are generated as spatial collapse zones over edges the fleet actually travels, because uniformly random road blocks are mostly invisible to the fleet and make the disaster look easy. Python 3.10+, Cordeau benchmark instances, 1,980 committed simulation runs.
Resolver e simular roteamento de frota com múltiplos depósitos quando a estrada quebra no meio da operação. Duas metades: uma que planeja as rotas do dia e outra que estraga esse plano de propósito, em horários e lugares controlados, para medir o que sobra.
Trabalho de Conclusão de Curso, feito em dupla, sobre o D-MDVRP (MDVRP dinâmico).
Uma transportadora tem vários depósitos espalhados pelo mapa, uma frota em cada um, e uma lista de clientes para atender no dia. Cada cliente tem uma demanda (quanto ocupa no caminhão) e um tempo de atendimento. Cada veículo tem uma capacidade e uma jornada máxima. A pergunta é dupla, e é isso que separa o MDVRP do roteamento comum:
- Qual depósito atende qual cliente? (a decisão de alocação)
- Em que ordem cada veículo visita os seus clientes? (a decisão de rota)
O objetivo é minimizar a distância total percorrida. As duas decisões são acopladas — a melhor alocação depende das rotas que ela vai permitir — e o problema é NP-difícil, então não se procura o ótimo: procura-se uma solução boa em tempo aceitável. É o mesmo problema de quem entrega gás, coleta leite, abastece lojas ou faz manutenção de campo a partir de mais de uma base.
A parte dinâmica. No MDVRP clássico o plano é feito de manhã e o mundo coopera. Aqui não: durante a execução, trechos de via são bloqueados (alagamento, acidente, obra, deslizamento) e os veículos que já estão na rua descobrem isso quando chegam lá. O plano do dia vira parcialmente inválido, e alguém precisa decidir, em segundos, o que fazer com os clientes que ficaram do outro lado do bloqueio.
instância Cordeau (clientes, depósitos, capacidade, jornada)
│
┌───────────────▼───────────────┐
│ FASE ESTÁTICA — o plano │
│ CCBC → clusteriza clientes │
│ GA → ordena a rota gigante │
│ split → corta em veículos │
└───────────────┬───────────────┘
│ solução inicial (rotas por depósito)
┌───────────────▼───────────────┐
│ FASE DINÂMICA — o improviso │
│ simulador por eventos │
│ + cenário de bloqueios │
│ → cascata S1 → S2 → S3 │
└───────────────┬───────────────┘
│
log da simulação + métricas (custo, desperdício,
clientes não atendidos, viabilidade, tempo por estágio)
A fase estática é literatura bem estabelecida, implementada com cuidado. A fase dinâmica é onde o trabalho tem opinião própria.
A primeira versão do gerador de falhas sorteava pares de nós uniformemente e bloqueava a aresta entre eles. É o que qualquer um faria — e é uma armadilha.
Num mapa com n clientes existem n·(n−1) arestas possíveis, mas a frota percorre só umas poucas dezenas delas. Sortear uniformemente significa que a esmagadora maioria dos bloqueios cai em trechos que ninguém ia usar. O experimento então mede um desastre que a frota evitou por acaso, não por competência, e qualquer algoritmo de contingência parece excelente. O código chama isso de viés de evasão (evasion bias).
A correção está em src/scenario/generate_failures.py, no modo Collapse
Zones:
- só são candidatas as arestas que a solução estática de fato percorre (o gerador recebe as rotas prontas como entrada);
- as arestas adjacentes a depósito são excluídas — bloqueá-las faz o motor de contingência tentar "rerotear um depósito" como se fosse um cliente órfão;
- o desastre não é pontual: sorteia-se um nó-epicentro e um raio R entre 2% e 10% da diagonal do mapa, e todas as arestas ativas dentro do raio caem no mesmo instante. Bloqueio real é regional, não é uma aresta isolada;
- o instante de cada zona sai de uma distribuição Beta (α = 1,2) calibrada para que a média dos tempos seja o EDOD pedido — assim dá para encomendar "desastre cedo", "espalhado" ou "tardio" sem cravar horários na mão.
Dois parâmetros controlam o cenário, e são os eixos do experimento:
| Parâmetro | O que é | Efeito |
|---|---|---|
| DOD (degree of dynamism) | fração das arestas ativas que devem cair | o tamanho do desastre |
| EDOD (expected degree of dynamism) | média normalizada dos instantes de bloqueio | quando o desastre acontece: 0 → tudo no começo, 1 → tudo no fim |
O modo uniforme continua no código, atrás da ausência de --routes-file. Ele
não foi apagado de propósito: serve de linha de base para mostrar a diferença.
O projeto começou como enxame de partículas. O histórico e o diretório
archive/ guardam essa fase: um MOPSO validado no ZDT1, um MOPSO aplicado a
VRP de brinquedo, e depois um híbrido "GA-PSO" para o problema real. Em maio de
2026 isso foi substituído — a branch se chamava, sem sutileza,
replace-pso-with-ga.
O motivo é de representação. PSO trabalha com vetor contínuo de posições: para virar uma rota, o vetor precisa de um decodificador de prioridades (SPV), e o operador de velocidade não tem nenhuma noção do que é uma sequência de visitas — ele mistura números, não trechos de caminho. O GA que ficou opera direto sobre a permutação:
- cruzamento OX (order crossover), que preserva subsequências de visita herdadas dos pais;
- mutação = busca local, no esquema memético de Prins (2004): a mutação não é ruído, é a aplicação dos 9 movimentos M1–M9 (realocação, troca, 2-opt e variantes inter/intra-rota) restritos aos 30 vizinhos mais próximos de cada cliente;
- sobrevivência com remoção de clones no espírito de Vidal (2012): dois
indivíduos com o mesmo
floor(F/δ)contam como iguais, e metade das vagas liberadas é preenchida com indivíduos novos, para a população não colapsar.
| Alternativa | Por que não ficou |
|---|---|
| PSO / MOPSO sobre vetor contínuo | precisa de decodificador de prioridades; os operadores não enxergam a estrutura de permutação (mantido em archive/ como registro da fase exploratória) |
| GA também para a alocação cliente→depósito | trocado por CCBC (k-means capacitado), que já nasce respeitando capacidade e jornada em vez de descobri-las por penalidade |
| Split de Bellman, O(n²) | trocado pelo split linear O(n·m) de Vidal (2016), com deque monótono de predecessores não dominados |
| Restrições duras no split | capacidade e duração viraram penalidades (soft): com restrição dura o split pode não achar partição nenhuma; com penalidade toda aresta é admissível e sempre sai uma solução completa, ainda que penalizada. Só o tamanho da frota ficou duro |
⚠️ O repositório registra a troca, não uma medição PSO × GA lado a lado. Se você quiser o comparativo numérico, ele não está aqui.
Estratégia cluster-first, route-second (src/algorithms/).
Fase 1 — CCBC (ccbc_cluster.py), Constrained Centroid-Based Clustering:
um k-means capacitado com três acréscimos.
- O k não é o número de depósitos, é o número de veículos: cada veículo vira um "slot" com orçamento de carga e de jornada próprios. Alocar contra o limite do veículo é mais apertado — e mais honesto — do que alocar contra o somatório do depósito.
- Multi-start: a partida 0 é geométrica (Voronoi dos depósitos, depois k-means dentro de cada região); as demais são perturbações gaussianas dessas centroides, com σ = 10% da distância média entre depósitos. Diversifica sem jogar fora o sinal geográfico.
- Atribuição em duas fases, a cada iteração. Primeiro os clientes
"decididos" — ordenados pelo escore de controvérsia, a diferença entre a
distância ao slot mais próximo e ao segundo mais próximo. Quem está claramente
perto de um slot escolhe primeiro; quem está na fronteira escolhe depois, com
o que sobrou. Os que não cabem em lugar nenhum vão para o slot que minimiza
distância × (1 + excesso de carga + excesso de jornada).
Fase 2 — GA + split (ga_router.py, ga_split.py), um GA por depósito,
rodando em paralelo (ProcessPoolExecutor), sobre o pymoo. O cromossomo é a
ordem de visita de uma "rota gigante" que passa por todos os clientes do
cluster; o split linear de Vidal (2016) corta essa rota gigante na melhor
partição em veículos, em O(n·m), respeitando o limite de frota como restrição
dura e penalizando excesso de carga e de jornada. Avaliar um indivíduo é rodar o
split: a ordem é o gene, a frota é consequência.
Quando uma aresta cai, o simulador (src/scenario/simulator.py) descobre qual
veículo ia usá-la e escala a resposta do mais barato para o mais caro. Cada
estágio só é tentado se o anterior falhou ou degradou demais; os limites vêm do
config.yaml.
| Estágio | Escopo | Regra de aceite |
|---|---|---|
| S1 — contenção local | só a rota afetada: reordena os clientes pendentes com M1/M2/M3 intra-rota | custo ≤ 1,20× o custo original da rota |
| S2 — reotimização do cluster | todos os veículos do mesmo depósito | custo do cluster ≤ 1,10× o anterior |
| S3 — reparo global entre depósitos | insere o cliente-alvo em qualquer veículo ainda ativo, de qualquer depósito | prioriza inserção hard-feasible; se não houver, aceita a melhor soft-feasible por fitness penalizado |
Se um veículo já estava em cima da aresta quando ela caiu, ele dá meia-volta
— e o retorno é contabilizado como distância desperdiçada (wasted_distance),
que entra no custo final. O algoritmo não ganha de graça o tempo que a frota
gastou andando para o lugar errado.
Quando nem o S3 resolve, entra o protocolo de cascata: uma varredura para a frente tentando resgatar os clientes seguintes um a um e, no limite, declarar cliente não atendido. Isso é uma escolha de projeto e não um bug: em desastre grande, alguém não é atendido, e o experimento precisa contar quantos, não fingir que a frota deu conta.
O simulador audita a si mesmo. Terminada a execução,
src/tools/validate_simulation_log.py relê o log gravado e verifica duas
coisas: se algum veículo atravessou uma aresta depois de ela ter sido
bloqueada e se algum cliente esperado ficou de fora sem estar registrado como
não atendido. Encontrando qualquer uma, imprime o detalhe e o main() devolve
código de erro. Sem essa trava, a maneira mais fácil de um algoritmo de
contingência parecer ótimo é ignorar o bloqueio em silêncio — e ninguém
perceber.
As instâncias são as de Cordeau para MDVRP, formato texto, em
data/raw/cordeau/ — 33 arquivos: p01–p23 (originais de Christofides,
Gillett & Miller e Chao) e pr01–pr10 (de Cordeau). As soluções de referência
publicadas ficam em data/raw/cordeau_sol/*.res, e são o que o benchmark usa
para calcular o gap.
O formato está descrito em data/raw/cordeau/README.TXT. Resumido:
tipo m n t ← tipo 2 = MDVRP; m veículos, n clientes, t depósitos
D Q ← uma linha por depósito: jornada máxima, capacidade
D Q
...
i x y d q f a [combinações] [e l]
← por nó: índice, coordenadas, tempo de atendimento,
demanda, frequência, combinações de visita,
e opcionalmente janela de tempo
As linhas vão de 1 a n + t: os últimos t nós são os depósitos, não os
primeiros — detalhe que quebra parser desatento. O leitor
(src/utils/data_loader.py) interpreta o arquivo inteiro, inclusive frequência,
combinações de visita (decodificadas de binário para dias) e janelas de tempo;
o solver usa apenas o subconjunto MDVRP: coordenadas, demanda, tempo de
atendimento, capacidade e jornada. Distâncias são euclidianas, pré-computadas
numa matriz para consulta O(1), e velocidade é unitária — tempo de viagem
é numericamente igual à distância.
Os cenários de falha são um artefato separado, em JSON, com metadata
(instância, semente, DOD, EDOD) e a lista de eventos edge_block com
trigger_time, node_a, node_b. Dois exemplos estão versionados em
data/processed/failures/.
Python 3.10 ou superior (o código usa X | Y em anotação de tipo).
python3 -m venv venv
source venv/bin/activate # Windows: venv\Scripts\activate
pip install -r requirements.txtUma instância, do plano à simulação, com as janelas de visualização:
python3 src/main.py --instance p01Sem --failures-file, ele procura sozinho um cenário para a instância em
data/processed/failures/. Flags úteis: --no-simulate (só a parte estática),
--stages 1 2 (desliga o S3, para medir o quanto cada estágio contribui),
--routes-file (reaproveita uma solução já calculada e vai direto para a
simulação).
Benchmark estático — roda o solver nas instâncias e compara com a solução de referência:
python3 src/benchmark.py # todas
python3 src/benchmark.py --instances p01 p02 p05
python3 src/benchmark.py --set prGerar um cenário de falhas no modo Collapse Zones (o modo bom):
python3 src/scenario/generate_failures.py \
--instance p01 --seed 42 --dod 0.20 --edod 0.3 --max-time 120.0 \
--routes-file data/processed/results/p01_routes.jsonOmitir --routes-file cai no modo uniforme — útil só como linha de base.
A bateria dinâmica inteira (varre DOD × EDOD × sementes sobre todas as rotas já calculadas e escreve o CSV de resultados):
python3 src/dynamic_benchmark.py --dry-run # mostra o que seria executado
python3 src/dynamic_benchmark.pyVer a operação acontecendo. O animador reproduz o log de uma simulação — veículos andando, clientes sendo atendidos, arestas caindo:
python3 src/tools/animate_simulation_log.py \
--log-file data/processed/simulation_logs/p01_log.jsonspace pausa, ↑/↓ mudam a velocidade, ←/→ saltam 5 minutos, --dry-run
valida o log e imprime o resumo sem abrir janela. O log precisa existir: ele é
produzido por uma execução do src/main.py e não vem versionado.
Testes:
pytest -qOs artefatos de experimento que estão versionados são estes — e nenhum número deles é reproduzido aqui de propósito: quem quiser o resultado abre o arquivo ou roda de novo.
data/processed/results/— a solução estática de cada uma das 33 instâncias, em dois arquivos por instância:*_clusters.json(que cliente foi para que depósito) e*_routes.json(as rotas finais, com carga e duração).data/processed/analysis/raw_results.csv— 1.980 execuções dinâmicas, uma por linha: 33 instâncias × DOD {0,05 · 0,10 · 0,20 · 0,40} × EDOD {0,25 · 0,50 · 0,75} × 5 sementes. As 41 colunas incluem custo estático e dinâmico, degradação percentual, distância desperdiçada, contagem e tempo de reroteamento por estágio, taxa de utilização de cada estágio, clientes não atendidos, violações de capacidade e de jornada, e as três flags de viabilidade.data/processed/failures/— dois cenários de exemplo para ap01.
As tabelas agregadas, as figuras e os arquivos LaTeX não estão no
repositório: o .gitignore exclui *.csv, *.png, *.pdf e *.tex
(o raw_results.csv é a exceção deliberada). Eles são regenerados por
src/plot_results.py e pelos scripts de tools/.
- O
requirements.txtestá incompleto. Ele cobre o solver e a simulação (pytest,matplotlib,numpy,pymoo,pyyaml), massrc/dynamic_benchmark.pyimporta pandas esrc/plot_results.pyimporta pandas e seaborn. Instale os dois à mão antes de rodar a bateria ou os gráficos. - A bateria versionada tem os três estágios sempre ligados. A flag
--stagesexiste e o simulador respeita, mas o estudo de ablação (S1 sozinho, S1+S2) não está entre os resultados commitados. - A coluna
operation_verdictdo CSV estáUNKNOWNem todas as linhas — o campo foi previsto e nunca preenchido. Use as colunas de viabilidade (fully_feasible,feasible_hard,feasible_soft) no lugar dele. - O único tipo de falha é
edge_block. Quebra de veículo, cliente novo chegando durante a operação e alteração de demanda não estão modelados — e cliente dinâmico é o caso mais citado na literatura de D-VRP. - Velocidade unitária. Tempo de viagem é igual à distância euclidiana; não há trânsito, nem velocidade por via, nem assimetria de sentido.
- Periodicidade e janelas de tempo são lidas mas não usadas. O parser
entende o formato Cordeau completo (PVRP, VRPTW); o solver resolve só o
MDVRP puro (
type == 2, e há umassertpara isso). - O GA tem teto de 10 minutos de relógio por depósito (
ga.time_limit). Em instância grande esse teto pode ser atingido antes da convergência, e o resultado passa a depender do hardware. Verifique o critério de parada que disparou antes de comparar execuções feitas em máquinas diferentes. - O código de erro da validação não chega ao shell. O
main()devolve1quando a auditoria acusa violação, mas a última linha desrc/main.pychamamain()sem repassar o retorno — o processo termina com0de qualquer jeito. Quem for usar isso em CI precisa deraise SystemExit(main()). - O animador tem herança de Windows. O wrapper
src/tools/animate_simulation_log.pyprocuravenv/Scripts/python.exe; em Linux e macOS ele simplesmente segue com o interpretador corrente, mas o caminho embutido denuncia onde foi escrito. - O GitHub classifica o repositório como parte ReScript. É falso positivo:
as soluções de referência de Cordeau têm extensão
.res, que o detector de linguagens confunde. Um.gitattributesmarcandodata/raw/comolinguist-vendoredresolveria.
src/
├── core/ entidades e solução
│ ├── entities.py Customer, Depot, Route (custo, viabilidade, desperdício)
│ └── solution.py conjunto de rotas + relatório de viabilidade
├── algorithms/
│ ├── base.py interface e o esqueleto cluster-first/route-second
│ ├── ccbc_cluster.py k-means capacitado com slots de veículo
│ ├── ccbc_ga.py o solver completo, encadeando as duas fases
│ ├── ga_router.py o GA por depósito (pymoo)
│ ├── ga_operators.py amostragem por vizinho-mais-próximo, mutação-busca-local, remoção de clones
│ ├── ga_problems.py função de fitness
│ ├── ga_local_search.py os 9 movimentos de Prins (2004)
│ └── ga_split.py split linear de Vidal (2016)
├── scenario/ a fase dinâmica
│ ├── generate_failures.py gerador de cenários (uniforme e Collapse Zones)
│ ├── simulator.py motor de eventos e a cascata S1/S2/S3
│ ├── event_queue.py fila de prioridade de eventos
│ ├── reroute_handler.py meia-volta, distância desperdiçada, reagendamento
│ ├── stage3_global_repair.py inserção entre depósitos
│ └── simulation_metrics.py métricas e detecção de violação
├── utils/ config, leitura Cordeau, métricas, gráficos, I/O de resultados
├── tools/ validador e animador do log de simulação
├── main.py uma instância, ponta a ponta
├── benchmark.py bateria estática (gap contra a referência)
├── dynamic_benchmark.py bateria dinâmica (DOD × EDOD × sementes)
└── plot_results.py figuras a partir do CSV de resultados
data/
├── raw/cordeau/ as 33 instâncias + o README do formato
├── raw/cordeau_sol/ soluções de referência publicadas
└── processed/
├── results/ clusters e rotas da fase estática
├── failures/ cenários de bloqueio em JSON
└── analysis/ raw_results.csv
tools/ geradores de tabela LaTeX e figuras para a monografia
tests/ testes unitários (parser, entidades, solução, CCBC, GA)
archive/ a fase exploratória: MOPSO (ZDT1 e VRP) e um TSP com GA
config.yaml todos os parâmetros, com a referência bibliográfica de cada um
O config.yaml merece a visita: cada parâmetro traz, em comentário, de onde
veio o valor — pop_size: 30 porque Prins (2004) mediu que população maior
piora por cruzamento improdutivo, granularity: 30 pelos vizinhos mais próximos
de Prins/Vidal, e assim por diante. Ajustar às cegas é fácil; o arquivo existe
para que não seja preciso.
TCC em ciência da computação, desenvolvido em dupla ao longo de 2026. As
instâncias e as soluções de referência são o conjunto público de Cordeau,
padrão da literatura de MDVRP, redistribuídas aqui com o README.TXT original
do formato.
Referências centrais implementadas:
- Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. — o esquema memético e os movimentos M1–M9.
- Vidal, T. (2016). Split algorithm in O(n) for the capacitated vehicle routing problem. — o split linear com deque monótono.
- Vidal, T. et al. (2012). — o espaçamento de população que evita clones.
- Cordeau, J-F. et al. — as instâncias de referência.