Чертков Александр Александрович — доктор технических наук, доцент
198035, Санкт-Петербург, ул. Двинская, 5/7
Chertkov, Alexandr A. — Dr. of Technical Sciences, associate professor
5/7 Dvinskaya Str., St. Petersburg 198035
Никифоров Владимир Григорьевич — доктор технических наук, профессор
198035, Санкт-Петербург, ул. Двинская 5/7
Nikiforov Vladimir G. — Dr. of Technical Sciences, professor
5/7 Dvinskaya Str., St. Petersburg, 198035
В работе рассмотрена задача автоматизации поиска и построения кратчайшего замкнутого маршрута для группы судов торгового флота на заданном множестве транзитных узлов транспортной сети с известными координатами. Цель — найти самый короткий замкнутый маршрут, который проходит через все узлы сети только по одному разу и завершается в исходящем узле. В общем случае математической моделью такой транспортной сети может служить взвешенный граф, в котором критерием эффективности искомого маршрута может служить, например, расстояние между городами или портами, время или эксплуатационные расходы. Это позволяет определить резервы времени, которые можно использовать для экономии топлива и энергии с учетом загрузки и стоимости грузов, путевых расходов и других факторов. В работе применяется комбинаторный метод с использованием стохастического (вероятностного) программирования, который реализуется с помощью алгоритма имитации отжига, дополненного рекурсивной процедурой пошаговой оптимизации. Задача относится к классу трансвычислительных даже при небольшой размерности сети, что делает невозможным ее решение методом перебора вариантов на современных компьютерах за разумное время. Предложенная модификация алгоритма имитации отжига устраняет это ограничение, позволяя не только оценивать кратчайшие пути в сети, но и строить замкнутые пути, проходящие через все вершины сети один раз. Применение в алгоритме итерационной стратегии с использованием вероятностного сценария по методу Монте-Карло позволяет избежать попадания решения в локальный минимум и обеспечивает глобальную оптимизацию. Алгоритм реализован в кодах MATLAB в виде рекурсивной процедуры пошаговой оптимизации с построением на координатной плоскости кривой замкнутого маршрута через все множество узлов транспортной сети без взаимных пересечений его участков. Показано, что результатом рекурсивной оптимизации является получение численной оценки замкнутого пути минимального веса в полном взвешенном графе, являющемся моделью транспортной сети с определением массива номеров транзитных узлов на этом маршруте. Разработанные алгоритм и процедура глобальной оптимизации могут быть использованы для автоматизации поиска энергоэффективных решений при управлении робототехническими и беспилотными объектами, а также судами при выполнении грузоперевозок на водном транспорте.
The paper considers the problem of automating the search and construction of the shortest closed route for a group of merchant ships on a given set of transit nodes of the transport network with known coordinates. The goal is to find the shortest closed route that passes through all hosts only once and ends at the outgoing node. In general, a weighted graph can serve as a mathematical model of such a transport network, in which the criterion for the efficiency of the desired route can be, for example, the distance between cities or ports, time or operating costs. This allows you to identify time reserves that can be used to save fuel and energy, taking into account the load and cost of goods, travel costs and other factors. The work uses a combinatorial method using stochastic (probabilistic) programming, which is implemented using an annealing simulation algorithm supplemented by a recursive step-by-step optimization procedure. The problem belongs to the class of transcomputational even with a small network dimension, which makes it impossible to solve it by brute force on modern computers in a reasonable time. The proposed modification of the simulated annealing algorithm eliminates this limitation and allows not only to evaluate the shortest paths in the network, but also to build closed paths that pass through all the vertices of the network once. The use of an iterative strategy in the algorithm using a probabilistic scenario according to the Monte Carlo method allows you to avoid the solution falling into the local minimum and provides global optimization. The algorithm is implemented in MATLAB codes in the form of a recursive step-by-step optimization procedure with the construction of a curve of a closed route on the coordinate plane through the entire set of nodes of the transport network without mutual intersections of its sections. It is shown that the result of recursive optimization is to obtain a numerical estimate of the closed path of the minimum weight in the full weighted graph, which is a model of the transport network with the definition of an array of transit node numbers on this route. The developed algorithm and global optimization procedure can be used to automate the search for energy-efficient solutions in the control of robotic and unmanned objects, as well as ships in the performance of cargo transportation in water transport.
The authors declare that there are no conflicts of interest present.