astАрхитектура, строительство, транспортArchitecture, Construction, Transport2782-232X2713-0770Industrial University of Tyumen10.31660/2782-232X-2022-1-80-87ast-46Research ArticleТРАНСПОРТTRANSPORTСравнительный анализ методов поиска кратчайшего пути в графеComparative analysis of methods for finding the shortest distance in a graphБлизняковаЕ. А.BliznyakovaE. A.

Близнякова Елена Александровна, студент кафедры автомобильных перевозок

Волгоград

Elena A. Bliznyakova, Student at the Department of Road Transport

Volgograd

el.44@bk.ruКуликовА. А.KulikovA. A.

Куликов Андрей Алексеевич, учащийся 11 класса

Волгоград

Andrey A. Kulikov, Student 

Volgograd

v2xoda@ya.ruКуликовА. В.KulikovA. V.

Куликов Алексей Викторович, к. т. н., доцент кафедры автомобильных перевозок

Волгоград

Alexey V. Kulikov, Candidate in Engineering, Associate Professor at the Department of Road Transport

Volgograd

AlekseyKulikov2007@ya.ruВолгоградский государственный технический университетРоссияVolgograd State Technical UniversityRussian FederationЛицей № 5 имени Ю. А. ГагаринаРоссияLyceum No. 5 named after Yu. A. GagarinRussian Federation202228032022018087Copyright © Близнякова Е.А., Куликов А.А., Куликов А.В., 20222022Близнякова Е.А., Куликов А.А., Куликов А.В.Bliznyakova E.A., Kulikov A.A., Kulikov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ast.tyuiu.ru/jour/article/view/46

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

Currently, there is a high need to determine the shortest distances to form freight and passenger transportation routes. One of the most effective ways to determine routes of minimum length are methods of finding the shortest distances in a graph. The article discusses algorithms for finding shortest distances, as well as other methods based on the principles of their operation. It was conducted a comparative analysis to identify the advantages and disadvantages of using these methods in routing tasks.

