Задача коммивояжера. Примеры решения задач онлайн

Примеры решений задачи коммивояжера разными методами с подробным объяснением. Сервис решения онлайн. Качественное решение на заказ от 150 рублей.

Заказать решение

Если вам нужна помощь с решением оптимизационных задач дискретной математики (задача коммивояжера, задача о ранце, задача раскроя или выбора пути), обращайтесь в МатБюро. Стоимость от 200 рублей, оформление производится в Word, срок от 2 дней.

Заказать решение задач по комбинаторной оптимизации

Города и расстояния

Допустим, у нас есть 5 городов, каждый из которых соединён с другим:

Решаем задачу коммивояжёра простым перебором

Из-за рельефа местности близкие города не всегда соединены по прямой, но для простоты мы нарисовали так. Теперь проставим время, которое требуется для переезда из города в город:

Решаем задачу коммивояжёра простым перебором

Чтобы было удобно пользоваться расстояниями, сделаем табличку:

Решаем задачу коммивояжёра простым перебором

Нулевые ячейки означают, что здесь нет маршрута, потому что это путь из одного и того же города и обратно. Остальные числа — это расстояния между городами. Например, расстояние между первым и третьим городом — 6 километров, а между четвёртым и вторым — 10 километров.

На языке JavaScript это будет выглядеть так:

// таблица с расстояниями между городамиvar towns = [ [0, 5, 6, 14, 15], [5, 0, 7, 10, 6], [6, 7, 0, 8, 7], [14, 10, 8, 0, 9], [15, 6, 7, 9, 0]];

Задача

Найдем кратчайший путь между 5 городами, координаты которых известны. Рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.

Формальное определение

Представление в виде графа

Симметричная задача для четырёх городов.

Симметричная задача для четырёх городов.

Для возможности применения математического аппарата для решения задачи её следует представить в виде математической модели. Задачу коммивояжёра можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а рёбра (i,j){displaystyle left(i,jright)}left(i,jright) между вершинами i{displaystyle i}i и j{displaystyle j}j — пути сообщения между этими городами. Каждому ребру (i,j){displaystyle left(i,jright)}left(i,jright) можно сопоставить критерий выгодности маршрута cij⩾0{displaystyle c_{ij}geqslant 0}c_{ij}geqslant 0, который можно понимать как, например, расстояние между городами, время или стоимость поездки.

Гамильтоновым циклом называется маршрут, включающий ровно по одному разу каждую вершину графа.

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

Таким образом, решение задачи коммивояжёра — это нахождение гамильтонова цикла минимального веса в полном взвешенном графе.

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

Асимметричная и симметричная задачи

В общем случае, асимметричная задача коммивояжёра отличается тем, что она моделируется ориентированным графом. Таким образом, следует также учитывать, в каком направлении находятся ребра.

В случае симметричной задачи все пары ребер между одними и теми же вершинами имеют одинаковую длину, то есть, для ребра (i,j){displaystyle left(i,jright)}left(i,jright) одинаковы длины cij=cji{displaystyle c_{ij}=c_{ji}}c_{ij}=c_{ji}. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая. Симметричная задача моделируется неориентированным графом (см. рисунок).

На самом деле, задача коммивояжёра в случае реальных городов может быть как симметричной, так и асимметричной в зависимости от длительности или длины маршрутов и от направления движения.

Метрическая задача

Симметричную задачу коммивояжёра называют метрической, если относительно длин ребер выполняется неравенство треугольника. Условно говоря, в таких задачах обходные пути длиннее прямых, то есть ребро от вершины i{displaystyle i}i до вершины j{displaystyle j}j никогда не бывает длиннее пути через промежуточную вершину k{displaystyle k}k:

cij⩽cik+ckj{displaystyle c_{ij}leqslant c_{ik}+c_{kj}}c_{ij}leqslant c_{ik}+c_{kj}.

Такое свойство длины ребер определяет измеримое пространство на множестве ребер и меру расстояния, удовлетворяющую интуитивному пониманию расстояния.

