De uma pergunta matemática à LATTIMEX

Durante anos pesquisei uma pergunta que hoje define o trabalho da LATTIMEX: como projetar rotas eficientes quando a capacidade não é só um número, mas mercadoria que precisa caber, chegar íntegra e ser descarregada na ordem certa?

Anos atrás, uma família de problemas me fisgou por completo: os relacionados ao transporte de mercadorias e pessoas. Não eram exercícios que terminavam ao encontrar uma fórmula elegante. Cada resposta abria outra pergunta, e cada restrição mudava por completo o espaço de soluções.

Por trás de uma operação de entregas aparentemente cotidiana existe uma decisão combinatória enorme: qual veículo deve atender cada entrega, em que ordem deve visitar os destinos e como fazer isso sem exceder sua capacidade. Assim que o número de paradas aumenta, as alternativas crescem tão rápido que revisar todas deixa de ser viável.

O que começou como curiosidade se transformou em uma linha de pesquisa independente que mantenho há anos. Dessa busca nasceram dois algoritmos: OAS, para transportar pessoas, e SENDA, para distribuir mercadorias com rapidez e com qualidade suficiente para apoiar decisões reais.

A pergunta que me obcecou

A primeira versão do OAS não nasceu para entregar pacotes. Surgiu do estudo de percursos com pares origem–destino: pessoas que precisam ser buscadas em um ponto e levadas a outro, dividindo o veículo com outros passageiros.

O objetivo não era apenas reduzir a distância do veículo. Também importava quanto cada pessoa esperava, quanto tempo ficava a bordo e como equilibrar o serviço entre todos. Essa tensão entre eficiência global e experiência individual me obrigou a pensar o problema de outra perspectiva.

Com o tempo percebi que a intuição central podia ser levada para a distribuição de mercadorias. Quando todos os percursos começam em um mesmo depósito, o problema muda de forma, mas conserva a pergunta essencial: como agrupar e ordenar entregas para produzir percursos de baixo custo com capacidade limitada.

De OAS a SENDA

Quando levei a pergunta para a distribuição de mercadorias, descobri que as regras do OAS não serviam ali. Com um único depósito, o veículo já sai carregado e não há coletas para ordenar: era preciso outro algoritmo. Assim nasceu o SENDA, o núcleo de roteirização que a LATTIMEX usa hoje.

O SENDA segue uma única trajetória de busca por execução: em cada execução há uma solução, com todas as suas rotas, que é parcialmente destruída, reparada e melhorada, sem uma população de soluções que se cruzam entre si. Combina ideias publicadas (busca adaptativa em vizinhanças grandes, vizinhanças granulares e penalização adaptativa de capacidade) em uma implementação própria, e divide seu tempo entre várias trajetórias em paralelo.

1. OAS. Sequenciamento para transporte de pessoas com pares de coleta e entrega. Será usado, em sua forma original, em um planejador de transporte de passageiros.
2. SENDA. Roteirização de mercadorias a partir de um depósito com uma trajetória de busca por execução. É o algoritmo medido neste artigo.
3. LATTIMEX. O motor que integra o SENDA com a arrumação 3D da carga, a frota real, as ruas da cidade e o plano de descarga por portas.

Do modelo ao CVRP

Em logística, essa classe de problema é conhecida como Capacitated Vehicle Routing Problem, ou CVRP. O modelo parte de um depósito, uma frota com capacidade limitada e um conjunto de clientes com demanda. O desafio é atender a todos com o menor custo total possível.

Na teoria da complexidade, o CVRP pertence à família de problemas NP-difíceis. Isso significa que o número de combinações cresce de forma explosiva conforme se adicionam clientes, veículos e restrições. Em uma operação pequena ainda é possível explorar muitas alternativas; em uma rede real, tentar enumerar todas pode exigir um tempo de computação impraticável. Por isso o desafio não é apenas encontrar uma solução, mas encontrar uma solução de alta qualidade dentro do tempo que a operação permite.

Durante anos fui formulando hipóteses, construindo versões, encontrando casos em que o método falhava e recomeçando. O avanço não veio de uma única descoberta espetacular. Foi um acúmulo de pequenas melhorias, cada uma testada antes de ser mantida.

