Установить проблему TSP
В комбинаторной оптимизации набор TSP , также известный как обобщенный TSP , групповой TSP , TSP с одним набором , TSP с множественным выбором или задача коммивояжера , является обобщением задачи коммивояжера (TSP), в соответствии с чем она Требуется найти кратчайший обход графа, посещающий все заданные подмножества вершин графа. Подмножества вершин должны быть непересекающимися, поскольку случай перекрывающихся подмножеств можно свести к случаю непересекающихся. [1] Обычный TSP — это частный случай множества TSP, когда все подмножества, которые необходимо посетить, являются одиночными . Следовательно, множество TSP также является NP-трудным .
Существует преобразование экземпляра заданного TSP в экземпляр стандартного асимметричного TSP. [2] Идея состоит в том, чтобы соединить каждое подмножество в ориентированный цикл с ребрами нулевого веса и наследовать исходящие ребра из исходного графа, сдвигая на одну вершину назад по этому циклу. Продавец, посещая вершину v в некотором подмножестве, бесплатно обходит цикл и выходит из него из вершины, предшествующей v , по исходящему ребру, соответствующему исходящему ребру вершины v в исходном графе.
Set TSP имеет множество интересных применений в ряде задач планирования пути. Например, задача совместной маршрутизации двух транспортных средств может быть преобразована в набор TSP, [3] точные нижние границы для TSP Дубинса и обобщенной задачи о пути Дубинса можно вычислить путем решения Set TSP. [4] [5]
Иллюстрация из задачи о раскрое запасов
[ редактировать ]Задача одномерной резки материала , применяемая в производстве бумаги и пластиковой пленки, включает в себя разрезание больших рулонов на более мелкие. Это делается путем создания схем резки, как правило, для минимизации отходов. Как только такое решение будет найдено, можно попытаться свести к минимуму замену ножей, изменяя последовательность рисунков (вверх и вниз на рисунке) или перемещая валки влево или вправо внутри каждого рисунка. Эти ходы не влияют на трату раствора.
На приведенном выше рисунке узоры (шириной не более 198) представляют собой строки; смена ножей обозначена маленькими белыми кружками; например, лекала 2-3-4 имеют валик размера 42,5 слева - соответствующий нож не должен перемещаться. Каждый шаблон представляет собой набор TSP, одну из перестановок которого необходимо посетить. Например, для последнего шаблона, содержащего два повторяющихся размера (по два раза каждый), их 5! / (2! × 2!) = 30 перестановок. Число возможных решений приведенного выше примера равно 12! × (5!) 6 × (6!) 4 × (7!) 2 / ((2!) 9 × (3!) 2 ) ≈ 5.3 × 10 35 . Приведенное выше решение содержит 39 замен ножей и было получено эвристическим путем; неизвестно, является ли это оптимальным. Преобразования в обычный TSP, как описано в [2] будет включать TSP с 5520 узлами.
См. также
[ редактировать ]- Задача Фаньяно найти кратчайший путь, охватывающий все три стороны треугольника.
Ссылки
[ редактировать ]- ^ CE Noon, «Общая проблема коммивояжера» , докторская диссертация, 1988.
- ^ Перейти обратно: а б Полдень, Чарльз Э.; Бин, Джеймс К. (февраль 1993 г.). «Эффективное преобразование обобщенной задачи коммивояжера». ИНФОР: Информационные системы и операционные исследования . 31 (1): 39–44. дои : 10.1080/03155986.1993.11732212 . hdl : 2027.42/6833 .
- ^ Сатьянараяна Г. Маньям, Сивакумар Ратинам, Сваруп Дарбха, Дэвид Касбир, Юнкан Цао, Фил Чендлер (2016). «GPS запретила маршрутизацию БПЛА из-за ограничений связи». Журнал интеллектуальных и робототехнических систем . 84 (1–4): 691–703. дои : 10.1007/s10846-016-0343-2 . S2CID 33884807 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Сатьянараяна Г. Маньям, Сивакумар Ратинам (2016). «О жестком ограничении оптимума коммивояжера Дубинса». Журнал динамических систем, измерений и управления . 140 (7): 071013. arXiv : 1506.08752 . дои : 10.1115/1.4039099 . S2CID 16191780 .
- ^ Сатьянараяна Г. Маньям, Сивакумар Ратинам, Дэвид Касбир, Элой Гарсия (2017). «Твердое ограничение кратчайших путей Дубинса через последовательность точек». Журнал интеллектуальных и робототехнических систем . 88 (2–4): 495–511. дои : 10.1007/s10846-016-0459-4 . S2CID 30943273 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )