|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
The routing problems with optimization of the starting point: dynamic programming
[Маршрутная задача с оптимизацией стартовой точки: динамическое программирование]
A. G. Chentsovab, P. A. Chentsovac a N. N. Krasovskii Institute of Mathematics and Mechanics, Ural
Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
b Institute of Radioelectronics and Information Technologies, Ural Federal University, ul. Mira,
19, Yekaterinburg, 620002, Russia
c Mechanical Engineering Institute, Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
Аннотация:
Рассматривается экстремальная задача маршрутизации, ориентированная на инженерные приложения в машиностроении. Имеется в виду известная задача управления инструментом при листовой резке деталей на машинах с ЧПУ. Используется математическая модель, включающая систему мегаполисов (непустых конечных множеств) и функции стоимости, зависящие от списка заданий. Мегаполисы конструируются на основе дискретизации эквидистант, отвечающих контурам деталей, а зависимость от списка заданий возникает из соображений, связанных с учетом ограничений динамического характера, возникающих по мере выполнения заданий. Среди всех ограничений выделяются условия предшествования (предваряющая резка внутренних контуров детали в сравнении с внешним, более ранняя резка крупных деталей и т.д.). Рациональный учет условий предшествования позволяет в определенной степени снизить сложность вычислений при использовании широко понимаемого динамического программирования (ДП) в реализации, развивающей схему Р.Беллмана. Данный подход позволяет принципиально решать задачу оптимизации комплексов, включающих начальное состояние (точку старта), способ нумерации мегаполисов в порядке их посещения и конкретную траекторию процесса. Для задачи, осложненной зависимостью терминальной функции от начального состояния, используется декомпозиционный алгоритм, позволяющий в существенной части процедуры применять единую (для всех начальных состояний) схему ДП. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ; проведен вычислительный эксперимент.
Ключевые слова:
маршрутная задача, динамическое программирование, условия предшествования.
Поступила в редакцию: 30.07.2019
Образец цитирования:
A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Изв. ИМИ УдГУ, 54 (2019), 102–121
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iimi385 https://www.mathnet.ru/rus/iimi/v54/p102
|
Статистика просмотров: |
Страница аннотации: | 271 | PDF полного текста: | 156 | Список литературы: | 20 |
|