транспортгрузовые перевозкимаршрутизация перевозокалгоритм Дейкстрыалгоритм Беллмана – Фордадинамический методметод «метлы»метод потенциаловtransportfreight transportationtransportation routingDijkstra’s algorithmBellman-Ford algorithmdynamic method“broom” methodmethod of potentialsReferencesГрузовые автомобильные перевозки : учебник для вузов / А. В. Вельможин, В. А. Гудков, Л. Б. Миротин, А. В. Куликов. – 3-е изд., испр. – Москва : Горячая линия – Телеком, 2016. – 560 с. – Текст : непосредственный.Vel'mozhin, A. V., Gudkov, V. A., Mirotin, L. B., & Kulikov, A. V. (2016). Gruzovye avtomobil'nye perevozki. 3rd edition, revised. Moscow, Goryachaya liniya – Telekom Publ., 560 p. (In Russian).Kulikov, A. V. Effectiveness of Road Transport Technology in Modern Housing Systems / A. V. Kulikov, S. Y. Firsova. – DOI: 10.1007/978-3-030-22063-1_87. – Direct text // Proceedings of the 5th International Conference on Industrial Engineering (ICIE 2019) : Conference proceedings ICIE 2019, Sochi, Russia, March 25–29, 2019 / South Ural State University (national research university), Platov South-Russian State Polytechnic University (NPI). – Sochi : Springer International Publishing, Switzerland AG, 2020. – Pp. 813–821.Kulikov, A. V., & Firsova, S. Yu. (2020). Effectiveness of Road Transport Technology in Modern Housing Systems. Proceedings of the 5th International Conference on Industrial Engineering (ICIE 2019): Conference proceedings ICIE 2019, Sochi, Russia, March 25-29, 2019. South Ural State University (national research university), Platov South-Russian State Polytechnic University (NPI). Sochi, Springer International Publishing, Switzerland AG Publ., pp. 813-821. (In English). DOI: 10.1007/978-3-030-22063-1_87Куликов, А. В. Повышение эффективности автомобильных перевозок в условиях Крайнего Севера Российской Федерации / А. В. Куликов, С. Ю. Фирсова, В. С. Дорохина. – DOI: 10.26518/2071-7296-2021-18-3-286-305. – Текст : непосредственный // Вестник Сибирского государственного автомобильно-дорожного университета. – 2021. – Т. 18. – № 3 (79). − С. 286−305.Kulikov, A. V., Firsova, S. Y., & Dorokhina, V. S. (2021). Improving efficiency of car transportation in extreme north conditions in Russian Federation. The Russian Automobile and Highway Industry Journal, 18(3), pp. 286-305. (In Russian). DOI: 10.26518/2071-7296-2021-18-3-286-305Домке, Э. Р. Методы оптимизации маршрутных схем развозки грузов автомобильным транспортом : учебное пособие для студентов высших учебных заведений / Э. Р. Домке, С. А. Жесткова. – Пенза : ПГУАС, 2014. – 164 с. – Текст : непосредственный.Domke, E. R., & Zhestkova, S. A. (2014). Metody optimizatsii marshrutnykh skhem razvozki gruzov avtomobil'nym transportom. Penza, PGUAS Publ., 164 p. (In Russian).Сулименова, Е. Р. Эффективные математические методы в транспортно-логистическом обслуживании малых предприятий г. Волгограда / Е. Р. Сулименова. – Текст : непосредственный // Конкурс научно-исследовательских работ студентов Волгоградского государственного технического университета : тезисы докладов, Волгоград, 26–30 апреля 2021 года. – Волгоград : Волгоградский государственный технический университет, 2021. – C. 151.Sulimenova, E. R. (2021). Effektivnye matematicheskie metody v transportno-logisticheskom obsluzhivanii malykh predpriyatiy g. Volgograda. Konkurs nauchno-issledovatel'skikh rabot studentov Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta: tezisy dokladov, Volgograd, April, 26–30. Volgograd, Volgograd State Technical University Publ., pp. 151. (In Russian).Выбор оптимального маршрута методом динамического программирования / Helpiks.Org : [сайт]. – URL : https://helpiks.org/2-66840.html (дата обрашения : 10.02.2022). – Текст : электронный.Vybor optimal'nogo marshruta metodom dinamicheskogo programmirovaniya. Helpiks.Org. (In Russian). Available at: https://helpiks.org/2-66840.html (date of the application: 10.02.2022).Определение кратчайших расстояний с использованием метода потенциалов / Studbooks. net : [сайт]. – URL : https://studbooks.net/2456287/tehnika/opredelenie_kratchayshih_rasstoyaniy_ispolzovaniem_metoda_potentsialov (дата обращения : 10.02.2022). – Текст : электронный.Opredelenie kratchayshikh rasstoyaniy s ispol'zovaniem metoda potentsialov. Studbooks.net. (In Russian). Available at: https://studbooks.net/2456287/tehnika/opredelenie_kratchayshih_ rasstoyaniy_ispolzovaniem_metoda_potentsialov (date of the application: 10.02.2022).Айтбагина, Э. Р. Влияние расстояния на результаты работы группы автомобилей при перевозке грузов грузоотправителем / Э. Р. Айтбагина, Е. Е. Витвицкий. – Текст : непосредственный // Вестник Сибирского государственного автомобильно-дорожного университета. – 2017. – № 4–5 (56– 57). – С.14–24.Aytbagina, E. R., & Vitvitskiy, E. E. (2017). The influence of the distance on the results of the work group of vehicles for the cargo transportation by the supplier. The Russian Automobile and Highway Industry Journal, 4-5(56-57), pp. 14-24. (In Russian).The dynamic traffic modelling system / S. Dorokhin, D. Likhachev, A. Artemov [et al.]. – DOI: 10.1007/ 978-3-030-96380-4_175. – Direct text // International Scientific Siberian Transport Forum. TransSiberia – 2021. – Cham : Springer, 2021. – Pp. 1586–1594.Dorokhin, S., Likhachev, D., Artemov, A., Sevostyanov, A., Kulikov, A., & Novikov, A. (2022). The dynamic traffic modelling system. International Scientific Siberian Transport Forum. TransSiberia 2021. Cham, Publ. Springer, pp. 1586-1594. (In English). DOI: 10.1007/978-3-030-96380-4_175Горев, А. Э. Грузовые автомобильные перевозки : учебное пособие для студентов высших учебных заведений / А. Э. Горев. – 5-е изд., испр. – Москва : Академия, 2008. – 288 с. – Текст : непосредственный.Gorev, A. E. (2008). Gruzovye avtomobil'nye perevozki. 5th edition, revised. Moscow, Akademiya Publ., 288 p. (In Russian).Афанасьев, Л. Л. Единая транспортная система и автомобильные перевозки : учебник для вузов / Л. Л. Афанасьев, Н. Б. Островский, С. М. Цукерберг. – 2-е изд., перераб. и доп. – Москва : Транспорт, 1984. – 333 с. – Текст : непосредственный.Afanas'ev, L. L., Ostrovsky, N. B., & Zuckerberg, S. M. (1984). Edinaya transportnaya sistema i avtomobil'nye perevozki. 2nd edition, revised. Moscow, Transport Publ., 333 p. (In Russian).

The authors declare that there are no conflicts of interest present.