Оптимальное построение кольцевых маршрутов

Исходной информацией для решения задачи являются условные схемы размещения пунктов, которые должны быть включены в маршрут, и матрица расстояний C = (c_ij) между этими пунктами, (см. табл. 4.1) в километрах. Рассмотрим решение задачи построения кольцевого маршрута на примере. Исходными данными для примера будут данные табл.4.1.

Алгоритм решения состоит из нескольких шагов.

Таблица 4.1

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

Таблица 4.2

Шаг 2. Получение приведенной матрицы.

Приведенной будем называть такую матрицу, которая имеет хотя бы один нулевой элемент. Для получения приведенной матрицы в каждой строке находим минимальный элемент и выписываем его с правой стороны матрицы. Это вектор-столбец вида (3, 3, 6, 5, 4) (см. табл.4.1). Из элементов соответствующей строки вычитаем минимальное значение элемента этой строки и получаем приведенную матрицу по строкам (см. табл. 4.3).

Таблица 4.3

Затем в каждом столбце находим минимальный элемент и выписываем их внизу матрицы. Это вектор-строка вида (0, 0, 2, 2, 0) (см. табл.4.3). Из элементов соответствующего столбца вычитается минимальное значение элемента этого столбца, и получают приведенную матрицу (табл.4.4). Математически доказано, что сделанные описанным способом процедуры получения приведенной матрицы (табл. 4.4) сохраняют свойства исходной матрицы.

Элемент приведенной матрицы c_ij будем называть полюсом, если c_ij = 0.

Таблица 4.4

Шаг 3. Последовательно для каждого полюса выполним следующее:

- для строки i₀, где находится полюс, находим минимальный элемент этой строки, исключая значение только для самого этого полюса:

- для столбца j₀, где находится полюс, находим минимальный элемент этого столбца, исключая значение только для самого этого полюса.

Находим значение параметра d( i₀, j₀) по формуле

d( i₀, j₀) = min ( c_ij) + min( c_ij ).

Имеем:
d₁₂ = 1 + 0 = 1,
d₂₁ = 0 + 0 = 0,
d₂₄ = 0 + 2 = 2,
d₃₅ = 2 + 1 = 3,
d₄₂ = 2 + 0 = 2,
d₅₁ = 0 + 0 = 0,
d₅₃ = 0 + 3 = 3.

Шаг 4. Находим параметр h(i₀,j₀) по формуле

h(i₀,j₀) = max ( d_ij ).

Если таких значений будет несколько, можно выбрать любое. Выбранный параметр h(i₀,j₀) показывает направление движения: нужно двигаться из пункта i₀ в пункт j₀. Чтобы не было возврата, делаем запрет, полагая c(j₀,i₀) = \\\\.

В нашем примере имеем

h₃₅ = 3 и h₅₃ = 3. Возьмем первый случай: h(i₀,j₀) = h_{35 .} Так как i₀ = 3, а j₀ = 5, то будем двигаться из пункта 3 в пункт 5 (см. рис. 4.1а.). В этом случае запрет будет иметь вид с₅₃=\\\\.

Шаг 5. Вычеркиваем строку i₀ и столбец j₀, сохраняя номера строк и столбцов матрицы неизменными. Для нашего примера это будет матрица табл. 4.5.

Таблица 4.5

Шаг 6. Если после вычеркивания в полученной матрице нет ни одного полюса, то необходимо создать полюса, применяя процедуры, описанные для шага 2. Получив приведенную матрицу, в которой имеются полюса, переходим к шагу 3.

Если после вычеркивания получаем матрицу (2Х2), то эту матрицу будем называть тривиальной, так как она позволяет однозначно достроить маршрут до кольцевого маршрута и получить решение задачи.

Рассмотрим последовательность действий для нашего примера.

Таблица 4.6

Так как в табл. 4.6 имеются полюса, то для каждого полюса находим d-параметры:

d₁₂= 2 + 0 = 2,
d₂₁= 0 + 0 = 0,
d₂₄= 0 + 2 = 2,
d₄₂= 2 + 0 = 2,
d₅₁= 3 + 0 = 3.

Находим h-параметр. Получим:

h(i₀,j₀) = d₅₁ = 3.

Вычеркиваются строка i₀ = 5 и столбец j₀ = 1 и полагаем элемент c₁₅=\\\\ (в нашем случае этот элемент отсутствует). Проводим стрелку от пункта 5 к пункту 1, согласно процедуре шага 4 (см. рис. 4.1б.). Однако чтобы избежать зацикливания 3 - 5 - 1 - 3, полагаем с₁₃=\\\\.

После этого составляется новая матрица (табл. 4.7).

Таблица 4.7

Так как в табл. 4.7 имеются полюса, снова рассчитываем d- и h-параметры. Получим:

d₁₂ = 2 + 0 = 2,
d₂₄ = 3 + 2 = 5,
d₄₂ = 3 + 0 = 3.

Анализ полученных значений дает

h(i₀,j₀) = d₂₄ = 5.

Организуем перевозку из пункта 2 в пункт 4 (см. рис. 4.1в.). Вычеркивается строка i₀ = 2 и столбец j₀ = 4. Чтобы избежать зацикливания, полагаем с₄₂=\\\\. Получаем матрицу табл. 4.8.

Таблица 4.8

Получена тривиальная матрица (2х2). По значениям этой матрицы строим две связи: 1 – 2 (т. к. по табл. 4.8 «расстояние» между этими пунктами самое короткое) и 4 – 3, чтобы получить замкнутый циклический маршрут (рис. 4.1г. и 4.1д. соответственно).

Протяженность кольцевого маршрута составляет 28 км. Это можно проверить по исходным данным табл. 4.1, обходя по контуру маршрута, начиная с пункта 3:

L = 6 + 4 + 3 + 5 + 10 = 28 (км).

Рис. 4.1. Результаты конструирования маршрута (по шагам)