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

Abstract

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.