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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Song Gao, (Autor:in) / Chabini, I. (Autor:in)


    Erscheinungsdatum :

    2002-01-01


    Format / Umfang :

    382918 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch