Optimal routing by landmarks in the time-dependent networks

The Time-Dependent Shortest-Path problem (TDSP) is considered. This is an extension of the shortest path problem in a graph. TDSP problem arises in designing and operating telecommunication and transport networks. In such a network, we need to consider the time and the possibility of appearance of predictable situations, for example, traffic jams or traffic reduction. In this case, the network is represented with a digraph $G=(V,E)$ in which, for each arc $(x,y)\in E$, two functions are defined. The first one, $w_{xy}(t)$, is the time required for move along an arc $(x,y)$. The second function, $F_{xy}(t)$, is the time of arrival at the vertex $y$ if the movement starts from the vertex $x$ at the time $t$. Such a graph is called a time-dependent network and the minimum time for movement from vertex $x$ to vertex $y$ is interpreted as the optimal route or the shortest path between these vertices. In this paper, TDSP problem is studied for polynomial case when the arrival function is monotonous. The two-phased ALT (A$^*$ with Landmarks & Triangle) algorithm is one of the modern algorithms which are able to fast solve the TDSP problem for the large dimension graphs. There exist many experimental works done to improve ALT algorithm. However, the theoretical foundation of the ALT algorithm applicability to different classes of graphs is desperately needed. In this paper, we establish and prove sufficient conditions for correctness of ALT algorithm with respect to TDSP problem. These conditions define requirements for a time-dependent network such that if the requirements are fulfilled, then the ALT algorithm finds the exact solution of TDSP problem – a time-dependent shortest path in the network. According to the conditions, the network must satisfy triangle inequality for the time intervals of moving between the network nodes. A distinguishing feature of this concept of the triangle inequality is its definition through so called optimistic arc weights providing an unimpeded movement along the arcs. We show that in the network, where a weight of an arc is defined as ratio of its length to velocity of moving on it, this triangle inequality is always true if the triangle inequality for the distance between the network nodes is true.