Текущий выпуск Выпуск 4, 2017 Том 27

Об одной задаче маршрутизации, моделирующей перемещения в радиационных полях

 pdf (2305K)

Рассматривается задача маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Предполагается, что объекты посещения суть мегаполисы (непустые конечные множества), при посещении которых должны выполняться некоторые работы, именуемые далее внутренними. По постановке задачи имеются ограничения в виде условий предшествования. Стоимость перемещений зависит от списка заданий, которые не выполнены на момент перемещения. Ситуация такого рода возникает, в частности, при аварийных ситуациях, связанных с работой АЭС и подобных происходящим в Чернобыле и Фукусиме. Речь идет об утилизации источников радиоактивного излучения, осуществляемой последовательно во времени; в этом случае исполнитель находится под воздействием источников, которые не были демонтированы на момент соответствующего перемещения. За счет этого в функциях стоимости, оценивающих воздействие радиации на исполнителя, возникает зависимость от списка невыполненных заданий. Последние состоят в том или ином варианте выключения соответствующего источника. В настоящем исследовании излагается подход к решению данной задачи параллельным алгоритмом, реализуемым на суперкомпьютере «УРАН».

Ключевые слова: динамическое программирование, маршрут, условия предшествования, параллельный алгоритм
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2017, т. 27, вып. 4, с. 540-557
DOI: 10.20537/vm170405

On one routing problem modeling movement in radiation fields

We consider a routing problem with constraints and complicated cost functions. The visited objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each of them entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints. The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which is also referred to as “sequence dependence”, “position dependence”, and “state dependence”. Such a dependence arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement is exposed to radiation from the sources that have not yet been dealt with. This gives rise to dependence on pending tasks in the cost functions that measure the crew's radiation exposure. The latter dependence reflects the “shutdown” operations for the corresponding radiation sources. This paper sets forth an approach to a parallel solution for this problem, which was implemented and run on the URAN supercomputer.

Keywords: dynamic programming, route, precedence constraints, parallel computation
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2017, vol. 27, issue 4, pp. 540-557

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref