7.3.3 К-путевая маршрутизация

При решении данной задачи будем предполагать, что ограничение на число исходящих линий - К больше 1, т. к. случай рассматривался в разделе 7.3.2. При задача (7.11) - (7.17) избавляется от целочисленности переменных что делает ее более простой, чем задача фиксированной маршрутизации.

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

Для решения задачи (7.11) - (7.17) предлагается алгоритм, являющийся модификацией алгоритма отклонения потока. Модификация заключается в том, что отклонение потока выполняется не для всех пар «источник-адресат» одновременно, а для каждой пары отдельно. Похожие идеи использованы в работе [82] при описании алгоритма решения задачи альтернативной маршрутизации.

Описание алгоритма

Шаг 1. Определить «веса» линий связи и инициализировать потоки в линиях связи

Шаг 2. Положить:

- множество оптимальных маршрутов между парой узлов

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

Включить кратчайшие пути в множества П:

Шаг 4. Распределить потоки по кратчайшим путям:

1)

2)

Шаг 5. Вычислить:

Шаг 6. Положить:

Шаг 7. Положить: где:

Шаг 8. Пересчитать потоки в линиях связи:

Шаг 9. Вычислить задержки между каждой парой узлов «источник - адресат

Шаг 10. Отсортировать множество пар узлов в порядке убывания величин Полученное множество пар обозначим через О.

Шаг 11. Выбрать очередную пару узлов Если все пары рассмотрены, то STOP:

если то допустимых решений нет;

если то получено оптимальное решение с заданной точностью .

Шаг 12. Для выбранной пары узлов инициализировать потоки по кратчайшим путям

1)

2)

Шаг 13. Определить «веса» линий связи

Шаг 14. Используя «веса» линий связи определить кратчайший путь для пары узлов

Шаг 15. Проверить ограничение (7.17):

1)

a)

b)

2) определить:

a)

b) если (условие (7.17) нарушено), то перейти к шагу 11. Шаг 16. Распределить поток по кратчайшему пути

Шаг 17. Найти величину (5 6 [0,1], минимизирующую функцию:

при условии выполнения ограничения (7.13)

Шаг 18. Выполнить отклонение потока на величину (5:

Шаг 19. Вычислить:

Шаг 20. Если то перейти к шагу 11 (значение целевой функции улучшить не удалось).

Иначе:

1) включить кратчайший путь в множество

2)

3) положить:

4) если то перейти к шагу 7; иначе перейти к шагу 9.