Uma abordagem de aprendizado por reforço profundo para o problema dinâmico assíncrono de despacho de veículos

Imagine que você gerencia uma frota de táxis em uma grande cidade. Requisições de corrida surgem em horários e locais imprevisíveis, e os motoristas ficam disponíveis sempre que terminam uma viagem. Toda vez que um desses eventos ocorre, você precisa decidir — agora mesmo — qual veículo atende qual requisição. Se esperar demais, os passageiros cancelam; se atribuir sem critério, você perde eficiência e qualidade de serviço.

Esse é o problema dinâmico de despacho de veículos (DVDP, do inglês dynamic vehicle dispatching problem): atribuir veículos a requisições que surgem de forma estocástica no tempo e no espaço. Ele aparece em serviços de táxi e de aplicativos de mobilidade, entrega de comida, transporte de cargas, mineração a céu aberto e sistemas de emergência, como patrulhamento policial e gestão de frotas de ambulâncias.

O DVDP é fundamentalmente diferente do roteamento clássico de veículos. Em problemas de roteamento, a demanda e os recursos são geralmente conhecidos de antemão, e o objetivo é calcular um plano ótimo (por exemplo, o melhor conjunto de rotas). No DVDP, um agente de controle precisa atribuir veículos a requisições em tempo real, com base no estado atual do sistema. Ele é mais bem compreendido como um problema de controle ótimo — exatamente o tipo de cenário em que o aprendizado por reforço se destaca.

Despacho síncrono vs. assíncrono

O despacho dinâmico pode ser feito em dois modos:

• Modo síncrono: as atribuições ocorrem em intervalos de tempo fixos. A cada época de decisão, um agente central reúne todas as requisições pendentes e os veículos disponíveis e resolve um problema combinatório de emparelhamento (tipicamente um problema de designação linear).
• Modo assíncrono: o despacho é disparado imediatamente sempre que uma requisição chega ou um veículo fica ocioso. Não é preciso esperar pelo próximo ciclo de decisão.

A maior parte da literatura estuda o modo síncrono, mas o modo assíncrono tem vantagens práticas reais. No patrulhamento policial ou na gestão de ambulâncias, esperar a formação de um “lote” de ocorrências é socialmente inaceitável — um veículo precisa partir o mais rápido possível. O despacho assíncrono também permite uma tomada de decisão distribuída, em vez de centralizada, e reduz drasticamente o espaço de decisão: em vez de escolher entre todos os emparelhamentos possíveis (uma explosão combinatória), o agente precisa apenas escolher um único veículo para uma requisição, ou uma única requisição para um veículo.

Apesar dessas vantagens, o DVDP assíncrono permanece amplamente inexplorado. Este post resume nossa abordagem para formulá-lo e resolvê-lo.

Formulando o problema como um processo de decisão semi-Markoviano

A característica definidora do DVDP assíncrono é que as épocas de decisão ocorrem em instantes aleatórios em tempo contínuo. Dois eventos disparam uma decisão:

• um evento de “nova chamada”, quando uma nova requisição é comunicada ao agente, e
• um evento de “veículo livre”, quando um veículo termina de atender uma requisição.

Como esses eventos ocorrem de forma estocástica, os intervalos de tempo entre decisões sucessivas são, eles próprios, aleatórios. É exatamente isso que um processo de decisão semi-Markoviano (SMDP, do inglês semi-Markov decision process) captura — uma generalização do processo de decisão de Markov (MDP) que permite que as épocas de decisão sejam separadas por intervalos de tempo aleatórios.

Outra característica-chave é que o conjunto de decisões viáveis $\mathcal{A}(s)$ depende de qual evento foi disparado:

