Проблема продавца

Идеальный маршрут для коммивояжера по 15 крупнейшим городам Германии . Данный маршрут является самым коротким из 43 589 145 600 возможных.

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

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

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

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

история

Неясно, когда впервые была исследована проблема коммивояжера с научной точки зрения. Справочник для коммивояжеров известен с 1832 года (название: «Коммивояжер - каким он должен быть и что он должен делать, чтобы получать заказы и быть уверенным в счастливом успехе в своем деле» - от старого комиссара). voyageur ), в котором проблема упоминается, но не рассматривается математически. Предлагаются примеры туров по некоторым регионам Германии и Швейцарии .

Уильям Роуэн Гамильтон (1805-1865)

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

Вскоре после этого, в настоящее время общего обозначения Задачи коммивояжер был введен по Hassler Уитни из Принстонского университета .

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

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

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

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

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

Алгоритм, независимо описанный Никосом Христофидесом и Анатолием Сердюковым в 1976 году, привел к тому, что поездка туда и обратно была максимум вдвое длиннее оптимального маршрута.

В 1990-х Дэвид Эпплгейт , Роберт Биксби , Вашек Хватал и Уильям Кук начали разработку программы Concorde , которая помогла установить множество рекордов. В 1991 году Герхард Райнельт представил TSPLIB, набор стандартизированных тестовых примеров различной сложности, с которыми многие исследовательские группы могли сравнивать свои результаты. В 2006 году Кук и другие вычислили наиболее короткое путешествие по 85 900 городам задачи компоновки интегральных схем , которая на сегодняшний день является крупнейшим оптимально решенным примером TSPLIB. Для других случаев с миллионами городов они использовали дополнительные методы декомпозиции для определения туров, длина которых, как можно доказать, составляет менее 1% от оптимальной.

В 2014 году Андраш Себё из Университета Гренобля и Йенс Виген из Университета Бонна установили новый рекорд в области эвристики с гарантией качества с помощью алгоритма с полиномиальным временем выполнения : их новый алгоритм , названный nice-ушами. -разложение , определяет решения графа -TSP, которые не более чем в 1,4 раза длиннее оптимального маршрута туда и обратно, что является новым рекордом.

Математическое описание

Моделирование в виде графика

Симметричный ТСП на четыре города

Чтобы математические методы могли быть использованы для решения, реальная ситуация сначала должна быть представлена ​​простой моделью . Задачу коммивояжера можно смоделировать с помощью графа , то есть с помощью узлов и ребер . (: От A до D на рисунке) города, в то время как каждое ребро Узлы представляют собой между двумя узлами и описывает связь между этими городами. Для каждого края есть длина (на рисунке: 20, 42, ...), которая, в зависимости от контекста, может интерпретироваться как географическая протяженность соединения, как время в пути или как стоимость поездки между два города. Тур (также называемый Гамильтон кругом ) представляет собой круг на этом графике , который содержит каждый узел ровно один раз. Цель - найти как можно более короткий тур. ${\ displaystyle (я, j)}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle (я, j)}$${\ displaystyle c_ {ij} \ geq 0}$

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

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

Асимметричный и симметричный TSP

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

В симметричном TSP, с другой стороны, длины ребер идентичны в обоих направлениях для всех пар узлов . то есть применяется . Как следствие, каждый тур имеет одинаковую длину в обоих направлениях. Симметрия уменьшает вдвое количество возможных туров. Симметричный TSP обычно моделируется с помощью неориентированного графа (как на картинке). Задача коммивояжера между реальными городами может быть асимметричной или симметричной, в зависимости от того, проходит ли, например, через строительные площадки или улицы с односторонним движением, путешествие в одном направлении занимает больше времени, чем в другом, или нет. Точно так же путешествие по воде или воздуху может быть подвержено различным течениям. ${\ displaystyle (я, j)}$${\ displaystyle c_ {ij} = c_ {ji}}$

Метрическая TSP

Симметричный TSP называется метрическим, если длины его ребер также удовлетворяют неравенству треугольника . Это явно означает, что объездные пути не имеют смысла, потому что прямое соединение от до никогда не бывает длиннее, чем путь от до через третий узел : ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle k}$

${\ displaystyle c_ {ij} \ leq c_ {ik} + c_ {kj}}$

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

• евклидова метрика в евклидовом TSP ,
• Манхэттен метрика (также город блок метрики) от прямолинейного ПБО , в котором расстояние между двумя узлами сетки-образного графика (например, сети улиц Manhattan) является сумма расстояний в х и у направлениях,
• или максимальная метрика , в которой расстояние между двумя узлами сеточного графа является максимальным из расстояний в направлении x или y.

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

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

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

Если не разрешено посещать места более одного раза, любой TSP также можно свести к метрическому TSP, увеличив длину каждого ребра на ту же неотрицательную константу: всегда можно найти константу, которая достаточно велика для всех, чтобы встретить тройки узлов. В случае эвристики, которая гарантирует максимальное отклонение от оптимума, эта процедура, естественно, увеличивает коэффициент отклонения исходной задачи. ${\ displaystyle q \ geq 0}$${\ Displaystyle (c_ {ij} + q) \ leq (c_ {ik} + q) + (c_ {kj} + q)}$

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

Один из подходов к решению проблемы состоит в том, чтобы сформулировать ее как интегральную линейную программу, в которой решения описываются переменными, а условия - линейными неравенствами . Для этого есть несколько возможных вариантов. Моделирование симметричной TSP с набором узлов должно быть представлено здесь в качестве примера . Для каждого ребра вводится двоичная переменная, которая указывает для данного обхода, включено ли ребро в этот обход ( ) или нет ( ). Таким образом можно указать каждый тур, указав связанные значения переменных, но не каждое присвоение значений переменных 0-1 определяет тур. Условия присвоения переменной для определения тура могут быть выражены линейными неравенствами, которые представлены ниже. ${\ displaystyle V}$ ${\ displaystyle \ {я, j \}}$${\ Displaystyle х _ {\ {я, j \}} \ в \ {0,1 \}}$${\ displaystyle \ {я, j \}}$${\ Displaystyle х _ {\ {я, j \}} = 1}$${\ Displaystyle х _ {\ {я, j \}} = 0}$

Условие степени: Ровно одно ребро обхода должно входить или выходить из каждого узла i.

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

${\ displaystyle \ sum _ {j \ in V \ setminus \ {i \}} x _ {\ {i, j \}} = 2 \ qquad (1)}$

для всех . В сумме каждое слагаемое либо 1 (включено в тур), либо 0 (не включено). Таким образом, сумма точно подсчитывает количество ребер маршрута, у которых узел является конечным узлом. Он должен иметь значение 2, так как ребро должно входить и выходить. На рисунке справа показан узел с входящими и исходящими ребрами, при этом переходящие ребра выделены жирным шрифтом. По краям указаны значения, которые вносят вклад в указанные выше суммы. ${\ displaystyle i \ in V}$ ${\ Displaystyle х _ {\ {я, j \}}}$${\ displaystyle i}$${\ displaystyle i}$${\ Displaystyle х _ {\ {я, j \}}}$

Короткие циклы: это присвоение переменной удовлетворяет всем условиям степени, но не определяет тур.

Вышеуказанным условиям степени удовлетворяют не только туры, но и присвоения переменных, которые описывают несколько отдельных кругов (так называемые короткие циклы ), причем каждый узел содержится ровно в одном круге (см. Рисунок). Чтобы исключить такое, должны быть выполнены неравенства коротких циклов (также называемые условиями исключения субтура ). Эти ограничения, введенные Данцигом, Фулкерсоном и Джонсоном в 1954 году как условия цикла, гласят , что каждый набор узлов, который не является пустым и не содержит все узлы, должен быть связан с остальными узлами по крайней мере двумя ребрами маршрута: ${\ Displaystyle S \ подмножество V}$

${\ Displaystyle \ сумма _ {я \ в S, \; j \ notin S} х _ {\ {я, j \}} \ geq 2 \ qquad (2)}$

для всех наборов узлов с . В сумме подсчитываются все ребра маршрута между одним узлом и другим узлом . Чтобы избежать избыточного неравенства, можно ограничиться наборами узлов, содержащими не менее двух и не более двух узлов. Изображение к краям снова с втягивается жирным шрифтом, а остальные края значения имеют. Добавление условия (2) для набора узлов , который состоит из трех узлов слева, гарантирует, что S должен быть связан с тремя узлами справа по крайней мере двумя переходными ребрами, исключая, таким образом, два показанных коротких цикла. Число условий исключения подтуров Данцига, Фулкерсона и Джонсона составляет . Альтернативное представление ограничений для избежания подтуров, опубликованное Миллером, Такером и Землином в 1960 году, обходится только ограничениями , вводя новые переменные, которые указывают порядок посещаемых мест . Однако из-за бинарной природы TSP, даже с формулировкой по Миллеру, Такеру и Землину , TSP остается NP-трудным . ${\ displaystyle S}$${\ Displaystyle 1 \ Leq | S | \ Leq | V | -1}$${\ displaystyle i \ in S}$${\ displaystyle j \ notin S}$${\ displaystyle S}$${\ displaystyle | V | -2}$${\ displaystyle \ {я, j \}}$${\ Displaystyle х _ {\ {я, j \}} = 1}$${\ Displaystyle х _ {\ {я, j \}} = 0}$${\ displaystyle S}$${\ Displaystyle 2 ^ {п} -2 (п-1)}$${\ displaystyle n}$${\ displaystyle n ^ {2} -n + 1}$${\ Displaystyle х _ {\ {я, j \}}}$

Поскольку каждый вектор с элементами от 0 и 1, который удовлетворяет всем этим неравенствам, определяет допустимый круговой обход, возникает переформулированная проблема продавца: найти ${\ Displaystyle х = (х _ {\ {я, j \}}) _ {я, j \ в V, я \ neq j}}$

${\ displaystyle \ min \; \ left \ {\ sum _ {i \ in V} \ sum _ {j \ in V \ setminus \ {i \}} c _ {\ {i, j \}} x _ { \ {i, j \}} \; | \; x {\ text {выполняет (1) и (2)}}, \; x _ {\ {i, j \}} \ in \ {0,1 \ } \ right \}. \ qquad (3)}$

Поскольку переменные принимают только значения 0 или 1, в сумме складываются точные длины ребер , содержащихся в маршруте. ${\ Displaystyle х _ {\ {я, j \}}}$${\ displaystyle c _ {\ {я, j \}}}$${\ displaystyle \ {я, j \}}$

Количество неравенств типа (2) растет экспоненциально с увеличением количества городов, поскольку почти каждое из подмножеств узлов определяет неравенство. Однако эту проблему можно обойти с помощью методов секущей плоскости , в которых эти неравенства добавляются только тогда, когда они действительно необходимы. Геометрически любое линейное уравнение можно интерпретировать как гиперплоскость в пространстве переменных. Множество допустимых решений образует в этом пространстве многогранник , то есть многомерный многоугольник, точная форма которого зависит от затрат и по большей части неизвестна. Однако можно показать, что большинство условий (1) и (2) определяют грани многогранника TSP, то есть боковые поверхности многогранника с максимально возможной размерностью. Это делает их одним из самых сильных линейных неравенств, которые можно использовать для описания тура. Есть много других аспектов, связанные с которыми неравенства известны лишь в некоторых случаях. Хотя (1) и (2) вместе с ограничением векторами 0/1 полностью моделируют проблему, такие дополнительные неравенства могут быть добавлены к формулировке в рамках метода ветвей и отсечений , чтобы идентифицировать определенные решения LP с нецелыми числами. Исключить координаты (см. Раздел Методы точного решения ). ${\ Displaystyle 2 ^ {| V |}}$${\ displaystyle c _ {\ {я, j \}}}$

Алгоритмическая сложность

Поскольку коммивояжер может выбирать города, в которых он еще не побывал, на каждом этапе возможны туры для асимметричного и туры для симметричного TSP (с ). Размер области поиска зависит от количества городов сверхэкспоненциально. ${\ Displaystyle (п-1)!}$${\ Displaystyle (п-1)! / 2}$${\ displaystyle n> 2}$

Задача коммивояжера NP-эквивалентна как для общего, так и для симметричного или метрического случаев . При общепринятом, но пока недоказанном предположении, что классы сложности P и NP различны (см. Проблему P-NP ), следует, что не существует детерминированной машины Тьюринга, которая могла бы решить проблему для каждого экземпляра за полиномиальное время выполнения по отношению к количество городов решает.

Также известно, что при предположении P NP для общей задачи коммивояжера не может быть алгоритма полиномиального времени, который в основном вычисляет решение для любого полинома , значение которого отклоняется от оптимального значения не более чем на один фактор . ${\ displaystyle \ neq}$${\ displaystyle p}$${\ Displaystyle 2 ^ {п (п)}}$

Однако для метрического TSP могут быть указаны алгоритмы аппроксимации, которые обеспечивают решение в полиномиальном времени выполнения, которое не более чем в два раза ( подход с минимальным остовным деревом ) или не более чем в 1,5 раза ( алгоритм Кристофидеса ) превышает оптимальное решение (см. Ниже ). Пока нет известного алгоритма полиномиального времени с гарантией качества лучше 1,5. Алгоритм полиномиального времени с гарантией качества 8/7 известен ограничением расстояний 1 и 2. В предположении P NP существует (неизвестная) константа , поэтому алгоритм с полиномиальным временем не может существовать для метрического TSP, который гарантирует качество , как показали Карпински, Лэмпис и Шмид 2013. Соответствующая наиболее известная константа для Graph TSP - это . Arora (1996) и Mitchell (1996) независимо предложили схему полиномиального приближения (PTAS) для евклидовой TSP.${\ displaystyle \ neq}$${\ displaystyle c \ geq {\ tfrac {1} {122}} \ приблизительно 0 {,} 0081}$${\ displaystyle 1 + c}$${\ displaystyle c}$${\ displaystyle {\ tfrac {1} {534}}}$

