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

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

1. Галин А. В. Задача проектирования контейнерной линии в современной транспортной системе России / А. В. Галин, П. C. Рудный // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2024. — Т. 16. — № 1. — С. 64–73. DOI: 10.21821/2309-5180-2024-16-1-64-73.

2. Christiansen M. Liner shipping network design / M. Christiansen, E. Hellsten, D. Pisinger, D. Sacramento, C. Vilhelmsen // European Journal of Operational Research. — 2020. — Vol. 286. — Is. 1. — Pp. 1–20. DOI: 10.1016/j.ejor.2019.09.057.

3. Guericke S. Liner shipping cargo allocation with service levels and speed optimization / S. Guericke, K. Tierney // Transportation Research Part E: Logistics and Transportation Review. — 2015. — Vol. 84. — Pp. 40– 60. DOI: 10.1016/j.tre.2015.10.002.

4. 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.

5. Thun K. Analyzing complex service structures in liner shipping network design / K. Thun, H. Andersson, M. Christiansen // Flexible Services and Manufacturing Journal. — 2017. — Vol. 29. — Pp. 535–552. DOI: 10.1007/s10696-016-9262-6.

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

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

8. 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.

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

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

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

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

13. 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.

14. 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.