Research output: Contribution to journal › Article › peer-review
Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - ОПТИМИЗИРУЮЩИЕ МУЛЬТИВСТАВКИ В ЗАДАЧАХ МАРШРУТИЗАЦИИ С ОГРАНИЧЕНИЯМИ
AU - Ченцов, Александр Георгиевич
AU - Григорьев, Алексей Михайлович
PY - 2018
Y1 - 2018
N2 - Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.
AB - Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.
UR - https://elibrary.ru/item.asp?id=36873367
UR - http://www.scopus.com/inward/record.url?scp=85062716372&partnerID=8YFLogxK
UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000467766800006
U2 - 10.20537/vm180406
DO - 10.20537/vm180406
M3 - Статья
SP - 513
EP - 530
JO - Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
JF - Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
SN - 1994-9197
ER -
ID: 9085063