Маршрутом коммивояжера. Предложен алгоритм смягчения последствий катастроф

01.03.2020

За математической задачей нередко стоят вполне конкретные прикладные проблемы. В Институте математики и механики УрО РАН (Екатеринбург) разработан новый алгоритм решения задачи последовательного обхода, который может быть использован в самых разных ситуациях.

Например, с его помощью найдены оптимальные маршруты перемещения людей, позволяющие минимизировать их дозовую нагрузку при демонтаже радиационно опасных объектов в случае аварий на атомных электростанциях, подобных Чернобылю и Фукусиме. Разумеется, это не значит, что грядут новые катастрофы в атомной энергетике, просто ученые лучше других понимают: идеальный способ предотвращения любой аварии — полная готовность к ней. К тому же построенный алгоритм может быть полезен и во многих других сферах.

«Поиск» поговорил об этой актуальной работе с членом-корреспондентом РАН Александром ЧЕНЦОВЫМ.

Почему вас заинтересовала «задача о ликвидаторах»?

Мы занимаемся задачей снижения облучения персонала АЭС при выполнении работ в условиях повышенной радиации. Допустим, нужно дезактивировать территорию, на которой в результате аварии разбросаны точечные источники излучения. Их необходимо  обнаружить — с соблюдением всех необходимых требований безопасности — и изъять или демонтировать. Доза облучения, получаемая людьми, исполнителями этой задачи, существенно зависит от маршрута их перемещений в радиационных полях и от того, в какой последовательности они будут подходить к радиационно опасным объектам. В такой задаче есть немало ограничений. Прежде всего это так называемые условия предшествования (условие типа «одно после другого»), а также «стоимости» перемещений (т. е. дозы радиации).

В чем суть вашей разработки?

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

Наш подход основан на методе динамического программирования, разработанном известным американским математиком Ричардом Беллманом. Это способ решения сложных задач путем разбиения их на более простые. В нашем случае это пошаговый процесс, когда выполненное задание вычеркивается из списка. Правда, Беллман не рассматривал задачи с ограничениями, поэтому нам пришлось искать нетрадиционные варианты решения.

Первое, что нужно сделать в математике, — поставить задачу, причем если учитывать все мелкие подробности, ничего не получится. Сначала необходимо найти точку старта, затем — составить очередность посещений излучающих источников и траекторию процесса. Выбор очередности определяется многими факторами. Например, один источник излучения находится на другом: допустим, радиоактивный бак стоит на радиоактивной тумбе, и нижний источник можно демонтировать только после верхнего. Или другое ограничение: чтобы дезактивировать трубопровод, надо сначала разобраться с насосом.

Казалось бы, ограничения не способствуют оптимизации, а в нашем случае оказалось как раз наоборот. Предложенный алгоритм основан на нетрадиционном варианте динамического программирования, для которого не используется построение всего массива значений функции Беллмана.
Мы вывели варианты уравнения Беллмана, которые позволили охватить единой схемой большое число конкретных задач, связанных с маршрутизацией. Мы учли целый ряд ограничений, которые ранее не рассматривались на строгом уровне. Более того, в рамках используемого варианта динамического программирования удалось применить ограничения для снижения вычислительной сложности задачи.
Вообще в динамическом программировании много здравого смысла. Если сформулировать его суть совсем просто, то надо смотреть на шаг вперед и не ухудшать свое положение.

Ваш алгоритм применим только для решения задач, связанных с аварийными ситуациями?

Нет, конечно. На тех же атомных станциях есть задачи, когда необходимо демонтировать энергоблоки, выведенные из эксплуатации. Такие проблемы существуют на Белоярской и Нововоронежской АЭС. Причем это задачи очень сложные: на энергоблоке часто нужно выполнять работы, никуда не двигаясь, или перемещаться приходится не горизонтально, а вверх и вниз. Для того чтобы составить оптимальный маршрут и реализовать его на практике, нужен большой коллектив квалифицированных инженеров и программистов. Но сегодня это очень актуальная задача, и мы бы с удовольствием поучаствовали в ее решении.

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

В каких еще прикладных задачах может использоваться ваш алгоритм?

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

Одна из них — управление процессом листовой резки. Ее мы решаем в сотрудничестве с ведущим научным сотрудником лаборатории оптимального раскроя промышленных материалов и оптимальных маршрутных технологий УрФУ профессором Александром Петуниным. В задачах машиностроения, связанных с раскроем, нужно управлять движением режущего инструмента. Он должен последовательно «посещать» окрестности контуров вырезаемых деталей при наличии большого числа разнообразных ограничений, учитывая ограничения, предписывающие вырезать сначала внутренние контуры деталей и только после этого внешние. Имеются и другие ограничения: жесткость листа и деталей, тепловые допуски. При этом работу нужно сделать за максимально короткое время.
Есть также задачи о морских и авиационных перевозках, где надо посетить большое число пунктов. Наш алгоритм может работать и в этих случаях, причем выбор оптимального маршрута позволяет уменьшить расход топлива.

Беседу вела Елена ПОНИЗОВКИНА

Нет комментариев