Задачи такого типа известны под общим названием задача коммивояжёра, в «классической» формулировке которой коммивояжёр пытается определить кратчайший маршрут для одноразового посещения n городов. По существу, это задача является задачей о назначениях с дополнительными ограничениями, которые гарантируют исключение из оптимального решения неполных замкнутых маршрутов (в задаче коммивояжёра замкнутый маршрут, проходящий через каждый пункт только один раз, называется циклом цикл, проходящий через все пункты, называется полным, в противном случае – частичным или подциклом).
В задаче коммивояжёра с n городами можно определить такие переменный приведённые в формуле.
xij=0, если город j достижим изгорода i1, в противном случае
Имея значения Cij – расстояние от города i до города j (считается, что Cij=∞ при i=j), задачу коммивояжёра можно формализовать следующим образом
f=i=1nj=1ncjxij→(min)
При ограничениях, показанных в формулах
j=1nxij=1, i=1..ni=1nxij=1, j=1..nxij=0 или 1
Основные методы решения задачи коммивояжёра построены на тех же основах, что и методы ветвей и границ, и отсекающих плоскостей.
