7.3.2 Фиксированная (однопутевая) маршрутизация

По сравнению с альтернативной маршрутизацией задача поиска единственного оптимального пути является гораздо более сложной.

Дело в том, что ограничение (7.15 а) является требованием целочисленности переменных которое переводит задачу в класс задач целочисленного нелинейного программирования, идентичных задаче «о рюкзаке». Известно [194], что такие задачи являются NP-полными, то есть для их решения не известны алгоритмы с полиномиальной сложностью. В работах [64, 89, 173] приводятся эвристические алгоритмы, которые позволяют получить приближенное решение задачи с небольшими вычислительными затратами. Одним из основных недостатков эвристических алгоритмов является невозможность оценки погрешности получаемых решений.

В настоящей работе предлагается подход, который позволяет получить точную нижнюю оценку задачи. Данный подход строится на методе релаксации (ослаблении) Лагранжа. Метод состоит в том, что вместо исходной задачи решается двойственная задача, в которой некоторые ограничения включаются в функцию Лагранжа с соответствующими неопределенными множителями (подвергаются лагранжеву ослаблению). Практика показывает [101], что для многих задач целочисленной оптимизации:

- двойственная функция хорошо обусловлена, что позволяет получить удовлетворительную скорость сходимости;

- скачки двойственности (разности между целочисленным оптимумом и оптимумом двойственной задачи) очень малы или могут отсутствовать вовсе.

Таким образом, получение хорошей нижней оценки позволяет:

- оценить качество решений, получаемых эвристическими алгоритмами (и останавливаться на них, если эти решения будут откланяться от нижней оценки не более чем на заданную величину);

- строить алгоритмы типа «ветвей и границ», чтобы получать оптимальные решения или решения с заданной точностью.

Использование метода релаксации Лагранжа для решения задачи фиксированной маршрутизации впервые было использовано в работе [194]. Предлагаемый здесь подход использует ослабление меньшего числа ограничений, что повышает точность решения задачи.

Для использования метода релаксации переформулируем исходную задачу. Введем следующее обозначение: для всех . Величина называется загрузкой линии связи и представляет собой одну из наиболее важных характеристик качества функционирования сети передачи данных. Из ограничения (7.13) следует, что Итак:

Требуется найти:

1) Переменные и загрузки линий связи такие, что:

при выполнении ограничений:

Заметим, что целевая функция в (7.22) является строго возрастающей функцией от .

Используя этот факт легко доказать, что равенство (7.23) можно заменить на неравенство

(7.23а)

Теперь исходная задача подготовлена к лагранжеву ослаблению. Избавимся от ограничений (7.23а), умножив их на неопределенные множители Лагранжа и переходим к функции Лагранжа:

Таким образом, решается следующая задача:

при выполнении ограничений:

Множество допустимых решений для задачи (7.27) - (7.31) является подмножеством всех допустимых решений задачи (7.22) - (7.26).

Условия (7.31) и (7.23 а) гарантируют, что для любого допустимого решения задачи (7.22) - (7.26) выражение: меньше или равно нулю. Таким образом, решение задачи (7.27) - (7.31) для произвольных значений переменных дает возможность определить нижнюю оценку задачи (7.22) - (7.26). Тогда, также является нижней оценкой задачи (7.22) -(7.26).

Предположим, что значения переменных известны. Перепишем целевую функцию в следующем виде:

Данный вид целевой функции позволяет разделить исходную задачу на две независимые подзадачи.

Подзадача 1.

при выполнении ограничений:

Подзадача 2.

при выполнении ограничений:

Подзадача 1 может быть разделена на М независимых подзадач (по одной на каждую линию связи):

при ограничении:

Решение данной подзадачи имеет следующий вид:

