Задача коммивояжера в коммерческой деятельности
В коммерческой деятельности коммерсанты, торговые агенты постоянно проводят работу по поиску партнеров или клиентов для заключения договоров на поставку и покупку товаров. Для решения этих задач коммерсантам необходимо выезжать в командировки, выполнять вояж по целой сети городов как по нашей стране, так и за рубежом. Поскольку продолжительность командировки и транспортные расходы следует сокращать, то необходимо перед поездкой составить кратчайший маршрут, предусматривающий посещение каждого пункта только один раз, и возвращение обратно. Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.Постановка задачи. Пусть имеется 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.
Использование задачи коммивояжера в жилищно-коммунальном хозяйстве
Задача коммивояжера (или задача кольцевого маршрута) используется в тех случаях, когда необходимо с совершить обход некоторых объектов с минимальными затратами. Затраты в этом случае могут выражаться как в стоимостном выражении (рубли), так и временном (часы). Особенностью решения задачи коммивояжера является кольцевое движение по определнному маршруту с посещением каждого пункта только один раз. Например, если необходимо посетить 5 объектов, то начать можно с любого из них, но обход будет совершаться последовательно. В коммунальном хозяйстве использовать решение задачи коммивояжера могут службы обслуживания населения, там, где необходимо совершать обход населения: опломбирование счетчиков воды, текущие ремонты и др. В этом случае минимизировать можно будет как стоимостные затраты, временные, или комбинированные.Рассмотрим пример решения задачи коммивояжера с помощью калькулятора.
Возьмем в качестве произвольного маршрута:
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
Перейти к онлайн решению своей задачи
Фомин г. П. Математические методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2005. — 616 с: ил.
