Solving a Routing Problem with the Aid of an Independent Computations Scheme

Аннотация

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