• Em um evento de veículo livre, o agente escolhe qual requisição em espera será atribuída ao veículo que acabou de ficar disponível. O tamanho de $\mathcal{A}(s)$ cresce linearmente com o número de requisições pendentes (e é vazio se nenhuma estiver aguardando).
• Em um evento de nova chamada, o agente escolhe qual veículo livre será atribuído à requisição que está chegando. O tamanho de $\mathcal{A}(s)$ cresce linearmente com o número de veículos livres (e é vazio se nenhum estiver disponível).

Buscamos uma política $\pi$ que maximize o valor esperado do fluxo de recompensas descontadas em um horizonte infinito:

$$ v^\star(s) = \max_{\pi \in \Pi} \lim_{N \to \infty} \mathbb{E} \Bigg[ \sum_{k=0}^{N-1} \int_{T_{k}}^{T_{k+1}} e^{-\beta t} r(S_k, \pi(S_k)) dt \Bigg| S_0 = s \Bigg], \quad \forall s \in \mathcal{S} $$

Note que a recompensa é integrada sobre os intervalos aleatórios entre as épocas de decisão $T_k$ e $T_{k+1}$, e que $e^{-\beta t}$ é o análogo em tempo contínuo do usual fator de desconto discreto $\gamma$ (com $e^{-\beta} = \gamma$). A equação de Bellman correspondente para o SMDP descontado é:

$$ v^\star(s) = \max_{a \in \mathcal{A}(s)} \Big\lbrace \bar{r}(s,a) + \mathbb{E}\big[e^{-\beta \tau} v^\star(S’)\big] \Big\rbrace, \quad \forall s \in \mathcal{S} $$

em que $\bar{r}(s,a)$ é a recompensa esperada acumulada entre duas épocas de decisão consecutivas. A única diferença real em relação à equação de Bellman do MDP comum é o intervalo aleatório $\tau$ que aparece no termo de desconto.

Por que não resolver de forma exata? A programação dinâmica exata (iteração de valor ou de política) exige a enumeração de todo o espaço de estados. Mas um estado precisa, no mínimo, codificar as localizações de cada veículo e de cada requisição — de modo que o espaço de estados cresce exponencialmente com o tamanho da frota e da demanda. Além disso, a dinâmica complexa torna impossível escrever uma expressão fechada para as probabilidades de transição. Métodos exatos são inviáveis para instâncias realistas, o que motiva uma abordagem de simulação combinada com aprendizado.

O caso síncrono como um caso particular

O despacho síncrono pode ser visto como um SMDP restrito, no qual as épocas de decisão são forçadas a ocorrer em intervalos fixos — ou seja, um MDP comum. Sua equação de Bellman é simplesmente

$$ v^\star(s) = \max_{a \in \mathcal{A}(s)} \Big\lbrace r(s, a) + \gamma \mathbb{E}[v^\star(s’)] \Big\rbrace, \quad \forall s \in \mathcal{S}. $$

O detalhe está no conjunto de ações: no modo síncrono, $\mathcal{A}(s)$ contém todos os emparelhamentos viáveis entre veículos e requisições, de modo que escolher a melhor ação significa resolver um programa não linear inteiro a cada passo. Para tornar isso tratável, os autores na literatura geralmente relaxam a função Q global em uma soma de termos por par $\tilde{q}_{ij}$ e resolvem, em vez disso, um problema de alocação linear:

$$ \begin{align} \max \quad & \sum_{i=1}^n \sum_{j=1}^n \tilde{q}_{ij}, x_{ij} \\ \text{s.a.} \quad & \sum_{j=1}^n x_{ij} = 1, \quad i \in \mathcal{I} \\ & \sum_{i=1}^n x_{ij} = 1, \quad j \in \mathcal{J} \\ & x_{ij} \in {0,1}, \quad (i,j) \in \mathcal{I} \times \mathcal{J} \end{align} $$