Распространенные на практике функции расстояния являются также метриками и удовлетворяют неравенству треугольника:

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

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

Неметрическая задача коммивояжёра может возникать, например, в случае минимизации длительности пребывания при наличии выбора транспортных средств в различных направлениях. В таком случае обходной путь самолетом может быть короче прямого сообщения автомобилем.

Если на практике в условиях задачи разрешается посещать города несколько раз, то симметричную задачу можно свести к метрической. Для этого задачу рассматривают на так называемом графе расстояний. Этот граф имеет такое же множество вершин, как и исходный, и является полностью связным. Длина рёбер cij{displaystyle c_{ij}}c_{ij} между вершинами i{displaystyle i}i и j{displaystyle j}j на графе расстояний соответствует длине кратчайшего расстояния между вершинами i{displaystyle i}i и j{displaystyle j}j в исходном графе. Для определенных таким образом длин cij{displaystyle c_{ij}}c_{ij} выполняется неравенство треугольника, и каждому маршруту на графе расстояний всегда соответствует маршрут с возможными повторениями вершин в исходном графе.

Формулировка в виде задачи дискретной оптимизации

Одним из подходов к решению задачи является формулировка её в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер V{displaystyle V}V. Каждому ребру {i,j}{displaystyle {i,j}}{i,j} сопоставляется двоичная переменная xij∈{0,1}{displaystyle x_{ij}in {0,1}}x_{ij}in {0,1}, равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства.

Условие кратности: каждая вершина должна иметь одно входное и одно выходное ребро маршрута.

Условие кратности: каждая вершина должна иметь одно входное и одно выходное ребро маршрута.

Каждая вершина должна сообщаться через пару ребер с остальным вершинам, то есть, через входное и выходное ребро:

∀i∈V,∑j∈V∖{i}xij=2(1){displaystyle forall iin V,;sum _{jin Vsetminus {i}}x_{ij}=2qquad (1)}forall iin V,;sum _{jin Vsetminus {i}}x_{ij}=2qquad (1)

В сумме каждое слагаемое xij{displaystyle x_{ij}}x_{ij} равно или 1 (принадлежит маршруту) или 0 (не принадлежит). То есть, полученная сумма равна количеству ребер в маршруте, имеющих вершину i{displaystyle i}i на одном из концов. Она равна 2, так как каждая вершина имеет входное и выходное ребро. В приведенном рядом рисунке вершина i{displaystyle i}i показана с входным и выходными ребрами, а ребра маршрута обозначены толстыми линиями. Рядом с ребрами указаны длины xij{displaystyle x_{ij}}x_{ij}, прилагаемые к указанной выше сумме.

Циклы: переменные удовлетворяют условию кратности, но не определяют маршрут.

Циклы: переменные удовлетворяют условию кратности, но не определяют маршрут.

Описанные ранее условия кратности выполняются не только маршрутами, но и значениями переменных, соответствующих отдельным циклам, где каждая вершина принадлежит лишь одному циклу (см. рисунок). Чтобы избежать подобных случаев, должны выполняться так называемые неравенства циклов (или условия устранения подмаршрутов), которые были определены Данцигом, Фалкерсоном и Джонсоном в 1954 году под названием условия петель (англ. loop conditions). Этими неравенствами определялось дополнительное условие того, что каждое множество вершин S⊂V{displaystyle Ssubset V}Ssubset V является либо пустым, либо содержит все вершины, сочетающееся с остальным вершинам через минимум два ребра:

∑i∈S,j∉Sxij⩾2(2){displaystyle sum _{iin S,;jnotin S}x_{ij}geqslant 2qquad (2)}sum _{iin S,;jnotin S}x_{ij}geqslant 2qquad (2)

