Двухфазный алгоритм маршрутизации в нестационарных сетях

У произвольной булевой функции может быть несколько пороговых приближений с разными, вообще говоря, мерами близости.

Определение 4. Статистическое пороговое приближение т(х1,...,хп) булевой функции f (х1,..., хп) назовём оптимальным, если мера его близости максимальная.

Как и в случае импликативного приближения, можно показать, что у конкретной булевой функции могут существовать различные оптимальные статистические пороговые приближения.

Особенности и параметры практического применения статистических пороговых приближений требуют изучения в непосредственной связи с конкретным методом решения результирующих систем линейных неравенств. В алгоритмах направленного перебора с минимизацией невязки ^(х) истинному решению будет отвечать уже не значение невязки, равное 0, а некоторое ненулевое определяемое конкретным алгоритмом, видом ^(х) и значением 8.

Обнаруженная авторами практическая эффективность как импликативных, так и статистических пороговых приближений приводит к постановке целого ряда актуальных задач не только экспериментального характера, но и теоретических, связанных с выбором оптимальных параметров методов, оценкой объёма необходимого материала, определением емкостной и временной сложностей.

ЛИТЕРАТУРА

1. Балакин Г. В., Никонов В. Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикладной и промышленной математики. 1994. Т. 1. №3. С.389-401.

2. Рыбников К. К. Оценки сложности некоторых схем метода разделяющих плоскостей при решении систем булевых уравнений // Обозрение прикладной и промышленной математики. 2002. Т. 2. №9. С. 442-443.

3. Анашкина Н. В., Шурупов А. Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств // Прикладная дискретная математика. Приложение. 2015. №8. С. 136-138.

УДК 519.7 DOI 10.17223/2226308X/10/65

ДВУХФАЗНЫЙ АЛГОРИТМ МАРШРУТИЗАЦИИ В НЕСТАЦИОНАРНЫХ СЕТЯХ

А. А. Солдатенко

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины x. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.

Ключевые слова: нестационарные сети, оптимальная маршрутизация, алгоритм ALT, расстановка ориентиров.

В современных телекоммуникационных сетях приходится иметь дело с расширением задачи о кратчайшем пути, когда время прибытия в конечную вершину y дуги e = (x,y) ориентированного графа G зависит не только от веса дуги e, но и времени выхода из начальной вершины x этой дуги. Функции, заданные на дугах графа G подобным образом, называют функциями прибытия, а сам граф G — нестационарной сетью. Задача поиска кратчайшего пути в нестационарной сети носит название Time-Dependent Shortest-Path problem, или коротко TDSP [1]. Известно, что TDSP для нестационарной сети общего вида без каких-либо ограничений на топологию сети и функции прибытия является NP-трудной задачей [2]. Когда функции прибытия удовлетворяют условию FIFO (First-In First-Out), задача TDSP полиномиально разрешима [1]. В этом случае задача TDSP традиционно решается алгоритмом Дейкстры. Предлагается решать задачу TDSP двухфазным алгоритмом маршрутизации по ориентирам, известным в литературе как алгоритм ALT (A* with Landmarks & Triangle). При этом под ориентиром понимается выделенная вершина исходного графа.

Пусть задан ориентированный граф G = (V, E) без кратных дуг и петель (далее просто граф), в котором для всякой дуги e = (x,y) G E определена весовая функция wxy(t) ^ 0 следующим образом:

w"(i)=vtxk •

Здесь величина lxy — расстояние между вершинами x,y G V, а vxy(t) —скорость движения по дуге (x, y) G E при условии, что старт из x осуществлён в момент времени t. Считаем, что выполнены естественные для сетей условия: vxy(t) > 0 и lxy ^ 0.

Сопоставим дуге (x,y) G E функцию прибытия Fxy(t) = t + wxy(t), где t — время отправления из вершины x при движении в вершину y по дуге (x,y). Если для каждой дуги (x,y) G E и любых моментов времени 0 < ti ^ t2 выполняется неравенство Fxy(t1) ^ Fxy(t2), то говорят, что функция прибытия является монотонной, или удовлетворяет условию FIFO. Для всякой дуги e = (x, y) G E всегда верны отношения x = y, t > 0, wxy(t) ^ 0. Отсюда следует, что

Fxy

Неравенство (1) отражает непосредственный ход времени: «отправляясь из вершины x в момент времени t, невозможно прибыть в вершину y раньше времени t вне зависимости от значений lxy и vxy (t)». Граф G с учётом всех указанных предположений будем называть нестационарной сетью с условием FIFO.

Последовательность вершин P = (x0, x1,..., xk), в которой s = x0, d = xk, (xi-1,xi) G E для i = 1, 2,... , k, задаёт путь из вершины s в вершину d в графе G, старт которого осуществляется в момент времени ts. Такой путь обозначается (P, ts). Если в G существует (s, d)-путь P, то вершина d достижима из s по пути P, что записывается как s ^ d. Полагаем, что вес (s, d)-пути в сети G вычисляется традиционным

