Geodesic
Two-phase routing algorithm in the time-dependent networks
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 168-171.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 ($\mathrm 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 AdaHeuris 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 $\mathrm O(n^2)$, where $n$ is the number of vertices in the time-dependent network $G$.
Keywords: time-dependent network, optimal routing, ALT algorithm, landmark placement. 
@article{PDMA_2017_10_a64,
     author = {A. A. Soldatenko},
     title = {Two-phase routing algorithm in the time-dependent networks},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {168--171},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a64/}
}
TY  - JOUR
AU  - A. A. Soldatenko
TI  - Two-phase routing algorithm in the time-dependent networks
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 168
EP  - 171
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a64/
LA  - ru
ID  - PDMA_2017_10_a64
ER  - 
%0 Journal Article
%A A. A. Soldatenko
%T Two-phase routing algorithm in the time-dependent networks
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 168-171
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a64/
%G ru
%F PDMA_2017_10_a64
A. A. Soldatenko. Two-phase routing algorithm in the time-dependent networks. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 168-171. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a64/

[1] Gimadi E. Kh., Glebov N. I., Matematicheskie modeli i metody prinyatiya reshenii, Izd-vo Novosib. un-ta, Novosibirsk, 2008, 162 pp.

[2] Goldberg A., Kaplan H., Werneck R., “Better landmarks within reach”, LNCS, 4525, 2007, 38–51

[3] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Knizhnyi dom “Librokom”, M., 2012, 390 pp. | MR

[4] Nejad M. M., Mashayekhy L., Chinnam R. B., Phillips A., “Hierarchical time-dependent shortest path algorithms for vehicle routing under ITS”, J. IIE Transactions, 48:2 (2016), 158–169 | DOI