Esse relaxamento torna o cálculo tratável, mas decompõe o valor global em contribuições independentes de cada par motorista–requisição, ignorando suas interações e produzindo decisões sob uma perspectiva individual, e não global. Os intervalos fixos também acrescentam latência: um passageiro rejeitado em um ciclo precisa esperar pelo próximo. O despacho assíncrono contorna ambos os problemas: um novo veículo pode ser proposto no instante em que uma rejeição acontece.

Nossa solução: RL profundo + simulação de eventos discretos

Como a maioria dos métodos modernos de RL, trabalhamos com funções Q (funções de valor-ação). A função Q ótima satisfaz a equação de Bellman do SMDP

$$ q^\star(s,a) = \bar{r}(s,a) + \mathbb{E}\Big[ e^{-\beta \tau} \max_{a’ \in \mathcal{A}(s’)} q^\star(s’,a’)\Big] $$

e, uma vez conhecida, uma política ótima é obtida agindo de forma gulosa:

$$\pi^\star(s) \in \arg\max_{a \in \mathcal{A}(s)} q^\star(s,a).$$

A vantagem das funções Q é que elas são livres de modelo — não precisamos de um modelo probabilístico explícito da dinâmica do ambiente para agir.

Dois agentes especializados

Inicialmente tentamos um único agente lidando com os dois tipos de evento, mas o treinamento foi instável. Dividir o problema em dois agentes especializados funcionou muito melhor:

• o NewCallAgent, que atua nos eventos de nova chamada (sob a perspectiva dos passageiros), e
• o FreeVehicleAgent, que atua nos eventos de veículo livre (sob a perspectiva dos motoristas).

Cada agente se concentra em seu próprio espaço de decisão e aprende decisões melhores para o seu lado do problema.

Como o espaço de estados é enorme, usamos redes neurais como aproximadores de função para a função Q. Sempre que um evento de decisão ocorre durante a simulação, o agente correspondente constrói um vetor de características $\phi(s,a)$ para cada ação viável, o passa por sua rede para obter $\hat{q}(s,a)$ e escolhe a ação com o maior valor Q estimado. Como o conjunto de ações cresce apenas linearmente, avaliar todos os candidatos é rápido — bem dentro do orçamento de tempo de um sistema online.

Aprendendo com experiência simulada

Trajetórias de amostra são geradas por um simulador de eventos discretos. À medida que a simulação avança, cada transição é armazenada em um buffer de experiência como uma tupla

$$ (s, a, r, s’, \tau) $$

em que $s$ é o estado atual, $a$ a decisão, $r$ a recompensa, $s'$ o próximo estado e $\tau$ o tempo de transição realizado. Treinamos as redes com o algoritmo double deep Q-learning, que usa duas redes (A e B) para reduzir o viés de superestimação do Q-learning padrão. Dada uma transição amostrada, a rede A é atualizada em direção ao alvo

$$ Y^{\text{DoubleQ}} = r + e^{-\beta \tau} q\Bigg(s’, \arg\max_{a’ \in \mathcal{A}(s’)} q(s’, a’; \boldsymbol{\theta}^{\text{A}}_t);\ \boldsymbol{\theta}^{\text{B}}_t\Bigg) $$

com a rede B atualizada de forma simétrica. O aprendizado começa assim que o buffer acumula transições iniciais suficientes (coletadas sob uma política aleatória), e ambos os agentes são treinados simultaneamente à medida que a simulação avança.

Estudo de caso: gestão de frota de táxis na cidade de Nova York

Validamos a abordagem em um cenário realista de gestão de frota de táxis usando os registros de viagens da New York City Taxi and Limousine Commission. Restringimos o estudo às viagens dentro do distrito do Brooklyn realizadas via Uber ou Lyft, usando os dados de janeiro de 2022 para treinamento e os dados de fevereiro de 2022 — completamente isolados para evitar vazamento de dados — para teste. Todas as distâncias usaram a métrica de Manhattan (L1).

