Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Este artigo propõe uma nova abordagem computacional para o problema de roteamento dinâmico de veículos que integra confirmação imediata de solicitações antecipadas com otimização contínua, utilizando aprendizado por reforço para maximizar o número de passageiros atendidos, conforme validado em dados reais de uma agência de transporte dos EUA.

O essencial

Imagine que você é o gerente de uma frota de vans de transporte compartilhado (como um Uber coletivo ou um ônibus sob demanda) que atende uma cidade. O seu trabalho é pegar passageiros em um lugar e levá-los a outro, mas com uma regra de ouro: você precisa dizer para o passageiro imediatamente se ele pode ir ou não.

Aqui está o resumo do que os autores deste artigo descobriram, explicado de forma simples:

O Problema: O Dilema do "Sim" ou "Não" Imediato

No mundo real, as pessoas querem planejar com antecedência. Elas pedem uma van para daqui a 2 horas. O problema é que, se você disser "sim" agora, você precisa ter certeza absoluta de que conseguirá cumprir essa promessa.

Existem duas formas antigas de fazer isso, e ambas têm defeitos:

1. O "Sim" Rápido, mas Rígido: Você olha o mapa, diz "sim" rápido, e trava o roteiro. É ótimo para o passageiro (ele sabe que vai), mas se aparecer um pedido melhor ou mais perto 10 minutos depois, você não pode mudar o roteiro para aproveitar essa oportunidade. Você perde eficiência.
2. O "Sim" Flexível, mas Incerto: Você diz "vamos ver", e fica mudando os roteiros o tempo todo para ficar o mais eficiente possível. O problema é que o passageiro fica ansioso: "Será que meu pedido foi aceito? Será que vou conseguir ir?". Isso é ruim para a experiência do usuário.

O que falta? Um sistema que diga "Sim" ou "Não" em menos de um segundo (para o passageiro ficar feliz), mas que, nos segundos seguintes, continue ajustando e melhorando os roteiros secretamente (para a empresa ganhar dinheiro e eficiência).

A Solução: O "Chef de Cozinha" e o "Garçom"

Os autores criaram um sistema inteligente que funciona como uma equipe de cozinha de um restaurante muito movimentado:

1. O Garçom (Confirmação Rápida):
   Quando um pedido chega, o "Garçom" olha rapidamente para a mesa e diz: "Sim, podemos atender" ou "Não, estamos cheios". Ele não pensa no futuro distante; ele apenas verifica se cabe no prato atual. Isso acontece em frações de segundo.

   • A mágica: Em vez de usar apenas regras simples, o Garçom usa uma "intuição treinada" (uma inteligência artificial) para saber se aceitar aquele pedido agora vai atrapalhar pedidos futuros.

2. O Chef (Otimização Contínua):
   Assim que o Garçom responde ao cliente, o "Chef" entra em ação. Enquanto o cliente espera o próximo pedido, o Chef pega o roteiro que o Garçom criou e começa a mexer nele. Ele troca passageiros de van, muda a ordem das paradas e otimiza o caminho para que, quando o próximo pedido chegar, a van esteja no lugar certo.

   • A mágica: O Chef usa um algoritmo chamado "Simulated Annealing" (que é como tentar várias combinações de ingredientes até achar a receita perfeita) e para assim que o próximo pedido chega. Ele é um "algoritmo de tempo livre" (anytime), ou seja, ele dá a melhor resposta possível no momento em que você o interrompe.

O Cérebro: Aprendendo com a Experiência (Reinforcement Learning)

Como o Garçom e o Chef sabem o que fazer? Eles não usam apenas regras fixas. Eles foram treinados por uma Inteligência Artificial que aprendeu jogando milhares de vezes.

Imagine um videogame onde o objetivo é atender o máximo de passageiros possível. A IA tentou milhões de vezes:

• "Se eu aceitar esse pedido agora, consigo atender 10 outros depois?"
• "Se eu recusar esse, posso atender 15?"

Com o tempo, a IA aprendeu uma "fórmula secreta" (chamada de função de valor) que diz: "Aceitar este pedido agora vale a pena porque, a longo prazo, vamos atender mais gente". Isso é chamado de não míope (não é de visão curta). Ela não olha só para o pedido de agora; ela olha para o dia todo.

Os Resultados: O Que Aconteceu na Vida Real?