Метод решения

Известные способы решения делятся на две группы, которые можно комбинировать друг с другом. Процедуры точного решения всегда найдут доказуемое оптимальное решение - при любой продолжительности работы. Эвристические методы часто находят хорошие решения за короткое время, но в целом они могут быть сколь угодно плохими. Для метрической TSP существуют полиномиальные эвристики , решения которых обычно не более чем в 1,5 или 2 раза длиннее, чем кратчайший путь туда и обратно.

Точные методы решения

Задачу коммивояжера можно решить точно, вычислив расстояния всех возможных рейсов туда и обратно, а затем выбрав один с наименьшим расстоянием. Однако для небольшого числа городов это уже невозможно. В простейшем варианте, симметричном ТКП с городами, существуют различные маршруты туда и обратно, то есть более 43 миллиардов в 15 городах и более 177 триллионов в 18 городах . В следующем примере показано, как быстро увеличивается время вычислений с ростом числа городов: если у вас есть компьютер, который вычисляет решение для 30 городов за один час, ему требуется почти в тысячу раз больше времени для двух дополнительных городов; это больше 40 дней. ${\ displaystyle n}$${\ Displaystyle (п-1)! / 2}$

TSP на трех узлах: красная пунктирная секущая плоскость отсекает все недопустимые решения не более чем с одной кромкой. Этому неравенству удовлетворяют все точки красного многогранника , включая единственную допустимую точку (1,1,1).${\ Displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}$

С другой стороны, с помощью методов целочисленной линейной оптимизации , в частности ветвления и разреза , можно доказать, что примеры практически значимых порядков величины оптимально решены, или, по крайней мере, качество найденного тура может быть оценено по сравнению с Оптимальное решение. В геометрической интерпретации эти методы рассматривают задачу как выпуклый многогранник , то есть как многомерный многоугольник в -мерном единичном кубе , где - количество ребер графа. Каждый угол этого единичного куба описывает обход, при условии, что связанный вектор 0/1 удовлетворяет линейным неравенствам, описанным выше. Следовательно, гиперплоскости, принадлежащие этим неравенствам, срезают углы единичного куба, которые не представляют тур. ${\ displaystyle m}$ ${\ displaystyle [0,1] ^ {m}}$${\ displaystyle m}$

Изображение справа иллюстрирует это для (очень простого) TSP с тремя узлами. Есть также три двоичных переменные и соответствующие три возможных ребер между этими узлами . В этом случае возможен только один тур, а именно тот, который использует все три ребра. Этот тур удовлетворяет неравенству, согласно которому каждый тур должен иметь как минимум два ребра. Кроме этого тура, который соответствует точке (1,1,1), все точки в области с красной рамкой также удовлетворяют этому неравенству. Соответствующая секущая плоскость , охваченная красными пунктирными линиями, срезает все углы, которые соответствуют невозможным маршрутам с не более чем одним ребром, а именно нулевым вектором (0,0,0) и единичными векторами (1,0,0 ), (0,1,0) и (0,0,1). Более сильное неравенство отрезало бы от единичного куба все, кроме единственной допустимой точки (1,1,1). В этом частном случае того же эффекта можно добиться, используя три неравенства типа (1). ${\ Displaystyle х_ {1}, \, х_ {2}}$${\ displaystyle x_ {3}}$${\ Displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}$${\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 3}$

Решая множество линейных программ , отсекая ненужные части единичного куба с помощью дополнительных секущих плоскостей (например, типа (2) или также неравенства четности гребня , кликового дерева и домино ) и разбивая на несколько подполитопов с с помощью функции Branch-and -Bound делается попытка определить допустимый угол 0/1 с минимальным значением целевой функции. Более подробное описание этих методов можно найти в статье Целочисленная линейная оптимизация .

Одного применения этих процедур обычно недостаточно для быстрого поиска хороших туров. Их главное преимущество в том, что они предоставляют информацию о минимальной длине самого короткого тура. Имея такую ​​нижнюю границу для оптимального значения решения, можно оценить, насколько хорошо найденный тур по сравнению с оптимальным круговым рейсом, не зная об этом. Например, если вы нашли нижнюю границу 100 и маршрут длиной 102, оптимальный маршрут может быть только между 100 и 102. Так называемый разрыв оптимальности , то есть максимальное относительное расстояние между оптимальной длиной маршрута и самой короткой известной длиной маршрута, составляет, таким образом, (102-100) / 100 = 2%, т. Е. ЧАС; значение 102 найденного решения отклоняется не более чем на 2% от оптимального значения. Если длина найденного тура точно такая же, как нижняя граница, это доказывает, что найденное решение является оптимальным. Чтобы найти хорошие туры, эти точные процедуры можно комбинировать с эвристикой, некоторые из которых описаны в следующем разделе.

