THE ROUTING PROBLEMS WITH OPTIMIZATION OF THE STARTING POINT: DYNAMIC PROGRAMMING

Переведенное название: Маршрутная задача с оптимизацией стартовой точки: динамическое программирование

Результат исследований: Вклад в журналСтатья

1 Цитирования (Scopus)

Аннотация

Рассматривается экстремальная задача маршрутизации, ориентированная на инженерные приложения в машиностроении. Имеется в виду известная задача управления инструментом при листовой резке деталей на машинах с ЧПУ. Используется математическая модель, включающая систему мегаполисов (непустых конечных множеств) и функции стоимости, зависящие от списка заданий. Мегаполисы конструируются на основе дискретизации эквидистант, отвечающих контурам деталей, а зависимость от списка заданий возникает из соображений, связанных с учетом ограничений динамического характера, возникающих по мере выполнения заданий. Среди всех ограничений выделяются условия предшествования (предваряющая резка внутренних контуров детали в сравнении с внешним, более ранняя резка крупных деталей и т.д.). Рациональный учет условий предшествования позволяет в определенной степени снизить сложность вычислений при использовании широко понимаемого динамического программирования (ДП) в реализации, развивающей схему Р.Беллмана. Данный подход позволяет принципиально решать задачу оптимизации комплексов, включающих начальное состояние (точку старта), способ нумерации мегаполисов в порядке их посещения и конкретную траекторию процесса. Для задачи, осложненной зависимостью терминальной функции от начального состояния, используется декомпозиционный алгоритм, позволяющий в существенной части процедуры применять единую (для всех начальных состояний) схему ДП. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ; проведен вычислительный эксперимент.
Переведенное названиеМаршрутная задача с оптимизацией стартовой точки: динамическое программирование
Язык оригиналаАнглийский
Страницы (с-по)102-121
Число страниц20
ЖурналИзвестия Института математики и информатики Удмуртского государственного университета
Том54
DOI
СостояниеОпубликовано - 2019

Ключевые слова

  • Dynamic programming
  • Precedence conditions
  • Routing problem

Предметные области ASJC Scopus

  • Mathematics(all)
  • Computational Theory and Mathematics

Предметные области WoS

  • Математика

ГРНТИ

  • 27.00.00 МАТЕМАТИКА

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

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

Fingerprint Подробные сведения о темах исследования «Маршрутная задача с оптимизацией стартовой точки: динамическое программирование». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать