The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Resumo Técnico: O Problema do Ladrão Viajante com Janelas de Tempo

1. Definição do Problema

O artigo aborda uma extensão do Problema do Ladrão Viajante (TTP - Traveling Thief Problem), que combina o Problema do Caixeiro Viajante (TSP) e o Problema da Mochila (KP). No TTP clássico, um ladrão deve visitar cidades para coletar itens, maximizando o lucro líquido (lucro dos itens menos o custo de aluguel da mochila), onde a velocidade de viagem diminui conforme o peso carregado aumenta.

A contribuição central deste trabalho é a introdução das Janelas de Tempo (Time Windows - TW), criando o problema TTPTW.

• Restrição de Janela de Tempo: Cada cidade $i$ possui uma janela de tempo $[L_i, U_i]$. O ladrão deve chegar na cidade dentro desse intervalo.
• Mecanismo de Espera: Se o ladrão chegar antes de $L_i$, ele deve esperar até o início da janela, o que aumenta o tempo total da viagem e, consequentemente, o custo de aluguel da mochila.
• Violação de Restrição: Se a chegada for após $U_i$, a solução é considerada inviável.
• Complexidade: A interdependência entre a rota (TSP), a seleção de itens (KP) e as restrições temporais torna o espaço de busca extremamente complexo e a área viável drasticamente reduzida.

2. Metodologia e Algoritmos Propostos

Os autores desenvolveram uma nova abordagem heurística e adaptaram algoritmos existentes para comparação.

A. Algoritmo Proposto: Dual Search Evolutionary Algorithm (DSEA)
O DSEA é um algoritmo evolutivo projetado especificamente para TTPTW, composto por:

1. Inicialização de Rota (Tour Initialization):
   • Diferente dos métodos padrão que usam Chained Lin-Kernighan (CLK), os autores propõem um algoritmo de inicialização baseado em vizinhança mais próxima com memória e pontuação.
   • O algoritmo calcula o tempo de chegada previsto e atribui pontuações: positivo se a janela for respeitada, negativo (penalizado) se houver violação. Isso gera uma rota inicial viável ou próxima da viabilidade, crucial para evitar que o algoritmo comece em regiões inviáveis.
2. Operadores de Busca (Dual Search):
   • O algoritmo utiliza dois operadores simultaneamente em cada execução:
     • Baseado em 2-opt: Topo (Two-Opt com perturbação) e ITP (Integração de Two-Opt e Packing).
     • Baseado em Inserção: Rain (Inserção Aleatória) e IIP (Integração de Inserção e Packing).
   • A combinação visa equilibrar exploração (perturbação) e exploração local.
3. Estratégias de Reparo de Plano de Carga (Packing Plan Repair):
   • Foram testadas três variantes do DSEA com diferentes estratégias de reparo:
     • DSEA1: Sem reparo explícito (gera o plano de carga apenas no final do loop principal).
     • DSEA2: Usa o método Repack (reavalia e remove itens pesados/pouco lucrativos que causam atrasos).
     • DSEA3: Integração de reparo e otimizador (atualiza o plano de carga dinamicamente durante a busca).

B. Adaptação de Algoritmos Existentes
Para comparação, os autores adaptaram os melhores algoritmos atuais de TTP e TSPTW (Traveling Salesperson Problem with Time Windows):

• TTP: S4, S5 e C5 (algoritmos de solução única e populacional).
• TSPTW: LKH-3 e VSR-LKH-3 (algoritmos baseados em Lin-Kernighan com aprendizado por reforço).
• Adaptação: Todos foram modificados para incluir o cálculo de violação de janelas de tempo e a separação entre valor objetivo e violação de restrição (técnica constraint-objective value separation).

3. Contribuições Principais

1. Definição do Problema TTPTW: Formalização matemática do TTP com restrições de janelas de tempo, incluindo a função objetivo que considera o tempo de espera e a penalidade de atraso.
2. Novos Benchmarks: Criação de um conjunto de instâncias de teste derivadas dos benchmarks clássicos de TTP (Polyakovskiy et al.), com janelas de tempo geradas sob diferentes níveis de "apertamento" (parâmetro $l$), incluindo cenários de janelas muito restritivas (úteis para serviços de emergência e entregas).
3. Algoritmo DSEA: Desenvolvimento de um algoritmo evolutivo híbrido que supera as abordagens adaptadas, especialmente através de uma inicialização de rota inteligente e operadores combinados.
4. Análise de Viabilidade: Demonstração de que algoritmos tradicionais falham em encontrar soluções viáveis em instâncias com janelas de tempo, enquanto o DSEA mantém altas taxas de viabilidade.

4. Resultados Experimentais

Os experimentos foram realizados em 30 execuções independentes, com limite de 1.000.000 de Avaliações de Função (FE), em instâncias variando de 51 a 1000 cidades.

• Desempenho dos Algoritmos Adaptados:

  • Os algoritmos S4, S5, C5, LKH-3 e VSR-LKH-3 falharam em encontrar soluções viáveis na maioria das instâncias, especialmente aquelas com mais de 100 cidades ou janelas de tempo mais restritas.
  • A taxa de viabilidade (Feasible Rate - FR) desses algoritmos caiu drasticamente (muitas vezes para 0%) à medida que o tamanho da instância aumentava.
  • A aplicação da nova inicialização de rota ajudou S4, S5 e C5 a encontrar soluções viáveis em instâncias menores, mas não melhorou significativamente o valor objetivo em comparação ao DSEA.

• Desempenho do DSEA:

  • O DSEA superou consistentemente todos os outros algoritmos em termos de valor objetivo e taxa de viabilidade.
  • Melhor Variante: O DSEA1 (sem reparo de plano de carga) foi a variante mais robusta, encontrando soluções viáveis em quase todas as instâncias e obtendo os melhores valores de lucro líquido na maioria dos casos.
  • Observação sobre Reparo: A adição de mecanismos de reparo (DSEA2 e DSEA3) aumentou o custo computacional sem necessariamente melhorar o resultado final. Em muitos casos, o reparo impediu a exploração de novas rotas. No entanto, em instâncias muito grandes (ex: 1000 cidades) ou com restrições específicas, o DSEA3 mostrou-se útil para escapar de ótimos locais.
  • Influência da Inicialização: A nova inicialização de rota foi fundamental. Sem ela, os algoritmos não conseguiam encontrar nenhuma solução viável nas instâncias mais difíceis.

5. Significado e Conclusão

O estudo demonstra que a combinação de roteamento e seleção de recursos sob restrições temporais rígidas exige abordagens específicas, pois os algoritmos padrão falham ao não conseguirem navegar no espaço de soluções viáveis reduzido.

• Importância Prática: O problema modela cenários reais críticos, como serviços de emergência, saúde domiciliar e logística de entregas, onde o tempo é um recurso limitado e a violação de prazos é inaceitável.
• Conclusão: O DSEA, particularmente a variante DSEA1 combinada com a inicialização de rota proposta, é o estado da arte atual para o TTPTW. A pesquisa estabelece novos benchmarks e direciona o foco para a importância da qualidade da solução inicial e da exploração eficiente do espaço de busca em problemas multi-componente com restrições complexas.

O trabalho sugere que, em problemas com janelas de tempo, a estratégia de "consertar" a solução (reparo) pode ser menos eficaz do que focar na geração de rotas viáveis desde o início e na exploração contínua do espaço de soluções.