General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Prikl. Diskr. Mat., 2017, Number 37, Pages 114–123 (Mi pdm589)  

This article is cited in 1 scientific paper (total in 1 paper)

Computational methods in discrete mathematics

Optimal routing by landmarks in the time-dependent networks

V. V. Bykova, A. A. Soldatenko

Siberian Federal University, Krasnoyarsk, Russia

Abstract: 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.

Keywords: time-dependent network, optimal routing, correctness of ALT algorithm.


Full text: PDF file (667 kB)
References: PDF file   HTML file

Document Type: Article
UDC: 519.7

Citation: V. V. Bykova, A. A. Soldatenko, “Optimal routing by landmarks in the time-dependent networks”, Prikl. Diskr. Mat., 2017, no. 37, 114–123

Citation in format AMSBIB
\by V.~V.~Bykova, A.~A.~Soldatenko
\paper Optimal routing by landmarks in the time-dependent networks
\jour Prikl. Diskr. Mat.
\yr 2017
\issue 37
\pages 114--123

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Soldatenko, “Algoritm optimalnoi marshrutizatsii v multiservisnykh telekommunikatsionnykh setyakh”, PDM. Prilozhenie, 2018, no. 11, 122–127  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:54
    Full text:26

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018