
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 timedependent networks
V. V. Bykova^{}, A. A. Soldatenko^{} ^{} Siberian Federal University, Krasnoyarsk, Russia
Abstract:
The TimeDependent ShortestPath 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 timedependent 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 twophased 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 timedependent network such that if the requirements are fulfilled, then the ALT algorithm finds the exact solution of TDSP problem – a timedependent 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:
timedependent 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 timedependent 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 timedependent networks
\jour Prikl. Diskr. Mat.
\yr 2017
\issue 37
\pages 114123
\mathnet{http://mi.mathnet.ru/pdm589}
\crossref{https://doi.org/10.17223/20710410/37/10}
Linking options:
http://mi.mathnet.ru/eng/pdm589 http://mi.mathnet.ru/eng/pdm/y2017/i3/p114
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:

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 