Эвристика

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

Процедура открытия

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

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

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

Минимальное покрывающее дерево соединяет все точки графика с минимальной длиной ребра

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

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

Еще лучшее качество аппроксимации для метрической TSP достигается алгоритмом Христофидеса и Сердюкова . Его можно использовать для расчета пути туда и обратно, который не более чем в полтора раза длиннее оптимального. Вместо того, чтобы удваивать ребра в эвристике MST , на узлах нечетной степени в минимально остовном дереве вычисляется наименьшая идеальная пара для создания графа Эйлера. Однако этот алгоритм более сложный.

Процесс улучшения

Улучшение методов оптимизации, а также методы пост-оптимизации (пост-оптимизация) пытаются сократить существующий тур путем внесения небольших изменений. Если ни одно из рассмотренных изменений не привело к улучшению, локальный оптимум был найден (но не обязательно глобальный). В к-Opt эвристики следовать этому подходу, систематически удаляя группы ребер из тура и заменяя их с другими краями , так что тур создается снова. Поскольку полная реализация этой процедуры соответствовала бы списку всех возможных маршрутов, в практических реализациях обычно используется максимум 5. Часто проверяются все возможности обмена двух и трех ребер, в то время как обмен ребрами более чем трех ребер выполняется. используется очень экономно из-за вычислительных затрат. ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

На практике качество k-opt эвристики сильно зависит от выбора ребер для обмена и параметра , для которого существуют различные эвристические критерии. Хорошо известной эвристикой, основанной на k-opt, является эвристика Лин-Кернигана , которая была разработана в 1973 году С. Лином и Б.В. Керниганом и при реализации Келда Хельсгауна, среди прочего, участвовала в оптимальном решении TSP на 24 978 шведских пунктов в 2004 г. Он основан на том, что сначала проверяются все возможности обмена двух ребер, затем - трех ребер и так далее, пока не будет удовлетворен один из нескольких возможных критериев завершения. ${\ displaystyle k}$

Метаэвристические процедуры

Метаэвристика объединяет методы локального и глобального поиска в абстрактную стратегию эвристической оптимизации проблемы. Многие из этих методов основаны на локальном поиске ; Другими словами, они вычисляют эвристическое начальное решение (например, с эвристикой ближайшего соседа) и улучшают его с помощью метода локального поиска, такого как эвристика K-Opt , до тех пор, пока не будет найден лучший маршрут. Чтобы попытаться максимально избежать застревания в локальных минимумах, можно использовать различные стратегии, такие как поиск табу или моделирование охлаждения . Другие подходы, такие как алгоритмы муравьев , генетические алгоритмы или искусственные нейронные сети (особенно сеть Хопфилда ), основаны на естественных процессах. В принципе, все эти методы могут вычислять хорошие решения, но они также могут быть настолько плохими, насколько вы хотите, по сравнению с оптимальным решением. Их качество и продолжительность во многом зависят от определения и выполнения отдельных шагов.

Двойная эвристика

Задача коммивояжера - одна из немногих задач комбинаторной оптимизации, для которой пригодные для использования нижние оценки минимальной длины маршрута (в общем: минимальная стоимость решения) могут быть определены простым способом. Эти ограничения особенно важны для заявлений о качестве допустимого тура. Так как, например, каждый маршрут, то есть, в частности, оптимальный, содержит точные ребра, он должен быть не меньше суммы наименьших длин ребер. Другая нижняя граница является результатом наблюдения, что при удалении любого ребра из обхода возникает остовное дерево , то есть подграф, содержащий все узлы, но не окружности. Маршрут по крайней мере такой же длины, как это дерево и, следовательно, по определению, по крайней мере, такой же длинный, как минимально остовное дерево (то есть остовное дерево с минимальной суммой длин ребер), которое можно легко определить. Поскольку это применимо к каждому туру, длина минимального остовного дерева обеспечивает нижнюю границу длины оптимального тура. В несколько более общем виде также можно вычислить так называемое минимальное 1-дерево . Это минимально остовное дерево между узлами от 2 до (с любой нумерацией), которое связано с узлом с номером 1 двумя кратчайшими возможными ребрами (отсюда и название). Его длина также дает нижнюю границу. Кроме того, каждый тур - это идеальное совпадение двух . Это означает, что кратчайший маршрут должен быть по крайней мере такой же длины, как значение минимального идеального 2-совпадения, которое может быть вычислено в O (n³). ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

Обзор

