История коммивояжёра

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Методы решения  задачи коммивояжера

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

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

• Полный перебор;

Полный  перебор (или  метод «грубой силы») — метод  решения задачи путем перебора всех возможных вариантов. Сложность  полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

• Случайный перебор;

Обычно  выбор решения  можно представить  последовательностью  выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», то есть наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, то есть комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

• Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

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

• Метод минимального основного дерева (деревянный алгоритм);

В основе алгоритма лежит  утверждение: «Если справедливо  неравенство  треугольника, то для  каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи». Это обобщение расхожего убеждения, что прямая короче кривой.

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

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

• Метод имитации отжига.

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

Алгоритм  имитации отжига относится к классу пороговых  алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения ik в его окрестности N(ik) выбирается некоторое решение j и, если разность по целевой функции между новым и текущим решением не превосходит заданного порога tk, то новое решение j заменяет текущее. В противном случае выбирается новое соседнее решение.

На  практике применяются  различные  модификации более  эффективных  методов:

• Метод ветвей и границ;

Метод ветвей и границ предложен в 1963 году группой авторов  Дж. Литлом, К. Мурти, Д. Суини, К. Кэролом. Широко используемый вариант поиска с возвращением, фактически является лишь специальным частным случаем метода поиска с ограничениями. Ограничения в данном случае основываются на предположении, что на множестве возможных и частичных решений задана некоторая функция цены и что нужно найти оптимальное решение, т.е. решение с наименьшей ценой. Для применения метода ветвей и границ функция цены должна обладать тем свойством, что цена любого частичного решения не превышает цены любого расширения этого частичного решения (Заметим, что в большинстве случаев функция цены неотрицательна и даже удовлетворяет более сильному требованию).

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

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

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

• Метод генетических алгоритмов;

 «Отцом-основателем»  генетических алгоритмов считается  Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований.

Генетический  алгоритм — это эвристический алгоритм поиска, используемый для решения  задач оптимизации и моделирования  путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

• Алгоритм муравьиной колонии.

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

 

 

 

 

 

Решение задачи коммивояжера в MS Excel

Определим булевы переменные задачи: xij = 1, если коммивояжер переезжает из города i в город j, и xij = 0, если коммивояжер  не переезжает из города i в город j.

Тогда задача заключается  в определении минимума целевой  функции

при ограничениях: 

 

          – только один въезд в город j,

 

   – только один выезд из города i.

 

 

В задаче коммивояжера необходимо еще одно условие, а именно:

 

ui – uj + (n – 1)xij ≤  n – 2,     i ≠ j, i,    j = 2,…, n.

 

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

Пример 

Рассмотрим задачу:

                                                

Решение:

1. В ячейки В13:F17 вводим матрицу расстояний.
2. Вводим формулы

Ячейка	Формула	Примечание
В9	=СУММ(В4:В8)	Копируем в диапазон В9:F9
G4	=СУММ(В4:F4)	Копируем в диапазон G4:G8
С19	=СУММПРОИЗВ(B4:F8;B13:F17)	Целевая функция
Е19	=B4+C5+D6+E7+F8	Исключение пути i → i
В23	=$C$10–C10+4*C5	Копируем в диапазон В23:Е23
В24	=$D$10–C10+4*C6	Копируем в диапазон В24:Е24
В25	=$E$10–C10+4*C7	Копируем в диапазон В25:Е25
В26	=$F$10–C10+4*C8	Копируем в диапазон В26:Е26

Исходные данные приведены  на рис.3.1.

 

Рис. 3.1. Исходные данные задачи

 

3. Сценарий решения:

 

Рис.3.2. Окно Поиск решения.

Рис. 3.3. Параметры Поиска решения.

 

4. Он приводит к следующим результатам:

 

Рис. 3.4. Результаты решения  задачи коммивояжера

 

5. Ответ:

 

маршрут 1→3→4→2→5→1. Длина маршрута –21.

Заключение

Задача коммивояжера была поставлена в 1934 году. Ее сущность заключается в поиске оптимального маршрута движения при необходимости  посетить все запланированные объекты  с наименьшими финансовыми и  временными издержками. Как правило, речь идет о простом перемещении по заданным точкам, либо с перевозкой груза небольшого формата на транспортном средстве.

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

Среди современных практических приложений задачи можно выделить: доставку продуктов в магазин  со склада, работу почтальона по разноске корреспонденции, мониторинг объектов (нефтяные вышки, базовые станции  сотовых операторов), изготовление отверстий на специализированном станке.

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

В работе была поставлена задача, сводимая к задаче коммивояжера, и составлена схема оптимального маршрута, подробно рассмотрен порядок выбора кратчайшего пути при помощи использования надстройки MS Excel «Поиск решения» методом полного перебора. Результаты решения были выведены на отдельный рабочий лист Excel.

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

 

 

 

 

 

 

 

 

Список Литературы