Two-phase routing algorithm in the time-dependent networks

The Time-Dependent Shortest-Path (TDSP) problem is an extension of the shortest path problem in a directed graph G when the weight of a graph arc (x, y) is a function of the time of departure from the initial vertex x of the arc. Such a graph G is called a time-dependent network. This problem arises when we search the route in a computer and communication networks. A traditional way to solve TDSP problem is Dijkstra's algorithm. We propose to solve TDSP problem by two-phase ALT (A* with Landmarks & Triangle) algorithm. ALT algorithm performs goal-directed shortest-path search from the initial vertex s to the target vertex d using landmarks. In the first phase, ALT algorithm performs the placement of landmarks in network vertices and calculates the potential functions. In the second phase, ALT algorithm finds the exact value of the shortest (s, d)-path using potential functions. We have found formulas for calculating potential functions and a way for determining triangle inequality which ensure correctness of ALT algorithm. We have proposed a polynomial time adaptive heuristic called Ada-Heuris for landmarks placement. This heuristic uses experience about all the completed queries at the repeated solution of TDSP problem. At any moment, the landmarks in it are corrected on the base of the history of query processing coming online. It is shown that ALT algorithm solves the TDSP problem for the time O(n²), where n is the number of vertices in the time-dependent network G.

Keywords

Authors

References