Monitoramento de tráfego dinâmico baseado em UAV sob incerteza como uma política estocástica de roteamento de inventário de arco

Diante dos rápidos avanços em veículos aéreos não tripulados, ou drones, e da crescente necessidade de monitoramento em nível de cidade, uma das lacunas atuais na pesquisa é como implantar sistematicamente drones ao longo de múltiplos períodos. Propomos uma abordagem baseada em dados em tempo real: formulamos o primeiro problema de roteamento de inventário de arco determinístico e derivamos sua política dinâmica estocástica. Espera-se que a política tenha maior valor em cenários onde a incerteza é mais alta e mais onerosa, como o monitoramento da cidade durante grandes eventos. A equação de Bellman para uma aproximação da política de roteamento de inventário proposta é formulada como um problema de roteamento de veículos seletivos. Propomos um algoritmo de programação dinâmica aproximada baseado na simulação de Monte Carlo de Mínimos Quadrados para encontrar essa política. O algoritmo foi modificado para que a variável dependente de mínimos quadrados seja definida como o “custo esperado de falta de estoque na próxima reposição”. O novo algoritmo é testado em 30 instâncias simuladas de trajetórias em tempo real ao longo de 5 períodos de tempo do problema de roteamento de veículos seletivos para avaliar a política e o algoritmo propostos. Resultados computacionais nas instâncias selecionadas mostram que o algoritmo, em média, supera a política míope em 23–28%, dependendo do desenho paramétrico. Testes adicionais são realizados em instâncias clássicas de problemas de roteamento de arco de referência. A instância de 11 links gdb19 (Golden et al., 1983) é expandida em um exemplo dinâmico estocástico sequencial de 15 períodos e usada para demonstrar por que um plano de implantação estática de múltiplos períodos ingênuo não seria eficaz em redes reais.