Статья

Название статьи ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И ЭВРИСТИЧЕСКИЕ МЕТОДЫ В ЗАДАЧАХ МАРШРУТИЗАЦИИ
Автор А. Г. Ченцов, П. А. Ченцов
Рубрика РАЗДЕЛ III. ПРОЕКТИРОВАНИЕ И ПРИМЕНЕНИЕ РОБОТОТЕХНИЧЕСКИХ И МЕХАТРОННЫХ СИСТЕМ
Месяц, год 09, 2017
Индекс УДК 519.6
DOI 10.23683/2311-3103-2017-9-169-181
Аннотация Рассматриваются «аддитивные» задачи маршрутизации перемещений, осложненные ограничениями и возможной зависимостью функций стоимости от списка заданий. Постановки такого рода естественны при исследовании инженерных задач, возникающих в атомной энергетике и машиностроении. В первом случае речь идет о снижении дозовой нагрузки работников АЭС при выполнении комплекса работ, связанных с демонтажом излучающих элементов оборудования, а во втором – исследуются процедуры, связанные с листовой резкой на машинах с ЧПУ. В статье рассматриваются вопросы, связанные с применением динамического программирования для решения задач маршрутизации ощутимой размерности, осложненных ограничениями и вышеупомянутой зависимостью функций стоимости от списка заданий. Имеются в виду процедуры тестирования и локального улучшения эвристик. В обоих вариантах используется аппарат широко понимаемого динамического программирования, реализуемый для подзадач умеренной размерности. Предполагается, однако, что упомянутые подзадачи осложнены условиями того же типа, что и в исходной «большой» задаче (ограничения, функции стоимости с зависимостью от списка заданий). Для реализации «локального» динамического программирования применяется схема, использующая условия предшествования в интересах снижения сложности вычислений (условия предшествования имеются практически во всех вариантах вышеупомянутых прикладных задач); при этом не требуется построение всего массива значений функции Беллмана. Учет динамических ограничений, возникающих по мере выполнения заданий, осуществляется посредством введения специальных пороговых функций стоимости, играющих роль ощутимых штрафов за нарушение ограничений. В работе приведены результаты вычислительного эксперимента как на уровне тестирования упомянутых эвристик, так и при решении задач ощутимой размерности. В основе статьи находится доклад одного из авторов, сделанный на конференции МКПУ-10.

Скачать в PDF

