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

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.

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

Инструкция. Выберите размерность матрицы (количество городов). Полученное онлайн решение сохраняется в файле Word и Excel (см. примеры решений задачи коммивояжера).
Количество городов

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть хij=1, если путешественник переезжает из i-ого города в j-ый и хij=0, если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u1=0, un+1=n. Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные xij и переменные ui (ui целые неотрицательные числа).


ui-uj+nxij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤ui≤n, xin+1=xi1, i=2..n

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

  1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ;
  2. венгерский метод. Пример решения венгерским методом.

Алгоритм Литтла или исключения подциклов

  1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент dmin и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑dmin.
  2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент dmin, и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑dmin.
  3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
  4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
  5. Выбирают дугу (i,j), для которой степень нулевого элемента достигает максимального значения.
  6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*). Для получения матрицы контуров, включающих дугу (i,j), вычеркивают в матрице строку i и столбец j. Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
  7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*).
  8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*). Если H(i,j)<H(i*,j*), то дальнейшему ветвлению в первую очередь подлежит множество (i,j), иначе - разбиению подлежит множество (i*,j*).
  9. Если в результате ветвлений получается матрица (2x2), то определяют полученный ветвлением гамильтонов контур и его длину.
  10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример. Решить по алгоритму Литтла задачу коммивояжера с матрицей

1234
1-587
25-615
386-10
471510-

Решение. Возьмем в качестве произвольного маршрута: X0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: di = min(j) dij
i j12345di
1M20181288
25M147115
31218M6116
4111711M1211
55555M5
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j12345
1M121040
20M926
3612M05
4060M1
50000M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i j12345
1M121040
20M926
3612M05
4060M1
50000M
dj00000
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j12345
1M121040
20M926
3612M05
4060M1
50000M
Сумма констант приведения определяет нижнюю границу H: H = ∑di + ∑dj = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j12345di
1M121040(5)4
20(2)M9262
3612M0(5)55
40(0)60(0)M10
50(0)0(6)0(0)0(0)M0
dj060010
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j12345di
1M1210400
20M9260
3612M050
4060M10
50M00M0
dj060006
Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j1345di
1M10400
2092M0
36M050
400M10
dj00000
Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0
Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j1345di
1M1040(5)4
20(2)92M2
36M0(7)55
40(0)0(9)M10
dj09210
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
i j1345di
1M10400
2092M0
36M050
40MM10
dj09009
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d34 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j145di
1M400
202M0
36M55
dj0207
Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X1.
План X1.
i j12345
1M121040
20M926
3612M05
4060M1
50M00M
Операция редукции.
i j12345
1M61040
20M926
366M05
4000M1
50M00M
Шаг №1.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j12345di
1M61040(5)4
20(2)M9262
366M0(5)55
40(0)0(6)0(0)M10
50(0)M0(0)0(0)M0
dj060010
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.
i j12345di
1M610400
20M9260
366M050
40M0M10
50M00M0
dj060006
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j1345di
1M10400
209M60
36M050
5000M0
dj00000
Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j1345di
1M1040(9)4
20(6)9M66
36M0(5)55
50(0)0(9)0(0)M0
dj09050
d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.
i j1345di
1M104M4
209M60
36M050
5000M0
dj00059
Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j134di
209M0
36M00
5M000
dj0000
Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j134di
20(15)9M9
36M0(6)6
5M0(9)0(0)0
dj6900
d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
i j134di
2M9M9
36M00
5M000
dj60015
Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j34di
3M00
5000
dj000
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

 1
Начало
 
                                              
     
 (5*,2*), H=41
 (5,2)
H = 35
 
                            
         
(4*,2*), H=47
 (4,2)
H = 41
 (4*,3*), H=44
 (4,3)
H = 42
                   
     
 (1*,5*), H=50
 (1,5)
H = 41
 
                    
     
 (2*,1*), H=56
 (2,1)
H = 41
 
              
     
 (3,4)
H = 41
 (3*,4*), H=41
 
          
     
 (5,3)
H = 41
 (5*,3*), H=41
 
 
Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект