Маршрутная задача с оптимизацией стартовой точки: динамическое программирование
Аннотация
Рассматривается экстремальная задача маршрутизации, ориентированная на инженерные приложения в машиностроении. Имеется в виду известная задача управления инструментом при листовой резке деталей на машинах с ЧПУ. Используется математическая модель, включающая систему мегаполисов (непустых конечных множеств) и функции стоимости, зависящие от списка заданий. Мегаполисы конструируются на основе дискретизации эквидистант, отвечающих контурам деталей, а зависимость от списка заданий возникает из соображений, связанных с учетом ограничений динамического характера, возникающих по мере выполнения заданий. Среди всех ограничений выделяются условия предшествования (предваряющая резка внутренних контуров детали в сравнении с внешним, более ранняя резка крупных деталей и т.д.). Рациональный учет условий предшествования позволяет в определенной степени снизить сложность вычислений при использовании широко понимаемого динамического программирования (ДП) в реализации, развивающей схему Р.Беллмана. Данный подход позволяет принципиально решать задачу оптимизации комплексов, включающих начальное состояние (точку старта), способ нумерации мегаполисов в порядке их посещения и конкретную траекторию процесса. Для задачи, осложненной зависимостью терминальной функции от начального состояния, используется декомпозиционный алгоритм, позволяющий в существенной части процедуры применять единую (для всех начальных состояний) схему ДП. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ; проведен вычислительный эксперимент.
Литература
2. Cook W.J. In pursuit of the traveling salesman. Mathematics at the limits of computation. Princeton, New Jersey: Princeton University Press, 2012.
3. Ченцов А.Г., Ченцов П.А. Оптимизация точки старта в задаче последовательного обхода мегаполисов при наличии условий предшествования // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. 2018. Т. 11. Вып. 2. С. 83-95.
4. Ченцов А.Г., Ченцов П.А. Об одной задаче маршрутизации с оптимизацией точки старта-финиша // Известия Института математики и информатики Удмуртского государственного университета. 2018. Т. 52. С. 103-115.
https://doi.org/10.20537/2226-3594-2018-52-08
5. Bellman R. Dynamic programming treatment of the travelling salesman problem // Journal of the ACM. 1962. Vol. 9. Issue 1. P. 61-63.
6. Held M., Karp R.M. A dynamic programming approach to sequencing problems // Journal of the Society for Industrial and Applied Mathematics. 1962. Vol. 10. No. 1. P. 196-210.
https://doi.org/10.1137/0110015
7. Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Динамическое программирование в обобщенной задаче «на узкие места» и оптимизация точки старта // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2018. Т. 28. Вып. 3. С. 348-363.
https://doi.org/10.20537/vm180306
8. Kuratowski K., Mostowski A. Set theory. Amsterdam: North-Holland Publishing Company, 1967.
9. Dieudonne J. Foundations of modern analysis. New York: Academic Press, 1960.
10. Cormen T., Leiserson C., Rivest R. Introduction to algorithms. Cambridge: MIT Press, 1990.
11. Ченцов А.Г. Экстремальные задачи маршрутизации и распределения заданий: вопросы теории. М.-Ижевск: Регулярная и хаотическая динамика, Ижевский институт компьютерных исследований, 2008.
12. Ченцов А.Г. Задача последовательного обхода мегаполисов с условиями предшествования // Автоматика и телемеханика. 2014. № 4. С. 170-190.
13. Ченцов А.Г. К вопросу о маршрутизации комплексов работ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 1. С. 59-82.
https://doi.org/10.20537/vm130107
14. Ченцов А.Г., Ченцов П.А. Маршрутизация в условиях ограничений: задача о посещении мегаполисов // Автоматика и телемеханика. 2016. № 11. С. 96-117.
15. Lawler E.L. Efficient implementation of dynamic programming algorithms for sequencing problems / CWI. Technical Reports. Stichting Mathematish Centrum. Mathematische Besliskunde. 1979. BW 106/79 P. 1-16.
16. Ченцов А.Г., Ченцов П.А. Динамическое программирование и эвристические методы в задачах маршрутизации // Известия ЮФУ. Технические науки. 2017. № 9. C. 169-181.
https://doi.org/10.23683/2311-3103-2017-9-169-181
Опубликована 2019-11-20