The best routing policy problem in stochastic and time-dependent networks is the subject of this study. This problem can be viewed as a counterpart of the shortest-path problem in deterministic networks. A stochastic time-dependent network is one in which the link travel times are random variables with time-dependent distributions. A routing policy is a decision rule that specifies what node to take next at each decision node on the basis of the realized link travel times and the current time. The framework of the problem is reviewed, on which basis one of the variants of the problem that are pertinent to the traffic context is studied. An exact algorithm to this variant is given, and its complexity is analyzed. Since the running time of the exact algorithm is generally exponential in the number of arcs, the importance of finding good approximations to the exact algorithm is pointed out. Several approximations are presented, and their effectiveness against the exact algorithm is studied both theoretically and computationally.
Abstract