Задайте задачу TSP - Set TSP problem

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

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

Set TSP имеет множество интересных приложений для решения нескольких задач планирования пути. Например, проблема совместной маршрутизации двух транспортных средств может быть преобразована в набор TSP,[2] жесткие нижние границы для TSP Дубинса и обобщенной проблемы пути Дубинса могут быть вычислены путем решения Set TSP.[3][4]

Иллюстрация из задачи раскроя

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

Generalized TSP knife changes.png

На рисунке выше узоры (ширина не более 198) - ряды; смены ножей обозначены маленькими белыми кружками; например, у выкроек 2-3-4 слева рулон размером 42,5 - соответствующий нож не должен двигаться. Каждый шаблон представляет собой набор TSP, одну из перестановок которого необходимо посетить. Например, для последнего шаблона, который содержит два повторяющихся размера (по два раза каждый), их 5! / (2! × 2!) = 30 перестановок. Количество возможных решений вышеуказанного примера - 12! × (5!)6 × (6!)4 × (7!)2 / ((2!)9 × (3!)2) ≈ 5.3 × 1035. Вышеупомянутое решение содержит 39 замен ножей и было получено эвристическим методом; неизвестно, оптимально ли это. Преобразования в обычный TSP, как описано в [1] будет включать TSP с 5 520 узлами.

Смотрите также

  • Проблема Фаньяно найти самый короткий тур, который посещает все три стороны треугольника

Рекомендации

  1. ^ а б Чарльз Нун, Джеймс Бин (1993). «Эффективное преобразование обобщенной задачи коммивояжера». Цитировать журнал требует | журнал = (помощь)
  2. ^ Сатьянараяна Дж. Маньям, Шивакумар Ратинам, Сваруп Дарбха, Дэвид Касбер, Йонгджан Цао, Фил Чандлер (2016). «Маршрутизация БПЛА запрещена по GPS с ограничениями связи». Журнал интеллектуальных и робототехнических систем. 84: 691–703. Дои:10.1007 / s10846-016-0343-2.CS1 maint: несколько имен: список авторов (связь)
  3. ^ Сатьянараяна Г. Маньям, Шивакумар Ратхинам (2016). «О плотном ограничении оптимума для коммивояжера Дубинса». Журнал динамических систем, измерения и управления. 140 (7): 071013. arXiv:1506.08752. Дои:10.1115/1.4039099.
  4. ^ Сатьянараяна Дж. Маньям, Шивакумар Ратинам, Дэвид Касбер, Элой Гарсия (2017). «Плотно ограничивая кратчайшие тропы Дубинса через последовательность точек». Журнал интеллектуальных и робототехнических систем. 88 (2–4): 495–511. Дои:10.1007 / s10846-016-0459-4.CS1 maint: несколько имен: список авторов (связь)