Os autores testaram isso com dados reais de uma agência de transporte nos EUA e com dados de táxis de Nova York. O resultado foi impressionante:

• Velocidade: O sistema responde em menos de 1 segundo (o passageiro nem pisca).
• Eficiência: Eles conseguiram atender muito mais pedidos do que os sistemas atuais. Enquanto outros sistemas rejeitavam cerca de 5% a 10% dos pedidos, o novo sistema rejeitou apenas cerca de 1%.
• Equilíbrio: Eles conseguiram o "pulo do gato": o passageiro tem a segurança de uma confirmação imediata, e a empresa tem a eficiência de roteiros que continuam sendo melhorados o tempo todo.

Em Resumo

Pense nisso como um GPS inteligente para transporte coletivo. Antigamente, o GPS ou era muito rígido (não mudava nada) ou muito lento (demorava para confirmar). Este novo sistema é como ter um piloto automático que confirma sua viagem em um piscar de olhos, mas que, enquanto você dirige, já está calculando a rota perfeita para os próximos passageiros, garantindo que ninguém fique para trás e que o serviço seja o mais eficiente possível.

É uma vitória para o passageiro (que tem certeza do seu transporte) e para a empresa (que atende mais pessoas com os mesmos carros).

Resumo técnico

Resumo Técnico: Problema de Roteamento Dinâmico de Veículos com Confirmação Imediata de Solicitações Antecipadas

1. O Problema

O artigo aborda uma lacuna crítica no Problema de Roteamento Dinâmico de Veículos (DVRP) aplicado a serviços de transporte sob demanda (como microtrânsito e paratransito). O cenário envolve:

• Solicitações Antecipadas: Passageiros fazem pedidos com horas de antecedência (ex: 2 horas antes da coleta).
• Requisito de Confirmação Imediata: A agência de transporte precisa confirmar instantaneamente (aceitar ou rejeitar) se o pedido pode ser atendido, permitindo que o passageiro planeje sua viagem.
• Garantia de Serviço: Uma vez aceito, o pedido deve ser atendido conforme prometido (dentro das janelas de tempo).
• Otimização Contínua: Entre o recebimento de dois pedidos consecutivos, o sistema deve ter tempo para reotimizar as rotas para melhorar a eficiência futura.

O Dilema Atual:

• Abordagens existentes que fornecem confirmação rápida geralmente fixam as rotas imediatamente, perdendo a capacidade de otimização futura (soluções míopes).
• Abordagens que permitem otimização contínua frequentemente adiam a confirmação ou não conseguem garantir que todos os pedidos aceitos sejam atendidos, violando a confiança do usuário.

O objetivo é maximizar a taxa de serviço (número de pedidos atendidos) garantindo confirmações rápidas e permitindo reotimização contínua das rotas.

2. Metodologia

Os autores propõem uma abordagem computacional híbrida que integra três componentes principais:

A. Formulação como Processo de Decisão de Markov (MDP)
O problema é modelado como um MDP para lidar com a incerteza das futuras solicitações.

• Estado ($s_t$): Inclui locais dos veículos, passageiros a bordo, pedidos aceitos, planos de rota atuais e o novo pedido recebido.
• Ação ($a_t$): Decisão de aceitar/rejeitar o novo pedido e a geração de novos planos de rota para todos os veículos.
• Recompensa: 1 se o pedido for aceito, 0 caso contrário. O objetivo é maximizar a recompensa acumulada a longo prazo.

B. Algoritmo de Busca Rápida para Confirmação (Prompt Confirmation)
Para atender à necessidade de resposta em frações de segundo:

• Utiliza uma busca de inserção simples (Quick Insertion Search).
• O algoritmo tenta inserir o novo pedido nas rotas existentes sem alterar a ordem dos pedidos já aceitos ou a atribuição de veículos.
• Verifica viabilidade (janelas de tempo e capacidade) e seleciona a inserção que maximiza a função de valor aprendida.
• Complexidade: $O(|T_{aceito}|^2)$, mas na prática é extremamente rápida (fração de segundo).

C. Algoritmo "Anytime" para Otimização Contínua
Entre o recebimento de pedidos consecutivos, o sistema executa um algoritmo de otimização que pode ser interrompido a qualquer momento:

