Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

O artigo propõe o método híbrido RL-CMSA, que combina otimização exata e aprendizado por reforço para resolver o problema de roteamento múltiplo de vendedores (mTSP) no cenário min-max, demonstrando superioridade em encontrar soluções de alta qualidade em comparação com algoritmos genéticos de última geração.

O essencial

Imagine que você é o gerente de uma grande empresa de entregas. Você tem um depósito central e precisa enviar pacotes para dezenas (ou centenas) de clientes espalhados pela cidade. Você tem vários motoristas (os "vendedores" do problema) e um objetivo muito específico: ninguém pode ficar sobrecarregado.

O desafio não é apenas fazer o menor caminho total, mas garantir que o motorista que fizer o trajeto mais longo tenha a menor distância possível. Se um motorista fizer 100 km e os outros 10 km, o sistema está desequilibrado. O objetivo é que todos façam, digamos, 30 km cada um.

Esse é o problema que os autores do artigo resolveram. Eles criaram um novo "cérebro" de computador chamado RL-CMSA. Vamos entender como ele funciona usando uma analogia de uma cozinha de restaurante de alta performance.

O Problema: A Cozinha Caótica

Pense nas cidades como ingredientes e nos motoristas como chefs. Você precisa dividir os ingredientes entre os chefs para que nenhum deles tenha uma lista de tarefas gigantesca enquanto os outros ficam ociosos. Fazer isso manualmente é impossível quando há 200 ingredientes e 30 chefs. O computador precisa tentar milhões de combinações.

A Solução: O Método "Construir, Fundir, Resolver e Adaptar" (RL-CMSA)

Os autores criaram um algoritmo que funciona como um chefe de cozinha sábio que aprende com seus erros. O processo tem 6 passos, que podemos imaginar como uma dança:

1. Construir (O Rascunho Criativo)

O computador começa criando várias soluções "rascunho".

• A Mágica do Aprendizado (Reinforcement Learning): Aqui entra o segredo. O computador tem um "diário de bordo" (chamado de valores Q). Ele aprende quais ingredientes (cidades) costumam ficar bons juntos na mesma panela (rota).
• A Analogia: Imagine que o computador percebeu que "Cidade A" e "Cidade B" sempre ficam perto uma da outra em entregas eficientes. Então, na próxima vez que ele tentar montar uma rota, ele tende a colocar A e B juntas, como se estivesse seguindo uma receita testada e aprovada.

2. Fundir (A Colagem de Ideias)

O computador pega todas as rotas que criou no passo anterior e joga tudo numa grande "piscina de ideias".

• Ele descarta as rotas ruins (aquelas que são muito longas ou repetitivas) e guarda apenas as melhores versões de cada trecho de rota. É como se ele dissesse: "Desses 100 pedaços de rota que fiz, vou guardar apenas os 20 melhores".

3. Resolver (O Mestre Matemático)

Agora, ele usa um "super-ajudante" matemático (um solver exato) para pegar esses melhores pedaços da piscina e tentar montar a melhor solução possível.

• A Analogia: É como se você tivesse os melhores pedaços de quebra-cabeça e pedisse a um gênio da matemática para encaixá-los perfeitamente, garantindo que todos os clientes sejam atendidos e o trajeto mais longo seja o menor possível.

4. Melhorar (O Polimento)

Às vezes, a solução matemática deixa dois clientes no mesmo lugar ou deixa uma rota um pouco torta. O algoritmo faz pequenos ajustes:

• Remover: Tira um cliente que está duplicado.
• Mover (Shift): Pega um cliente de uma rota cheia e coloca em uma rota vazia.
• Trocar (Swap): Troca dois clientes entre duas rotas para ver se fica mais equilibrado.
• É como um chef provando o prato e ajustando o sal ou o tempero no final.

5. Aprender (O Ciclo de Feedback)

Aqui está a inteligência do sistema. O computador olha para a solução final que conseguiu.

• Se dois clientes apareceram juntos na rota perfeita, o computador diz: "Isso funcionou! Vou aumentar a chance de juntá-los novamente no futuro".
• Se dois clientes juntos causaram problemas, ele diz: "Evitemos isso na próxima vez".
• Isso é o Aprendizado por Reforço: ele ganha "pontos" por acertos e "perde pontos" por erros, ajustando sua estratégia para a próxima tentativa.

6. Adaptar (A Limpeza)