для всех множеств вершин S{displaystyle S}S, где 1⩽|S|⩽|V|−1{displaystyle 1leqslant |S|leqslant |V|-1}1leqslant |S|leqslant |V|-1. Эта сумма равна сумме длин ребер маршрута между вершиной i∈S{displaystyle iin S}iin S и вершиной j∉S{displaystyle jnotin S}jnotin S. Чтобы устранить лишние неравенства, можно ограничиться множествами вершин S{displaystyle S}S с минимум двумя и максимум |V|−2{displaystyle |V|-2}|V|-2 вершинами. На рисунке рядом ребра {i,j}{displaystyle {i,j}}{i,j} с длинами xij=1{displaystyle x_{ij}=1}x_{ij}=1 обозначены толстыми линиями, остальные ребра имеют длину xij=0{displaystyle x_{ij}=0}x_{ij}=0. Введение дополнительных условий (2) для множества вершин S{displaystyle S}S, состоящего из трех левых вершин, будет гарантировать, что S{displaystyle S}S сочетается через минимум два ребра маршрута с тремя вершинами справа, чтобы устранить оба цикла. Количество неравенств устранения циклов согласно Данцигу, Фалкерсону и Джонсону равняется 2n−2(n−1){displaystyle 2^{n}-2(n-1)}2^{n}-2(n-1).

В 1960 году Миллер, Такер и Землин изобрели альтернативные условия устранения подмаршрутов путём введения n{displaystyle n}n новых переменных, определяющих порядок посещенных городов, требующих только n2−n+1{displaystyle n^{2}-n+1}n^{2}-n+1 дополнительных неравенств. Более того, из-за двойственности xij{displaystyle x_{ij}}x_{ij} в формулировках Миллера, Такера и Землина задача коммивояжёра остается NP-сложной.

Так, каждый вектор с элементами, равными 0 и 1, удовлетворяющий всем неравенствам, определяет корректный маршрут, который является решением переформулированной задачи коммивояжёра: вычислить

min{∑i∈V∑j∈V∖{i}cijxij|x valid (1) (2),xij∈{0,1}}.(3){displaystyle min ;left{sum _{iin V}sum _{jin Vsetminus {i}}c_{ij}x_{ij};|;x{mbox{ valid (1) (2),}};x_{ij}in {0,1}right}.qquad (3)}min ;left{sum _{iin V}sum _{jin Vsetminus {i}}c_{ij}x_{ij};|;x{mbox{ valid (1) (2),}};x_{ij}in {0,1}right}.qquad (3)

Поскольку переменные xij{displaystyle x_{ij}}x_{ij} имеют значения только 0 и 1, сумма равна общей длине cij{displaystyle c_{ij}}c_{ij} ребер {i,j}{displaystyle {i,j}}{i,j}, принадлежащих маршруту.

Количество неравенств типа (2) растет экспоненциально по мере увеличения количества городов, поскольку почти каждое из 2|V|{displaystyle 2^{|V|}}2^{|V|} подмножеств узлов определяет одно неравенство. Эту задачу можно решить применением метода отсечения плоскостью, благодаря которому неравенства добавляются, только когда эти неравенства действительно необходимы. С геометрической точки зрения, линейные неравенства можно представить как гиперплоскости в пространстве переменных. Множество векторов, удовлетворяющих этим неравенствам, образуют в таком пространстве политоп (многомерный многогранник), или многомерный многоугольник, точная форма определяется длинами cij{displaystyle c_{ij}}c_{ij} и является в основном неизвестной. Однако, можно показать, что условия (1) и (2) определяют грани (фацет) политопа, то есть боковые поверхности политопа с наивысшей размерностью. Поэтому они относятся к самым сильным линейным неравенствам, которые могут описывать маршрут. Также существует много разных граней, определяемых неравенствами, известными лишь в немногих случаях. Хотя (1) и (2) вместе с ограничениями полностью моделируют задачу только для двоичных векторов, эти неравенства могут использоваться в методе ветвей и границ, чтобы отбросить решения методами линейной оптимизации с нецелыми координатами (см. раздел точные методы ниже).

Логика работы

Наша задача — найти такой маршрут, в котором сумма километров будет минимальной. 

