Routing and Traffic Assignment in Stochastic Networks

Existing studies have revealed the significant influence of travel time reliability on travel decisions. With the information about travel time reliability, an individual traveler can better arrange his/her travel according to trip purpose and risk preference. Accordingly, transportation planning agencies should anticipate the impact of such behavior on the planning, management and operation of transportation systems. Therefore, the primary purpose of this thesis is to facilitate travel reliability sensitive decision making by introducing reliability analysis models.;Travel time reliability can be defined in various ways. This thesis first defines travel time reliability as "on-time arrival probability", i.e., the probability that a traveler arrives at the destination within a planned travel time. This definition gives rise to the reliable a priori shortest path (RASP) problem, which aims to find a priori paths that are the shortest to ensure a specified probability of on-time arrival. We show that the RASP problem can be formulated as a problem of finding all non-dominated paths by the first order stochastic dominance. Although a non-dominated path may not be shortest under any on-time arrival probability, the reliable shortest paths are always included in the set of non-dominated paths.;The path travel time distribution is obtained by convolving link travel time distributions. To simplify this calculation, the distributions of travel times are discretized. Several discretization schemes and the corresponding convolution methods are proposed including those based discrete Fourier transform (DFT). A label-correcting algorithms are designed to solve the problem. Numerical examples are conducted to compare these discretization and convolution methods and a best one is identified. The numerical examples also demonstrate the utility of the RASP model and feasibility of the proposed solution algorithm. The RASP model has been solved on a regional transportation network with over 44,000 links.;We also study the RASP problem in travel-time temporally and spatially dependent network, in which travel time conditions are restricted to adjacent links through a Markovian process. The probability distribution of link travel time is also allowed to vary over time, which provides a mechanism to account for the dynamic network behavior such as congestion effects caused by rush hour traffic.;The reliable shortest paths solved under the first order stochastic dominance may not properly capture heterogeneous risk-taking behavior. To address this important issue, we extend the RASP model to incorporate higher order stochastic dominance, which captures travelers' risk-taking behavior without requiring the knowledge of their specific utility functions. In particular, a general approach to modeling heterogeneous risk-taking behavior in route choice is proposed based on the theory of stochastic dominance (SD). This approach offers not only an interpretation of risk-taking behavior consistent with the SD theory for a variety of existing route choice models, but also a unified and computationally viable solution approach through SD-admissible path sets, which are usually small and can be generated without having to enumerate all paths.;One important utility of the proposed routing problem is for solving reliability-based traffic assignment problem, which offers a base for reliability-sensitive planning decisions and network design. In this new assignment model, travelers are assumed to choose paths to minimize the travel time budget that ensures their desired probability of on-time arrival, i.e., the percentile path travel time. Therefore, they drive the system to a percentile user equilibrium (UE) where no traveler can reduce their time budget by unilaterally changing route. This thesis is focused on developing and testing a heuristic algorithm for the percentile UE problem. The algorithm is based on a column generation scheme which is implemented by solving a RASP problem.