STREAMING NETWORK ROUTING BASED ON BELLMAN-FORD ALGORITHM MODIFICATION

The operational task of automating the construction and routing of the network model with the known coordinates of the conditional goals set for a group of vessels to achieve them in the minimum time is solved; it makes it possible to obtain the reserves of running time necessary for saving fuel and energy, taking into account the load, the cost of cargo, transportation costs, logistics characteristics, etc. It is emphasized that in stormy weather conditions and vessel management in situations related to schedule correction, flexible operational decisions of dispatching services, made on the basis of numerical optimization methods using modern computing environments, are necessary. In this regard, the method of dynamic programming, implemented using the Bellman-Ford routing algorithm, which is supplemented by a recursive step-by-step optimization procedure that removes the limitation of the algorithm in the presence of inversely oriented edges with negative weights in the graph, is discussed in the paper. In the presence of negative weights, there are conditions for the appearance of a negative cycle in the graph, in which the practical implementation of the Bellman-Ford algorithm will become impossible due to an endless cycle of relaxations (attenuation) of the vertices weights included in this cycle. Hence, at a limited period of time for weighing all vertices (passes on all edges), the algorithm can give a knowingly false result. The proposed procedure for modifying the well-known Bellman-Ford algorithm eliminates this limitation and allows it to be used not only for estimating the shortest paths in a network containing arcs with negative weights, but also to detect negative cycles in it. The modified Bellman-Ford algorithm is implemented as a program compiled in MATLAB codes, and it is demonstrated by the example of automated construction and calculation of a network model containing both positive and negative edges (flows), using a recursive procedure of step-by-step optimization. It is shown that the proposed model, unlike the known models, eliminates the limitations caused by the presence of negative cycles in the network model, which makes it possible to automate the search for the shortest paths to conditional goals by the functional means of the MATLAB environment. The constructed computer model is simple and compact. The proposed algorithm and the recursive procedure are recommended for finding energy-efficient solutions for managing mobile objects in water transport.

automation, shortest route, negative cycle, algorithm, weight of graph ribs, optimization, computational procedure

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.