Скрипт полного перебора будет работать так:

  1. С помощью 5 вложенных циклов мы сможем перебрать все варианты маршрутов. 
  2. В каждом цикле проходим от 0 до 4, потому что у нас 5 городов. Если бы у нас было 10 городов, нам нужно было бы сделать 10 вложенных циклов и в каждом цикле проходить от 0 до 9, чтобы перебрать все возможные расстояния для этого города.
  3. На каждом шаге проверяем, чтобы у нас не повторялись города в маршруте, потому что в каждом можно побывать только один раз.
  4. Если это условие выполняется, то запоминаем очередной маршрут и считаем его длину. 
  5. Если длина получилась меньше, чем наименьшая до этого — значит, сейчас у нас получился самый короткий маршрут. Возможно, на следующих шагах цикла мы найдём маршрут ещё короче, но пока минимальный — этот. Делаем эту длину наименьшей и запоминаем номер маршрута.
  6. Так прогоняем все комбинации городов.
  7. Выводим найденный минимальный маршрут и его длину.

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

Задача 1. Решите методом ветвей и границ следующую задачу коммивояжера

Задача 2. Решите методом ветвей и границ задачу коммивояжера

Задача 3.Решить задачу коммивояжёра по алгоритму Литтла:

Задача 4. Для задачи коммивояжера задана матрица расстояний между городами. Вычислить длину маршрута (4,3,2,1,4)

Задача 5. Решить задачу коммивояжера в Excel:

Решение

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).

likbezpng-solver72.pnglikbezpng-solver73.png

Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$F7+1;1)-ИНДЕКС($C$7:$D$11;G$6+1;1))^2 +(ИНДЕКС($C$7:$D$11;$F7+1;2)-ИНДЕКС($C$7:$D$11;G$6+1;2))^2)

likbezpng-solver74.png

Теперь создадим модель для Поиска решения .

likbezpng-solver75.png

Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

Переменные (выделено зеленым) . В качестве переменных модели следует взять номера городов. Так как начальная и конечная точка известны (Город0), то переменных будет 4. Ограничения (выделено синим) . Необходимо, чтобы номера городов не повторялись. Это означает, что количество уникальных (неповторяющихся) номеров городов должно быть равно 4. Для этого используется формула для подсчета уникальных значений : = СУММПРОИЗВ(1/СЧЁТЕСЛИ(B16:B19;B16:B19))

Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.

likbezpng-solver76.png

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

Выберите Эволюционный метод поиска решения, т.к. созданная модель не является линейной из-за наложенного на переменные ограничения.

Что здесь не так

С одной стороны, у нас получился простой и понятный алгоритм, который делает то, что нам нужно. С другой — у него есть серьёзные проблемы:

  1. Если у нас будет 15 городов, нам нужно будет делать 15 вложенных циклов и делать 120 проверок — это выглядит очень громоздко, легко ошибиться в таком коде.
  2. Чем больше будет городов, тем медленнее будет считаться результат. Уже на 10 городах мы получим 3,5 миллиона выполнений тела цикла, что займёт гораздо больше времени. На 13 городах таких выполнений будет уже 6 миллиардов, и компьютер может их считать неделю или даже больше. 

Попробуем исправить эти недостатки в следующих подходах к задаче. Следите за новыми статьями.

Текст и код:

Михаил Полянин

Соцсети:

Анастасия Гаврилова

Примечания

  1. Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 275.
  2. Euler, Leonhard, Solution d’une question curieuse que ne paroit soumise à aucune analyse, Mémoires de l’académie des sciences de Berlin, 15 (1759) 1766, p. 310—337.
  3. Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л. С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150, ISBN 985-6516-83-8
  4. Richard Durbin, David Willshaw. An analogue approach to the travelling salesman problem using an elastic net method (англ.) // Nature. — 1987-04-22. — Vol. 326, iss. 6114. — P. 689–691. — doi:10.1038/326689a0.
  5. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. — М., Наука, 1969. — C. 258—264
Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...