В следующей обзорной таблице перечислены типы процедур для большинства представленных здесь эвристик, максимальное время выполнения для городов и любые гарантии качества для рассчитанных решений. Поскольку время выполнения и качество метаэвристики сильно зависят от выбора подалгоритмов и не могут быть указаны в целом, они здесь не перечислены. ${\ displaystyle n}$

Процедура	Тип	Продолжительность	Макс. Отклонение от оптимума
Эвристика ближайшего соседа	Открытие эвристики	${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$	Фактор (log (n) +1) / 2 (метрическое TSP)
Эвристика дальнего соседа	Открытие эвристики	${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$	любой размер
Эвристика самой дальней вставки	Эвристика вставки	${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$	любой размер
Ближайшая эвристика вставки	Эвристика вставки	${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$	любой размер, коэффициент 2 (метрическая TSP)
Эвристика минимального остовного дерева	Открытие эвристики	${\ Displaystyle {\ mathcal {O}} (п ^ {2} \ журнал (п))}$	как ближайшая вставка
Христофидес эвристический	Открытие эвристики	${\ Displaystyle {\ mathcal {O}} (п ^ {3})}$	Фактор 1,5 (метрическая TSP)
K-opt эвристика	Эвристика улучшения	${\ Displaystyle {\ mathcal {O}} (к!)}$ за шаг	любой размер
Сумма n кратчайших ребер	Двойная эвристика	${\ Displaystyle {\ mathcal {O}} (п ^ {2} \ журнал (п))}$	любой размер
Длина минимального остовного дерева	Двойная эвристика	${\ Displaystyle {\ mathcal {O}} (п ^ {2} \ журнал (п))}$	любой размер

Практические пределы предсказуемости

Самым большим нетривиальным примером (симметричной) задачи туда и обратно, которая до сих пор была решена оптимально, является задача планирования компоновки интегральных схем с 33 810 узлами. Этот рекорд был установлен в 2005 году Уильямом Куком и другими с помощью комбинации различных эвристик и программы Concorde , основанной на принципах ветвей и отсечений, на основе более ранних частичных результатов различных университетских рабочих групп. Самый крупный пример с оптимальным разрешением на тот момент состоял из 24 978 шведских городов, рассмотренный в 2004 году. С помощью специальных методов декомпозиции и использования нескольких параллельных компьютеров Уильям Кук нашел туры для TSP к более чем 526 миллионам звезд , длина которых было доказано, что отклонение от оптимума не превышает 0,798%.

Тем не менее, тот факт , что TSP определенного размера может быть оптимально решена не означает , что каждый экземпляр такого размера может быть оптимально решен , потому что - как и с большинством задач комбинаторной оптимизации - трудность решения в значительной степени зависит от входных параметров (в в данном случае - краевые веса). Меньшую проблему решить гораздо сложнее; Например, в TSPLIB есть пример всего с 225 городами, который трудно решить из-за его множества симметрий. В случае ПБО, возникающих в результате практического применения, часто необходимо учитывать другие второстепенные условия, такие как временные окна. Следовательно, наиболее крупные примеры оптимально решаемых задач таких вариантов обычно значительно меньше, чем для классической задачи коммивояжера, так что на практике для решения проблемы часто используются эвристические подходы. Комбинации эвристических процедур с процедурами на основе LP, такими как ветвление и разрезание, в основном используются в исследованиях, чтобы иметь возможность оценивать качество решений и процедуры решения с помощью нижних границ длины обхода.

Варианты и приложения

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

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

Практическая процедура отличается от математической теории тем, что обычно ищут не лучшее решение, а только достаточно хорошее. Здесь следует рассматривать общие усилия - как усилия для реализации и расчета. Что означает «хорошо» и какие критерии используются, зависит от контекста проблемы. Таким образом, вы приложите меньше усилий для одноразовой доставки, чем для планирования сборки печатной платы, которая производится миллионными тиражами.

Несколько коммивояжеров

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

Автомобиля Задача маршрутизации (VRP) является несколько TSP с дополнительными ограничениями транспортной емкости. Это возникло непосредственно из практической необходимости планирования маршрута , при котором товары должны доставляться покупателям с центрального склада. Поездки туда и обратно соответствуют поездкам на фургонах, которые отправляются из общего депо и возвращаются в него. Цель VRP - обеспечить всех клиентов как можно дешевле. Заказчику можно доставить несколько раз, но только из одного фургона за раз. В особом случае, когда вместимость фургонов превышает сумму всех объемов заказа, VRP соответствует mTSP и, следовательно, также является NP-тяжелым . Варианты, полученные из задачи выбора маршрута транспортного средства ( VRP ):

Емкостный VRP ( CVRP )

Все фургоны имеют максимальную вместимость.

Multiple Depot VRP ( MDVRP )

Фургоны могут стартовать с нескольких разных депо.

VRP с временными окнами ( VRPTW )

Заказчики могут быть доставлены только в установленные сроки.

Периодический VRP ( PVRP )

Потребности клиентов периодически растут. Считается определенный период времени.

Разделенная доставка VRP ( SDVRP )

Заказчику могут поставляться разные транспортеры.

VRP с обратным рейсом ( VRPB )

Учитываются поставщики и их объемы поставки.

Динамический VRP ( DVRP )

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

Городские кластеры

С помощью обобщенного TSP (GTSP) (немецкий: обобщенный TSP) несколько городов объединяются в кластер. Коммивояжер должен посетить ровно один город из каждого кластера. TSP - это частный случай GTSP, в котором каждый город находится в кластере, который содержит только этот один город. Каждый экземпляр GTSP можно преобразовать в экземпляр простого TSP и решить с помощью алгоритмов, известных для этой проблемы. По этой причине GTSP также NP-сложен.

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

Изменения критерия оптимизации

В рамках TSP по сбору призов ( PCTSP ) коммивояжер получает определенные призовые деньги в каждом городе (например, выручку от продаж). Однако, чтобы путешествовать из одного города в другой, ему приходится повышать расходы. Теперь он должен выбрать указанное количество городов и поездку туда и обратно между этими городами таким образом, чтобы прибыль была максимальной. Поскольку задача содержит классический вариант как частный случай (все города посещаются, и все призовые деньги равны 0), PCTSP также NP-сложен. Формой, полученной на основе этого, является задача выбора коммивояжера ( TSSP ), в которой для данного города ищется кратчайший маршрут между любыми городами , без призовых денег и метрических расстояний. ${\ displaystyle k}$${\ displaystyle k}$

При использовании TSP «Узкое место» ( BTSP ) необходимо минимизировать не сумму длин кромок, а длину самой длинной используемой кромки. Это приводит к менее выраженному разбросу отдельных расстояний, чтобы противодействовать возможным узким местам, узким местам . Связанный вариант - это TSP с максимальным разбросом , при котором наименьшая используемая длина максимальна.

Дополнительные ограничения

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

С помощью онлайн-TSP не все города указаны заранее, а становятся известными только постепенно, когда коммивояжер уже в пути. Затем он меняет свой тур так, чтобы новые города «как можно лучше» вписывались в его ранее запланированный тур. Этот вариант встречается, например, с аварийными службами, такими как ADAC , где местонахождение сломанных автомобилей становится известно лишь постепенно, а штаб-квартира пытается как можно дешевле включить новые случаи в существующие туры. Поскольку в дороге много помощников по поломке, и когда сообщается о поломке, центр управления сообщает приблизительное время прибытия помощника по поломке, это несколько онлайн-провайдеров с временными окнами .

Служба посылок UPS с примерно 55 000 водителями-курьерами и в среднем 120 посылками в день и водителем использовала ранее оптимизированные статические маршруты для каждого транспортного средства, которые были индивидуально изменены водителями в соответствии с их опытом. С 2013 года компания перейдет на систему ORION ( On-Road Integrated Optimization and Navigation ). При этом учитываются гарантированные сроки доставки для отдельных посылок, зарегистрированные коллекции и особые классы клиентов с предпочтительным обслуживанием, а также данные о потоке трафика в режиме реального времени. Это дает опытному персоналу возможность отклониться от предложенного маршрута. Для этой компании существует дополнительное условие, согласно которому водители UPS не должны поворачивать налево в городах с регулярной сетью дорог, поскольку это влечет за собой чрезмерные задержки в ожидании встречного транспорта и чрезмерный риск аварий.

Индивидуальные доказательства

1. ^ Рене ван Беверн, Виктория А. Слугина: историческая заметка об алгоритме приближения 3/2 для метрической задачи коммивояжера . В: Historia Mathematica . Май 2020, DOI : 10.1016 / j.hm.2020.04.003 , Arxiv : 2004,02437 ( elsevier.com ). 
2. ^ Дэвид Л. Эпплгейт, Роберт Э. Биксби, Вашек Хватал и Уильям Дж. Кук: проблема коммивояжера. Вычислительное исследование . Princeton University Press, февраль 2007 г., стр. 522-524. ISBN 0-691-12993-2
3. ↑ Андраш Себё, Йенс Виген: Более короткие экскурсии более красивыми ушами: аппроксимация 7/5 для графа-TSP, 3/2 для версии пути и 4/3 для подграфов, связанных с двумя ребрами . Combinatorica 34 (5) (2014), 597-629, (DOI : 10.1007 / s00493-011-2960-3 )
4. ↑ Петр Берман, Марек Карпински, алгоритм аппроксимации 8/7 для (1,2) -TSP , Proceedings SODA '06, pp. 641-648. DOI: 10.1145 / 1109557.1109627
5. ↑ Марек Карпински, Майкл Лэмпис и Ричард Шмид, Новые границы несовместимости для TSP , появились в книге « Алгоритмы и вычисления - 24-й международный симпозиум», ISAAC 2013, стр. 568-578, 2013, DOI : 10.1007 / 978-3-642-45030- 3
6. ^ Марек Карпински, Ричард Шмид: Аппроксимационная твердость графического TSP на кубических графах . В: RAIRO Operations Research . № 49, 2015, с. 651-668.
7. ^ Санджив Арора: схемы полиномиальной аппроксимации времени для евклидова коммивояжера и других геометрических задач . В: J. ACM . 45, No. 5, 1998, pp. 753-782. DOI : 10.1145 / 290179.290180 .
8. ^ Джозеф С.Б. Митчелл: Подразделения гильотины Приближенные многоугольные подразделения: простая схема аппроксимации полиномиального времени для геометрической TSP, k-MST и связанных задач . В: SIAM J. Comput. . 28, No. 4, 1999, pp. 1298-1309. DOI : 10,1137 / S0097539796309764 .
9. ^ ^{A b} Уильям Кук, Даниэль Эспиноза, Маркос Гойкулеа: вычисления с неравенствами домино-четности для TSP. 2005. (Препринт, pdf; 261 kB)
10. ↑ Келд Хельсгаун: Эффективная реализация эвристики коммивояжера Лин-Керниган. (PDF; 646 kB) В: Европейский журнал операционных исследований. Амстердам 126.2000, № 1, стр. 106-130. ISSN  0377-2217
11. ↑ После Розенкранца, DJ; Stearns, RE; Льюис П.М. «Приближенные алгоритмы для задачи коммивояжера », Конференция по теории коммутации и автоматов, 1974. doi: 10.1109 / SWAT.1974.4
12. ^ Страница TSP по Васек Chvátal
13. ↑ Документированные приложения Concorde
14. ↑ Wired.com: Астрономическая математика, лежащая в основе нового инструмента UPS для более быстрой доставки пакетов , 13 июня 2013 г.
15. ↑ New York Times: Ликвидация левого поворота , 9 декабря 2007 г.

литература

• Дэвид Эпплгейт, Роберт Биксби , Вашек Хватал , Уильям Кук : о решении проблем коммивояжера . Documenta Mathematica. Дополнительный том 3 для Международного конгресса математиков. Берлин 1998, стр. 645-656. ( Postscript ; Gzip ; 68 кБ)
• Дэвид Л. Эпплгейт, Роберт Э. Биксби, Вашек Хватал и Уильям Дж. Кук: проблема коммивояжера. Вычислительное исследование . Princeton University Press, февраль 2007 г. ISBN 0-691-12993-2
• Уильям Дж. Кук: В погоне за коммивояжером: математика на грани вычислений. Princeton University Press 2011, ISBN 0-691-15270-5 .
• Лоулер, Ленстра, Риннуй Кан, Шмойс (ред.): Задача коммивояжера. Экскурсия по комбинаторной оптимизации . Уайли, Чичестер, 1985. ISBN 0-471-90413-9
• В. Домшке: Логистика - поездки и туры . Oldenbourg-Verlag, Мюнхен / Вена 1997 (4-е издание). ISBN 3-486-29472-5
• Т. Грюнерт, С. Ирних: Оптимизация на транспорте. Том 2. Пути и туры. Shaker Verlag , Aachen 2005. ISBN 3-8322-4515-4.
• Грегори Гутин, Абрахам П. Пуннен: Задача коммивояжера и ее варианты . Kluwer Academic Publishers. Выдержки онлайн (англ.)
• Вальтер Шмиттинг: Задача коммивояжера - приложения и эвристическое использование структур Вороного / Делоне для решения евклидовых двумерных задач коммивояжера .

веб ссылки

• Игра TSP - интерактивная игра по задаче «Коммивояжер» с подробным объяснением и иллюстрацией процедуры решения.
• Главная страница задачи коммивояжера - подробная информация о задаче коммивояжера (на английском языке)
• TSPLIB - Сборник тестовых экземпляров TSP и различных вариантов (английский)
• Спектр науки (4/99): Оптимизированная одиссея - статья Мартина Грётчеля и Манфреда Падберга
• Интернет VRP - подробная информация о проблеме с маршрутизацией транспортных средств (на английском языке)
• 40-й алгоритм недели - IT год 2006 TSP или оптимальный тур на Святой Николай.
• Free Tourplan - программное обеспечение с открытым исходным кодом для решения задач планирования туров, включая TSP

Эта статья была добавлена в список отличных статей 7 ноября 2006 года в этой версии .