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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Optimal Routing in Stochastic Networks with Reliability Guarantees


    Contributors:


    Publication date :

    2021-09-19


    Size :

    361831 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Sampling Policy that Guarantees Reliability of Optimal Policy in Reinforcement Learning

    Senda, K. / Iwasaki, Y. / Fujii, S. | British Library Online Contents | 2010


    Combinatorial Approach for Geographic Routing with Delivery Guarantees

    Samarasinghe, Kasun / Leone, Pierre | BASE | 2014

    Free access

    Combinatorial Approach for Geographic Routing with Delivery Guarantees

    Samarasinghe, Kasun / Leone, Pierre | BASE | 2014

    Free access


    Optimal Routing of Hazardous Materials in Stochastic, Time-Varying Transportation Networks

    Miller-Hooks, E. / Mahmassani, H. S. / National Research Council; Transportation Research Board | British Library Conference Proceedings | 1998