*_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 24^th , 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), expectingto 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.