AbstractWe study optimal routing policy problems in stochastic time-dependent networks, where link travel times are modeled as random variables with time-dependent distributions. These are fundamental network optimization problems for a wide variety of applications, such as transportation and telecommunication systems. The routing problems studied can be viewed as counterparts of shortest path problems in deterministic networks. A routing policy is defined as a decision rule that specifies what node to take next at each decision node based on realized link travel times and the current time. We establish a framework for optimal routing policy problems in stochastic time-dependent networks, which we believe is the first in the literature. We give a comprehensive taxonomy and an in-depth discussion of variants of the problem. We then study in detail one variant that is particularly pertinent in traffic networks, where both link-wise and time-wise stochastic dependencies of link travel times are considered and online information is represented. We give an exact algorithm to this variant, analyze its complexity and point out the importance of finding good approximations to the exact solution. We then overview several approximations, and present a summary of a theoretical and computational analysis of their effectiveness against the exact algorithm.


    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


    Contributors:
    Gao, Song (author) / Chabini, Ismail (author)

    Published in:

    Publication date :

    2005-02-07


    Size :

    30 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English