🤖 machine learning

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

Este artigo apresenta uma nova abordagem de aprendizado por reforço profundo, baseada em um modelo JAMPR modificado, que resolve eficazmente problemas de coleta e entrega de médio porte com restrições de capacidade e de janela de tempo (CPDPTW) em tempo real e fornece soluções subótimas rápidas para instâncias de grande escala que excedem 200 nós.

Autores originais: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Publicado 2026-08-17

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Andrew Soroka, Alex Meshcheryakov, 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 caminhões de entrega em uma cidade movimentada e em constante crescimento. Seu trabalho é entregar pacotes e retirar devoluções para centenas de clientes, mas você tem um conjunto estrito de regras: seus caminhões só podem carregar certa quantidade de carga e cada cliente tem uma janela de tempo específica quando está em casa para receber um pacote. Se você chegar cedo demais ou tarde demais, ou se tentar socar caixas demais na parte de trás de uma van, o plano falha. Este é o "Problema de Coleta e Entrega" (Pickup and Delivery Problem), um quebra-cabeça massivo que fica mais difícil à medida que mais pessoas são adicionadas à mistura.

Por décadas, computadores tentaram resolver isso agindo como calculadoras super-rápidas, testando milhões de rotas possíveis uma por uma para encontrar o caminho perfeito. Mas, conforme as cidades crescem e o número de paradas explode, essas calculadoras ficam travadas. Elas levam horas para determinar uma rota que um humano conseguiria esboçar em minutos ou, pior, desistem completamente e dizem: "Não consigo resolver isso". É aqui que um novo tipo de cérebro de computador entra em cena: o Aprendizado por Reforço Profundo (Deep Reinforcement Learning). Pense nisso não como uma calculadora, mas como um personagem de videogame que aprende jogando. Em vez de calcular cada possibilidade, ele joga o jogo da entrega milhares de vezes, tornando-se mais rápido e inteligente a cada rodada, aprendendo a identificar as melhores jogadas sem precisar verificar todas as opções.

Neste artigo, Andrew Soroka e sua equipe da Universidade Estadual de Moscou e do Instituto de Pesquisa Espacial do RAS decidiram ensinar este "cérebro de videogame" a lidar com as regras bagunçadas e reais de entrega: o espaço limitado do caminhão e as janelas de tempo rigorosas. Eles pegaram um modelo inteligente já existente chamado JAMPR e lhe deram um upgrade especial para entender as regras de "coleta e entrega", onde um caminhão pode precisar pegar um pacote em uma parada e entregá-lo em outra, tudo isso enquanto lida com limites de capacidade.

Os pesquisadores descobriram que seu modelo atualizado é um demônio da velocidade para cidades de pequeno a médio porte (com 50 a 200 paradas). Nesses cenários, a IA pode cuspir uma rota quase perfeita nos primeiros segundos, superando os métodos tradicionais de "calculadora" que levam muito mais tempo apenas para começar. É como ter um motorista de entrega que conhece a cidade tão bem que consegue gritar instantaneamente a melhor rota, enquanto o computador antigo ainda está tentando ler o mapa.

No entanto, a história fica um pouco mais complicada quando a cidade se torna enorme (400 a 1.000 paradas). Aqui, a IA ainda vence a corrida de velocidade, oferecendo uma solução "boa o suficiente" quase instantaneamente, enquanto os métodos tradicionais lutam para encontrar qualquer rota válida no primeiro minuto. Mas a IA ainda não é perfeita. Para obter a rota absolutamente melhor para essas cidades gigantes, a IA precisa de "treinamento" por dias, o que é um longo tempo. Mesmo após o treinamento, para os problemas mais amplos, a rota final da IA ainda é cerca de 20% mais cara (em termos de distância) do que a melhor solução que um método tradicional poderia eventualmente encontrar se tivesse tempo ilimitado. De fato, assim que o tempo de otimização ultrapassa apenas alguns minutos, os métodos tradicionais ultrapassam a IA, encontrando rotas melhores que a IA não consegue igualar sem um treinamento significativamente maior.

A equipe também testou o quão resistente é a sua IA quando as regras mudam. Eles descobriram que a IA é incrivelmente confiável dentro das condições específicas de teste utilizadas: ela nunca falhou em fornecer alguma solução, mesmo quando o computador tradicional desistiu e disse "impossível" para a mesma distribuição de problemas. No entanto, se o layout da cidade mudar drasticamente — por exemplo, de uma dispersão aleatória de casas para um padrão onde todos vivem em um círculo apertado — o desempenho da IA cai um pouco, embora ela ainda consiga superar os métodos tradicionais durante a primeira hora de resolução.

