Although many studies on shortest-path algorithms have been conducted, few of them have taken advantage of the added characteristics of highway networks and, thus, have failed to become more efficient in finding shortest paths, or lowest-cost paths, for transportation problems. A new concept is proposed for enhancing most existing shortest-path algorithms. Taking advantage of the geographical nature of most transportation networks, the new concept uses a minimal search area to reduce the amount of computations that must be performed by existing algorithms. To simplify the analysis, a hypothetical network in an L1 metric was used to approximate two-dimensional roadways. Empirical results from thousands of shortest paths between arbitrary origin–destination pairs suggested that an elliptical shape is most suitable for confining the search area when seeking a shortest path. Further analysis established the formulation of the ellipse, which becomes rounder when the origin is close to the destination and more elongated when the two points are far apart. The elliptical minimal search area is stable and has a high level of confidence in containing the true shortest path, even if the cost function for each link is dynamic or stochastic. A list of future tasks is presented to further the promising findings of this research. The algorithm, which is not in itself a shortest algorithm per se, can enhance other shortest-path algorithms for transportation roadway networks.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Finding Shortest Paths under Time–Bandwidth Constraints by using Elliptical Minimal Search Area


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2006-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Finding Shortest Paths Under Time-Bandwidth Constraints by Using Elliptical Minimal Search Area

    Han, Lee / Wang, Hui / Mackey Jr., William | Transportation Research Record | 2006



    Finding Shortest Paths Under Time-Bandwidth Constraints by Using Elliptical Minimal Search Area

    Han, L. D. / Wang, H. / Mackey, W. F. et al. | British Library Conference Proceedings | 2006



    Finding Reliable Shortest Paths in Dynamic Stochastic Networks

    Wu, Xing | Transportation Research Record | 2013