🤖 machine learning

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

Este artigo apresenta a plataforma "Smart Routes" para desenvolver e comparar algoritmos para resolver o Problema de Roteamento de Veículos Capacitados com Janelas de Tempo, demonstrando que o aprendizado profundo e os métodos heurísticos clássicos alcançam resultados próximos do ótimo com custos computacionais significativamente menores em comparação com resolvedores exatos como o SCIP, especialmente à medida que os tamanhos dos problemas aumentam.

Autores originais: Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov

Publicado 2026-08-17

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é o capitão de uma frota de entregas, encarregado de entregar centenas de pacotes por uma cidade movimentada. Você tem um mapa, uma lista de clientes e um conjunto estrito de regras: seus caminhões só podem carregar certa quantidade de peso e alguns clientes só querem seus pacotes entre as 9:00 e as 11:00. Seu objetivo é simples: visitar todos, obedecer às regras e gastar o mínimo de tempo e combustível possível. Este é o "Problema de Roteamento de Veículos", um enigma clássico que tem mantido empresas de logística e matemáticos ocupados por décadas.

Por anos, cientistas tentaram resolver isso usando duas ferramentas principais. A primeira é a "Calculadora Perfeita", um método que tenta verificar cada rota possível para encontrar a melhor absoluta. É como tentar provar cada prato em um enorme buffet para encontrar a mordida perfeita. Funciona muito bem para refeições pequenas, mas se o buffet ficar grande demais, você ficará com fome para sempre antes de terminar. A segunda ferramenta é o "Palpite Inteligente", ou heurística. Isso é como um chef experiente que conhece bem a cozinha; ele não verifica cada prato, mas usa experiência e truques rápidos para encontrar uma refeição deliciosa muito rápido. Recentemente, um novo concorrente entrou no ringue: o "Aprendizado Profundo" (Deep Learning). Pense nisso como um chef robô que assiste a milhares de vídeos de culinária, aprende os padrões e então tenta adivinhar a melhor rota instantaneamente, ficando melhor à medida que pratica.

Este artigo, intitulado "Smart Routes", é um torneio de um contra um entre esses três chefs. Os autores construíram um novo parquinho digital chamado "Smart Routes" para testá-los de forma justa. Eles não olharam apenas para quebra-cabeças pequenos e fáceis; eles testaram os algoritmos em problemas com 50 e 100 paradas, o que é como passar de um pequeno bairro para uma cidade inteira. Eles queriam ver quem conseguiria encontrar uma boa rota o mais rápido possível sem quebrar as regras do jogo.

A Grande Corrida: Perfeito vs. Rápido vs. Inteligente

Os pesquisadores organizaram uma corrida usando sua nova plataforma "Smart Routes". Esta plataforma é como um campo de testes universal onde você pode conectar qualquer algoritmo — seja um truque matemático clássico, um poderoso resolvedor de computador ou um robô de aprendizado — e assisti-lo rodar. Eles testaram três tipos principais de competidores:

O Resolvedor Exato (SCIP): A "Calculadora Perfeita" que promete a melhor resposta possível, mas leva muito tempo.
As Heurísticas Clássicas (LKH, 2-OPT, 3-OPT, OR-Tools): Os "Palpitadores Inteligentes" que usam atalhos astutos para encontrar boas respostas rapidamente.
O Modelo de Aprendizado Profundo (JAMPR): O "Chef Robô" treinado para aprender padrões e fazer palpites rápidos e de alta qualidade.

Eles colocaram esses competidores em dois tipos de desafios: uma cidade menor com 50 paradas de entrega e uma cidade maior com 100 paradas. Eles deram à "Calculadora Perfeita" uma vantagem enorme de tempo (1.000 segundos para a cidade pequena e 2.000 segundos para a grande) porque ela precisa pensar muito. Os outros receberam muito menos tempo (100 e 200 segundos, respectivamente).

Os Resultados: Velocidade Vence, mas o Tamanho Importa

O Desafio das 50 Paradas (A Cidade Pequena)
Na cidade menor, a corrida foi surpreendentamente próxima. A "Calculadora Perfeita" (SCIP) eventualmente encontrou a melhor rota absoluta, mas levou muito tempo para chegar lá. Enquanto isso, os "Palpitadores Inteligentes" e o "Chef Robô" encontraram rotas quase tão boas — apenas cerca de 5% piores que a perfeita — mas fizeram isso em uma fração do tempo.

A Lição: Para problemas menores, você não precisa esperar pela resposta perfeita. Os métodos rápidos são tão próximos do melhor que são um negócio muito melhor, pois economizam horas de espera.