1. Construir uma primeira solução confiável. Antes de buscar excelência, o método precisava produzir rotas completas e respeitar a capacidade.
2. Entender os casos difíceis. Nem todas as instâncias se comportam igual: a distribuição geográfica, a saturação dos veículos e a variação da demanda mudam o problema.
3. Concentrar o esforço onde ele gera valor. O tempo de computação é um recurso; um solver comercial precisa decidir rápido, não pesquisar indefinidamente.
4. Verificar de forma independente. Uma solução não conta se omite clientes, excede a capacidade ou reporta uma distância que não corresponde às suas rotas.

O resultado foi um motor compacto, pensado para concentrar o esforço computacional nas decisões de maior impacto e evitar complexidade desnecessária. Sua implementação tem licença livre para a comunidade interessada em melhorar a roteirização; o importante para uma operação é que ele possa ser implantado, integrado e entregar resultados verificáveis.

Medir o SENDA frente a uma referência

Para conhecer o valor real do SENDA não bastava compará-lo com suas versões anteriores. Era preciso colocá-lo diante de uma referência séria. Escolhi o HGS-CVRP —Hybrid Genetic Search—, um dos métodos mais reconhecidos e competitivos na pesquisa sobre o CVRP.

O HGS é fruto de anos de engenharia algorítmica. Sua capacidade de produzir soluções de alta qualidade o tornou um ponto de comparação internacional. A pergunta não era se o SENDA podia ser declarado vencedor em termos gerais; a pergunta era quanto ele sacrificava em qualidade, quanto ganhava em velocidade e em que tamanhos essa relação podia ser útil.

O experimento fez parte de um manuscrito formal que permanece inédito. Congelamos as regras antes de executar, usamos o mesmo orçamento de tempo, fizemos 10 réplicas externas por instância e verificamos de forma independente custo, cobertura, capacidade e frota.

BKS significa Best Known Solution: a melhor solução conhecida, usada como referência científica para uma instância. Quanto menor a diferença em relação ao BKS, maior a qualidade da solução obtida.

Em 60 instâncias comparáveis das famílias A, B e E, respeitando o número de veículos de cada instância, o SENDA obteve um gap médio de 0,111% em relação ao BKS. O HGS obteve 0,004%. A diferença média foi de cerca de um décimo de ponto percentual.

Sem jargão: para problemas desse tamanho, o SENDA chegou muito perto da melhor solução conhecida e empatou com o HGS em 37 das 60 instâncias; nas outras 23, o HGS foi melhor. Ambos tiveram o mesmo orçamento de 2 segundos; o SENDA reserva por projeto uma margem de segurança e terminou em 1,58 segundo, em média.

A honestidade também faz parte do produto

Nas instâncias X, de maior tamanho, apareceu uma mudança de regime. O SENDA registrou um gap médio de 4,119%, contra 1,450% do HGS: uma diferença de 2,669 pontos percentuais.

Ali o HGS mantém uma vantagem clara no CVRP clássico. Esconder esse resultado teria produzido uma frase publicitária melhor, mas uma empresa pior. Conhecer a fronteira de uma tecnologia é tão importante quanto conhecer seus pontos fortes: permite decidir onde usá-la, quando lhe dar mais tempo e o que deve ser avaliado no sistema completo.

O SENDA não precisa ser o melhor solver para todos os tamanhos e todas as variantes. Precisa resolver com qualidade, rapidez e consistência o problema que uma operação realmente enfrenta.

A terceira dimensão mudou a pergunta

Até aqui falamos apenas de atribuir clientes e ordenar visitas. Mas uma operação de última milha não despacha pontos em um mapa: despacha caixas, volumes e produtos que ocupam espaço, têm peso e precisam ser descarregados em certa ordem.

Quando incorporamos dimensões, orientação, apoio, fragilidade e sequência de descarga, entramos no terreno do 3L-CVRP. Então uma rota pode ser excelente no CVRP tradicional e, ainda assim, impossível de executar.

• A soma dos volumes pode caber e a geometria das caixas, não.
• Um pacote pesado pode acabar sobre uma mercadoria frágil.
• A entrega seguinte pode ficar bloqueada no fundo do veículo.
• Uma atribuição eficiente em quilômetros pode exigir um veículo que fisicamente não consegue transportar a carga.

Por isso, ao incorporar o 3L, a vantagem de um solver na roteirização isolada deixa de determinar sozinha qual é a melhor solução. Essa diferença não desaparece, mas passa a fazer parte de uma decisão maior: produzir um plano completo, carregável e executável.

