Задача коммивояжера в коммерческой деятельности
В коммерческой деятельности коммерсанты, торговые агенты постоянно проводят работу по поиску партнеров или клиентов для заключения договоров на поставку и покупку товаров. Для решения этих задач коммерсантам необходимо выезжать в командировки, выполнять вояж по целой сети городов как по нашей стране, так и за рубежом. Поскольку продолжительность командировки и транспортные расходы следует сокращать, то необходимо перед поездкой составить кратчайший маршрут, предусматривающий посещение каждого пункта только один раз, и возвращение обратно. Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.Постановка задачи. Пусть имеется n городов. Расстояния между любой парой городов (i, j) известны и составляют dij где i=1,m; j=1,n, Если прямого маршрута сообщения между городами не существует, а также для всех i =j полагаем, что dij = ∞. На этом основании расстояния между городами удобно представить в виде матрицы D = (dij)nxn. Если городам поставить в соответствие вершины графа, а соединяющим их дорогам ребра, то в терминах теории графов задача заключается в определении гамильтонова цикла минимальной длины. Гамильтонов цикл включает все вершины графа ровно один раз, причем начальная вершина совпадает с конечной, а длина определяется суммой длин всех ребер. Таким образом, необходимо построить кольцевой маршрут проезда всех городов минимальной длины, начиная с любого пункта и в любую сторону.
Поскольку всего городов п, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько — оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т. е. dij = dji. Расстояния между городами запишем в виде матрицы D. Если в задаче n городов, то D является матрицей размером (nхn) с неотрицательными элементами dij ≥0, которые отображают длины ребер в сети городов. Так, при n = 5 количество возможных вариантов маршрутов равно (5-1)! = 24.
Фомин г. П. Математические методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2005. — 616 с: ил.
Рассмотрим пример решения задачи коммивояжера с помощью калькулятора.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 13 + 13 + 12 + 19 + 6 + 14 = 77
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
1 |
M |
13 |
8 |
5 |
10 |
10 |
5 |
|
2 |
21 |
M |
13 |
10 |
16 |
11 |
10 |
|
3 |
7 |
14 |
M |
12 |
15 |
14 |
7 |
|
4 |
6 |
10 |
10 |
M |
19 |
6 |
6 |
|
5 |
9 |
13 |
14 |
16 |
M |
6 |
6 |
|
6 |
14 |
10 |
14 |
7 |
6 |
M |
6 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
M |
8 |
3 |
0 |
5 |
5 |
|
2 |
11 |
M |
3 |
0 |
6 |
1 |
|
3 |
0 |
7 |
M |
5 |
8 |
7 |
|
4 |
0 |
4 |
4 |
M |
13 |
0 |
|
5 |
3 |
7 |
8 |
10 |
M |
0 |
|
6 |
8 |
4 |
8 |
1 |
0 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
M |
8 |
3 |
0 |
5 |
5 |
|
2 |
11 |
M |
3 |
0 |
6 |
1 |
|
3 |
0 |
7 |
M |
5 |
8 |
7 |
|
4 |
0 |
4 |
4 |
M |
13 |
0 |
|
5 |
3 |
7 |
8 |
10 |
M |
0 |
|
6 |
8 |
4 |
8 |
1 |
0 |
M |
|
dj |
0 |
4 |
3 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
M |
4 |
0 |
0 |
5 |
5 |
|
2 |
11 |
M |
0 |
0 |
6 |
1 |
|
3 |
0 |
3 |
M |
5 |
8 |
7 |
|
4 |
0 |
0 |
1 |
M |
13 |
0 |
|
5 |
3 |
3 |
5 |
10 |
M |
0 |
|
6 |
8 |
0 |
5 |
1 |
0 |
M |
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 5+10+7+6+6+6+0+4+3+0+0+0 = 47
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
1 |
M |
4 |
0(0) |
0(0) |
5 |
5 |
0 |
|
2 |
11 |
M |
0(0) |
0(0) |
6 |
1 |
0 |
|
3 |
0(3) |
3 |
M |
5 |
8 |
7 |
3 |
|
4 |
0(0) |
0(0) |
1 |
M |
13 |
0(0) |
0 |
|
5 |
3 |
3 |
5 |
10 |
M |
0(3) |
3 |
|
6 |
8 |
0(0) |
5 |
1 |
0(5) |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
d(1,3) = 0 + 0 = 0; d(1,4) = 0 + 0 = 0; d(2,3) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(3,1) = 3 + 0 = 3; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,6) = 3 + 0 = 3; d(6,2) = 0 + 0 = 0; d(6,5) = 0 + 5 = 5;
Наибольшая сумма констант приведения равна (0 + 5) = 5 для ребра (6,5), следовательно, множество разбивается на два подмножества (6,5) и (6*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,5*) = 47 + 5 = 52
Исключение ребра (6,5) проводим путем замены элемента d65 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,5*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
1 |
M |
4 |
0 |
0 |
5 |
5 |
0 |
|
2 |
11 |
M |
0 |
0 |
6 |
1 |
0 |
|
3 |
0 |
3 |
M |
5 |
8 |
7 |
0 |
|
4 |
0 |
0 |
1 |
M |
13 |
0 |
0 |
|
5 |
3 |
3 |
5 |
10 |
M |
0 |
0 |
|
6 |
8 |
0 |
5 |
1 |
M |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
5 |
0 |
5 |
Включение ребра (6,5) проводится путем исключения всех элементов 6-ой строки и 5-го столбца, в которой элемент d56 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 3
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
1 |
M |
4 |
0 |
0 |
5 |
0 |
|
2 |
11 |
M |
0 |
0 |
1 |
0 |
|
3 |
0 |
3 |
M |
5 |
7 |
0 |
|
4 |
0 |
0 |
1 |
M |
0 |
0 |
|
5 |
3 |
3 |
5 |
10 |
M |
3 |
|
dj |
0 |
0 |
0 |
0 |
0 |
3 |
Нижняя граница подмножества (6,5) равна:
H(6,5) = 47 + 3 = 50 < 52
Поскольку нижняя граница этого подмножества (6,5) меньше, чем подмножества (6*,5*), то ребро (6,5) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
1 |
M |
4 |
0(0) |
0(0) |
5 |
0 |
|
2 |
11 |
M |
0(0) |
0(0) |
1 |
0 |
|
3 |
0(3) |
3 |
M |
5 |
7 |
3 |
|
4 |
0(0) |
0(0) |
1 |
M |
0(1) |
0 |
|
5 |
0(0) |
0(0) |
2 |
7 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
1 |
0 |
d(1,3) = 0 + 0 = 0; d(1,4) = 0 + 0 = 0; d(2,3) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(3,1) = 3 + 0 = 3; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 0 = 0; d(4,6) = 0 + 1 = 1; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (3 + 0) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,1*) = 50 + 3 = 53
Исключение ребра (3,1) проводим путем замены элемента d31 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,1*), в результате получим редуцированную матрицу.
|
i j |
1 |
2 |
3 |
4 |
6 |
di |
|
1 |
M |
4 |
0 |
0 |
5 |
0 |
|
2 |
11 |
M |
0 |
0 |
1 |
0 |
|
3 |
M |
3 |
M |
5 |
7 |
3 |
|
4 |
0 |
0 |
1 |
M |
0 |
0 |
|
5 |
0 |
0 |
2 |
7 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
0 |
3 |
Включение ребра (3,1) проводится путем исключения всех элементов 3-ой строки и 1-го столбца, в которой элемент d13 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
2 |
3 |
4 |
6 |
di |
|
1 |
4 |
M |
0 |
5 |
0 |
|
2 |
M |
0 |
0 |
1 |
0 |
|
4 |
0 |
1 |
M |
0 |
0 |
|
5 |
0 |
2 |
7 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
0 |
Нижняя граница подмножества (3,1) равна:
H(3,1) = 50 + 0 = 50 < 53
Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
2 |
3 |
4 |
6 |
di |
|
1 |
4 |
M |
0(4) |
5 |
4 |
|
2 |
M |
0(1) |
0(0) |
1 |
0 |
|
4 |
0(0) |
1 |
M |
0(1) |
0 |
|
5 |
0(2) |
2 |
7 |
M |
2 |
|
dj |
0 |
1 |
0 |
1 |
0 |
d(1,4) = 4 + 0 = 4; d(2,3) = 0 + 1 = 1; d(2,4) = 0 + 0 = 0; d(4,2) = 0 + 0 = 0; d(4,6) = 0 + 1 = 1; d(5,2) = 2 + 0 = 2;
Наибольшая сумма констант приведения равна (4 + 0) = 4 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 50 + 4 = 54
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
|
i j |
2 |
3 |
4 |
6 |
di |
|
1 |
4 |
M |
M |
5 |
4 |
|
2 |
M |
0 |
0 |
1 |
0 |
|
4 |
0 |
1 |
M |
0 |
0 |
|
5 |
0 |
2 |
7 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
4 |
Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
2 |
3 |
6 |
di |
|
2 |
M |
0 |
1 |
0 |
|
4 |
0 |
1 |
0 |
0 |
|
5 |
0 |
2 |
M |
0 |
|
dj |
0 |
0 |
0 |
0 |
Нижняя граница подмножества (1,4) равна:
H(1,4) = 50 + 0 = 50 < 54
Чтобы исключить подциклы, запретим следующие переходы: (4,3).
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
|
i j |
2 |
3 |
6 |
di |
|
2 |
M |
0(3) |
1 |
1 |
|
4 |
0(0) |
M |
0(1) |
0 |
|
5 |
0(2) |
2 |
M |
2 |
|
dj |
0 |
2 |
1 |
0 |
d(2,3) = 1 + 2 = 3; d(4,2) = 0 + 0 = 0; d(4,6) = 0 + 1 = 1; d(5,2) = 2 + 0 = 2;
Наибольшая сумма констант приведения равна (1 + 2) = 3 для ребра (2,3), следовательно, множество разбивается на два подмножества (2,3) и (2*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,3*) = 50 + 3 = 53
Исключение ребра (2,3) проводим путем замены элемента d23 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,3*), в результате получим редуцированную матрицу.
|
i j |
2 |
3 |
6 |
di |
|
2 |
M |
M |
1 |
1 |
|
4 |
0 |
M |
0 |
0 |
|
5 |
0 |
2 |
M |
0 |
|
dj |
0 |
2 |
0 |
3 |
Включение ребра (2,3) проводится путем исключения всех элементов 2-ой строки и 3-го столбца, в которой элемент d32 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
|
i j |
2 |
6 |
di |
|
4 |
0 |
0 |
0 |
|
5 |
0 |
M |
0 |
|
dj |
0 |
0 |
0 |
Нижняя граница подмножества (2,3) равна:
H(2,3) = 50 + 0 = 50 < 53
Поскольку нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (5,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(6,5), (5,2), (2,3), (3,1), (1,4), (4,6),
Длина маршрута равна F(Mk) = 50