O Descimento das 100 Paradas (A Cidade Grande)
Quando a cidade dobrou de tamanho para 100 paradas, as regras do jogo mudaram drasticamente. A "Calculadora Perfeita" começou a ter dificuldades. Ela levou cerca de 13 vezes mais tempo apenas para encontrar sua primeira rota válida em comparação aos outros métodos. Pior ainda, quando finalmente encontrou uma rota, essa rota era cerca de 50% mais cara (mais longa e lenta) do que as rotas encontradas instantaneamente pelo "Chef Robô" e pelos "Palpitadores Inteligentes".

A Lição: À medida que a cidade cresce, a "Calculadora Perfeita" torna-se lenta demais para ser útil. Ela gasta tanto tempo pesquisando que nem consegue encontrar uma boa solução a tempo. O "Chef Robô" (JAMPR) e os "Palpitadores Inteligentes" avançados (como o OR-Tools) permaneceram rápidos e encontraram rotas de alta qualidade, provando que, para grandes problemas, a velocidade e o palpite inteligente vencem a busca pela perfeição.

O Veredito

O artigo conclui que, embora a "Calculadora Perfeita" seja ótima para quebra-cabeças pequenos, ela atinge um limite quando o problema fica grande demais. A plataforma "Smart Routes" mostrou que, para problemas de entrega realistas e de grande escala (como 100 paradas), confiar em soluções exatas e perfeitas é muitas vezes uma má ideia, pois elas demoram muito e nem sequer garantem um ótimo resultado dentro de um tempo razoável.

Em vez disso, os autores sugerem que uma mistura de heurísticas clássicas (os atalhos experientes) e aprendizado profundo (o robô treinado) é a estratégia vencedora. Esses métodos podem encontrar rotas que são quase tão boas quanto as perfeitas, mas o fazem tão rápido que são realmente úteis para a logística do mundo real. O próprio sistema "Smart Routes" é destacado como uma ferramenta valiosa porque permite que qualquer pessoa teste facilmente esses diferentes métodos, visualize as rotas em um mapa e até adicione suas próprias novas ideias sem precisar reconstruir todo o sistema.

Em resumo, se você está tentando entregar pacotes em uma cidade em crescimento, não espere pelo plano perfeito. Use as ferramentas inteligentes e rápidas que aprendem com a experiência, porque, no mundo real, uma boa rota encontrada agora é melhor do que uma rota perfeita encontrada na semana que vem.

Resumo Técnico: Smart Routes – Um Sistema para Desenvolvimento e Comparação de Algoritmos para Resolução de Problemas de Roteamento de Veículos com Restrições Realistas

Definição do Problema
O artigo aborda o Problema de Roteamento de Veículos com Capacidade e Janelas de Tempo (CVRPTW), um desafio crítico na logística de transporte que envolve a otimização de rotas para uma frota de veículos para atender clientes com limites de capacidade específicos e janelas de tempo de entrega. Os autores destacam que, embora as abordagens matemáticas exatas produzam teoricamente soluções ótimas, sua aplicação é severamente limitada pela complexidade exponencial conforme as dimensões do problema aumentam. Consequentemente, há uma necessidade de equilibrar a qualidade da solução em relação ao tempo de busca, particularmente para cenários do mundo real envolvendo o crescimento das populações urbanas e restrições complexas. Além disso, os autores identificam a falta de plataformas unificadas que permitam aos pesquisadores integrar, comparar e visualizar de forma contínua diversas abordagens algorítmicas (exatas, heurísticas e de aprendizado profundo) sem alterar a arquitetura do sistema.

Metodologia
O estudo emprega uma análise comparativa de três classes distintas de algoritmos aplicados a instâncias de CVRPTW:

Métodos Exatos: Os autores utilizam o conjunto de otimização SCIP, que emprega algoritmos de Branch&Bound, Cutting Plane e Branch&Cut para encontrar soluções ótimas.
Heurísticas Clássicas: O estudo avalia abordagens construtivas e metaheurísticas, especificamente a heurística Lin-Kernighan (LKH), métodos de busca local 2-OPT e 3-OPT, bem como o framework OR-Tools do Google.
Aprendizado por Reforço Profundo (DRL): Os autores utilizam uma versão modificada do modelo JAMPR (Joint Attention Model for Pickup and Delivery with Time Windows). Esta arquitetura adapta o Modelo de Atenção (AM) adicionando matrizes treináveis ( $M+$ ) à saída do decodificador para lidar com restrições específicas. O modelo trata a construção da rota como um processo de tomada de decisão sequencial (Processo de Decisão de Markov), onde o estado inclui a rota atual e os nós não visitados, e as ações envolvem a seleção do próximo nó.

