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

Имеется n городов, пронумерованных числами 1, 2,..., n. Для любой пары городов (I, j) задано расстояние (время, путевые расходы) C(i, j) ³ 0 между ними. Поэтому в общем случае C(i, j) ¹ C(j, i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.

Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали I к обработке детали J. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программирования определим переменные следующим образом: = 1, если коммивояжер переезжает из I-го города в J-й; – в противном случае. Тогда задача заключается в отыскании значений переменных , удовлетворяющих следующим соотношениям:

(5.1)

При условиях

(въезд в город j); (5.2)

(выезд из города i); (5.3)

(I ¹ J); (5.4)

Xij = {0,1}, , целые, I = 1, ..., M, J = 1, ..., N. (5.5)

Ограничения (5.4) требуют, чтобы маршрут образовывал контур.

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

Допустимый маршрут Х представим как множество упорядоченных пар городов:

Х = .

Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (I, j) является дугой маршрута. Длина F(Х) маршрута Х равна сумме соответствующих элементов C(I, j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.

Обозначим через Матрицу расстояний. Чтобы запретить переезды вида (I, i), положим C(I, i) = +∞ (I = 1,…, N).

Пусть

.

Тогда – редуцированная матрица.

Пусть D(X) = – сумма констант редуцирования.

Тогда для любого маршрута

F(Х) = =

= + D(X) ≥ D(X) (5.6)

Неравенство (5.6) показывает, что D(X) является оценкой снизу для множества Х. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину D(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

< Предыдущая		Следующая >