Reducing the Search Space in Real-Road Shortest Path Finding using Elliptical Pruning WithGeographical Databases

摘要

Real-road shortest-path finding algorithmsinvolve large set of geographical data which includegeo-tagged nodes and edges of the road network. Practicalshortest path finding algorithms need minimizedsearch-space for performing these computations bykeeping these data in the computer?s conventionalmemory. The hierarchical pruning methods forminimizing the search-space to support real-road shortestalgorithms are more suitable for connecting multiple citiesand towns via highways. This study is to present a newsuitable pruning method for intra-city shortest pathfinding, called elliptical pruning to bring the geo-taggednodes and edges in to the memory for the subsequentshortest path finding process for the complex cityroad-transport networks.