O computador mantém a "piscina de ideias" fresca. As rotas antigas que não são mais usadas são descartadas (envelhecidas) para dar espaço a novas ideias. Isso impede que o sistema fique preso em soluções velhas e ruins.

O Resultado: Quem Ganhou?

Os autores testaram esse novo "chefe de cozinha" contra o melhor método que já existia (chamado HGA, que é como um time de cozinheiros experientes que tentam de tudo, mas sem o mesmo aprendizado contínuo).

• Em cidades pequenas: Os dois competidores empataram ou foram muito parecidos.
• Em cidades grandes e com muitos motoristas: O RL-CMSA venceu de lavada.
  • Ele encontrou soluções melhores (menos quilômetros rodados pelo motorista mais cansado).
  • Foi mais consistente (nunca falhou em encontrar uma boa solução).
  • Foi mais rápido na maioria dos casos.

Por que isso é importante?

Imagine que você precisa coordenar drones para entregar remédios em uma cidade grande, ou robôs em um armazém. Se um robô ficar sobrecarregado, o sistema todo atrasa.

O RL-CMSA é como um gerente que aprende com a experiência. Em vez de tentar adivinhar aleatoriamente, ele usa o que funcionou no passado para tomar decisões melhores no futuro. Ele equilibra a exploração (tentar coisas novas) com a exploração (usar o que já sabe que funciona), garantindo que o trabalho seja dividido de forma justa e eficiente entre todos os "trabalhadores".

Em resumo: Os autores criaram um sistema inteligente que aprende a dividir o trabalho de entrega para que ninguém fique sobrecarregado, usando uma mistura de criatividade, matemática pura e aprendizado contínuo, superando os métodos antigos, especialmente em cenários complexos e grandes.

Resumo técnico

Resumo Técnico: RL-CMSA para o Problema do Caixeiro Viajante Múltiplo Min-Max

1. O Problema: mTSP Min-Max

O artigo aborda o Problema do Caixeiro Viajante Múltiplo (mTSP), uma generalização do clássico Problema do Caixeiro Viajante (TSP). No mTSP, $m$ rotas devem ser construídas, todas começando e terminando em um depósito comum, visitando todos os clientes exatamente uma vez.

O foco específico deste trabalho é a variante Min-Max:

• Objetivo: Minimizar o comprimento da rota mais longa entre as $m$ rotas.
• Aplicação: Esta métrica é crucial para o equilíbrio de carga de trabalho (workload balance) em cenários como entregas de última milha com veículos idênticos, patrulhamento coordenado de robôs, planejamento de saídas de drones (UAVs) e roteamento de técnicos.
• Desafio: O problema é NP-difícil. Algoritmos exatos não escalam bem para instâncias grandes, tornando-se necessárias heurísticas e metaheurísticas.

2. Metodologia Proposta: RL-CMSA

Os autores propõem uma abordagem híbrida chamada Construct, Merge, Solve & Adapt com Aprendizado por Reforço (RL-CMSA). O algoritmo opera em um ciclo iterativo até atingir um limite de tempo, composto por seis fases principais:

1. Construção (Construct):

   • Gera $n_{solutions}$ soluções candidatas probabilisticamente.
   • Fase de Agrupamento (Cluster): Utiliza um processo de seeding (semeadura) baseado em $k$-means++ modificado por Q-values (valores aprendidos por RL). Cidades com alta probabilidade de co-ocorrência em rotas ótimas (baseado em Q-values) são agrupadas.
   • Fase de Roteamento (Route): Para cada cluster, constrói uma rota inicial usando uma heurística de inserção gulosa e aplica busca local intra-rota (2-opt e Or-opt).
   • Aplica melhorias inter-rotas focadas na rota mais longa.

2. Fusão (Merge):

   • As rotas das soluções geradas são adicionadas a um pool candidato ($R_{cand}$).
   • Rotas que visitam o mesmo conjunto de cidades são consolidadas (mantendo apenas a mais curta).
   • Rotas que excedem o comprimento da melhor solução atual são descartadas para evitar viés no aprendizado.

3. Resolução (Solve):

   • Formula um Programa Linear Inteiro Misto (MILP) de cobertura de conjuntos.
   • O objetivo é selecionar exatamente $m$ rotas do pool $R_{cand}$ que cubram todos os clientes e minimizem o comprimento da rota mais longa.
   • Utiliza o solucionador CPLEX para resolver este subproblema exato de forma eficiente.

