Перевод названия: Two-phase routing algorithm in the time-dependent networks
Тип публикации: статья из журнала
Год издания: 2017
Идентификатор DOI: 10.17223/2226308X/10/65
Ключевые слова: нестационарные сети, оптимальная маршрутизация, алгоритм alt, расстановка ориентиров, Time-dependent network, Optimal routing, ALT algorithm, Landmark placement
Аннотация: Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа - функция от времени отправления из вершины x. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленПоказать полностьюный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP. 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 (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 Ada-Heuris 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 O(n2), where n is the number of vertices in the time-dependent network G.
Журнал: Прикладная дискретная математика. Приложение
Выпуск журнала: № 10
Номера страниц: 168-171
ISSN журнала: 2226308X
Место издания: Томск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет"