Transportation shortest path search area model

by Wang, Hui.

Although many studies on shortest-path algorithms have been conducted in the past, few of them have considered the time and effort required to obtain and update the weight property of the network arcs. For transportation-related problems – due to the size and complexity of the network – preparing, updating, and transmitting the network database on which the shortest-path algorithms perform can be a challenge. This study designed a Transportation Shortest Path Search Area (TSPSA) model to enhance the database preparation and updating step before any shortest-path search algorithm can start processing. Taking advantage of the characteristics of the transportation networks, this new TSPSA model divides a transportation network into hierarchical levels of areas, and uses an elliptical search area to reduce the amount of data required by existing methods. For testing the designed TSPSA model, the DC- Baltimore metropolitan area roadway network was selected as a performance case study. The network GIS map was obtained by translating Census 2000 Topologically Integrated Geographic Encoding and Referencing system (TIGER) files into GIS shape files. Using the TSPSA model, when the Origin and Destination (OD) Euclidean distance increases, the amount of data saving increases; concurrently, the maximum percent error between the TSPSA model and other traditional models rapidly decreases. The percentage of the data saving is around 75% to 85%, which means the data transmitting time is reduced about 80%. Moreover, the maximum percent error between the TSPSA model and other traditional models reduces to less than 5% when the Euclidean distance between the original and destination points (ED) is greater than 1.8 miles in urban areas. Similarly, the maximum percent error reduces to less than 5% when ED is greater than 4 miles in suburban areas, and less than 5% when ED is greater than 9 miles in rural areas. v The study concludes that the TSPSA model greatly reduces shortest-path search area data size, and increases the data transmitting speed between the information control center and its clients. It contributes to speeding up the shortestpath search process as a whole, as well as reducing the congestion obstacles in data transmission. vi