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.
Optimal Routing in Stochastic Networks with Reliability Guarantees
2021-09-19
361831 byte
Conference paper
Electronic Resource
English
Sampling Policy that Guarantees Reliability of Optimal Policy in Reinforcement Learning
British Library Online Contents | 2010
|Optimal routing policy problems in stochastic time-dependent networks
Online Contents | 2006
|Optimal Routing of Hazardous Materials in Stochastic, Time-Varying Transportation Networks
British Library Conference Proceedings | 1998
|