Автоматизация поиска кратчайшего замкнутого пути в транспортной сети средствами MATLAB

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

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

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

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

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

5. Sakharov V. V. Network routing method for ships and other moving objects using MATLAB / V. V. Sakha rov, A. A. Chertkov, I. B. Ariefjew // Scientific Journal of the Maritime University of Szczecin. — 2020. — Is. 62(134). — Pp. 61–68.

6. Hornik K. TSP – Infrastructure for the traveling salesperson problem / K. Hornik // Journal of statistical software. — 2007. — Is. 23 (2). — Pp. 1–21. DOI: 10.18637/jss.v023.i02.

7. Борознов В. О. Исследование решения задачи коммивояжера / В. О. Борознов // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. — 2009. — № 2. — С. 147–151. — EDN KWYPNF.

8. Stützle T. Parameter Adaptation in Ant Colony Optimization / T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo // Technical Report — IRIDIA, Université Libre de Bruxelles 2010-002, 2010. — 26 p.

9. Кормен Т. Х. Алгоритмы. Построение и анализ. — 2 изд. / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Р. Ривест, К. Штайн — М.: Вильямс, 2012. — 1296 с.

10. Костюк Ю. Л. Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ // Прикладная дискретная математика. — 2013. — № 2(20). — С. 78‒90. — EDN QCAKVP.

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

12. Metropolis V. N. Equations of state calculations by fast computing machines / V. N Metropolis., A. W. Rosenbluth, M. N.Rosenbluth, A. H. Teller, E. J. Teller // Chem. Phys. — 1953. — Vol. 21. — Pp. 1087–1092.

13. Winkler G. Image analysis, random fields and Markov chain Monte Carlo methods: a mathematical introduction — Vol. 27. — Springer Science and Business Media, 2012.

14. Ермаков С. М. К анализу метода имитации отжига в многоэкстремальном случае / С. М. Ермаков, Д. В. Куликов, С. Н. Леора // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. — 2017. — Т. 4. — № 2. — С. 220‒226. DOI: 10.21638/11701/spbu01.2017.205. — EDN ZDJRWD.

15. Костин А. С. Исследование моделей и методов маршрутизациии практического выполнения автономного движения беспилотными транспортными системами для доставки грузов / А. С. Костин, Н. Н. Майоров // Вестник государственного университета морского и речного флота им. адмирала С. О. Макарова. — 2023. — Т. 15. — № 3. — С. 524‒536. DOI: 10.21821/2309-5180-2023-15-3-524-536. — EDN SBJQBU.