Решение задачи коммивояжера методом ветвей и границ

Решение задачи коммивояжера методом ветвей и границ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.

Общий план решения задачи коммивояжера

Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):

  1. Построение матрицы с исходными данными.
  2. Нахождение минимума по строкам.
  3. Редукция строк.
  4. Нахождение минимума по столбцам.
  5. Редукция столбцов.
  6. Вычисление оценок нулевых клеток.
  7. Редукция матрицы.
  8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
  9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4. Нахождение минимума по столбцам

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути, ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Читайте также:  Как сделать нормальное расширение экрана

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута

Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.

В нашем примере маршрут получился следующий: 42314.

Общая длина пути: L = 30.

Практическое применение задачи коммивояжера

Применение задачи коммивояжера на практике довольно обширно. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.

Решение задачи коммивояжера онлайн

Иногда бывает необходимо быстро просчитать какой-либо вариант для этой задачи или проверить правильность решения. На этот случай я создал сервис для решения задачи коммивояжера онлайн. Воспользоваться им можно перейдя по приведенной здесь ссылке.

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

Пригодилась статья? Поделитесь с друзьями:

Библиографическая запись для цитирования статьи по ГОСТ Р 7.0.5-2008:
Галяутдинов Р.Р. Задача коммивояжера — метод ветвей и границ // Сайт преподавателя экономики. [2013]. URL: http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 15.03.2020).

Нашли опечатку? Помогите сделать статью лучше! Выделите орфографическую ошибку мышью и нажмите Ctrl+Enter.

ФОРМУЛЫ —> ТЕРМИНЫ —> БУХУЧЕТ —> НАЛОГИ —> СТАТИСТИКА —> БИОГРАФИИ —> ЗАДАЧИ —> ENGLISH —>

ГАЛЯУТДИНОВ
Руслан Рамилевич

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

Пример решения задачи коммивояжера

Решение будем вести с использованием калькулятора. Возьмем в качестве произвольного маршрута:
X= (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di= min(j) dij

i j 1 2 3 4 5 di 1 M 90 80 40 100 40 2 60 M 40 50 70 40 3 50 30 M 60 20 20 4 10 70 20 M 50 10 5 20 40 50 20 M 20

Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j 1 2 3 4 5
1 M 50 40 60
2 20 M 10 30
3 30 10 M 40
4 60 10 M 40
5 20 30 M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj= min(i) dij

i j 1 2 3 4 5
1 M 50 40 60
2 20 M 10 30
3 30 10 M 40
4 60 10 M 40
5 20 30 M
dj 10

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.

i j 1 2 3 4 5
1 M 40 40 60
2 20 M 10 30
3 30 M 40
4 50 10 M 40
5 10 30 M

Сумма констант приведения определяет нижнюю границу H:
H = ∑di+ ∑dj
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы dijсоответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij>=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j 1 2 3 4 5 di
1 M 40 40 0(40) 60 40
2 20 M 0(20) 10 30 10
3 30 0(10) M 40 0(30)
4 0(10) 50 10 M 40 10
5 0(0) 10 30 0(0) M
dj 10 10 30

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d14= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j 1 2 3 4 5 di
1 M 40 40 M 60 40
2 20 M 10 30
3 30 M 40
4 50 10 M 40
5 10 30 M
dj 40

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:

i j 1 2 3 5 di
2 20 M 30
3 30 M
4 M 50 10 40 10
5 10 30 M
dj 10

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j 1 2 3 5 di
2 20 M 0(20) 30 20
3 30 0(10) M 0(30)
4 M 40 0(30) 30 30
5 0(30) 10 30 M 10
dj 20 10 30

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d35= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i j 1 2 3 5 di
2 20 M 30
3 30 M M
4 M 40 30
5 10 30 M
dj 30 30

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 10
После операции приведения сокращенная матрица будет иметь вид:

i j 1 2 3 di
2 20 M
4 M 40
5 10 M
dj 10 10

Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3.
Определяем ребро ветвленияи разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j 1 2 3 di
2 20 M 0(20) 20
4 M 30 0(30) 30
5 0(20) 0(30) M
dj 20 30

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d52= 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j 1 2 3 di
2 20 M
4 M 30
5 M M
dj 30 30

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 20
После операции приведения сокращенная матрица будет иметь вид:

i j 1 3 di
2 20
4 M
dj 20 20

Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180

Пример №2 . Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов A1, A2,…, A6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Ai до Aj. Элемент матрицы aij считается равным расстоянию от Ai до Aj.

A 1 A 2 A 3 A 4 A 5 A 6
A 1 c+2 2c c+3 2c c+1
A 2 c c+5 c-1 c-1 3c
A 3 c c+1 c+7 c+2 c+3
A 4 c-1 c+2 c c+1 c-1
A 5 c+5 c+2 c c 2c
A 6 c c+1 c+2 c+5 c+7

где с = m + n

Решение. Возьмем в качестве произвольного маршрута: X= (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X) = 4 + 7 + 9 + 3 + 4 + 2 = 29
Для определения нижней границы множества воспользуемся операцией редукцииили приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di= min(j) dij

i j 1 2 3 4 5 6 di
1 M 4 4 5 4 3 3
2 2 M 7 1 1 6 1
3 2 3 M 9 4 5 2
4 1 3 2 M 3 1 1
5 7 4 1 1 M 4 1
6 2 3 4 7 9 M 2

Посмотреть все итерации
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(2,5), (5,4), (4,6), (6,3), (3,1), (1,2)
Длина маршрута равна F(Mk) = 13
Решение

Пример №3 . Рассмотрим пример решения задачи с помощью сервиса задачи коммивояжера .

Возьмем в качестве произвольного маршрута: X = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X) = 10 + 11 + 3 + 12 + 14 + 17 = 67

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.

