4. Формирование маршрутов движения транспортных средств с помощью методов Свира и «ветвей и границ»
Метод Свира предполагает воображаемый луч, исходящий из точки, где расположен грузоотправитель, который постепенно вращается по (или против) часовой стрелке, "стирая" с карты изображения грузополучателей (Рис.2). В тот момент, когда сумма заказов "стертых" грузополучателей достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом. При использовании метода Свира следует учитывать, что количество пунктов, включаемых в один маршрут должно быть не более пяти.
Так как в нашем случае получается, что за пунктом Б закреплено 6 пунктов, поделим сформируем 3 маршрута:
За маршрутом А закрепляем 7, 3, 10, 8 пункты.
За маршрутом Б1 закрепляем пункты 9, 4, 1.
За маршрутом Б2 закрепляем 5, 2, 6 пункты.
Рисунок 2. Закрепление за грузоотправителями грузополучателей с помощью метода Свира
На маршруте А общий вес получается 11.51 т
На маршруте Б1 общий вес 12.41 т
На маршруте Б2 11.21 т
Для работы на всех трех маршрутах привлекаем машину HYUNDAI 170 с грузоподъемностью 13 тонн.
Примем
А=1,
Пункт 3=2,
Пункт 7=3,
Пункт 8=4,
Пункт 10=5
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X0) = 9 + 1 + 11 + 8 + 8 = 37
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
Таблица 4.1
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
1 |
M |
9 |
8 |
10 |
8 |
8 |
|
2 |
9 |
M |
1 |
11 |
3 |
1 |
|
3 |
8 |
1 |
M |
11 |
3 |
1 |
|
4 |
10 |
11 |
11 |
M |
8 |
8 |
|
5 |
8 |
3 |
3 |
8 |
M |
3 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Таблица 4.2
|
i j |
1 |
2 |
3 |
4 |
5 |
|
1 |
M |
1 |
0 |
2 |
0 |
|
2 |
8 |
M |
0 |
10 |
2 |
|
3 |
7 |
0 |
M |
10 |
2 |
|
4 |
2 |
3 |
3 |
M |
0 |
|
5 |
5 |
0 |
0 |
5 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
Таблица 4.3
|
i j |
1 |
2 |
3 |
4 |
5 |
|
1 |
M |
1 |
0 |
2 |
0 |
|
2 |
8 |
M |
0 |
10 |
2 |
|
3 |
7 |
0 |
M |
10 |
2 |
|
4 |
2 |
3 |
3 |
M |
0 |
|
5 |
5 |
0 |
0 |
5 |
M |
|
dj |
2 |
0 |
0 |
2 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
Таблица 4.3
|
i j |
1 |
2 |
3 |
4 |
5 |
|
1 |
M |
1 |
0 |
0 |
0 |
|
2 |
6 |
M |
0 |
8 |
2 |
|
3 |
5 |
0 |
M |
8 |
2 |
|
4 |
0 |
3 |
3 |
M |
0 |
|
5 |
3 |
0 |
0 |
3 |
M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 8+1+1+8+3+2+0+0+2+0 = 25
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.4
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
1 |
M |
1 |
0(0) |
0(3) |
0(0) |
0 |
|
2 |
6 |
M |
0(2) |
8 |
2 |
2 |
|
3 |
5 |
0(2) |
M |
8 |
2 |
2 |
|
4 |
0(3) |
3 |
3 |
M |
0(0) |
0 |
|
5 |
3 |
0(0) |
0(0) |
3 |
M |
0 |
|
dj |
3 |
0 |
0 |
3 |
0 |
0 |
d(1,3) = 0 + 0 = 0; d(1,4) = 0 + 3 = 3; d(1,5) = 0 + 0 = 0; d(2,3) = 2 + 0 = 2; d(3,2) = 2 + 0 = 2; d(4,1) = 0 + 3 = 3; d(4,5) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 25 + 3 = 28
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
Таблица 4.5
|
i j |
1 |
2 |
3 |
4 |
5 |
di |
|
1 |
M |
1 |
0 |
M |
0 |
0 |
|
2 |
6 |
M |
0 |
8 |
2 |
0 |
|
3 |
5 |
0 |
M |
8 |
2 |
0 |
|
4 |
0 |
3 |
3 |
M |
0 |
0 |
|
5 |
3 |
0 |
0 |
3 |
M |
0 |
|
dj |
0 |
0 |
0 |
3 |
0 |
3 |
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 3
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.6
|
i j |
1 |
2 |
3 |
5 |
di |
|
2 |
6 |
M |
0 |
2 |
0 |
|
3 |
5 |
0 |
M |
2 |
0 |
|
4 |
M |
3 |
3 |
0 |
0 |
|
5 |
3 |
0 |
0 |
M |
0 |
|
dj |
3 |
0 |
0 |
0 |
3 |
Нижняя граница подмножества (1,4) равна:
H(1,4) = 25 + 3 = 28 ≤ 28
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 28
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.7
|
i j |
1 |
2 |
3 |
5 |
di |
|
2 |
3 |
M |
0(2) |
2 |
2 |
|
3 |
2 |
0(2) |
M |
2 |
2 |
|
4 |
M |
3 |
3 |
0(5) |
3 |
|
5 |
0(2) |
0(0) |
0(0) |
M |
0 |
|
dj |
2 |
0 |
0 |
2 |
0 |
d(2,3) = 2 + 0 = 2; d(3,2) = 2 + 0 = 2; d(4,5) = 3 + 2 = 5; d(5,1) = 0 + 2 = 2; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (3 + 2) = 5 для ребра (4,5), следовательно, множество разбивается на два подмножества (4,5) и (4*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(4*,5*) = 28 + 5 = 33
Исключение ребра (4,5) проводим путем замены элемента d45 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,5*), в результате получим редуцированную матрицу.
Таблица 4.8
|
i j |
1 |
2 |
3 |
5 |
di |
|
2 |
3 |
M |
0 |
2 |
0 |
|
3 |
2 |
0 |
M |
2 |
0 |
|
4 |
M |
3 |
3 |
M |
3 |
|
5 |
0 |
0 |
0 |
M |
0 |
|
dj |
0 |
0 |
0 |
2 |
5 |
Включение ребра (4,5) проводится путем исключения всех элементов 4-ой строки и 5-го столбца, в которой элемент d54 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.9
|
i j |
1 |
2 |
3 |
di |
|
2 |
3 |
M |
0 |
0 |
|
3 |
2 |
0 |
M |
0 |
|
5 |
0 |
0 |
0 |
0 |
|
dj |
0 |
0 |
0 |
0 |
Нижняя граница подмножества (4,5) равна:
H(4,5) = 28 + 0 = 28 ≤ 33
Чтобы исключить подциклы, запретим следующие переходы: (5,1),
Поскольку нижняя граница этого подмножества (4,5) меньше, чем подмножества (4*,5*), то ребро (4,5) включаем в маршрут с новой границей H = 28
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.10
|
i j |
1 |
2 |
3 |
di |
|
2 |
1 |
M |
0(1) |
1 |
|
3 |
0(1) |
0(0) |
M |
0 |
|
5 |
M |
0(0) |
0(0) |
0 |
|
dj |
1 |
0 |
0 |
0 |
d(2,3) = 1 + 0 = 1; d(3,1) = 0 + 1 = 1; d(3,2) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (2,3), следовательно, множество разбивается на два подмножества (2,3) и (2*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,3*) = 28 + 1 = 29
Исключение ребра (2,3) проводим путем замены элемента d23 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,3*), в результате получим редуцированную матрицу.
Таблица 4.11
|
i j |
1 |
2 |
3 |
di |
|
2 |
1 |
M |
M |
1 |
|
3 |
0 |
0 |
M |
0 |
|
5 |
M |
0 |
0 |
0 |
|
dj |
0 |
0 |
0 |
1 |
Включение ребра (2,3) проводится путем исключения всех элементов 2-ой строки и 3-го столбца, в которой элемент d32 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.12
|
i j |
1 |
2 |
di |
|
3 |
0 |
M |
0 |
|
5 |
M |
0 |
0 |
|
dj |
0 |
0 |
0 |
Нижняя граница подмножества (2,3) равна:
H(2,3) = 28 + 0 = 28 ≤ 29
Поскольку нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут с новой границей H = 28
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,1) и (5,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,5), (5,2), (2,3), (3,1),
Длина маршрута равна F(Mk) = 30
Для маршрута Б1 пункты
Б=1,
1=2,
4=3,
9=4.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,1)
Тогда F(X0) = 4 + 2 + 1 + 2 = 9
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
Таблица 4.13
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
4 |
3 |
2 |
2 |
|
2 |
4 |
M |
2 |
3 |
2 |
|
3 |
3 |
2 |
M |
1 |
1 |
|
4 |
2 |
3 |
1 |
M |
1 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Таблица 4.14
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
2 |
1 |
0 |
|
2 |
2 |
M |
0 |
1 |
|
3 |
2 |
1 |
M |
0 |
|
4 |
1 |
2 |
0 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
Таблица 4.15
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
2 |
1 |
0 |
|
2 |
2 |
M |
0 |
1 |
|
3 |
2 |
1 |
M |
0 |
|
4 |
1 |
2 |
0 |
M |
|
dj |
1 |
1 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
Таблица 4.16
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
1 |
1 |
0 |
|
2 |
1 |
M |
0 |
1 |
|
3 |
1 |
0 |
M |
0 |
|
4 |
0 |
1 |
0 |
M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 2+2+1+1+1+1+0+0 = 8
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.17
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
1 |
1 |
0(1) |
1 |
|
2 |
1 |
M |
0(1) |
1 |
1 |
|
3 |
1 |
0(1) |
M |
0(0) |
0 |
|
4 |
0(1) |
1 |
0(0) |
M |
0 |
|
dj |
1 |
1 |
0 |
0 |
0 |
d(1,4) = 1 + 0 = 1; d(2,3) = 1 + 0 = 1; d(3,2) = 0 + 1 = 1; d(3,4) = 0 + 0 = 0; d(4,1) = 0 + 1 = 1; d(4,3) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 8 + 1 = 9
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
Таблица 4.18
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
1 |
1 |
M |
1 |
|
2 |
1 |
M |
0 |
1 |
0 |
|
3 |
1 |
0 |
M |
0 |
0 |
|
4 |
0 |
1 |
0 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
1 |
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 1
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.19
|
i j |
1 |
2 |
3 |
di |
|
2 |
1 |
M |
0 |
0 |
|
3 |
1 |
0 |
M |
0 |
|
4 |
M |
1 |
0 |
0 |
|
dj |
1 |
0 |
0 |
1 |
Нижняя граница подмножества (1,4) равна:
H(1,4) = 8 + 1 = 9 ≤ 9
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 9
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.20
|
i j |
1 |
2 |
3 |
di |
|
2 |
0(0) |
M |
0(0) |
0 |
|
3 |
0(0) |
0(1) |
M |
0 |
|
4 |
M |
1 |
0(1) |
1 |
|
dj |
0 |
1 |
0 |
0 |
d(2,1) = 0 + 0 = 0; d(2,3) = 0 + 0 = 0; d(3,1) = 0 + 0 = 0; d(3,2) = 0 + 1 = 1; d(4,3) = 1 + 0 = 1;
Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (3,2), следовательно, множество разбивается на два подмножества (3,2) и (3*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,2*) = 9 + 1 = 10
Исключение ребра (3,2) проводим путем замены элемента d32 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,2*), в результате получим редуцированную матрицу.
Таблица 4.21
|
i j |
1 |
2 |
3 |
di |
|
2 |
0 |
M |
0 |
0 |
|
3 |
0 |
M |
M |
0 |
|
4 |
M |
1 |
0 |
0 |
|
dj |
0 |
1 |
0 |
1 |
Включение ребра (3,2) проводится путем исключения всех элементов 3-ой строки и 2-го столбца, в которой элемент d23 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.22
|
i j |
1 |
3 |
di |
|
2 |
0 |
M |
0 |
|
4 |
M |
0 |
0 |
|
dj |
0 |
0 |
0 |
Нижняя граница подмножества (3,2) равна:
H(3,2) = 9 + 0 = 9 ≤ 10
Поскольку нижняя граница этого подмножества (3,2) меньше, чем подмножества (3*,2*), то ребро (3,2) включаем в маршрут с новой границей H = 9
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,2), (2,1),
Длина маршрута равна F(Mk) = 9
Для маршрута Б2 примем, что пункты
Б=1,
2=2,
5=3,
6=4,
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,1)
Тогда F(X0) = 10 + 6 + 7 + 12 = 35
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
Таблица 4.23
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
10 |
6 |
12 |
6 |
|
2 |
10 |
M |
6 |
2 |
2 |
|
3 |
6 |
6 |
M |
7 |
6 |
|
4 |
12 |
2 |
7 |
M |
2 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Таблица 4.24
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
4 |
0 |
6 |
|
2 |
8 |
M |
4 |
0 |
|
3 |
0 |
0 |
M |
1 |
|
4 |
10 |
0 |
5 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
Таблица 4.25
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
4 |
0 |
6 |
|
2 |
8 |
M |
4 |
0 |
|
3 |
0 |
0 |
M |
1 |
|
4 |
10 |
0 |
5 |
M |
|
dj |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
Таблица 4.26
|
i j |
1 |
2 |
3 |
4 |
|
1 |
M |
4 |
0 |
6 |
|
2 |
8 |
M |
4 |
0 |
|
3 |
0 |
0 |
M |
1 |
|
4 |
10 |
0 |
5 |
M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 6+2+6+2+0+0+0+0 = 16
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.27
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
4 |
0(8) |
6 |
4 |
|
2 |
8 |
M |
4 |
0(5) |
4 |
|
3 |
0(8) |
0(0) |
M |
1 |
0 |
|
4 |
10 |
0(5) |
5 |
M |
5 |
|
dj |
8 |
0 |
4 |
1 |
0 |
d(1,3) = 4 + 4 = 8; d(2,4) = 4 + 1 = 5; d(3,1) = 0 + 8 = 8; d(3,2) = 0 + 0 = 0; d(4,2) = 5 + 0 = 5;
Наибольшая сумма констант приведения равна (4 + 4) = 8 для ребра (1,3), следовательно, множество разбивается на два подмножества (1,3) и (1*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,3*) = 16 + 8 = 24
Исключение ребра (1,3) проводим путем замены элемента d13 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,3*), в результате получим редуцированную матрицу.
Таблица 4.28
|
i j |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
4 |
M |
6 |
4 |
|
2 |
8 |
M |
4 |
0 |
0 |
|
3 |
0 |
0 |
M |
1 |
0 |
|
4 |
10 |
0 |
5 |
M |
0 |
|
dj |
0 |
0 |
4 |
0 |
8 |
Включение ребра (1,3) проводится путем исключения всех элементов 1-ой строки и 3-го столбца, в которой элемент d31 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 8
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.29
|
i j |
1 |
2 |
4 |
di |
|
2 |
8 |
M |
0 |
0 |
|
3 |
M |
0 |
1 |
0 |
|
4 |
10 |
0 |
M |
0 |
|
dj |
8 |
0 |
0 |
8 |
Нижняя граница подмножества (1,3) равна:
H(1,3) = 16 + 8 = 24 ≤ 24
Поскольку нижняя граница этого подмножества (1,3) меньше, чем подмножества (1*,3*), то ребро (1,3) включаем в маршрут с новой границей H = 24
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
Таблица 4.30
|
i j |
1 |
2 |
4 |
di |
|
2 |
0(2) |
M |
0(1) |
0 |
|
3 |
M |
0(1) |
1 |
1 |
|
4 |
2 |
0(2) |
M |
2 |
|
dj |
2 |
0 |
1 |
0 |
d(2,1) = 0 + 2 = 2; d(2,4) = 0 + 1 = 1; d(3,2) = 1 + 0 = 1; d(4,2) = 2 + 0 = 2;
Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) = 24 + 2 = 26
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
Таблица 4.31
|
i j |
1 |
2 |
4 |
di |
|
2 |
M |
M |
0 |
0 |
|
3 |
M |
0 |
1 |
0 |
|
4 |
2 |
0 |
M |
0 |
|
dj |
2 |
0 |
0 |
2 |
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 1
После операции приведения сокращенная матрица будет иметь вид:
Таблица 4.32
|
i j |
2 |
4 |
di |
|
3 |
0 |
1 |
0 |
|
4 |
0 |
M |
0 |
|
dj |
0 |
1 |
1 |
Нижняя граница подмножества (2,1) равна:
H(2,1) = 24 + 1 = 25 ≤ 26
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 25
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,2) и (4,4).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,3), (3,2), (2,1),
Длина маршрута равна F(Mk) = 22
Пробег с грузом (Lг), общий пробег (Lо) и транспортная работа (Р) для развозочных маршрутов определяются по следующим формулам:
Lг=(10+8+3+1)+(2+1+3)+(6+6+2)=42 км
Lо=(10+8+3+1+8)+(2+1+3+4)+(6+6+2+10)=64 км
РА=10*4.64+8*0.25+3*4.75+1*1.87=64.52 ткм
РБ1=2*3.12+1*3.87+3*5.42=26.37 ткм
РБ2=6*3.41+6*3.72+2*4.08=50.94 ткм
Робщ=64.52+26.37+50.94=141.83 ткм
По результатам решения третьего и четвертого пунктов задания сформируем сводную таблицу, сделаем количественные и качественные выводы.
Таблица 4.33
Сравнение технико-эксплуатационных показателей
|
Показатель |
Пробег с грузом, км |
Общий пробег, км |
Транспортная работа, ткм |
|
После решения транспортной задачи |
72 |
144 |
252.26 |
|
После решения задачи маршрутизации |
42 |
64 |
141.83 |
Как можно сделать вывод из полученных данных, после решения задачи маршрутизации значительно уменьшился пробег с грузом (в 1.7 раз), общий пробег (в 2,25 раз) и транспортная работа в 1.78 раза. Можно сделать вывод о том, что кольцевые маршруты значительно уменьшают общий пробег и увеличивают транспортную работу по сравнению с маятниковыми.