• Utiliza Simulated Annealing (Recozimento Simulado) como metaheurística.
• Opera sobre os planos de rota gerados pela confirmação inicial.
• Aplica operadores de mutação aleatória: Swap (troca de pedidos entre veículos), Move (mover pedido para outro veículo), Shift (mudar ordem dentro da rota) e Reverse (inverter ordem).
• Se o próximo pedido chegar, o algoritmo para e retorna a melhor solução viável encontrada até aquele momento.

D. Aprendizado por Reforço (RL) para Função Objetivo Não Miópica
O grande desafio é definir a função objetivo para o algoritmo de otimização. Maximizar apenas o serviço imediato é míope.

• Aprendizado: Os autores treinam uma função de valor de ação $Q(s, a)$ usando Aprendizado por Reforço (Q-Learning).
• Objetivo: A função $Q$ aprende a prever o valor de longo prazo de uma decisão, maximizando a chance de aceitar pedidos futuros e melhorando as rotas para o horizonte temporal.
• Pré-treinamento Supervisionado: Para acelerar o treinamento, o modelo é pré-treinado com uma política simples (aceitar sempre que possível e maximizar tempo ocioso) antes de ser refinado pelo RL.
• Arquitetura: Redes Neurais (MLP, KAN ou CNN) recebem vetores de características espaciais e temporais (ex: tempo ocioso total, disponibilidade temporal e espacial dos veículos) como entrada.

3. Principais Contribuições

1. Nova Formulação de Problema: Definição formal do DVRP com confirmação imediata e otimização contínua, um cenário real não coberto adequadamente pela literatura anterior.
2. Abordagem Híbrida: Integração de um algoritmo de busca rápida (para confirmação) com um algoritmo anytime (para otimização), resolvendo o conflito entre velocidade de resposta e qualidade da solução.
3. Função Objetivo Aprendida: Uso de RL para aprender uma função de valor não miópica que guia tanto a decisão de aceitação quanto a reotimização de rotas, superando heurísticas tradicionais.
4. Validação em Dados Reais: Avaliação utilizando um conjunto de dados real de microtrânsito de uma agência de transporte dos EUA, além do conjunto de dados de táxis de NYC.

4. Resultados Numéricos

Os experimentos compararam a abordagem proposta ($\pi^*$) com três baselines de ponta:

• Google OR-Tools: Solucionador de VRP state-of-the-art.
• Rolling Horizon (RH): Decomposição temporal com otimização completa a cada pedido.
• MC VRP: Busca baseada em Monte Carlo Tree Search.

Desempenho:

• Tempo de Confirmação: A abordagem proposta confirma pedidos em ~0,2 segundos (dados de microtrânsito) e ~1 segundo (dados de NYC), sendo adequada para tempo real. O RH, por exemplo, leva em média 50 segundos, o que é inviável para confirmação imediata.
• Taxa de Rejeição: A abordagem proposta reduziu a taxa de rejeição para cerca de 1% nos dados de microtrânsito, superando significativamente todas as baselines.
  • OR-Tools e RH tiveram taxas de rejeição muito mais altas (até 15-20% em alguns episódios).
  • A otimização contínua (Simulated Annealing) mostrou-se crucial: aumentar o tempo de execução do algoritmo anytime entre pedidos reduziu drasticamente a taxa de rejeição.
• Eficiência: O método proposto oferece o melhor compromisso (trade-off) entre tempo de confirmação e taxa de serviço.

5. Significado e Impacto

Este trabalho é fundamental para o desenvolvimento de serviços de microtrânsito sob demanda viáveis e confiáveis.

• Confiança do Usuário: Permite que passageiros reservem viagens com antecedência e recebam confirmação imediata, essencial para a adoção do serviço.
• Eficiência Operacional: Garante que as agências possam atender a maior quantidade possível de passageiros sem violar compromissos feitos, maximizando o uso da frota.
• Viabilidade Técnica: Demonstra que é possível combinar decisões em tempo real (subsegundos) com otimização complexa de longo prazo através de arquiteturas híbridas e aprendizado de máquina, superando as limitações de abordagens puramente heurísticas ou puramente baseadas em otimização matemática tradicional.

Em suma, o artigo apresenta uma solução computacional robusta que preenche a lacuna entre a necessidade de resposta imediata ao usuário e a necessidade de eficiência operacional a longo prazo em sistemas de transporte dinâmico.