Перевод названия: Adaptive algorithm for optimal route search in time-dependent network
Тип публикации: статья из журнала
Год издания: 2018
Ключевые слова: нестационарные сети, графы большой размерности, оптимальная маршрутизация, алгоритм alt, расстановка ориентиров
Аннотация: Рассматривается задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Задача TDSP возникает при проектировании и эксплуатации телекоммуникационных и транспортных сетей, когда требуется учитывать временной фактор и возможность возникновения в отдельные промежутки времени снижения Показать полностьюобъема трафика и наличия пробок в сети. В этих случаях сеть представляется ориентированным графом G = (V, E), в котором для каждой дуги (x, y) E определены две функции: время, необходимое для передвижения по этой дуге, и время прибытия в вершину y при условии, что старт из вершины x осуществлен в момент времени t. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут между этими вершинами. Известно, что задача TDSP для нестационарной сети общего вида является NP-трудной. В данной статье задача TDSP рассматривается для полиномиально разрешимого случая, когда функции прибытия монотонны. Предлагается решать TDSP с помощью двухфазного алгоритма ALT (A* with Landmarks & Triangle) – одного из современных алгоритмов оптимальной маршрутизации, изначально разработанного для решения задачи о кратчайшем пути в графе. Данный алгоритм на первой фазе расставляет некоторое множество ориентиров в вершинах сети и вычисляет потенциальные функции, а на второй с помощью алгоритма A* и потенциальных функций находит оптимальный маршрут. Предлагается модификация алгоритма ALT, эффективно решающая задачу TDSP для последовательности запросов на поиск оптимальных маршрутов в нестационарной сети. Модификация заключается в применении адаптивной эвристики для расстановки ориентиров, а также специальных формул вычисления потенциальных функций. Адаптивная эвристика использует историю обработки предыдущих запросов и корректирует текущий набор ориентиров для эффективного исполнения последующих запросов. Приводятся описание и оценка времени работы модифицированного алгоритма ALT. Представлены результаты вычислительных экспериментов, выполненные с помощью разработанных программных средств и подтверждающие высокое быстродействие модифицированного алгоритма ALT по сравнению с его классическими аналогами. The Time-Dependent Shortest-Path problem (TDSP) is an extension of the shortest path problem in a graph. TDSP problem arises when designing and operating telecommunications and transport networks. Such networks require considering time and possibility of appearing predictable situations for example traffic jams or traffic reduction. In this case, network is represented with an oriented graph G = (V, E) where for each arc (x, y) E, two functions are defined. First function is time required for moving along the arc (x, y). Second function is arrival time in vertex y if the movement started from vertex x in time t. Such graph is called time-dependent network. The minimum time for moving from vertex x to vertex y is an optimal route between these vertices. It is known that TDSP for a general time-dependent network without any restrictions on network topology or arrival function is NP-hard. When arrival function satisfies FIFO (First-In First-Out) condition, TDSP problem is polynomially solvable. This paper studies TDSP problem for a polynomial case when arrival functions are monotonous. It is proposed to solve TDSP problem using a two-phased algorithm ALT (A* with Landmarks & Triangle). ALT algorithm is one of the modern least cost routing algorithms originally developed for solving the problem of the shortest path in a graph. In the first phase, ALT algorithm places landmarks in network vertices and calculates potential functions. In the second phase it finds the exact value of an optimal route in a graph with A* algorithm. The paper proposes modification of ALT algorithm which is capable of correct and efficient solving the TDSP problem for a sequence of queries for searching for optimal routes in a time-dependent network. The modification consists in using adaptive heuristic for landmark placement and special formulas for calculating potential functions. This heuristic uses experience of processing all completed queries; adapts current set of landmarks for next queries. There is a description of the modified ALT algorithm and estimation of its working time. The paper also gives a description of the software that implements the proposed algorithm. The results of computational experiments confirm the effectiveness of the modified ALT algorithm.
Журнал: Программные продукты и системы
Выпуск журнала: № 2
Номера страниц: 321-329
ISSN журнала: 0236235X
Место издания: Тверь
Издатель: Закрытое акционерное общество Научно-исследовательский институт Центрпрограммсистем