Optimal Routing in Stochastic Networks with Reliability Guarantees

Wanzheng Zheng, Pranay Thangeda, Yagiz Savas, Melkior Ornik

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Optimal routing in highly congested street networks where the travel times are often stochastic is a challenging problem with significant practical interest. While most approaches to this problem use minimizing the expected travel time as the sole objective, such a solution is not always desired, especially when the variance of travel time is high. In this work, we pose the problem of finding a routing policy that minimizes the expected travel time under the hard constraint of retaining a specified probability of on-time arrival. Our approach to this problem models the stochastic travel time on each segment in the road network as a discrete random variable, thus translating the model of interest into a Markov decision process. Such a setting enables us to interpret the problem as a linear program. Our work also includes a case study on the street of Manhattan, New York where we constructed the model of travel times using real-world data, and employed our approach to generate optimal routing policies.

Original languageEnglish (US)
Title of host publication2021 IEEE International Intelligent Transportation Systems Conference, ITSC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3521-3526
Number of pages6
ISBN (Electronic)9781728191423
DOIs
StatePublished - Sep 19 2021
Externally publishedYes
Event2021 IEEE International Intelligent Transportation Systems Conference, ITSC 2021 - Indianapolis, United States
Duration: Sep 19 2021Sep 22 2021

Publication series

NameIEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC
Volume2021-September

Conference

Conference2021 IEEE International Intelligent Transportation Systems Conference, ITSC 2021
Country/TerritoryUnited States
CityIndianapolis
Period9/19/219/22/21

ASJC Scopus subject areas

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Optimal Routing in Stochastic Networks with Reliability Guarantees'. Together they form a unique fingerprint.

Cite this