- Код статьи
- 10.31857/S0005231023100033-1
- DOI
- 10.31857/S0005231023100033
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 10
- Страницы
- 18-36
- Аннотация
- Рассматривается задача комбинаторной оптимизации поиска плана перехвата в простых движениях прямолинейно движущихся целей как модификация динамической задачи коммивояжера. Вводятся новые для такой задачи макрохарактеристики и определения, которые используются для классификации полученных решений. Описаны векторные критерии, составленные из нескольких функционалов, имеющих прикладное значение. Для двух типов критериев доказаны принципы неоптимальности простоя и максимальной скорости. Предложен и реализован интеллектуальный полнопереборный алгоритм с элементами динамического программирования для поиска оптимальных планов по введенным критериям перехвата. Для набора различных начальных обстановок собрана статистика решений разработанного алгоритма, на которой исследованы предложенные макрохарактеристики и сделаны выводы об их применимости в качестве локальных правил для жадного алгоритма поиска субоптимального плана перехвата.
- Ключевые слова
- динамическая задача коммивояжера комбинаторная оптимизация перехват в простых движениях
- Дата публикации
- 15.10.2023
- Год выхода
- 2023
- Всего подписок
- 0
- Всего просмотров
- 8
Библиография
- 1. Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. I // А и Т. 1971. No. 8. P. 116-123.
- 2. Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. II // А и Т. 1971. No. 10. P. 142-147.
- 3. Picard J.C., Queyranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling // Oper. Res. 1978. V. 26. No. 1. P. 86-110. https://doi.org/10.1287/opre.26.1.86
- 4. Helvig C.S., Robins G., Zelikovsky A. The moving-target traveling salesman problem // J. Algorithm.Comput. Technol. 2003. V. 49. No. 1. P. 153-174. https://doi.org/10.1016/S0196-6774 (03)00075-0
- 5. Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco, Calif.: W.H. Freeman & Co., 1979.
- 6. Ny J., Feron E., Frazzoli E. On the Dubins traveling salesman problem // IEEE Trans. Automat. Contr. 2012. V. 57. No. 1. P. 265-270. https://doi.org/10.1109/TAC.2011.2166311
- 7. Isaiah P., Shima T. Motion planning algorithms for the Dubins travelling salesperson problem // Automatica. 2015. V. 53. P. 247-255. https://doi.org/10.1016/j.automatica.2014.12.041
- 8. Stieber A. The multiple traveling salesperson problem with moving targets. Brandenburg University of Technology Cottbus-Senftenberg, 2022.
- 9. Ahrens B. The tour construction framework for the dynamic Travelling Salesman Problem // SoutheastCon, IEEE. 2015. P. 1-8. https://doi.org/10.1109/SECON.2015.7132999
- 10. Choubey N.S. Moving target travelling salesman problem using genetic algorithm // Int. J. Comput. Appl. 2013. V. 70. No. 1. P. 30-34. https://doi.org/10.5120/11937-7726
- 11. Smith C.D. Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets // Thesis (M.S.), Department of Civil and Mechanical Engineering. University of Missouri, Kansas City, 2021.
- 12. Buzikov M.E., Galyaev A.A. Minimum-time lateral interception of a moving target by a Dubins car // Automatica. 2022. V. 135. https://doi.org/10.1016/j.automatica.2021.109968
- 13. Galyaev A.A., Lysenko P.V., Rubinovich E.Y. Optimal Stochastic Control in the Interception Problem of a Randomly Tacking Vehicle // Mathematics. 2021. V. 9. No. 19. https://doi.org/10.3390/math9192386
- 14. Galyaev A.A., Dobrovidov A.V., Lysenko P.V., Shaikin M.E. et.al. Path Planning in Threat Environment for UUV with Non-Uniform Radiation Pattern // Sensors. 2020. V. 20. No. 7. https://doi.org/10.3390/s20072076