Em resumo, o artigo sugere que esta abordagem de aprendizado profundo é uma ferramenta poderosa para a logística em tempo real. Ela não substitui totalmente os métodos antigos, especialmente para os quebra-cabeças maiores e mais complexos onde uma resposta absolutamente perfeita é necessária. Mas para situações em que você precisa de uma resposta rápida e confiável agora — como um serviço de entrega reagindo ao tráfego ou a um aumento repentino nos pedidos — esta IA é um divisor de águas, oferecendo uma solução robusta e rápida onde as ferramentas tradicionais muitas vezes travam ou falham.

Resumo Técnico: Aprendizado por Reforço Profundo para CPDPTW

Definição do Problema

O artigo aborda o Problema de Coleta e Entrega com Capacidade e Janela de Tempo (CPDPTW). Este é um problema de otimização combinatória onde uma frota de veículos deve transportar mercadorias de locais específicos de coleta para locais de entrega. O problema é caracterizado por três restrições principais do mundo real:

Capacidade: Os veículos possuem um limite de volume máximo ( $Q$ ).
Janelas de Tempo: Os clientes estão disponíveis apenas durante intervalos de tempo específicos.
Coleta e Entrega (PDP): Diferente dos Problemas de Roteamento de Veículos (VRP) padrão, as mercadorias podem ser coletadas em um depósito ou em um cliente e entregues a outro cliente, exigindo uma sequência rigorosa (coleta antes da entrega).

Os autores observam que, embora existam abordagens clássicas (Programação Inteira Mista, heurísticas), elas têm dificuldade com instâncias de grande escala (ex: >200 nós) sob restrições do mundo real, sofrendo frequentemente de alta carga computacional, falta de flexibilidade para lidar com novas restrições ou falha em encontrar soluções viáveis em prazos razoáveis.

Metodologia

Os autores propõem uma abordagem de Aprendizado por Reforço Profundo (DRL) baseada em uma arquitetura JAMPR (Modelo de Atenção Conjunta para Coleta e Roteamento) modificada.

Arquitetura do Modelo

Base: O modelo baseia-se na estrutura JAMPR, que estende o Modelo de Atenção (AM) e as Redes de Ponteiros (Pointer Networks). Utiliza uma estrutura codificador-decodificador com mecanismos de autoatenção.
Representação de Estado: O problema é modelado como um Processo de Decisão de Markov (MDP).
- Codificador: Codifica características dos nós (coordenadas, demandas, janelas de tempo) em vetores de incorporação (embeddings) ocultos.
- Contexto ( $C(t)$ ): Inclui a incorporação do grafo do problema, o índice do depósito, o último nó adicionado e a capacidade restante do veículo.
- Contexto Estendido: Para lidar com PDP e janelas de tempo, o modelo incorpora incorporações específicas para rotas construídas e características do veículo (capacidade residual, nó atual, tempo atual) em redes neurais totalmente conectadas. Isso permite a construção paralela de múltiplas rotas.
Espaço de Ação: A ação é definida como um par $(r, i)$ , representando a seleção de um nó $i$ a ser adicionado a uma rota ativa $r$ . Uma máscara de viabilidade é aplicada para garantir que as restrições (capacidade, janelas de tempo e ordem de PDP) não sejam violadas.
Política: O decodificador calcula as pontuações de atenção para os nós viáveis. Essas pontuações são usadas para seleção gananciosa (greedy) ou amostradas via distribuição softmax durante o treinamento.

Modificações para CPDPTW

Os autores introduziram modificações específicas ao modelo JAMPR padrão para abordar a natureza de PDP do problema:

Máscara de PDP: Uma máscara adicional foi adicionada à função feasible() para impor restrições de ordem de entrega (uma coleta deve ocorrer antes de sua respectiva entrega).
Tratamento de Restrição Suave (Soft Constraint): Reconhecendo que encontrar uma solução 100% viável para todos os clientes é às vezes impossível em formulações rígidas, os autores adotaram uma configuração SOFT. A função de custo final é uma combinação linear da distância total percorrida e do número de clientes perdidos (ponderados em 13:10, respectivamente). Isso garante que o modelo sempre produza uma solução, mesmo que parcial.

Treinamento e Dados

Geração de Dados: As instâncias foram geradas com base na distribuição Solomon R201. Os tamanhos dos problemas variaram de 50 a 1000 nós. As capacidades dos caminhões e os horizontes de tempo foram escalonados de acordo com o tamanho do problema.
Treinamento: Os modelos foram treinados usando aprendizado por reforço com critérios de parada antecipada (sem redução de custo ao longo de 10 etapas). Os tempos de treinamento variaram significamente conforme o tamanho do problema, indo de 3 horas para problemas de 50 nós a mais de 336 horas para 1000 nós.
Baseline: O modelo proposto foi comparado com o Google OR-Tools, um resolvedor heurístico padrão usado em aplicações do mundo real.

