Real-time vehicle routing and scheduling in dynamic and stochastic traffic networks

Central to both in-vehicle route guidance systems (RGS) and automated vehicle dispatching systems (AVDS) is the vehicle routing and scheduling component which is required to find "optimal" routes and schedules in real-time for individual RGS-equipped vehicles and AVDS fleet vehicles in urban traffic networks. This thesis is motivated by the realization of the potential importance of explicitly considering the dynamic and stochastic nature of travel times within the vehicle routing and scheduling procedures in both RGS and AVDS and the need to develop efficient routing algorithms that can operate successfully in real time.;The dynamic and stochastic nature of the link travel time under three typical traffic conditions in urban traffic networks are first investigated through various theoretical and statistical procedures. The shortest path problem (SPP) with dynamic and stochastic link travel time and the dial-a-ride problem (DARP) with dynamic and stochastic O-D travel time are formulated and their respective solution algorithms are developed. These models and algorithms are then used to analyze the influences of the uncertainties of the travel times on the routing and scheduling results. The techniques from the artificial intelligent field (AI), including heuristic search strategies and artificial neural networks (ANN), are applied in vehicle routing and travel time estimation procedures to improve the computational efficiency of the routing and scheduling algorithms for real-time operation purposes.;The theoretical and computational analyses indicates that the consideration of the dynamic and stochastic nature of travel times in the SPP will result in different "optimal" paths as compared to a deterministic model. lt is found that the dynamic and stochastic nature of travel times has a significant effect on the routing and scheduling results of the DARP. The heuristic routing and scheduling algorithms developed in this thesis are extensively tested and evaluated using an actual network from the City of Edmonton, Alberta and the results indicate that these algorithms are applicable in real-time operation systems such as RGS and AVDS.