Optimal routing in time-varying, stochastic networks: Algorithms and implementations

Travel time between an origin and destination is often the primary criterion in optimally routing vehicles such as ambulances, police cars, and vehicles carrying hazardous substances. Travel times in congested transportation networks are inherently time-varying and stochastic in nature. In order to optimally route vehicles, both the randomness and time-varying nature of the travel times must be considered. A consequence of recognizing the uncertainty in the travel times is that there may be, for any origin-destination pair, more than one path which have some positive probability of being shortest. Such paths are called Pareto-optimal. This dissertation addresses the problem of determining "superior" paths in networks where the arc weights are random variables whose probability distribution functions vary with time. Two basic approaches are taken for solving this problem, (1) generate all Pareto-optimal paths, and (2) efficiently determine "superior" paths for more specific characterizations of the problem.;In this thesis, the methodological and conceptual framework for comparing the travel times of paths with stochastic, time-varying arc weights in order to determine Pareto-optimal paths are given. The design of the specific computational steps to generate the a priori Pareto-optimal least time paths, including the computation of the time-varying path travel time probability distribution functions, and the rationale for determining the range of path travel times are presented. Similarly, the derivation of the rationale and the design of the specific computational steps to find the a priori least expected time paths, absolute least time paths, and a lower bound on the expected time of the least expected time paths are presented. Modifications required for the calculation of least cost paths and for solving multiobjective problems of stochastic, time-varying attributes are presented. Extensions of these procedures for applications where drivers are permitted to react to revealed arrival times at intermediate nodes are given.;Extensive numerical experiments are conducted to assess the performance of these procedures. The procedures are tested on an actual transportation network, illustrating the utility of these procedures in determining paths for the transport of hazardous materials.