<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">gumrf</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова</journal-title><trans-title-group xml:lang="en"><trans-title>Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2309-5180</issn><issn pub-type="epub">2500-0551</issn><publisher><publisher-name>ФГБОУ ВО «Государственный университет морского и речного флота имени адмирала С.О. Макарова»</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.21821/2309-5180-2023-15-6-951-958</article-id><article-id custom-type="elpub" pub-id-type="custom">gumrf-398</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Эксплуатация водного транспорта, водные пути сообщения и гидрография</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>OPERATION OF WATER TRANSPORT, WATERWAYS AND HYDROGRAPHY</subject></subj-group></article-categories><title-group><article-title>Модификация волнового алгоритма для расчета эвклидовых расстояний в транспортных задачах</article-title><trans-title-group xml:lang="en"><trans-title>Modification of the wave algorithm for Euclidean distances calculation in transport applications</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Кузнецов</surname><given-names>А. Л.</given-names></name><name name-style="western" xml:lang="en"><surname>Kuznetsov</surname><given-names>A. L.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Кузнецов Александр Львович — доктор технических наук, профессор </p><p>198035, Санкт-Петербург, ул. Двинская, 5/7 </p></bio><bio xml:lang="en"><p>Kuznetsov, Aleksandr L. — Dr. of Technical Sciences, professor </p><p>5/7 Dvinskaya Str., St. Petersburg, 198035</p></bio><email xlink:type="simple">kaf_pgt@gumrf.ru</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>ФГБОУ ВО «ГУМРФ имени адмирала С. О. Макарова»</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Admiral Makarov State University of Maritime and Inland Shipping</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2023</year></pub-date><pub-date pub-type="epub"><day>06</day><month>02</month><year>2024</year></pub-date><volume>15</volume><issue>6</issue><fpage>951</fpage><lpage>958</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Кузнецов А.Л., 2024</copyright-statement><copyright-year>2024</copyright-year><copyright-holder xml:lang="ru">Кузнецов А.Л.</copyright-holder><copyright-holder xml:lang="en">Kuznetsov A.L.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://journal.gumrf.ru/jour/article/view/398">https://journal.gumrf.ru/jour/article/view/398</self-uri><abstract><p> Предметом настоящего исследования является математическая проблема нахождения кратчайшего пути в некотором ограниченном пространстве с препятствиями с помощью теории графов и динамического программирования, в которой предусмотрено достаточно много точных и эвристических алгоритмов, работающих с ориентированными и неориентированными, взвешенными и невзвешенными, связными и несвязными графами. Все эти методы предполагают различные способы расчета расстояния между вершинами, выбор которых обусловлен удобством реализации и методическими соображениями. Как следствие, найденные пути характеризуются некоторой абстрактной длиной, которая чаще всего трудно поддается пересчету в эвклидову. Тем не менее пространственные задачи в инженерной практике зачастую требуют получения результата именно в реальных физических расстояниях. В статье выполнено описание модификации наиболее распространенного метода поиска кратчайших путей — волнового ортогонально-диагонального алгоритма, который позволяет включить в расчет длины найденного маршрута геометрические характеристики его отдельных участков, что дает возможность достаточно точно оценить длину в смысле эвклидова расстояния. Отмечается, что в полной мере такая задача возникает в инженерных приложениях, связанных с проектированием морских портов, а именно: при прокладке трасс внутритерминального транспорта и сетей электропитания, при проектировании подходных каналов. К аналогичной проблеме приводит также прокладка маршрутов морских судов в сложных ледовых условиях. Во всех указанных случаях важной является не только топологическая конфигурация построенного маршрута, но и его оценка в терминах традиционного геометрического расстояния. Невозможность прямого получения этих характеристик сдерживает применение алгоритмических методов поиска оптимальных трасс и путей в практике технологического проектирования, что ограничивает использование цифровых инструментов для повышения эффективности расчетноконструкторских методов проектирования объектов инфраструктуры морского транспорта.</p></abstract><trans-abstract xml:lang="en"><p>Many engineering problems could be either reduced to or directly involve the mathematical problem of finding the shortest path in some confined space with obstacles. To solve this problem, graph theory and dynamic programming offers quite a lot of exact and heuristic algorithms that work with directed and undirected, weighted and unweighted, connected and disconnected graphs. All these methods are based on their own techniques of calculating the distance between the vertices, the choice of which is dictated by the convenience of implementation and methodological considerations. As a result, the resulted paths found by the algorithms usually are characterized by a certain abstract length, which is often difficult to convert into Euclidean one. Nevertheless, spatial problems in engineering practice often require an answer in terms of real physical distances. Specifically, such a task fully arises in engineering applications related to the design of seaports, namely, in the laying of routes of intra-terminal transport, power supply networks, in the design of approach channels. A modification of the most common method for finding the shortest paths, the wave orthogonal-diagonal algorithm, is described in the paper. It allows you to include the geometric characteristics of its individual sections in the calculation of the length of the found route, which makes it possible to accurately estimate the length in the sense of the Euclidean distance.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>технологическое проектирование портов</kwd><kwd>алгоритм поиска пути</kwd><kwd>эвклидово расстояние</kwd><kwd>манхеттенова метрика</kwd><kwd>геометрические характеристики</kwd><kwd>инженерные приложения</kwd><kwd>прокладка маршрутов</kwd></kwd-group><kwd-group xml:lang="en"><kwd>path finding algorithm</kwd><kwd>Euclidean distance</kwd><kwd>Manhattan metric</kwd><kwd>geometric characteristics</kwd><kwd>engineering applications</kwd><kwd>routing routes</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Bellman, Richard. “On a routing problem.” Quarterly of applied mathematics 16.1 (1958): 87–90. DOI: 10.1090/qam/102435.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Dijkstra, E. W. “A note on two problems in connexion with graphs.” Numerische Mathematik 1 (1959): 269–271. DOI: 10.1007/BF01386390.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Евстигнеев В. А. Итеративные алгоритмы глобального анализа графов. Пути и покрытия / В. А. Евстигнеев; Под ред. А. П. Ершова. — М: Наука, 1985. — 352 с.</mixed-citation><mixed-citation xml:lang="en">Evstigneev, V. A. Iterativnye algoritmy global’nogo analiza grafov. Puti i pokrytiya. Edited by A. P. Ershov. M: Nauka. Glavnaya redaktsiya fiziko-matematicheskoi literatury, 1985.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Кузнецов А. Л. Матричный метод поиска путей на взвешенных ориентированных графах в задачах сетевого планирования при проектировании и эксплуатации морских портов / А. Л. Кузнецов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2020. — Т. 12. — № 2. — С. 230–238. DOI: 10.21821/2309-5180-2020-12-2-230-238.</mixed-citation><mixed-citation xml:lang="en">Kuznetsov, Aleksandr L. “Matrix method for finding the paths on weighted oriented graphs in the tasks of port net operational planning.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 12.2 (2020): 230–238. DOI: 10.21821/2309-5180-2020-12-2-230-238.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Chen, Danny Z. “Developing algorithms and software for geometric path planning problems.” ACM Computing Surveys (CSUR) 28.4es (1996): 18‑es. DOI: 10.1145/242224.242246.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Галкина В. А. Построение кратчайших путей в ориентированном графе / В. А. Галкина // Дискретная математика. Комбинаторная оптимизация на графах. — М.: Издательство «Гелиос АРВ», 2003. — С. 75–94.</mixed-citation><mixed-citation xml:lang="en">Galkina, V. A. “Postroenie kratchaishikh putei v orientirovannom grafe.” Diskretnaya matematika. Kombinatornaya optimizatsiya na grafakh. M.: Izdatel’stvo “Gelios ARV”, 2003. 75–94.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Kröger, Martin. “Shortest multiple disconnected path for the analysis of entanglements in two-and three-dimensional polymeric systems.” Computer physics communications 168.3 (2005): 209–232. DOI: 10.1016/j.cpc.2005.01.020.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Алексеев В. Е. Глава 3.4. Нахождения кратчайших путей в графе / В. Е. Алексеев, В. А. Таланов // Графы. Модели вычислений. Структуры данных. — Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2005. — С. 236–237.</mixed-citation><mixed-citation xml:lang="en">Alekseev, V. E., and V. A. Talanov. “Glava 3.4. Nakhozhdeniya kratchaishikh putei v grafe.” Grafy. Modeli vychislenii. Struktury dannykh. Nizhnii Novgorod: Izdatel’stvo Nizhegorodskogo gos. universiteta, 2005. 236–237.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Abraham, Ittai, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. “Highway dimension, shortest paths, and provably efficient algorithms.” Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010. 782–793. DOI: 10.1137/1.9781611973075.6.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Abraham, Ittai, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. “A hub-based labeling algorithm for shortest paths in road networks.” Experimental Algorithms: 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5–7, 2011. Proceedings 10. Springer Berlin Heidelberg, 2011. 230–241. DOI: 10.1007/978-3-642-20662-7_20.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">Lee, Chin Yang. “An algorithm for path connections and its applications.” IRE transactions on electronic computers 3 (1961): 346–365. DOI: 10.1109/TEC.1961.5219222.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Федоренков А. AutoCAD 2002: практический курс / А. Федоренков, A. Кимаев. — М.: «ДЕСС КОМ», 2002. — 576 с.</mixed-citation><mixed-citation xml:lang="en">Fedorenkov, A., and A. Kimaev. AutoCAD 2002: prakticheskii kurs. M.: «DESS KOM», 2002.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Кузнецов А. Л. Инструмент расчета потребности в ресурсах контейнерного терминала / А. Л. Кузнецов, H. Oja, А. Д. Семенов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2021. — Т. 13. — № 5. — С. 659–669. DOI: 10.21821/2309-5180-2021-13-5-659-669.</mixed-citation><mixed-citation xml:lang="en">Kuznetsov, Aleksandr L., Hannu Oja, and Anton D. Semionov. “Tool for assessing the resources requirement of a container terminal.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 13.5 (2021): 659–669. DOI: 10.21821/2309-5180-2021-13-5-659-669.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
