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
19.09.2021
361831 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
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
|