O simulador de eventos discretos, do tipo orientado por rastros (trace-driven), foi construído com o SimPy . Para aumentar o realismo, modelamos as rejeições de atribuição: a probabilidade de rejeição de cada motorista é amostrada de uma distribuição beta, e a tolerância de espera de cada passageiro, de uma distribuição gama (de modo que requisições que esperam tempo demais acabam canceladas).

Características de estado e ação

Cada par estado–ação $(s,a)$ é mapeado para um vetor de características $\phi(s,a)$ que combina informações sobre o veículo, a requisição e o contexto mais amplo:

Índice	Tipo	Descrição da característica
1	veículo	Coordenadas (x, y) da localização atual do veículo
2	veículo	Coordenadas (x, y) do destino do veículo
3	veículo	Tempo para concluir o serviço atual
4	veículo	Probabilidade de cancelamento
5	veículo	Situação do veículo (ocupado ou ocioso)
6	requisição	Coordenadas (x, y) da origem da requisição
7	requisição	Coordenadas (x, y) do destino da requisição
8	requisição	Instante em que a requisição chegou ao sistema
9	contexto	Razão nº de veículos / nº de requisições nos últimos 15 minutos
10	contexto	Característica cíclica da semana: $\sin(2\pi, m / 10080)$
11	contexto	Característica cíclica da semana: $\cos(2\pi, m / 10080)$

Aqui, $m$ é o minuto dentro da semana (10080 minutos = 1 semana), de modo que as características cíclicas permitem ao modelo capturar padrões semanais de demanda.

Projetando a função de recompensa

Acertar a recompensa foi crucial. Recompensar apenas tempos de espera curtos saiu pela culatra: os agentes aprenderam a atender as requisições mais recentes e deixaram as antigas definharem até o cancelamento. Nossa recompensa final parte de um termo proporcional à duração da corrida, mais um bônus fixo:

$$ r_d = t_d + b $$

em que $t_d$ é o tempo estimado de viagem da origem ao destino. Corridas mais longas são mais desejáveis (maiores ganhos), enquanto a constante $b$ atua como uma recompensa fixa por corrida que incentiva maiores taxas de atendimento. Ajustar $b$ equilibra “muitas corridas curtas” contra “poucas corridas longas”. Por fim, como o tempo total de serviço $t_s$ é aleatório, descontamos a recompensa ao longo dessa duração:

$$ r = \dfrac{r_d}{t_s} + \gamma \dfrac{r_d}{t_s} + \cdots + \gamma^{t_s-1} \dfrac{r_d}{t_s} = \dfrac{r_d(\gamma^{t_s} - 1)}{t_s(\gamma - 1)} $$

de modo que atribuições com a mesma recompensa imediata, mas com durações diferentes, sejam valoradas de forma distinta.

Resultados

Comparamos a política aprendida (rotulada como DQN) com quatro heurísticas assíncronas — Vizinho Mais Próximo (NN, do inglês Nearest Neighbor), Primeiro a Entrar, Primeiro a Sair (FIFO), Último a Entrar, Primeiro a Sair (LIFO) e Aleatória — e com duas políticas síncronas em lote (batch) que resolvem um problema de designação linear a cada 15 segundos com o algoritmo de Jonker–Volgenant:

• BWO — lote sem o tempo de espera prévio (minimiza apenas o tempo de deslocamento do veículo até a origem), e
• BW — lote com o tempo de espera prévio (minimiza espera + deslocamento).

Avaliamos quatro regimes de oferta em relação à demanda — “muito fácil”, “fácil”, “médio” e “difícil” — correspondentes a razões frota/demanda de 3%, 2%, 1% e 0,5%. Três métricas foram acompanhadas: atraso médio (tempo entre a requisição e o embarque), taxa de cancelamento e tempo total de serviço (uma proxy para a receita dos motoristas).

