Non-Myopic Adaptive Route Planning in Uncertain Congestion Environments

Siyuan Liu, Yisong Yue, Ramayya Krishnan

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian process dynamic congestion model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop efficient algorithms for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability to efficiently reason about the long-term value of exploration, which enables collectively balancing the exploration/exploitation trade-off for entire fleets of vehicles. Our approach is validated by traffic data from two large Asian cities. Our congestion model is shown to be effective in modeling dynamic congestion conditions. Our routing algorithms also generate significantly faster routes compared to standard baselines, and achieve near-optimal performance compared to an omniscient routing algorithm. We also present the results from a preliminary field study, which showcases the efficacy of our approach.

Original languageEnglish (US)
Article number7056447
Pages (from-to)2438-2451
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume27
Issue number9
DOIs
StatePublished - Sep 1 2015

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Non-Myopic Adaptive Route Planning in Uncertain Congestion Environments'. Together they form a unique fingerprint.

Cite this