Revealed Path Choice Behavior and Network Pruning for Efficient Path Finding

This dissertation addresses two separate problems related to transportation networks. In the first part, route choice behavior revealed from real world trips is studied. In part two, efficient pruning of large transportation networks for expediting one-to-one path search is studied.;Part I:.;Route-choice behavior is influenced by a variety of factors ranging from physical attributes, such as the characteristics of the street network, to abstract variables, such as personal preferences of the driver. Street network composition and network variables, such as roadway type, the mere presence and density of signalized intersections, and path characteristics, such as frequency of turn movements, are expected to have a significant influence on a driver's route-choice. This study explores the impacts of roadway type, signal control, and turning movements on route-choice by comparing observed paths in the real world and computed shortest paths for a set of origin and destination (O-D) pairs. Robust methodologies are devised and Python scripts are developed to conduct data processing and statistical analysis.;The comparison of real paths and computed paths indicated that drivers do not necessarily choose the theoretical shortest time paths and shortest distance paths in the real world. Drivers are willing to spend more time or travel longer distance on the paths that require fewer turns. Paired sample t-tests indicated that real paths have more signalized turns than computed shortest paths. Moreover, drivers seem more prone to making a turn (left or right) at a signal controlled intersection, while at the same time trying to minimize the number of turns occurring at non-signalized intersections. Statistical evidence also indicated that drivers tend to minimize left turns along their selected path. The number of right turns (normalized per mile), on the other hand, does not have a significant influence on route-choice. The mere presence of signalized intersections along alternative routes does not influence path choice. Statistical results showed that in terms of the number of signals per mile, theoretical paths are not different from real paths. A methodology is developed to quantify the impact of turning movements in the form of turn penalties, and to integrate them into path finding algorithms. However, the optimal path yielded by incorporating turn penalties into these algorithms has not significantly increased the chance of matching theoretical paths to actual paths.;Part II:.;Computational efficiency of path finding algorithms is very dependent on the size of the street network. Most of the shortest-path algorithms extend the search into the areas of the network that are not part of the solution to the path finding problem. For this reason, the full network must be "pruned" or narrowed to a more relevant sub-network. Commercially available route guidance systems / solutions have successfully used network pruning methods for faster and real-time solution to shortest path algorithms, but those solutions are proprietary in nature. Hence, the literature available on this subject is very limited. This research is expected to fill the gap in available literature on the methodologies for efficient network pruning.;This study also examines computational accuracy and efficiency of pruning large networks into sub-networks in the search for the shortest path between a given pair of origin and destination nodes in the network (one-to-one path search). A bounding-box approach is introduced to prune the network. Computational experiments are conducted with different buffer sizes for the bounding box. Real-world paths are analyzed for their geographic relationship to the driver's origin and destination and the concept of "proportional buffer" is introduced to define the boundaries of the sub-network. An approach to extracting a sub-network, within which the search work will be limited, is developed. Compared to the most commonly used uniform buffer method, the proportional buffer method can accelerate the computation while maintaining the same level of accuracy.