Глава 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 городами.