Como arrumamos 300 pacotes em 4 caminhões em 1,3 segundo

Uma execução completa com 300 entregas sintéticas distribuídas na malha viária real de Querétaro, no México. Estes são os números, incluindo os que não favorecem o algoritmo.

A instância

300 entregas posicionadas em nós reais da malha viária de Querétaro extraída do OpenStreetMap, com dimensões e pesos por pacote que vão de caixas de 20 × 15 × 10 cm e 400 gramas até volumes de 80 × 50 × 40 cm e quase 19 quilos. Frota mista de quatro veículos: uma van de teto alto com baú de 365 × 139,2 × 164,8 cm e 1.900 kg de carga máxima, uma van furgão de 339,5 × 149 × 157 cm e 1.351 kg, e duas vans compactas de 200 × 150 × 150 cm e 600 kg. Restrições ativas: apoio mínimo, fragilidade e descarga LIFO.

Os resultados

Por rota: 98, 73, 49 e 80 pacotes, com percursos de 138,4, 198,9, 98,6 e 83,6 km. A assimetria não é um erro: a rota de 98 entregas cobre a zona densa do centro, onde as paradas ficam a centenas de metros; a de 73 vai para a periferia, onde cada cliente custa quilômetros.

Por que a ocupação fica em 60%

É a pergunta de todo mundo que vê o diagrama de carga pela primeira vez. A resposta é geometria, não ineficiência. Quando se exige que cada caixa tenha pelo menos 75% da base apoiada, que nada pesado fique sobre um volume frágil e que os pacotes da parada 12 saiam sem mexer nos da 13, o espaço realmente aproveitável fica muito abaixo do volume nominal.

O dado prático: se o seu sistema de planejamento assume que um veículo de 8,3 m³ aceita 8,3 m³ de mercadoria, ele está montando rotas que a doca não conseguirá carregar. Nós roteirizamos com uma capacidade efetiva calibrada —cerca de 51% a 59% do volume nominal, conforme as restrições ativas— e o resultado são planos executados sem correções de última hora.

O custo da geometria

Aqui vai o número incômodo. Se a mesma instância for resolvida como CVRP clássico, ignorando a terceira dimensão, a distância total cai para 431,7 km. Ou seja: considerar a arrumação real custou 87,8 km a mais, 20% a mais.

Essa diferença não é uma perda do algoritmo: é o preço da viabilidade. As rotas de 431 km existem no papel e não podem ser carregadas. Qualquer ferramenta que anuncie distâncias muito menores provavelmente está resolvendo um problema mais fácil do que o que você tem na doca.

O que falhou e como corrigimos

A primeira versão do sistema deixava o motor de roteirização trabalhar com o volume nominal e confiava em um mediador para reparar depois as rotas impossíveis de carregar. Funcionou, mas saiu caro: na avaliação formal sobre as instâncias de Gendreau, o reparo alcançava a viabilidade à custa de 13,7% de distância adicional, e 36,6% no pior caso.

A mudança foi levar a restrição para a frente em vez de reparar para trás: roteirizar desde o início com capacidade efetiva calibrada por variante. Nos testes de fumaça, o mediador ficou ocioso —zero reparos— e na variante só de carga a distância caiu de 429,6 para 329,3 km. A lição é antiga, mas muitas vezes esquecida: em otimização combinatória, vale mais pagar a restrição na função de custo do que num remendo posterior.

Reprodutibilidade

Os resultados vêm de uma execução registrada do planejador, com matriz de caminhos mínimos sobre a malha viária, preço do combustível de MXN 24,50/L e consumo real por veículo. O mapa, o diagrama de arrumação e os gráficos deste artigo (e a demonstração do site) são desenhados com os dados dessa execução: o diagrama mostra as posições exatas calculadas para os 98 pacotes da rota 1, não uma ilustração.

Para ler depois

A formulação do problema base está em o que é o CVRP (em espanhol), e o detalhe das restrições tridimensionais em 3L-CVRP (em espanhol). Se quiser testar com seus próprios dados, o Planner recebe uma matriz de distâncias e uma lista de pacotes.