для задач маршрутизации способом [3]

k-1

w(P,ts) = ts Wxixi+1 (ti), где to = ts,ti+1 = Fxixi+i (ti),

i=0

а вес кратчайшего (s, d, t^-пути определяется следующим образом:

dist(s, d, ts) = min{w(P, ts): s ^ d}.

Тройку величин (s, d, ts), где s и d — стартовая и целевая вершина соответственно, ts — стартовое время, будем называть запросом на поиск в нестационарной сети G = (V, E) кратчайшего (s, d, ^)-пути, или кратко (s, d, ^-запросом. С использованием введённых понятий и обозначений задача TDSP формулируется следующим образом:

Time-Dependent Shortest-Path problem

Заданы: нестационарная сеть G = (V, E) с условием FIFO, (s, d, t^-запрос.

Требуется: найти значение dist(s, d, ts) и последовательность вершин, образующих кратчайший (s, d, ^-путь.

Задача TDSP всегда имеет решение, возможно, не единственное, если вершина d достижима из вершины s в графе G. Условие FIFO гарантирует справедливость неравенства (1), которое требуется для корректной работы алгоритма Дейкстры, а также его различных версий, включая алгоритмы A* и ALT [1]. В данной работе предполагается, что сеть является метрической, т. е. выполнено неравенство треугольника для весов дуг. Доказано, что неравенство треугольника, определённое через оптимистичные значения весов дуг, обеспечивает выполнимость свойств допустимости и преемственности потенциальных функций, необходимых для корректной работы алгоритма ALT.

Расстановка ориентиров в вершинах графа — фактор, существенно влияющий на значение потенциальных функций, а значит, и на быстродействие алгоритма A*, выполняющегося на второй фазе алгоритма ALT [2]. Задача оптимального выбора ориентиров в графе G заключается в определении числа ориентиров и мест их расстановки в вершинах этого графа. Данная задача носит комбинаторный характер и является труднорешаемой. Доказано, что даже в частном случае, когда число ориентиров фиксировано, эта задача NP-трудная [2]. Поэтому расстановку ориентиров обычно осуществляют с помощью эвристических алгоритмов. Экспериментально установлено разумное число ориентиров, которое обеспечивает эффективность алгоритма A* на больших графах,—от 9 до 16. С учётом данного факта задача выбора ориентиров сводится к более простой, но по-прежнему труднорешаемой задаче расстановки заданного числа K ориентиров в графе G = (V, E) [2].

Предложена эвристика AdaHeuris по расстановке заданного числа ориентиров в вершинах графа, которая отличается от существующих и применяемых в ALT эвристик тем, что в ней текущий набор ориентиров корректируется на основе истории обработки запросов. Эвристика AdaHeuris позволяет значительно уменьшить время работы второй фазы алгоритма ALT и решать задачу TDSP для последовательности запросов, поступающих в режиме онлайн.

Показано, что разработанный алгоритм ALT находит точное решение задачи TDSP за время O(|V|2). Алгоритм проверен на реальных сетях, представленных в базе данных DIMACS http://www.dis.uniroma1.it/challenge9/. Результаты сравнения разработанного алгоритма с алгоритмом Дейкстры приведены в таблице, где C — коэффициент ускорения, определяемый как отношение времени работы сравниваемых между собой алгоритмов; T — среднее время выполнения одного запроса алгоритмом ALT. Достигнутые значения коэффициента ускорения оказались сопоставимы со значениями подобных коэффициентов, полученных в работе [4], в которой задача TDSP решается с помощью иерархического алгоритма. Иерархические алгоритмы — альтернативный

подход ускорения алгоритма Дейкстры (по отношению к алгоритму ALT), в котором ускорение достигается за счёт разложения исходной сети на несколько уровней. Результаты экспериментов показали, что разработанный алгоритм ALT может быть использован для эффективного решения задачи TDSP на последовательности запросов, поступающих в режиме онлайн, наряду с другими подходами.

Результаты сравнения алгоритмов

Название графа Параметры графа C T, с

Rome99 3353 8870 1,2 0,03622

AK 69082 156200 4,01 8,04443

VT 97975 215116 5,32 17,8026

ЛИТЕРАТУРА

1. Гимади Э. Х., Глебов Н. И. Математические модели и методы принятия решений. Новосибирск: Изд-во Новосиб. ун-та, 2008. 162 с.

2. Goldberg A., Kaplan H., and Werneck R. Better landmarks within reach // LNCS. 2007. V. 4525. P. 38-51.

3. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «Либроком», 2012. 390 с.

4. Nejad M. M., Mashayekhy L., Chinnam R. B., and Phillips A. Hierarchical time-dependent shortest path algorithms for vehicle routing under ITS //J. IIE Transactions. 2016. V. 48. No. 2. P. 158-169.