Dynamic UAV-based traffic monitoring under uncertainty as a stochastic arc-inventory routing policy

Research output: Contribution to journalArticle

Abstract

Given the rapid advances in unmanned aerial vehicles, or drones, and increasing need to monitor at a city level, one of the current research gaps is how to systematically deploy drones over multiple periods. We propose a real-time data-driven approach: we formulate the first deterministic arc-inventory routing problem and derive its stochastic dynamic policy. The policy is expected to be of greatest value in scenarios where uncertainty is highest and costliest, such as city monitoring during major events. The Bellman equation for an approximation of the proposed inventory routing policy is formulated as a selective vehicle routing problem. We propose an approximate dynamic programming algorithm based on Least Squares Monte Carlo simulation to find that policy. The algorithm has been modified so that the least squares dependent variable is defined to be the “expected stock out cost upon the next replenishment”. The new algorithm is tested on 30 simulated instances of real time trajectories over 5 time periods of the selective vehicle routing problem to evaluate the proposed policy and algorithm. Computational results on the selected instances show that the algorithm on average outperforms the myopic policy by 23–28%, depending on the parametric design. Further tests are conducted on classic benchmark arc routing problem instances. The 11-link instance gdb19 (Golden et al., 1983) is expanded into a sequential 15-period stochastic dynamic example and used to demonstrate why a naïve static multi-period deployment plan would not be effective in real networks.

Original languageEnglish (US)
Pages (from-to)167-185
Number of pages19
JournalInternational Journal of Transportation Science and Technology
Volume5
Issue number3
DOIs
StatePublished - Oct 2016

Keywords

  • Approximate dynamic programming
  • Capacitated arc routing problem
  • Inventory routing problem
  • Traffic monitoring
  • Unmanned aerial vehicle

ASJC Scopus subject areas

  • Transportation
  • Automotive Engineering
  • Civil and Structural Engineering
  • Management, Monitoring, Policy and Law

Fingerprint Dive into the research topics of 'Dynamic UAV-based traffic monitoring under uncertainty as a stochastic arc-inventory routing policy'. Together they form a unique fingerprint.

  • Cite this