Multiple path-based vehicle routing in dynamic and stochastic transportation networks

One of the central tenets of in-vehicle route guidance system (RGS) is that each driver has a number of alternative routes she may choose for the journey to her destination. The motivation of this dissertation is the need to identify an “optimal route” based on drivers' multiple route choice criteria rather than simply using a traditional shortest path algorithms based on a single criterion. The basic notion of the proposed approach is that obtaining a mathematical representation of the driver's utility function is theoretically difficult and impractical, and identifying the optimal path using a realistic multiple attribute nonlinear utility function is a NP-hard problem. Consequently, a heuristic two-stage strategy which identifies multiple reasonable routes and then selects the “near- optimal path” may be effective and practical.; A piecewise additive linear utility function is used to approximate the nonlinear utility function. A relaxation based pruning technique based on an entropy model is utilized to focus the search of the nondominated paths on areas that meet drivers' generic and context-dependent preferences. In addition, to make sure that routes are dissimilar in terms of links used, route similarity is limited. Two k reasonable path algorithms are developed for this step. In order to evaluate the k reasonable routes, a fuzzy logic-based multiple objective route choice model is proposed which can explicitly take into account crisp values, fuzzy numbers, and linguistic variables which are common phenomenon in a real-time vehicle routing environment. To reflect the dynamic and stochastic nature of the traffic network, link travel time reliability or forecasting error and link travel time variance are also modeled as independent attributes. For forecasting multiple-periods link travel times, modular and spectral basis neural network models are proposed and validated with actual freeway link travel times from Houston, Texas.; The proposed strategy was tested on a traffic network from Austin, Texas under various traffic conditions. When multiple attributes were considered, an alternative path to the fastest path was found to be the best path for a significant number of O-D pairs. This difference between the best and fastest paths was found to increase as the level of congestion and O-D distance increased.