Principais Resultados

O desempenho foi avaliado em três categorias de tamanho de problema:

1. Tamanho Pequeno (50 nós)

Desempenho: O modelo JAMPR treinado forneceu uma solução ótima rápida, superando a solução heurística em custo durante os primeiros segundos de otimização.
Custo: À medida que o tempo de otimização aumentava, os resultados do modelo JAMPR aproximavam-se gradualmente dos do OR-Tools. Após um treinamento extensivo (723 épocas), os resultados finais diferiram do baseline do OR-Tools em não mais do que 0,3%.
Viabilidade: O JAMPR resolveu 100% das instâncias, enquanto o OR-Tools falhou em encontrar soluções para um número crescente de instâncias conforme a complexidade do problema aumentava.

2. Tamanho Médio (100–200 nós)

Desempenho: O modelo forneceu soluções subótimas rápidas que foram superiores às meta-heurísticas nos segundos iniciais de otimização (15–200% melhores em custo do que o OR-Tools).
Convergência: Embora o desempenho do modelo tenha estabilizado rapidamente, ele superou consistentemente o OR-Tools em velocidade. O OR-Tools exigiu tempos de otimização significativamente maiores para se aproximar de níveis de custo semelhantes.
Viabilidade: O JAMPR manteve uma taxa de falha de 0%, resolvendo todas as instâncias, enquanto o OR-Tools falhou em encontrar soluções viáveis para uma porcentagem crescente de instâncias conforme o tamanho aumentava.

3. Tamanho Grande (400–1000 nós)

Desempenho: Para problemas de alta dimensão, o modelo neural ainda forneceu uma solução subótima rápida que é significativamente melhor que o OR-Tools nos primeiros 60 segundos (onde o OR-Tools frequentemente não encontrava nenhuma solução).
Limitações: À medida que o tempo de otimização aumentava, as meta-heurísticas (OR-Tools) eventualmente superavam o modelo neural. O resultado final do JAMPR com tempo máximo de otimização perdeu cerca de 20% do custo do caminho em comparação com a meta-heurística.
Custo de Treinamento: O treinamento para instâncias grandes foi computacionalmente caro (ex: 336 horas para 1000 nós), limitando a capacidade de otimizar totalmente o modelo em tempos razoáveis em GPUs únicas.

Análise de Robustez

Mudança de Distribuição (Distribution Shift): O modelo demonstrou robustez a mudanças na distribuição de dados. Quando testado com uma mistura de distribuições uniforme e normal, o modelo manteve sua capacidade de fornecer soluções subótimas rápidas mesmo com até 25% de dados da nova distribuição.
Invariância de Métrica: O desempenho do modelo permaneceu consistente quando os cálculos de distância foram alterados de métrica Euclidiana para Manhattan.

Significância e Alegações

O artigo afirma ser a primeira aplicação bem-sucedida de uma abordagem de aprendizado por reforço profundo (especificamente um modelo JAMPR modificado) para resolver o problema CPDPTW.

Os autores destacam três contribuições principais:

Troca entre Velocidade e Qualidade (Speed vs. Quality Trade-off): O modelo oferece uma solução subótima rápida (em décimos de segundo) que é frequentemente superior às heurísticas clássicas nos estágios iniciais de otimização. Isso é particularmente valioso para sistemas dinâmicos com limites de tempo rigorosos.
Robustez e Viabilidade: Ao contrário das meta-heurísticas tradicionais, que podem falhar em encontrar qualquer solução viável para instâncias grandes ou complexas, o modelo neural garante uma solução (mesmo que parcial, sob a configuração SOFT onde clientes perdidos são penalizados) para todas as instâncias do problema, independentemente do tamanho.
Escalabilidade da Existência de Solução: A taxa de falha do modelo neural permanece em zero em todos os tamanhos testados, enquanto a taxa de falha do OR-Tools aumenta com o tamanho do problema.

Os autores concluem que, embora os modelos de DRL atualmente exijam um tempo de treinamento significativo para problemas de grande escala e possam ainda não igualar a otimalidade final das meta-heurísticas para instâncias muito grandes, eles representam uma direção promissora para a otimização de rotas em tempo real, onde a velocidade e a existência de solução são críticas. Eles sugerem que trabalhos futuros poderiam envolver a combinação desses modelos de RL com resolvedores de Programação Inteira Mista (MIP) ou o uso de políticas de particionamento aprendidas para lidar com problemas de alta dimensão de forma mais eficaz.