Bounding Box Approach to Network Pruning for Efficient Path Search through Large Networks

Abstract

In this paper, the term network pruning is used to describe the process of extracting an appropriate subnetwork from a larger network for efficient and accurate path search. There is sparse literature on network pruning methods, potentially due to the rapid improvement of computing resources and the proprietary nature of such problems for service providers. However, this issue reemerges due to applications on small devices and travel behavior studies that require repeated running of route search routines. To ensure the soundness of travel behavior studies and route guidance applications that rely on such routines, different methods need to be evaluated based on real routes chosen by travelers, which represents a gap in literature. A bounding box method is proposed for efficient pruning of large networks and expediting search for the shortest path. The method is evaluated using real-world trips tracked by global positioning system (GPS). It is observed that an appropriate subnetwork can greatly improve the efficiency of path-finding algorithms without losing much accuracy. Through the investigations on real paths, the study found the orientation of the straight line connecting the origin and destination locations is relevant to the relationship of x and y deviations of the real path. Two types of buffers were investigated in this study: uniform and proportional. The results indicated that the proportional buffer is superior to the usually used uniform buffer, considering the balance between efficiency and accuracy. The proportional buffer methodology is expected to be useful in developing such innovative solutions as route guidance applications for drivers of connected vehicles where small devices perform the bulk of the computing task. The methodology simply uses popular path finding algorithms.