Heuristic Bidirectional Dijkstra Algorithm Using Piece-Wise Linear Function
Gelareh B. Sanjabi, Duc T. Nguyen, Caleb Talbot · International Conference on Transportation and Development 2018 · 2018
A simple and efficient heuristic time dependent bidirectional search algorithm is proposed which can find point to point shortest path on time sdependent transportation networks. This proposed algorithm is based on the classical Dijkstra’s algorithm. The time delay factor (TDF) method (applied on top of the “static” links’ cost) combined with a piece-wise linear function is used to incorporate the links’ cost for “dynamic, or time dependent” networks. This new algorithm simultaneously starts the forward and backward search until the collided node is found. Then, the backward search stops, and forward search continues to explore only those nodes which have been previously explored through backward search process. The backward search is only implemented to limit the number of nodes required to be explored by forward search. In the forward search, the departure time is known while in the backward search the departure time (i.e., the arrival time for the forward search) is unknown. In this work, to start the backward search, two methods are examined: an arbitrary guessed arrival time and an extrapolated guessed arrival time to estimate the arrival time. Numerical results (based on real-life transportation networks) of this study clearly show significant advantage of the proposed algorithm in term of computational effort with respect to the classical Dijkstra’s algorithm. The obtained shortest path and arrival time are only slightly different from the optimum solution in few cases.