di = min(j) dij

i j 1 2 3 4 5 6 di
1 M 10 5 9 16 8 5
2 6 M 11 8 18 19 6
3 7 13 M 3 4 14 3
4 5 9 6 M 12 17 5
5 5 4 11 6 M 14 4
6 17 7 12 13 16 M 7

Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j 1 2 3 4 5 6
1 M 5 4 11 3
2 M 5 2 12 13
3 4 10 M 1 11
4 4 1 M 7 12
5 1 7 2 M 10
6 10 5 6 9 M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj= min(i) dij

i j 1 2 3 4 5 6
1 M 5 4 11 3
2 M 5 2 12 13
3 4 10 M 1 11
4 4 1 M 7 12
5 1 7 2 M 10
6 10 5 6 9 M
dj 1 3

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.

i j 1 2 3 4 5 6
1 M 5 4 10
2 M 5 2 11 10
3 4 10 M 8
4 4 1 M 6 9
5 1 7 2 M 7
6 10 5 6 8 M

Сумма констант приведения определяет нижнюю границу H: H = ∑di+ ∑dj = H = 5+6+3+5+4+7+0+0+0+0+1+3 = 34

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

Длина маршрута равна F(Mk) = 38

Пример №4 . Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Задана матрица расстояний между городами cij.

Решение проводим с помощью калькулятора Решение задачи коммивояжера . Возьмем в качестве произвольного маршрута: X = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,1)
Тогда F(X) = 20 + 20 + 16 + 9 + 21 + 18 + 12 = 116

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом.

  • Решение онлайн
  • Видеоинструкция
  • Оформление Word
Ссылка на основную публикацию
Регулятор громкости для автомагнитолы
Бывший хозяин видимо пытаясь снять магнитолу за рукоятку громкости, сломал её. В результате громкость не регулировалась, а отпаявшиеся контакты энкодера...
Работа с far manager
Фар менеджер - один из самых удобных файловых менеджеров, рассчитанный на работу с файлами и папками на дисках, прежде всего,...
Работа с классами python
Серия контента: Этот контент является частью # из серии # статей: Этот контент является частью серии: Следите за выходом новых...
Регулярные выражения perl примеры
Regular expressions, или регулярные выражения - способ определения символьной маски для последующего сравнения с ней строки символов или для обработки...
Adblock detector