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

Содержание

Введение………………………………………………………………………..….3

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

Сущность и применение  на практике………………………..………………….6

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

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

Заключение……………………………………………………...………………..15

Список литературы…………………………………………...………………….16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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

Большой вклад в систематическое  развитие комбинаторных методов  был сделан Г. Лейбницем (диссертация "Комбинаторное искусство"), Я. Бернулли (работа "Искусство предположений"), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций - методу производящих функций.

Возвращение интереса к  комбинаторному анализу относится  к 50-м годам ХХ в. в связи с  бурным развитием кибернетики и  дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.

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

В 1859 г. У. Гамильтон придумал игру "Кругосветное путешествие", состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

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

 

 

 

 

 

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

 

Точно неизвестно, когда  проблему коммивояжера исследовали  впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», в которой описана проблема, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая  заключалась в том, чтобы найти  маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так: 

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

 

Вскоре появилось известное  сейчас название задача странствующего продавца (Traveling Salesman Problem), которую предложил Гаслер Уитни из Принстонского университета.

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

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

В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых в США и Европе. Важный вклад  в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону и Селмеру Джонсону, которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и разработали метод деления плоскостью для её решения. Используя новый метод, они вычислили путь для отдельного набора узлов с 49 городами и доказали, что не существует более короткого пути. В 1960-е и 1970-е годы многочисленные группы исследователей изучали задачу с точки зрения математики и её применения, например, в информатике, экономике, химии и биологии.

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

Больших успехов удалось  достичь в конце 1970-х и 1980-х  годах, когда Мартин Грётчел, Манфред  Падберг и Джованни Ринальди и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт, Роберт Биксби, Вашека Шватал и Уильям Кук установили рекорды по программе Конкорд. Герхард Райнельт создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1 % больше оптимальной.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Сущность и применение  на практике

 

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

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

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

В задаче коммивояжера целевой  функцией, которую надо минимизировать, является стоимость обхода.

Особенностью  задачи о коммивояжере является необходимость  дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно  заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.

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

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

Гамильтоновы  путь, цикл и граф названы в честь  ирландского  математика У. Гамильтона, который впервые определил эти  классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые  вершины которого символизировали крупнейшие города Земли, а ребра – соединяющие их дороги.

Существует  несколько  частных случаев общей  постановки задачи, в частности:

- геометрическая задача  коммивояжёра (когда матрица расстояний  отражает расстояния между точками  на плоскости);

- треугольная задача  коммивояжёра (когда на матрице  стоимостей выполняется неравенство  треугольника);

- симметричная и асимметричная задачи коммивояжёра.

Также существует обобщение задачи, так  называемая обобщённая задача коммивояжёра.

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

При постановке задачи коммивояжера для  k коммивояжеров на множестве из n+1 городов строится k замкнутых маршрутов по следующим правилам:

- один из городов, называемый  базой входит во все маршруты;

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

- суммарная длина всех маршрутов минимальна.

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

• Разбивается ли задача достаточно хорошо на совокупность более мелких подзадач?
• Существует ли точная, непротиворечивая информация о задаче?
• Ожидается ли, что в процессе решения задачи человек будет взаимодействовать с вычислительной машиной?

Задача  коммивояжера имеет ряд практических применений.

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

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