 |
 |
Notice and Invitation Oral Defense of Doctoral Dissertation The Volgenau School of Engineering, George Mason University
Xi Zhou Bachelor of Science, Beijing Jiaotong University, 2000 Master of Science, George Mason University, 2006
Revealed Path Choice Behavior and Network Pruning for Efficient Path Finding
Thursday,
April 24th,
2014
1:00 PM –
3:00 PM
The Nguyen Engineering Building,
Room 2901
Committee
Dr. Mohan M. Venigalla, Chair
Dr.
Mark H. Houck
Dr.
Shanjiang Zhu
Dr.
Chaowei Yang
Abstract
The practice of finding a path from the origin to the destination has to consider the driver’s path choice behavior, as well as the computational efficiency. Path choice behavior is influenced by a variety of factors ranging from such physical attributes as network characteristics to abstract variables as personal preferences. 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 significant influence on people’s path choice. This study explores impacts of roadway type, signal control, and turn movements on route choice by comparing observed paths 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 analysis indicated that people do not necessarily choose the theoretical shortest paths in the real-world. Instead, drivers are willing to spend longer time or travel longer distance on the paths that have fewer turning movements. Statistical evidence indicated that drivers tend to minimize turns occurring at non-signalized intersection along their selected path. The mere presence of signalized intersections along alternative routes does not influence path choice. A methodology is developed to quantify the impacts of turning movements in the form of turn penalties, and to integrate them into path finding algorithms. The study also examined computational accuracy and efficiency of pruning large networks into sub-networks so as to search for the shortest path between a given pair of origin and destination nodes in the network (on-to-one path search), expecting to fill the gap in available literature on the methodologies for efficient network pruning. Computational efficiency of path finding algorithms is very dependent on the size of network. A bounding-box approach is introduced to prune the network. An approach to extracting a sub-network, within which the search work will be limited, is developed. Real world paths are analyzed for their geographic relationship with origin and destination and the concept of proportional buffer to define the boundaries of the bounding-box is introduced. Computational experiments are conducted with different sub-network sizes. Compared to the most commonly used uniform buffer method, the proportional buffer method can accelerate the computation while maintaining the same level of accuracy.
A
copy of this doctoral
dissertation is on reserve at the Johnson Center Library.