RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

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

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.

DOI: https://doi.org/10.17223/20710410/37/10

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
\Bibitem{BykSol17} \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 \mathnet{http://mi.mathnet.ru/pdm589} \crossref{https://doi.org/10.17223/20710410/37/10} 

• http://mi.mathnet.ru/eng/pdm589
• http://mi.mathnet.ru/eng/pdm/y2017/i3/p114

 SHARE:

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
•  Number of views: This page: 54 Full text: 26 References: 13