Модификация волнового алгоритма для расчета эвклидовых расстояний в транспортных задачах

 Предметом настоящего исследования является математическая проблема нахождения кратчайшего пути в некотором ограниченном пространстве с препятствиями с помощью теории графов и динамического программирования, в которой предусмотрено достаточно много точных и эвристических алгоритмов, работающих с ориентированными и неориентированными, взвешенными и невзвешенными, связными и несвязными графами. Все эти методы предполагают различные способы расчета расстояния между вершинами, выбор которых обусловлен удобством реализации и методическими соображениями. Как следствие, найденные пути характеризуются некоторой абстрактной длиной, которая чаще всего трудно поддается пересчету в эвклидову. Тем не менее пространственные задачи в инженерной практике зачастую требуют получения результата именно в реальных физических расстояниях. В статье выполнено описание модификации наиболее распространенного метода поиска кратчайших путей — волнового ортогонально-диагонального алгоритма, который позволяет включить в расчет длины найденного маршрута геометрические характеристики его отдельных участков, что дает возможность достаточно точно оценить длину в смысле эвклидова расстояния. Отмечается, что в полной мере такая задача возникает в инженерных приложениях, связанных с проектированием морских портов, а именно: при прокладке трасс внутритерминального транспорта и сетей электропитания, при проектировании подходных каналов. К аналогичной проблеме приводит также прокладка маршрутов морских судов в сложных ледовых условиях. Во всех указанных случаях важной является не только топологическая конфигурация построенного маршрута, но и его оценка в терминах традиционного геометрического расстояния. Невозможность прямого получения этих характеристик сдерживает применение алгоритмических методов поиска оптимальных трасс и путей в практике технологического проектирования, что ограничивает использование цифровых инструментов для повышения эффективности расчетноконструкторских методов проектирования объектов инфраструктуры морского транспорта.

1. Bellman R. On a routing problem / R. Bellman // Quarterly of Applied Mathematics. —1958. — Vol. 16. — Is. 1. — Pp. 87–90. DOI: 10.1090/qam/102435.

2. Dijkstra E. W. A note on two problems in connexion with graphs / E. W. Dijkstra // Numerische Mathematik. — 1959. — Vol. 1. — Pp. 269–271. DOI: 10.1007/BF01386390.

3. Евстигнеев В. А. Итеративные алгоритмы глобального анализа графов. Пути и покрытия / В. А. Евстигнеев; Под ред. А. П. Ершова. — М: Наука, 1985. — 352 с.

4. Кузнецов А. Л. Матричный метод поиска путей на взвешенных ориентированных графах в задачах сетевого планирования при проектировании и эксплуатации морских портов / А. Л. Кузнецов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2020. — Т. 12. — № 2. — С. 230–238. DOI: 10.21821/2309-5180-2020-12-2-230-238.

5. Chen D. Z. Developing algorithms and software for geometric path planning problems / D. Z. Chen // ACM Computing Surveys (CSUR). — 1996. — Vol. 28. — Is. 4es. — Pp. 18‑es. DOI: 10.1145/242224.242246.

6. Галкина В. А. Построение кратчайших путей в ориентированном графе / В. А. Галкина // Дискретная математика. Комбинаторная оптимизация на графах. — М.: Издательство «Гелиос АРВ», 2003. — С. 75–94.

7. Kröger M. Shortest multiple disconnected path for the analysis of entanglements in two-and three-dimensional polymeric systems / M. Kröger // Computer physics communications. — 2005. — Vol. 168. — Is. 3. — Pp. 209–232. DOI: 10.1016/j.cpc.2005.01.020.

8. Алексеев В. Е. Глава 3.4. Нахождения кратчайших путей в графе / В. Е. Алексеев, В. А. Таланов // Графы. Модели вычислений. Структуры данных. — Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2005. — С. 236–237.

9. Abraham I. Highway dimension, shortest paths, and provably efficient algorithms / I. Abraham, A. Fiat, A. V. Goldberg, R. F. Werneck // Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. — Society for Industrial and Applied Mathematics, 2010. — Pp. 782–793. DOI: 10.1137/1.9781611973075.6.

10. Abraham I. A hub-based labeling algorithm for shortest paths in road networks / I. Abraham, D. Delling, A. V. Goldberg, R. F. Werneck // Experimental Algorithms: 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5–7, 2011. Proceedings 10. — Springer Berlin Heidelberg, 2011. — Pp. 230–241. DOI: 10.1007/978-3-642-20662-7_20.

11. Lee C. Y. An algorithm for path connections and its applications / C. Y. Lee // IRE transactions on electronic computers. — 1961. — № 3. — Pp. 346–365. DOI: 10.1109/TEC.1961.5219222.

12. Федоренков А. AutoCAD 2002: практический курс / А. Федоренков, A. Кимаев. — М.: «ДЕСС КОМ», 2002. — 576 с.

13. Кузнецов А. Л. Инструмент расчета потребности в ресурсах контейнерного терминала / А. Л. Кузнецов, H. Oja, А. Д. Семенов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2021. — Т. 13. — № 5. — С. 659–669. DOI: 10.21821/2309-5180-2021-13-5-659-669.