ЗАДАЧА КОММИВОЯЖЕРА

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

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

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

Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных , если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений:

(4)

Условия (5) – (7) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (5), (6) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (5)), и один раз из него выехав (ограничение (6)).

Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (5)–(7) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла.

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

, где , и .

Ограничения (5)-(7) соответствуют ограничениям задачи о назначениях, которая отличается от задачи коммивояжера отсутствием требования цикличности пути.

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