Geodesic
Optimal routing by landmarks in the time-dependent networks
Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 114-123.

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

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. 
@article{PDM_2017_3_a9,
     author = {V. V. Bykova and A. A. Soldatenko},
     title = {Optimal routing by landmarks in the time-dependent networks},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {114--123},
     publisher = {mathdoc},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_3_a9/}
}
TY  - JOUR
AU  - V. V. Bykova
AU  - A. A. Soldatenko
TI  - Optimal routing by landmarks in the time-dependent networks
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 114
EP  - 123
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_3_a9/
LA  - ru
ID  - PDM_2017_3_a9
ER  - 
%0 Journal Article
%A V. V. Bykova
%A A. A. Soldatenko
%T Optimal routing by landmarks in the time-dependent networks
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 114-123
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_3_a9/
%G ru
%F PDM_2017_3_a9
V. V. Bykova; A. A. Soldatenko. Optimal routing by landmarks in the time-dependent networks. Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 114-123. http://geodesic.mathdoc.fr/item/PDM_2017_3_a9/

[1] Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I., Lectures in Graph Theory, Librokom Publ., Moscow, 2012, 390 pp. (in Russian) | MR

[2] Kormen T. Kh., Leyzerson Ch. I., Rivest R. L., Shtayn K., Introduction to Algorithms, Vil'yams Publ., Moscow, 2016, 1328 pp. (in Russian)

[3] Sherali H. D., Ozbay K., Subramanian S., “The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms”, J. Networks, 31:4 (1998), 259–272 | 3.0.CO;2-C class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[4] Kaufman D. E., Smith R. L., “Fastest paths in time-dependent networks for intelligent vehicle-highway systems application”, J. Intelligent Transportation Systems, 1:1 (1993), 1–11 | MR

[5] Gimadi E. Kh., Glebov N. I., Mathematical Models and Methods of decision-making, NSU Publ., Novosibirsk, 2008, 162 pp. (in Russian)

[6] Wagner D., Willhalm T., “Speed-up techniques for shortest-path computations”, LNCS, 4393, 2007, 23–36 | MR | Zbl

[7] Goldberg A., Harrelson C., “Computing the shortest path: $A^*$ search meets graph theory”, Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), 2005, 156–165 | MR | Zbl

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

[9] Delling D., “Time-dependent SHARC-routing”, J. Algorithmica, 60:1 (2011), 60–94 | DOI | MR | Zbl

[10] Delling D., Wagner D., “Landmark-based routing in dynamic graphs”, LNCS, 4525, 2007, 52–65

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

[12] A Landmark Algorithm for the Time-Dependent Shortest Path Problem, , Tatsuya OHSHIMA, 2008 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.396.6069&rep=rep1&type=pdf

[13] Rassel S., Norvig P., Artificial Intelligence: A Modern Approach, Vil'yams Publ., Moscow, 2007, 1410 pp. (in Russian)

[14] DIMACS Implementation Challenge. Shortest Paths, , 2006 http://www.dis.uniroma1.it/challenge9/