Задача коммивояжера в коммерческой деятельности

В коммерческой деятельности коммерсанты, торговые агенты постоянно проводят работу по поиску партнеров или клиентов для заключения договоров на поставку и покупку товаров. Для решения этих задач коммерсантам необходимо выезжать в командировки, выполнять вояж по целой сети городов как по нашей стране, так и за рубежом. Поскольку продолжительность командировки и транспортные расходы следует сокращать, то необходимо перед поездкой составить кратчайший маршрут, предусматривающий посещение каждого пункта только один раз, и возвращение обратно. Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.
Постановка задачи. Пусть имеется 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

Перейти к онлайн решению своей задачи

загрузка...