Para facilitar essas comparações, os autores desenvolveram o Smart Routes, uma plataforma de software personalizada. Este sistema apresenta:

Arquitetura Modular: Composta por um módulo de Dados (para geração e carregamento de dados), um módulo de Algoritmo (para treinamento e avaliação de modelos definidos pelo usuário ou integrados) e um módulo de Solução (para geração de métricas e visualização).
Extensibilidade: Usuários podem integrar algoritmos personalizados herdando de classes base, permitindo o teste de novas ideias sem modificar o núcleo do sistema.
Visualização: A plataforma fornece interfaces web interativas para visualizar rotas e gerar gráficos de desempenho comparando custos de rota ao longo do tempo.

Configuração Experimental
Experimentos foram conduzidos em conjuntos de dados artificiais gerados com base no conjunto de referência Solomon R201, focando em tamanhos de problema de 50 e 100 nós.

Restrições: O problema foi resolvido em configurações "suaves" (soft), permitindo o salto de clientes não visitados com um custo de penalidade.
Hardware: Os testes foram executados em um servidor equipado com uma GPU NVIDIA Tesla A40 e uma CPU Intel Xeon Gold.
Limites de Tempo: Métodos heurísticos e de DRL receberam 100s (para 50 nós) e 200s (para 100 nós). Métodos exatos (SCIP) receberam tempos significativamente maiores (1000s e 2000s, respectivamente) para tentar encontrar soluções ótimas.

Principais Resultados
A análise comparativa produziu as seguintes descobertas:

Instâncias de 50 Nós: Tanto as heurísticas clássicas (LKH, OR-Tools) quanto o modelo de aprendizado por reforço profundo (JAMPR) produziram rapidamente soluções subótimas. Nos primeiros 10 segundos, a qualidade da solução do SCIP era inferior à destes métodos. Embora o SCIP eventualmente os tenha superado após aproximadamente 100 segundos, a lacuna final entre o modelo de DRL e a solução exata permaneceu inferior a 5%.
Instâncias de 100 Nós: As limitações dos métodos exatos tornaram-se pronunciadas. O SCIP exigiu aproximadamente 13 vezes mais tempo do que os métodos heurísticos e de DRL para alcançar o mesmo custo de rota. Além disso, dentro do tempo alocado, o SCIP falhou em encontrar uma solução ótima, e sua primeira solução viável foi aproximadamente 50% mais custosa do que as fornecidas pelo OR-Tools e JAMPR.
Escalabilidade: À medida que a dimensionalidade do problema dobrou, o tempo necessário para o SCIP encontrar uma solução aumentou cerca de 14 vezes, enquanto o desempenho das abordagens heurísticas e neurais permaneceu relativamente estável, sugerindo que os métodos exatos tornam-se inviáveis para problemas de 100 nós ou mais.

Significância e Alegações
O artigo reivindica duas contribuições primárias:

A Plataforma Smart Routes: Um ambiente unificado e extensível que integra abordagens exatas, heurísticas e de aprendizado profundo para VRP. Os autores argumentam que este sistema oferece uma vantagem significativa sobre os frameworks existentes (como OR-Tools, Gurobi e SCIP) ao suportar aprendizado por reforço profundo, fornecer visualização integrada e permitir a fácil integração de algoritmos customizados.
Validação Empírica de Abordagens: O estudo fornece uma comparação abrangente demonstrando que, para problemas de tamanho moderado (50 nós), as heurísticas clássicas e o aprendizado por reforço profundo oferecem um equilíbrio superior entre qualidade de solução e tempo de computação em comparação com solvers exatos. Para instâncias maiores (100 nós), o artigo conclui que os métodos exatos são praticamente inviáveis devido ao crescimento exponencial do tempo, enquanto o aprendizado por reforço profundo e heurísticas avançadas fornecem soluções subótimas rápidas e de alta qualidade.

Os autores posicionam seu trabalho como um passo em direção a uma otimização de rotas mais eficiente diante do crescimento urbano global, enfatizando que sua plataforma facilita o teste rápido e a comparação de novas ideias algorítmicas na logística.

A Grande Corrida: Perfeito vs. Rápido vs. Inteligente

Os Resultados: Velocidade Vence, mas o Tamanho Importa

O Veredito

Mais como este