We study a specific variant of the optimal routing policy problem in stochastic time-dependent networks where expected general travel costs are optimized. A stochastic time-dependent network is a network where the link travel times and the link travel costs are random variables with time-dependent distributions. A routing policy is defined as a decision rule that specifics what node to take next at each decision node based on the realized link travel times, the realized link travel costs and the current time. We assume the network users have perfect online travel time information and no travel cost information, implying that they have knowledge about all link travel time realizations up to the current time, but have no knowledge about any link travel cost realizations. An exact algorithm is designed, based on a specification of the generic optimality conditions presented in part I of this study. We then analyze the complexity of the exact algorithm and point out the importance of finding effective and efficient approximations to the exact algorithm. We proceed to present four approximations, and study their effectiveness against the exact algorithm theoretically.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Optimal routing policy problems in stochastic time-dependent networks. II. Exact and approximation algorithms


    Contributors:
    Song Gao, (author) / Chabini, I. (author)


    Publication date :

    2002-01-01


    Size :

    382918 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English