Глава 1. История формулировки задачи
Есть n городов. В одном из них живет коммивояжер. Будем считать этот город первым. Коммивояжеру надо объехать n-1 город и вернуться в первый. Каким образом ему надо проложить свой маршрут, чтобы проехать минимальное расстояние?
Эта проблема была сформулирована в 1934 году Гаслером Уитни. В то время еще не было приемлемых вычислительных методов и мало математических результатов относительно задачи.
В 1859 г. Гамильтон придумал игру «Кругосветное путешествие», в которой требовалось обойти 20 городов, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города. Обязательными условиями являлись требования посетить каждую вершину однократно и вернуться в исходную вершину. Данная задача получила название «Гамильтоновы циклы».
Позднее задача о гамильтоновых циклах получила различные обобщения. Одно из этих обобщений задача коммивояжера, имеющая ряд применений в исследовании операций, в частности, при решении некоторых транспортных проблем.
Задача коммивояжера тесно связана с задачей о назначении и отличается от нее только тем, что в задаче о назначении не требуется цикличности.
Задача о назначениях состоит в том, чтобы обеспечить n работников n вакансиями, наиболее выгодным способом.
Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжера отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины 20-го века, исследование задачи коммивояжера имеет не столько практический смысл, сколько теоретический, в качестве модели для разработки новых алгоритмов оптимизации.
Многие современные распространенные методы дискретной оптимизации, такие как метод деления плоскостью, метод ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера.
В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых из США и Европы. Важный вклад в исследовании задачи принадлежит Джорджу Данцигу, Делберту Рею Фаркерсону и Селмеру Джонсону, которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и разработали метод деления плоскостью для ее решения. Используя новый метод, они вычислили путь для отдельного набора узлов с 49 городами и доказали, что не существует более короткого пути. В 1960-е и 1970-е годы многочисленные группы исследователей изучали задачу с точки зрения математики и ее применения, например, в информатике, экономике, химии и биологии.
Ричард Карл в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-полнота задачи коммивояжера. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений на практике.
Больших успехов удалось достичь в конце 1970-х и1980-х годов, когда Мартин Грётчел, Манфред Падберг, Джованни Ринальди и другие, с применением новых методов деления плоскостью, ветвей и границ, вычислили решение для отдельного случая задачи с 2393 городами.
В 1990-е годы Дэвид Аплгейт, Роберт Биксби, Вашека Шватал и Уильям Кук установили рекорды по программе Конкорд. Герхард Райнельт создал TSPLIB-набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33810 узлами была решена программой Конкорд: был вычислен путь длиной 66048945 и доказано отсутствие более коротких путей. В апреле 2006 года было найдено решение для экземпляра с 85900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1% больше оптимальной.
Формулировка задачи.
Задача коммивояжера состоит в том, чтобы отыскать перестановку P={1, i2, i3 ….,n} из целых чисел от 1 до n, которая будет минимизировать сумму a1 i2 + ai2 i3+…+ain 1, где aj k – расстояние между городами j и k. Поскольку у нас (n-1)! вариант возможной перестановки, то проблема заключается в нахождении оптимального метода нахождение нужной нам перестановки.