4. Melhoria (Improve):

   • Refina a solução obtida pelo MILP aplicando operadores de busca local:
     • Remoção: Remove duplicatas de cidades (caso existam) para garantir viabilidade.
     • Deslocamento (Shift): Move uma cidade de uma rota para outra se reduzir o comprimento total ou a rota máxima.
     • Troca (Swap): Troca cidades entre rotas diferentes para melhorar a qualidade.

5. Aprendizado (Learn):

   • Atualiza os Q-values (valores de par de cidades) baseando-se na qualidade das soluções.
   • Se um par de cidades $\{i, j\}$ aparece na melhor solução ($R_{best}$), o Q-value é reforçado (tendendo a 0, indicando que devem estar na mesma rota). Se não aparecem juntos, o valor é desincentivado (tendendo a 1).
   • Isso guia a fase de construção futura para agrupar cidades que tendem a estar juntas em soluções de alta qualidade.

6. Adaptação (Adapt):

   • Gerencia o pool de rotas ($R_{cand}$) usando uma política baseada em "idade".
   • Rotas novas têm idade 0. Rotas que não são usadas na melhor solução têm a idade incrementada.
   • Rotas que atingem um limite de idade ($age_{max}$) são removidas, garantindo que o pool permaneça compacto e atualizado.

3. Contribuições Principais

• Integração Híbrida: Combina a geração de soluções diversificada guiada por Aprendizado por Reforço (RL) com a precisão da otimização exata (MILP) dentro do framework CMSA.
• Mecanismo de Aprendizado Específico: Desenvolveu um mecanismo de atualização de Q-values focado em co-ocorrência de pares de cidades para guiar o agrupamento (clustering) no mTSP min-max.
• Estratégia de Balanceamento: O algoritmo equilibra exploração (gerando soluções diversas) e exploração (refinando e combinando rotas promissoras via MILP e busca local).
• Adaptação Dinâmica: Ajusta automaticamente a diversidade e o tamanho do pool de rotas com base no progresso da busca.

4. Resultados Experimentais

Os autores compararam o RL-CMSA com um Algoritmo Genético Híbrido (HGA) de última geração, considerado o baseline mais forte na literatura para este problema.

• Instâncias Aleatórias:

  • O RL-CMSA superou consistentemente o HGA em qualidade média de solução e na frequência de encontrar a melhor solução (#b), especialmente para instâncias maiores ($n=100, 200$) e com maior número de vendedores ($m$).
  • Para $n=200$ e $m$ pequeno (1%), o HGA teve desempenho ligeiramente superior, mas o RL-CMSA dominou à medida que $m$ aumentava.
  • O RL-CMSA foi geralmente mais rápido para encontrar soluções de alta qualidade em instâncias menores e médias.
  • Testes Estatísticos: Testes de Wilcoxon confirmaram que o RL-CMSA é estatisticamente superior na maioria das configurações (especialmente para $n=100$ e $n=200$ com $m \ge 5\%$).

• Instâncias TSPLIB (eil51, berlin52, eil76, rat99):

  • O RL-CMSA igualou ou superou o HGA em 5 dos 16 cenários testados (combinações de instância e $m$).
  • Nas demais, os resultados foram comparáveis, mas o RL-CMSA foi geralmente mais rápido.

• Análise de Trajetória de Busca (STN):

  • A análise de Redes de Trajetória de Busca mostrou que o HGA tende a dispersar-se amplamente pelo espaço de busca, enquanto o RL-CMSA converge mais rapidamente e consistentemente para uma região de alta qualidade, explicando sua maior robustez.

5. Significância e Conclusão

O trabalho demonstra que a combinação de metaheurísticas guiadas por aprendizado com otimização exata é uma estratégia poderosa para problemas de roteamento complexos como o mTSP min-max.

• Robustez: O RL-CMSA oferece resultados mais consistentes e menos variáveis entre execuções do que os algoritmos genéticos tradicionais.
• Escalabilidade: O método escala bem com o aumento do número de cidades e vendedores, tornando-se a opção preferida para cenários de grande escala onde o equilíbrio de carga é crítico.
• Futuro: Os autores planejam enriquecer o pool de rotas com vizinhanças de maior escala e estender o esquema de aprendizado para características de ordem superior (além de pares), além de testar em cenários com restrições adicionais (janelas de tempo, capacidades).

Em suma, o RL-CMSA representa um avanço significativo no estado da arte para o mTSP min-max, superando abordagens puramente evolutivas através de uma sinergia inteligente entre construção probabilística, aprendizado e resolução exata.