Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

Resumo Técnico: Heurística de Densidade de Recompensa para Roteamento Dinâmico de Múltiplos Veículos

Definição do Problema
O artigo aborda uma variante dinâmica e online do Problema de Roteamento de Veículos (VRP) que integra elementos do Problema de Orienteering (OP). Nesta formulação, uma frota de veículos opera dentro de um horizonte de tempo fixo para maximizar a recompensa cumulativa. Diferente das variantes estáticas de VRP, as tarefas chegam dinamicamente (online), necessitando de replanejamento contínuo. O problema é limitado por um orçamento de tempo por veículo, onde um veículo só pode ser atribuído a uma tarefa se a soma do tempo de viagem e do tempo de serviço não exceder seu orçamento restante. Esta estrutura modela cenários do mundo real, como a alocação de tarefas de drones autônomos e o despacho de táxis urbanos, onde as decisões de atribuição devem ser tomadas em milissegundos conforme novas solicitações emergem.

Metodologia
Os autores propõem e avaliam uma "Heurística de Densidade de Recompensa" (denominada Heurística de Eficiência) contra quatro heurísticas de construção e três algoritmos metaheurísticos.

1. Abordagem Proposta (Heurística de Eficiência):
   O núcleo do método é uma função de pontuação baseada na densidade de recompensa, definida como a razão entre a recompensa de uma tarefa ($R$) e seu custo de tempo total (tempo de viagem $d$ + tempo de serviço $s$):
   $$\eta(\tau) = \frac{R(\tau)}{d(v, \tau) + s(\tau)}$$
   Duas instanciações são testadas:

   • Greedy-Efficiency (Eficiência Gananciosa): Atribui cada veículo disponível ao alvo não reivindicado de maior pontuação sequencialmente.
   • Hungarian-Efficiency (Eficiência Húngara): Formula a atribuição como um Problema de Atribuição Linear (LAP) usando a densidade de recompensa negativa ($-\eta$), resolvido de forma ótima via algoritmo húngaro.

2. Linhas de Base Comparativas:

   • Heurísticas de Construção: Greedy-Nearest (minimiza a distância), Greedy-Reward (maximiza a recompensa bruta), Hungarian-Time (minimiza o tempo de viagem) e Hungarian-Reward (maximiza a recompensa bruta via LAP).
   • Metaheurísticas: Adaptive Large Neighborhood Search (ALNS), Algoritmo Genético (GA) e Simulated Annealing (SA). Estas são reinicializadas em cada evento de replanejamento para se adaptarem ao cenário mutável.

3. Configuração Experimental:
   O estudo utiliza um simulador orientado a eventos onde o replanejamento é acionado após a conclusão de uma tarefa. As avaliações são conduzidas em dois domínios:

   • Ambiente de Drones Sintético: 12, 20 e 50 drones operando em um mapa de $5000 \times 5000$ com 50–200 alvos.
   • Despacho de Táxis do Mundo Real: 50 e 200 táxis operando ao longo de 120 minutos contra aproximadamente 7.600 tarefas derivadas do conjunto de dados NYC TLC Yellow Cab 2024.
     O desempenho é medido pela recompensa (ou receita) cumulativa e pelo tempo de planejamento (custo computacional).

Resultos Principais
Os experimentos demonstram uma clara dominância de Pareto das heurísticas de Eficiência sobre todos os métodos concorrentes:

• Qualidade da Solução: As heurísticas de Eficiência (tanto as variantes Greedy quanto as Hungarian) alcançam uma qualidade de solução estatisticamente indistinguível das melhores metaheurísticas (ALNS, GA, SA) em todos os tamanhos de frota e domínios. Em contraste, heurísticas mais simples (Greedy-Nearest, Greedy-Reward, Hungarian-Time, Hungarian-Reward) apresentam consistentemente um desempenho inferior com déficits estatisticamente significativos em recompensa/receita.
• Eficiência Computacional: As heurísticas de Eficiência exigem duas a três ordens de magnitude menos tempo de planejamento do que as metaheurísticas.
  • No cenário de 50 drones, a Hungarian-Efficiency exigiu ~128 ms, enquanto a GA exigiu ~1,1 milhão de ms, ALNS ~42.654 ms e SA ~5.247 ms.
  • No cenário de 200 táxis, a Hungarian-Efficiency exigiu ~363 ms, enquanto a GA exigiu ~4,58 milhões de ms.
• Greedy vs. Otimalidade Global: O estudo descobriu que a abordagem Greedy-Efficiency, computacionalmente mais barata, produz resultados estatisticamente equivalentes à abordagem Hungarian-Efficiency, que é globalmente ótima, sugerindo que a garantia de otimalidade global do algoritmo húngaro confere benefício prático limitado nestes contextos dinâmicos de alta frequência.

Significância e Alegações
O artigo alega que a escolha do critério de otimização (densidade de recompensa/eficiência) é mais impactante do que a sofisticação do mecanismo de atribuição.

• Vantagem Estrutural: O sucesso da heurística de Eficiência sugere que, no roteamento de maximização de recompensa dinâmica, a razão entre recompensa e custo (eficiência) é um proxy superior para a geração de valor da frota em comparação com a otimização apenas pela recompensa bruta ou pelo tempo de viagem.
• Viabilidade Prática: As metaheurísticas, embora capazes de atingir tetos de qualidade de solução semelhantes, incorrem em tempos de planejamento que as tornam impraticáveis para o despacho em tempo real. Um ciclo de planejamento que leva minutos é descrito como "ativamente prejudicial" em operações ao vivo, pois o ambiente muda materialmente antes que uma solução seja produzida.
• Dominância de Pareto: As heurísticas de Eficiência estabelecem a dominância de Pareto na fronteira recompensa-computação, oferecendo desempenho próximo do ótimo com overhead computacional mínimo.

Os autores concluem que, para o despacho de frotas em tempo real, o design cuidadoso da função objetivo (especificamente a pontuação de densidade de recompensa) supera a complexidade algorítmica, tornando a heurística de Eficiência um candidato robusto para sistemas operacionais onde o tempo de planejamento é uma restrição limitante. O estudo reconhece as limitações relativas à natureza baseada em simulação dos experimentos e ao foco na receita como um objetivo único, observando que trabalhos futuros devem explorar restrições multiobjetivo e demanda não estacionária.