Atraso médio. Entre as políticas assíncronas, a DQN reduziu o atraso médio em 50,6% em relação à segunda melhor (NN) no cenário difícil. A política síncrona BW alcançou o menor atraso geral (3,4 min contra 6,49 min da DQN no cenário difícil), graças à sua estratégia de “esperar para ver” — mas, como veremos, isso tem um custo.

Taxa de cancelamento. Nos cenários difícil e médio, a DQN obteve a menor taxa de cancelamento entre todas as políticas — uma redução de 18,4% em relação à segunda melhor (BWO) no cenário difícil. Como as políticas assíncronas atribuem veículos o mais rápido possível, elas evitam os cancelamentos induzidos pela estratégia de espera das políticas em lote. Isso revela um verdadeiro compromisso (trade-off): a BW vence em atraso, mas favorece requisições com pouco tempo de espera, deixando as demais aguardando até que cancelem.

Tempo total de serviço. As políticas DQN e BWO entregaram os maiores tempos totais de serviço (receita dos motoristas) no cenário difícil, sem diferença estatisticamente significativa entre elas; as diferenças foram desprezíveis nos cenários mais fáceis.

Por fim, a política DQN mantém o menor conjunto de requisições em espera durante a maior parte do dia, especialmente nos horários de pico — uma consequência direta de sua natureza de atribuir o mais rápido possível.

De modo geral, a política assíncrona baseada em aprendizado (DQN) atinge um equilíbrio eficaz entre eficiência e confiabilidade do serviço, com desempenho especialmente bom nos cenários com recursos escassos, que são os que mais importam na prática.

Conclusão

Neste trabalho, formulamos o problema assíncrono dinâmico de despacho de veículos como um processo de decisão semi-Markoviano e o resolvemos combinando simulação de eventos discretos com aprendizado por reforço profundo, usando dois agentes especializados treinados via double deep Q-learning. Com dados reais de táxis de Nova York, a política aprendida alcançou até 50,6% de redução no atraso médio dos passageiros e 18,4% de redução nas taxas de cancelamento em comparação com outras políticas assíncronas, mantendo tempos totais de serviço comparáveis.

O arcabouço fornece uma base escalável e adaptável para a gestão de frotas em tempo real em ambientes estocásticos e dinâmicos. Direções futuras incluem cenários multiagente, a integração de previsão de demanda e a melhoria da transferibilidade de políticas entre diferentes contextos operacionais.

Este estudo foi financiado em parte pelo Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq; Processo nº 407466/2021-5) e pela NVIDIA Corporation por meio do Programa GPU Grant.

Referências

[1] Cordeiro, F. E. A.; Pitombeira-Neto, A. R. A deep reinforcement learning approach for the asynchronous dynamic vehicle dispatching problem. Artificial Intelligence for Transportation, 3–4, 100038, 2025. https://doi.org/10.1016/j.ait.2025.100038

[2] Powell, W. B. A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers. Transportation Science, 30(3), 195–219, 1996.

[3] Xu, Z. et al. Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. Proceedings of the 24th ACM SIGKDD, 2018.

[4] Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.

[5] van Hasselt, H.; Guez, A.; Silver, D. Deep reinforcement learning with double Q-learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2016.

Como citar este artigo

Cordeiro, F. E. A., & Pitombeira-Neto, A. R. (2025). A deep reinforcement learning approach for the asynchronous dynamic vehicle dispatching problem. Artificial Intelligence for Transportation, 3–4, 100038. https://doi.org/10.1016/j.ait.2025.100038

@article{cordeiro2025deep,
  title     = {A deep reinforcement learning approach for the asynchronous dynamic vehicle dispatching problem},
  author    = {Cordeiro, Francisco Edyvalberty A. and Pitombeira-Neto, Anselmo R.},
  journal   = {Artificial Intelligence for Transportation},
  volume    = {3--4},
  pages     = {100038},
  year      = {2025},
  issn      = {3050-8606},
  doi       = {10.1016/j.ait.2025.100038},
  publisher = {Elsevier}
}