Подзадача 2 может быть разделена на независимых подзадач (по одной на каждую пару «источник - адресат

при выполнении ограничений:

Легко заметить, что задача (7.40) - (7.42) представляет собой задачу выбора кратчайших маршрутов между заданной парой узлов если в качестве «весов» ребер рассматривать величины .

Так как подзадачи (7.40) - (7.42) независимы, то для решения подзадачи 2 можно использовать алгоритм поиска кратчайших путей между всеми парами узлов, например, алгоритм Флойда.

Теперь рассмотрим процедуру поиска множителей Лагранжа о Функция является вогнутой, не всюду дифференцируемой функцией от а [101]. Для данной функции легко вычислить субградиент в точке а:

Тогда, для поиска минимума функции можно использовать субградиентный алгоритм [112], в соответствии с которым множители Лагранжа вычисляются по следующей итеративной формуле:

Существует несколько методов выбора параметров перемещения в частности:

- метод с постоянным шагом - ;

- метод сходящегося ряда -

- метод релаксации - , где Т - оценка оптимального решения задачи (7.22) - (7.26) и, следовательно, функции коэффициент релаксации S удовлетворяет условию:

Аналогично [194] остановимся на методе релаксации, который состоит из следующих основных шагов.

Шаг 1. Инициализация:

1) Используя любой приближенный алгоритм, найти верхнюю оценку решения задачи (7.22) - (7.26) - Т.

2) Выбрать начальные значения множителей Лагранжа -

3) Установить:

( — номер итерации);

( — счетчик «безрезультатных» итераций);

(коэффициент релаксации);

(текущее значение оптимального решения).

Шаг 2. Решение задачи Лагранжа:

Используя значения решить подзадачи 1 и 2. В результате решения будут получены:

Шаг 3. Оценка полученного решения и проверка условий прекращения поиска:

1) Если , то положить:

а)

b) (множители Лагранжа, соответствующие текущему оптимальному решению);

с)

2) Если являются допустимыми решениями задачи то вычислить среднее значение задержки сообщения Т, соответствующее переменным и, если, то запомнить данную величину в качестве оптимального решения: .

3) Положить Если заданного значения , то:

а)

b)

c)

d)

e) перейти к шагу 2.

4) Если заданного значения гтах, или или заданной погрешности вычислений , то STOP: найдено оптимальное решение.

Шаг 4. Вычисление множителей Лагранжа:

1) Вычисляется новое значение субградиента:

2) Вычисляется параметр перемещения

3) Вычисляются новые множители Лагранжа:

4)

5) Переход к шагу 2.

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

В тех случаях, когда в результате решения задачи необходимо получить оптимальные пути между каждой парой узлов «источник - адресат». Для этой цели необходимо использовать приближенные методы, один из которых описывается ниже. Заметим также, что решение, полученное с помощью данного алгоритма, может быть использовано на шаге 1 предыдущего алгоритма.

Шаг 1. Инициализация:

1) Упорядочить множество пар «источник - адресат по убыванию величин Полученное множество пар обозначим через .

2) Положить

Шаг 2. Поиск допустимого решения:

1) Для V пары «источник - адресат выполнить следующие действия:

a) найти «наименее загруженный» маршрут (под загрузкой маршрута понимается величина если таких маршрутов несколько, выбрать среди них маршрут с наименьшим числом промежуточных узлов;

b) распределить потоки по выбранному маршруту:

если то STOP (допустимого решения не существует).

2) Вычислить задержки Z между каждой парой узлов «источник - адресат

Шаг 3. Поиск «оптимального» решения:

1) Упорядочить множество пар «источник - адресат по убыванию величин Полученное множество пар обозначим через

2) Для V пары «источник - адресат выполнить следующие действия:

a) найти маршрут такой, что отклонение всего потока 7 на этот маршрут приведет к максимальному уменьшению величины (алгоритм определения такого маршрута будет описан ниже);

b) распределить потоки по выбранному маршруту:

3) Вычислить:

Остановимся подробнее на следующих шагах приближенного алгоритма: определение «наименее загруженного» маршрута (шаг 2.1 а) и определение «оптимального» маршрута (шаг 3.2 а).

«Наименее загруженный» маршрут можно найти с помощью модификации алгоритма Дейкстры [177].

Для определения «оптимального» маршрута можно использовать следующий простой алгоритм (напомним, что определение такого маршрута выполняется для заданной пары узлов ).

Шаг 1. Удалить поток из «наименее загруженного» маршрута (предполагается, что все маршруты были сохранены):

Шаг 2. Добавить поток во все линии связи :

Шаг 3. Вычислить «веса» линий связи

если положить: , иначе:

Шаг 4. Используя «веса» определить кратчайший путь между парой узлов Для этой цели вновь можно использовать алгоритм Дейкстры.

Шаг 5. Удалить поток из всех линии связи

Шаг 6. Конец работы алгоритма.

Теоретическая сложность приближенного алгоритма определяется шагами 2.1 а и 3.2 а и составляет