Essa foi uma das conclusões que acabaram mudando o rumo do projeto. Já não se tratava apenas de aperfeiçoar um algoritmo. Era preciso construir a ponte entre a pesquisa e a doca.

Formar a LATTIMEX

Um solver sozinho não é um produto. Para usá-lo todos os dias, uma empresa precisa carregar pedidos, configurar veículos, calcular distâncias em ruas reais, designar motoristas, revisar custos, visualizar a arrumação, entregar roteiros e manter o controle de seus dados.

Construir a LATTIMEX significou cercar o motor matemático de tudo o que é necessário para que uma decisão chegue até a operação:

1. Dados que uma empresa possa usar. Importação de entregas, frota, pacotes, dimensões e pesos.
2. Distâncias que correspondam à cidade. Planejamento sobre a malha viária, não apenas com linhas retas entre coordenadas.
3. Roteirização e carga na mesma conversa. A atribuição precisa considerar o que o veículo realmente pode transportar.
4. Resultados que cheguem ao motorista. Sequência de paradas, navegação, custos e diagrama de carga por veículo.
5. Privacidade desde o projeto. Os dados sensíveis dos clientes permanecem na infraestrutura da empresa; o motor trabalha com a informação mínima necessária para otimizar.

Assim nasceu a visão comercial da LATTIMEX: não vender um resultado abstrato, mas transformar uma operação de entregas em decisões claras sobre veículos, rotas e carga.

O nome da empresa veio depois da pesquisa, mas seu propósito já estava lá: levar precisão matemática a operações que não podem se dar ao luxo de existir só no papel.

Um dia na LATTIMEX

Um dia de trabalho na LATTIMEX não começa perguntando que nova função podemos adicionar ao software. Começa conversando com transportadores, responsáveis de tráfego, planejadores e pessoas que conhecem as entregas pela operação diária.

Perguntamos quais decisões consomem mais tempo, onde aparecem as viagens que poderiam ter sido evitadas e que situações obrigam a refazer um plano. Às vezes o problema está em atribuir os veículos; outras, em uma capacidade que só existia na planilha, em uma rota que mudou durante o dia ou em uma carga que chegou à doca e não pôde ser arrumada como previsto.

Depois transformamos essas conversas em perguntas de otimização: que parte da decisão pode ser automatizada? Que restrições precisam ser representadas para que o resultado seja executável? Como medimos se uma alternativa realmente melhora a operação?

Então começa a experimentação. Projetamos estratégias algorítmicas, construímos protótipos, colocamos esses protótipos diante de cenários diferentes e medimos qualidade, tempo e viabilidade. Como o espaço de soluções é grande demais para ser percorrido por completo, trabalhamos com métodos de aproximação capazes de concentrar o esforço computacional nas alternativas mais promissoras. A pergunta prática é sempre a mesma: quanta qualidade conseguimos obter com o tempo e os recursos disponíveis?

Algumas ideias funcionam; outras revelam seus limites e são descartadas. Também estudamos como o comportamento muda quando a instância cresce ou novas restrições entram, porque uma estratégia eficaz com dezenas de entregas não necessariamente mantém o mesmo desempenho com centenas. Nem toda hipótese merece virar produto, e aprender isso cedo também é uma forma de avançar.

Quando uma solução demonstra que gera valor, começa outro trabalho: transformá-la em uma ferramenta que possa ser usada sem conhecer a matemática por trás. É preciso automatizar a preparação dos dados, apresentar as decisões com clareza, verificar os resultados e conectá-los ao fluxo diário da empresa.

O propósito não é substituir a experiência de quem conhece a operação. É dar a essa pessoa a capacidade de avaliar em minutos alternativas que levariam horas manualmente, detectar oportunidades que não são evidentes e manter o controle da decisão final.

Esse ciclo —ouvir uma dificuldade real, formulá-la, experimentar, automatizar e voltar à operação para medir— é hoje a forma de trabalhar na LATTIMEX. Cada conversa pode revelar o próximo problema que vale a pena resolver.

A partir de Querétaro, estamos incorporando empresas de distribuição e última milha no México para comparar suas rotas atuais com alternativas otimizadas e medir quilômetros, combustível, utilização da frota, tempo de planejamento e viabilidade de carga com seus próprios dados.

A pesquisa continua, mas agora cada avanço tem um destino concreto: ajudar uma operação a usar melhor seus veículos, reduzir percursos desnecessários e tomar decisões com base em evidências.