Здавалка
Главная | Обратная связь

Задача коммивояжера



Сформулированная задача - задача целочисленная. Пусть х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. венгерский метод.

ПРИМЕР. В качестве начального маршрута выбирается любой, например, X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1). Оценка для этого маршрута равна F(X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Для определения нижней границы множества используют операцию редукции, для чего в каждой строке матрицы D находят минимальный элемент: di = min(j) dij

 

 

i j di
M
M
M
M
M
M


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

i j
M
M
M
M
M
M


Такую же операцию редукции проводят по столбцам: dj = min(i) dij

i j
M
M
M
M
M
M
dj


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

i j
M
M
M
M
M
M


Сумма констант приведения определяет нижнюю границу H = ∑di + ∑dj = 9+52+13+17+8+10+0+20+0+5+0+0 = 134. Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Длина маршрута определяется выражением: F(Mk) = ∑dij. Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.

Затем в ходе последующих итераций, определяется ребро ветвлений. Все множество маршрутов относительно этого ребра разбивается на два подмножества (i,j) и (i*,j*).

 

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.