АВТОМАТИЗАЦИЯ ВЫБОРА КРАТЧАЙШИХ МАРШРУТОВ СУДОВ НА ОСНОВЕ МОДИФИЦИРОВАННОГО АЛГОРИТМА БЕЛЛМАНА-ФОРДА

Аннотация

Решается задача автоматизации операций определения кратчайших маршрутов для группы судов, получивших задание достижения условных целей с известными координатами, расположенными в ограниченном пространстве. При оперативном управлении процессом выхода судов в заданный район важен показатель времени, минимизация которого связана с поиском маршрута, имеющего самую короткую длину из всех возможных маршрутов. Ключевым вопросом в проблеме автоматизации формирования оптимальных маршрутов является выбор математического аппарата не только для расчета длин кратчайших маршрутов, но и для восстановления самих кратчайших путей. С этой целью в работе подробно рассматривается рекурсивный метод динамической оптимизации на основе модифицированного алгоритма Беллмана-Форда, позволяющего избежать большой размерности и вычислительной сложности в решении данной задачи. Предложенный метод, в отличие от других методов динамической оптимизации, позволяет автоматизировать определение кратчайшего пути в сетевой модели со сложной топологией при наличии в ней дуг с отрицательными весами. Практическая реализация модифицированного алгоритма Беллмана-Форда показана на примере расчета сетевой модели со сложной топологией с применением итерационной процедуры по программе, составленной в кодах MATLAB. Реализованная на ее основе компьютерная модель компактна, проста и, в отличие от существующих моделей, позволяет устранить ограничения, связанные с наличием отрицательных весов и циклов на сетевой модели, автоматизировать расчеты кратчайших путей в разветвленном районе мест рыболовецких промыслов с использованием компьютерных технологий, реализованных средствами MATLAB, и заданного критерия качества. На примере расчета подтверждается корректность полученных результатов исследований автора. Предложенные алгоритм и рекурсивная процедура, а также выводы из их анализа могут найти применение в организации движения морского, воздушного и наземного транспорта.

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

маршрут, цель, алгоритм, путь, оптимизация, процедура, центр управления, транспорт

Читать полный текст статьи:  PDF

Список литературы

Чертков А. А. Рекурсивный метод оптимизации логистических путей средствами MATLAB / А. А. Чертков, А. А. Вардомская, А. А. Дмитриев // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 6 (34). - С. 196-204.
Касьянов В. Н. Графы в программировании: визуализация и применение / В. Н. Касьянов, В. А. Евстигнеев. - СПб.: БХВ-Петербург, 2003. - 1104 с.
Сазонов А. Е. Прогнозирование траектории движения судна при помощи нейронной сети / А. Е. Сазонов, В. В. Дерябин // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2013. - № 3 (22). - С. 6-13.
Gao S. Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks / S. Gao, H. Huang // Transportation Research Part C: Emerging Technologies. - 2012. - Vol. 21. - Is. 1. - Pp. 196-213. DOI: 10.1016/j.trc.2011.09.007.
Fu L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information / L. Fu // Transportation Research Part B: Methodological. - 2001. - Vol. 35. - Is. 8. - Pp. 749-765. DOI: 10.1016/S0191-2615(00)00019-9.
Сахаров В. В. Модели и алгоритмы оптимизации технологических процессов на объектах водного транспорта в среде MatLab / В. В. Сахаров, А. А. Кузьмин, А. А. Чертков. - СПб.: Изд-во ГУМРФ им. адм. С. О. Макарова. - 2015. - 436 с.
Castillo O. Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots / O. Castillo, L. Trujillo, P. Melin // Soft Computing-A Fusion of Foundations, Methodologies and Applications. - 2007. - Vol. 11. - Is. 3. - Pp. 269-279. DOI: 10.1007/s00500-006-0068-4.
Чертков А. А. Итерационный алгоритм выбора оптимальной стратегии группового взаимодействия подвижных объектов / А. А. Чертков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 4 (32). - С. 207-215.
Сахаров В. В. Алгоритм оптимального планирования группового взаимодействия роботов / В. В. Сахаров, А. А. Чертков, Д. С. Тормашев // Морской вестник. - 2014. - № 4. - С. 119-122.
Каляев И. А. Модели и алгоритмы коллективного управления в группах роботов / И. А. Каляев, А. Р. Гайдук, С. Г. Капустян. - М: Физматлит, 2009. - 280 с.
Kalyaev I. A. UAV group control in task of order forming / I. A. Kalyaev, A. R. Gaiduk, S. G. Kapustyan // Робототехника и техническая кибернетика. - 2014. - № 4 (5). - С. 28-39.
Александров В. А. Коллективный алгоритм выделения операционных подпространств для группы роботов при решении задачи покрытия территории / В. А. Александров, А. И. Кобрин // Известия высших учебных заведений. - Серия: Машиностроение. - 2011. - № 9. - С. 65-69.
Александров В. А. Аппаратно-программный комплекс для моделирования задач группового управления мобильными роботами / В. А. Александров, А. И. Кобрин // Вестник Московского энергетического института. - 2011. - № 3. - С. 88-95.
Кирсанов М. Н. Анализ алгоритмов выбора оптимальных маршрутов группы судов / М. Н. Кирсанов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2016. - № 2 (36). - C. 183-190. DOI: 10.21821/2309-5180-2016-8-2-183-190.
Dedkov V. A. The problem of control for multirobot systems / V. A. Dedkov, M. N. Kirsanov // Инновационные информационные технологии. - 2013. - Т. 2. - № 2. - С. 206-213.
Kirsanov A. Path planning for the autonomous underwater vehicle / A. Kirsanov, S. Anavatti, T. Ray // International Conference on Swarm, Evolutionary, and Memetic Computing. - Springer, Cham, 2013. - Pp. 476-486. DOI: 10.1007/978-3-319-03756-1_43.
Zeng Z. A survey on path planning for persistent autonomy of autonomous underwater vehicles / Z. Zeng, L. Lian, K. Sammut, F. He, Y. Tang, A. Lammas // Ocean Engineering. - 2015. - Vol. 110. - Part A. - Pp. 303- 313. DOI: 10.1016/j.oceaneng.2015.10.007.
Bellman R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. - 1958. - Vol. 16. - № 1. - C. 87-90. DOI: 10.1090/qam/102435.

Об авторах

Чертков Александр Александрович - кандидат технических наук, доцент

chertkov51@mail.ru. kaf_electricautomatic@gumrf.ru

ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»