В работе решена операционная задача автоматизации построения и маршрутизации сетевой модели с известными координатами условных целей, поставленных группе судов для их достижения в течение минимального времени, что позволяет получить резервы ходового времени, необходимые для экономии топлива и энергии с учетом загрузки, стоимости груза, расходов на перевозки и др. Подчеркивается, что в условиях штормовой погоды и при управлении судами в ситуациях, связанных с корректировкой расписания, необходимы гибкие оперативные решения диспетчерских служб, принимаемые на основе численных методов оптимизации с использованием современных вычислительных сред. В связи с этим в работе рассмотрен метод динамического программирования, реализуемый с использованием алгоритма маршрутизации Беллмана - Форда, дополненный рекурсивной процедурой пошаговой оптимизации, снимающей ограничение алгоритма при наличии в графе обратно ориентированных ребер с отрицательными весами. Отмечается, что при наличии отрицательных весов возникают условия появления отрицательного цикла в графе, при котором практическая реализация алгоритма Беллмана - Форда становится невозможной из-за бесконечного цикла релаксаций (ослабления) весов вершин, входящих в этот цикл. Отсюда на ограниченном отрезке времени взвешивания всех вершин (проходов по всем ребрам) алгоритм может дать заведомо ложный результат. Предложенная процедура модификации известного алгоритма Беллмана - Форда устраняет это ограничение, позволяя применять его не только для оценок кратчайших путей в сети, содержащей дуги с отрицательными весами, но и для обнаружения в ней отрицательных циклов. Модифицированный алгоритм Беллмана - Форда реализован в виде программы, составленной в кодах MATLAB, и демонстрируется на примере автоматизированного построения и расчета сетевой модели, содержащей как положительные, так и отрицательные ребра (потоки) с применением рекурсивной процедуры пошаговой оптимизации. Показано, что предложенная модель, в отличие от известных, устраняет ограничения, обусловленные наличием отрицательных циклов в сетевой модели, что позволяет автоматизировать поиск кратчайших путей до условных целей функциональными средствами среды MATLAB. При этом построенная компьютерная модель обладает простотой и компактностью. Предложенные алгоритм и рекурсивная процедура рекомендуются для поиска энергоэффективных решений при управлении подвижными объектами на водном транспорте.
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.
The authors declare that there are no conflicts of interest present.