Time constrained shortest paths in stochastic and dynamic transportation networks

This thesis develops methodologies for solving constrained shortest path problems in dynamic and random conditions. Due to the randomness of the network, the decisions need to account for uncertainty of the future real-time network state. Currently the randomness of the arc attributes is not taken into consideration. In this thesis, the intent is to develop methodologies for finding best paths when the arc attributes are uncertain, and change with time. Modified label correcting algorithms are developed for several new variations of the constrained stochastic dynamic shortest path problem where the objective is to minimize the expected cost subject to a specified constraint on the travel time of the path. The constraint can be placed on the expected travel time of the path, or on the cumulative probability of experiencing a maximum travel time. Unlike deterministic networks, in which a single minimum cost path can be determined between an origin and a destination, several paths may each have some positive probability of having the least cost for some realization of the network when the arc times and costs are stochastic and thus, a set of Pareto-optimal paths can be generated. Multiple variations are also examined when considering the FIFO nature of travel times in the network. The correctness of the proposed algorithms is proved. Extensive numerical experiments are conducted to access the performance of these procedures. Also some of the instances are discussed where this problem has practical significanceCivil, Architectural, and Environmental Engineerin