Аннотация

Рассматриваются «аддитивные» задачи маршрутизации перемещений, осложненные ограничениями и возможной зависимостью функций стоимости от списка заданий. Постановки такого рода естественны при исследовании инженерных задач, возникающих в атомной энергетике и машиностроении. В первом случае речь идет о снижении дозовой нагрузки работников АЭС при выполнении комплекса работ, связанных с демонтажом излучающих элементов оборудования, а во втором - исследуются процедуры, связанные с листовой резкой на машинах с ЧПУ. В статье рассматриваются вопросы, связанные с применением динамического программирования для решения задач маршрутизации ощутимой размерности, осложненных ограничениями и вышеупомянутой зависимостью функций стоимости от списка заданий. Имеются в виду процедуры тестирования и локального улучшения эвристик. В обоих вариантах используется аппарат широко понимаемого динамического программирования, реализуемый для подзадач умеренной размерности. Предполагается, однако, что упомянутые подзадачи осложнены условиями того же типа, что и в исходной «большой» задаче (ограничения, функции стоимости с зависимостью от списка заданий). Для реализации «локального» динамического программирования применяется схема, использующая условия предшествования в интересах снижения сложности вычислений (условия предшествования имеются практически во всех вариантах вышеупомянутых прикладных задач); при этом не требуется построение всего массива значений функции Беллмана. Учет динамических ограничений, возникающих по мере выполнения заданий, осуществляется посредством введения специальных пороговых функций стоимости, играющих роль ощутимых штрафов за нарушение ограничений. В работе приведены результаты вычислительного эксперимента как на уровне тестирования упомянутых эвристик, так и при решении задач ощутимой размерности. В основе статьи находится доклад одного из авторов, сделанный на конференции МКПУ-10.
Переведенное названиеDYNAMIC PROGRAMMING AND HEURISTIC METHODS IN ROUTING PROBLEMS
Язык оригиналаРусский
Страницы (с-по)169-181
Число страниц13
ЖурналИзвестия ЮФУ. Технические науки
Номер выпуска9(194)
DOI
СостояниеОпубликовано - 2017

ГРНТИ

  • 27.41.00 Вычислительная математика

Уровень публикации

  • Перечень ВАК

Fingerprint Подробные сведения о темах исследования «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И ЭВРИСТИЧЕСКИЕ МЕТОДЫ В ЗАДАЧАХ МАРШРУТИЗАЦИИ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать