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

В работе решена операционная задача автоматизации построения и маршрутизации сетевой модели с известными координатами условных целей, поставленных группе судов для их достижения в течение минимального времени, что позволяет получить резервы ходового времени, необходимые для экономии топлива и энергии с учетом загрузки, стоимости груза, расходов на перевозки и др. Подчеркивается, что в условиях штормовой погоды и при управлении судами в ситуациях, связанных с корректировкой расписания, необходимы гибкие оперативные решения диспетчерских служб, принимаемые на основе численных методов оптимизации с использованием современных вычислительных сред. В связи с этим в работе рассмотрен метод динамического программирования, реализуемый с использованием алгоритма маршрутизации Беллмана - Форда, дополненный рекурсивной процедурой пошаговой оптимизации, снимающей ограничение алгоритма при наличии в графе обратно ориентированных ребер с отрицательными весами. Отмечается, что при наличии отрицательных весов возникают условия появления отрицательного цикла в графе, при котором практическая реализация алгоритма Беллмана - Форда становится невозможной из-за бесконечного цикла релаксаций (ослабления) весов вершин, входящих в этот цикл. Отсюда на ограниченном отрезке времени взвешивания всех вершин (проходов по всем ребрам) алгоритм может дать заведомо ложный результат. Предложенная процедура модификации известного алгоритма Беллмана - Форда устраняет это ограничение, позволяя применять его не только для оценок кратчайших путей в сети, содержащей дуги с отрицательными весами, но и для обнаружения в ней отрицательных циклов. Модифицированный алгоритм Беллмана - Форда реализован в виде программы, составленной в кодах MATLAB, и демонстрируется на примере автоматизированного построения и расчета сетевой модели, содержащей как положительные, так и отрицательные ребра (потоки) с применением рекурсивной процедуры пошаговой оптимизации. Показано, что предложенная модель, в отличие от известных, устраняет ограничения, обусловленные наличием отрицательных циклов в сетевой модели, что позволяет автоматизировать поиск кратчайших путей до условных целей функциональными средствами среды MATLAB. При этом построенная компьютерная модель обладает простотой и компактностью. Предложенные алгоритм и рекурсивная процедура рекомендуются для поиска энергоэффективных решений при управлении подвижными объектами на водном транспорте.

автоматизация, кратчайший маршрут, отрицательный цикл, алгоритм, веса ребер графа, оптимизация, вычислительная процедура

1. Чертков А. А. Рекурсивный метод оптимизации логистических путей средствами MATLAB / А. А. Чертков, А. А. Вардомская, А. А. Дмитриев // Вестник Государственного университета морского и речного флота имени адмирала С.О. Макарова. - 2015. - № 6(34) - С. 196-204. DOI: 10.21821/2309-5180-2015-7-6-196-204.

2. Чертков А. А. Автоматизация определения критического пути в логистической системе / А. А. Чертков, А. А. Вардомская, А. А. Дмитриев // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 5(33). - С. 194-200. DOI: 10.21821/2309-5180-2015-7-5-194-200.

3. Сахаров В. В. Автоматизация поиска оптимальных маршрутов и грузовых потоков в транспортных сетях средствами целочисленного линейного программирования / В. В. Сахаров, И. А. Сикарев, А. А. Чертков // Вестник государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2018. - Т. 10. - № 3. - С. 647-657. DOI: 10.21821/2309-5180-2018-10-3-647-657.

4. Сахаров В. В. Алгоритм трафика перевозки грузов с обеспечением минимума транспортной работы / В. В. Сахаров, А. А. Чертков, А. А. Дмитриев // Вестник государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2016. - № 1(35). - С. 180-188. DOI: 10.21821/2309-5180-2016-8-1-180-188.

5. Bellman R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. - 1958. - Vol. 16. - № 1. - C. 87-90. DOI: 10.1090/qam/102435

6. Чертков А. А. Автоматизация выбора кратчайших маршрутов судов на основе модифицированного алгоритма Беллмана - Форда / А. А. Чертков // Вестник государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2017. - Т. 9. - № 5. - С. 1113-1122. DOI: 10.21821/2309-5180-2017-9-5-1113-1122.

7. Сахаров В. В. Маршрутизация сетей с отрицательными весами звеньев в пакете оптимизации MATLAB / В. В. Сахаров, А. А. Чертков, Л. Б. Очина // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2019. - Т. 11. - № 2. - С. 230-242. DOI: 10.21821/2309-5180-2019-11-2-230-242.

8. Sakharov V. V.Network routing method for ships and other moving objects using MATLAB / V. V. Sakharov, A. A. Chertkov, I. B. Ariefjew // Zeszyty Naukowe Akademii Morskiej w Szczecinie. - 2020. - No. 62 (134). - Pp. 61-68. DOI: 10.17402/420.

9. Сахаров В. В. Алгоритм оптимального планирования группового взаимодействия роботов / В. В. Сахаров, А. А. Чертков, Д. С. Тормашев // Морской Вестник. - 2014. - № 4. - С. 119-122.

10. Чертков А. А. Итерационный алгоритм выбора оптимальной стратегии группового взаимодействия подвижных объектов / А. А. Чертков // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2015. - № 4 (32). - С. 207-215.

11. Dedkov V. A. The problem of control for multirobot systems / V. A. Dedkov, M. N. Kirsanov // Инновационные информационные технологии. - 2013. - Т. 2. - № 2. - С. 206-213.

12. Кирсанов М. Н. Анализ алгоритмов выбора оптимальных маршрутов группы судов / М. Н. Кирсанов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2016. - № 2 (36). - C. 183-190. DOI: 10.21821/2309-5180-2016-8-2-183-190.

13. Сазонов А. Е. Прогнозирование траектории движения судна при помощи нейронной сети / А. Е. Сазонов, В. В. Дерябин // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2013. - № 3 (22). - С. 6-13.

14. Fonseca C. M. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization / C. M. Fonseca, P. J. Fleming // Genetic Algorithms: Proceedings of the Fifth International Conference (S. Forrest, ed.). - San Mateo, CA: Morgan Kaufmann, 1993. - Pp. 416-423.

15. Федоренко К. В. Исследование основных параметров генетического алгоритма применительно к задаче поиска оптимального маршрута / К. В. Федоренко, А. Л. Оловянников // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2017. - Т. 9. - № 4. - С. 714-723. DOI: 10.21821/2309-5180-2017-9-4-714-723.

16. 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.