Ключевые слова Маршрутные задачи; условия предшествования; оптимизация резки металла.
Библиографический список 1. Little L.D.C., Murty K.G., Sweeney D.W., Karel C. An Algorithm for the Travelling Salesman Problem // Opns. Res. – 1963. – Vol. 11, No. 6. – P. 972-990.
2. William J. Cook. In pursuit of the traveling salesman. Mathematics at the limits of computation. – NJ. Princeton Univer. Press., 2012. – 248 p.
3. Gutin G., Punnen A. The Traveling Salesman Problem and Its Variations. – Berlin: Springer, 2002. – 850 p.
4. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. – 1989. – № 9. – С. 3-34.
5. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // Автоматика и телемеханика. – 1989. – № 10. – С. 3-29.
6. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // Автоматика и телемеханика. – 1989. – № 11. – С. 3-26.
7. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. – Екатеринбург: Изд-во УМЦ УПИ, 2016. – 220 с.
8. Коробкин В.В., Сесекин А.Н., Ташлыков О.Л., Ченцов А.Г. Методы маршрутизации и их приложения в задачах повышения безопасности и эффективности эксплуатации атомных станций. – М.: Изд-во “Новые технологии”, 2012. – 234 с.
9. Петунин А.А. О некоторых стратегиях формирования маршрута инструмента при разработке управляющих программ для машин термической резки материала // Вестник УГАТУ. Сер. Управление, вычислительная техника и информатика. – 2009. – Т. 13, № 2 (35). – C. 280-286.
10. Фроловский В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Информационные технологии в проектировании и производстве. – 2005. – № 4. – С. 63-66.
11. Верхотуров М.А., Тарасенко П.Ю. Математическое обеспечение задачи оптимизации пути режущего инструмента при плоском фигурном раскрое на основе цепной резки // Вестник УГАТУ. Сер. Управление, вычислительная техника и информатика. – 2008.
– T. 10, № 2 (27). – С. 123-130.
12. Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации движения инструмента в машинах листовой резки с числовым программным управлением // Науч.-техн. ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. – 2013. – № 2 (169). – С. 103-111.
13. Wang G.G., Xie S.Q. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization // International Journal of Production Research. – Jun. 2005. – Vol. 43 (11). – P. 2195-2216.
14. Lee M.-K., Kwon K.-B. Cutting path optimization in CNC cutting processes using a two-step genetic algorithm // Int. J. Product. Res. Dec. – 2006. – Vol. 44 (24). – P. 5307-5326.
15. Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. – 2016. – № 11. – С. 96-117.
16. Ченцов А.Г., Ченцов А.А. Дискретно-непрерывная задача маршрутизации с условиями предшествования // Тр. Ин-та математики и механики. – 2017. – T. 23, № 1. – C. 275-292.
17. Ченцов А.Г. Беллмановские вставки в задаче маршрутизации с ограничениями и с усложненными функциями стоимости // Вестник УдГУ. Математика. Механика. Компьютерные науки. – 2014. – Вып. 4. – С.122-141.
18. Ченцов А.Г. Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования // Вестник УдГУ. Математика. Механика. Компьютерные науки. – 2016. – Т. 26, № 4. – C. 565-578.
19. Петунин А.А., Ченцов А.А., Ченцов А.Г., Ченцов П.А. Элементы динамического программирования в конструкциях локального улучшения эвристических решений задач маршрутизации с ограничениями // Автоматика и телемеханика. – 2017. – Вып. 4.
– С. 106-125.
20. Ченцов А.А., Ченцов А.Г. К вопросу о нахождении значения маршрутной задачи с ограничениями // Проблемы управления и информатики. – 2016. – № 1. – С. 41-54.
21. Ченцов А.А., Ченцов А.Г. Задача последовательного обхода мегаполисов // Вестник Тамбовского университета. Сер.: Естественные и технические науки. – 2014. – Т. 19, вып. 2. – С. 454-475.
22. Петунин А.А., Ченцов А.Г., Ченцов П.А. Локальные вставки на основе динамического программирования в задаче маршрутизации с ограничениями // Вестник УдГУ. Математика. Механика. Компьютерные науки. – 2014. – Вып. 2. – С. 56-75.
23. Петунин А.А., Ченцов А.Г., Ченцов П.А. К вопросу о маршрутизации перемещений при листовой резке деталей // Вестник ЮУрГУ. Сер. Математическое моделирование и программирование. – 2017. – Т. 10, № 3. – С. 25-39.
24. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. – М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2008. – 240 с.
25. Lawler, Eugene L. Efficient implementation of dynamic programming algorithms for sequencing problems // Mathematical Centre. 1979.BW 106/79.
26. Hoeft J., Palekar U.S. Heuristics for the plate-cutting traveling salesman problem // IIE Transactions. – 1997. – Vol. 29 (9). – P. 719-731.
27. Bellman R. On a Routing Problem // Quart. Appl. Math. – 1958. – Vol. 16. – P. 87-90.
28. Held M., Karp R.M. A Dynamic Programming Approach to Sequencing problems // Journal of the Society for Industrial and Applied Mathematics. – 1962. – No. 10 (1). – P. 196-210.
29. Alkaya A.F., Duman E. Combining and solving sequence dependent travelling salesman and quadratic assignment problems in PCB assembly // Discrete Applied Mathematics. – No. 192. – P. 2-16.

Comments are closed.