Аннотация:
Рассматривается задача маршрутизации перемещений, осложненная ограничениями различных типов (условия предшествования, ограничения на достижимость состояний при каждом перемещении и др.). Допускается многовариантность на этапе перемещений, что естественным образом приводит к задаче о посещении мегаполисов. Стоимости перемещений и работ, выполняемых при посещении мегаполисов, могут зависеть от списка заданий. Данный список может отвечать уже выполненным, либо, напротив, еще не выполненным заданиям. Допускается также, что "текущие" ограничения (на перемещения) могут зависеть от упомянутого списка заданий. Рассматриваемая постановка ориентирована на приложения к задачам атомной энергетики (проблема снижения облучаемости персонала АЭС при выполнении комплекса работ в условиях повышенной радиации) и машиностроения. В последнем случае, связанном с управлением инструментом при листовой резке деталей на машинах с ЧПУ, "текущие" ограничения на перемещения могут быть обусловлены тепловыми допусками по отношению к уже "пройденным" фрагментам листа. В статье приведена схема построения оптимального решения на основе широко понимаемого динамического программирования. Используемый при этом алгоритм реализован на ПЭВМ; результаты его применения иллюстрируются на модельных примерах.
Ключевые слова:
маршрут, трасса, условия предшествования.
Работа выполнена при финансовой поддержке
программы фундаментальных исследований Президиума РАН «Математические задачи современной теории управления».
Работа выполнена при финанcовой поддержке
Российского фонда фундаментальных исследований (проекты 14-08-00419, 15-01-07909).
Работа выполнена при финансовой поддержке Постановления № 211 Правительства Российской Федерации, контракт № 02.A03.21.0006.
Поступила в редакцию: 28.11.2015
Реферативные базы данных:
Тип публикации:
Статья
УДК:519.6
Образец цитирования:
А. Г. Ченцов, А. А. Ченцов, “Задача маршрутизации, осложненная зависимостью функций стоимости и "текущих" ограничений от списка заданий”, Модел. и анализ информ. систем, 23:2 (2016), 211–227
\RBibitem{CheChe16}
\by А.~Г.~Ченцов, А.~А.~Ченцов
\paper Задача маршрутизации, осложненная зависимостью функций стоимости и "текущих" ограничений от~списка заданий
\jour Модел. и анализ информ. систем
\yr 2016
\vol 23
\issue 2
\pages 211--227
\mathnet{http://mi.mathnet.ru/mais492}
\crossref{https://doi.org/10.18255/1818-1015-2016-2-211-227}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3504590}
\elib{https://elibrary.ru/item.asp?id=25810353}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais492
https://www.mathnet.ru/rus/mais/v23/i2/p211
Эта публикация цитируется в следующих 2 статьяx:
A. A. Chentsov, A. G. Chentsov, A. N. Sesekin, “Optimal routing in a problem with constraints and cost functions depending on the task list”, J. Phys.: Conf. Ser., 1864:1 (2021), 012050
А. Г. Ченцов, А. А. Ченцов, А. Н. Сесекин, “О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий”, Тр. ИММ УрО РАН, 26, № 3, 2020, 219–234; A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “On the Problem of Sequential Traversal of Megalopolises with Precedence Conditions and Cost Functions Depending on a List of Tasks”, Proc. Steklov Inst. Math. (Suppl.), 315, suppl. 1 (2021), S67–S80
Цитирование в формате AMSBIB
Обратная связь: