Каковы реальные отраслевые приложения TSP?

я. Сверление печатных плат Прямое применение TSP связано с проблемой сверления печатных плат (PCBs). Чтобы соединить проводник одного слоя с проводником другого слоя или разместить выводы интегральных схем, в плате необходимо просверлить отверстия. Отверстия могут быть разного размера. Чтобы последовательно просверлить два отверстия разного диаметра, головка станка должна переместиться в инструментальный ящик и сменить буровое оборудование. Это довольно много времени. Таким образом, ясно, что нужно выбрать какой-то диаметр, просверлить все отверстия одного диаметра, сменить сверло, просверлить отверстия следующего диаметра и т. д. Таким образом, эту задачу о сверлении можно рассматривать как ряд ЗК, по одному на каждое. диаметр отверстия, где «города» — начальное положение и множество всех отверстий, которые можно просверлить одним и тем же сверлом. «Расстояние» между двумя городами определяется временем, которое требуется для перемещения буровой головки из одного положения в другое. Цель состоит в том, чтобы свести к минимуму время перемещения головки машины.

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

III. Рентгеновская кристаллография Анализ структуры кристаллов является важным приложением TSP. Здесь для получения информации о структуре кристаллического материала используется рентгеновский дифрактометр. Для этого детектор измеряет интенсивность рентгеновских отражений кристалла с различных положений. В то время как само измерение может быть выполнено довольно быстро, существуют значительные затраты времени на позиционирование, поскольку для некоторых экспериментов необходимо реализовать до сотен тысяч местоположений. В двух примерах, на которые мы ссылаемся, позиционирование включает в себя перемещение четырех двигателей. Время, необходимое для перехода из одного положения в другое, можно рассчитать очень точно. Результат эксперимента не зависит от последовательности, в которой производятся измерения в различных положениях. Однако общее время, необходимое для эксперимента, зависит от последовательности. Поэтому задача состоит в том, чтобы найти последовательность, минимизирующую общее время позиционирования. Это приводит к задаче коммивояжера.

IV. Разводка компьютера Сообщается о частном случае соединения компонентов на плате компьютера. Модули расположены на плате компьютера, и к ним должно быть подключено заданное подмножество контактов. В отличие от обычного случая, когда желательно соединение дерева Штейнера, здесь требуется, чтобы к каждому выводу было присоединено не более двух проводов. Отсюда возникает проблема поиска кратчайшего гамильтонова пути с неопределенными начальной и конечной точками. Аналогичная ситуация возникает для так называемой проводки тестовой шины. Для тестирования изготовленной платы необходимо реализовать соединение, которое входит в плату в определенной точке, проходит через все модули и заканчивается в определенной точке. Для каждого модуля у нас также есть определенная точка входа и выхода для этой тестовой проводки. Эта задача также сводится к решению задачи о гамильтоновых путях с той разницей, что расстояния несимметричны и заданы начальная и конечная точки.

v. Проблема комплектования заказов на складах Эта проблема связана с обработкой материалов на складе. Предположим, что на склад поступает заказ на определенное подмножество товаров, хранящихся на складе. Некоторое транспортное средство должно собрать все элементы этого заказа, чтобы отправить их клиенту. Сразу видна связь с TSP. Места хранения предметов соответствуют узлам графа. Расстояние между двумя узлами определяется временем, необходимым для перемещения транспортного средства из одного места в другое. Задача нахождения кратчайшего маршрута для транспортного средства с минимальным временем посадки теперь может быть решена как TSP. В частных случаях эта проблема решается легко, vi. Маршрутизация транспортных средств Предположим, что в городе ежедневно в течение определенного промежутка времени, скажем, 1 час, необходимо опорожнять n почтовых ящиков. Задача состоит в том, чтобы найти минимальное количество грузовиков для этого и кратчайшее время, необходимое для проведения сборов с использованием этого количества грузовиков. В качестве другого примера предположим, что n клиентов требуют определенного количества некоторых товаров, и поставщик должен удовлетворить все потребности с помощью парка грузовиков. Задача состоит в том, чтобы найти такое распределение клиентов по грузовикам и график доставки для каждого грузовика, чтобы не превышалась грузоподъемность каждого грузовика и сводилось к минимуму общее расстояние в пути. Несколько вариантов этих двух проблем, в которых сочетаются ограничения по времени и мощности, распространены во многих реальных приложениях. Эта задача решается как TSP, если нет ограничений по времени и пропускной способности и если количество грузовиков фиксировано (скажем, m). В этом случае мы получаем задачу m-продавцов. Тем не менее, можно применить методы TSP, чтобы найти хорошие возможные решения этой проблемы.

vii. Нанесение масок при производстве печатных плат Для производства каждого слоя печатной платы, а также для слоев интегральных полупроводниковых приборов необходимо изготовить фотошаблон. В нашем случае для печатных плат это делается с помощью механического чертёжного устройства. Плоттер перемещает линзу по стеклянной пластине со светочувствительным покрытием. Затвор может открываться или закрываться для доступа к определенным частям пластины. Доступны различные апертуры для создания различных структур на плате. Необходимо рассмотреть два типа структур. Линия экспонируется на пластине путем перемещения закрытой заслонки в одну конечную точку линии, затем открывания заслонки и перемещения ее в другую конечную точку линии. Затем затвор закрывается. Структура точечного типа создается путем перемещения (с соответствующей апертурой) в положение этой точки, затем открытия затвора только для того, чтобы сделать короткую вспышку, а затем снова его закрытия. Точное моделирование задачи управления плоттером приводит к задаче более сложной, чем задача TSP, а также более сложной, чем задача сельского почтальона.

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