The article describes the essence and methods of logistics, and considers a specific example of the application of Dijkstra's algorithm, which allows minimizing logistics costs by constructing the shortest (optimal) route
logistics, logistics costs, path optimization, Dijkstra`s algorithm
Как известно, в современной экономике продукт нужно не только произвести, но и продать с минимальными затратами, а для этого нужно оптимизировать производственные и логистические процессы. Логистика – это наука, помогающая управлять сложными цепочками поставок товаров от места их производства (или поставщика) до конечного потребителя, а также снизить затраты при производстве, хранении и перевозке товаров [1, С. 6].
Логистика охватывает множество функциональных областей производственной, хозяйственной и экономической деятельности. К сфере ее изучения можно отнести: снабжение – это обеспечение производства необходимыми предметами и средствами труда, перевозку, продажу и хранение грузов, а также управление сопутствующими потоками финансов и информации [2,3].
На практике многие предприниматели тестируют разные методы по снижению логистических издержек. Для предприятия важно снижать логистические затраты, т.к. от них зависит прибыль предприятия. Логистические издержки – это затраты на выполнение логистических операций (складирование, перевозка, хранение, разгрузка и др.) [3].
Для того, чтобы снизить транспортные издержки, важно выбрать наиболее подходящее и экономически выгодное транспортное средство, оптимизировать маршрут, сократить время на транспортировку, определить необходимый объем партии поставки. Существует множество способов оптимизации логистических затрат при транспортировке. К таким методам можно отнести транспортные задачи. В данной статье рассмотрим решение транспортной задачи с помощью алгоритма Дейкстры, благодаря которому можно определить оптимальный маршрут.
С помощью алгоритма Дейкстры можно найти кратчайший путь между вершинами s и t (начальная и конечная точка, соответственно) в графе.
К ограничениям алгоритма Дейкстры можно отнести следующее: во-первых, он работает только со взвешенными графами – то есть такими, где веса между рёбрами известны заранее, а во-вторых, эти расстояния должны быть неотрицательными. Предположим, что бизнес может описать в информационной модели графов взаимосвязи между необходимыми объектами для доставки грузов в соответствии с ограничениями модели, тогда алгоритм Дейкстры будет состоять из следующих шагов:
- Выбираем точку отправления и обозначаем ее оценкой ноль. Все остальные вершины помечаем как бесконечность.
- Выбираем ближайшие к началу вершины.
- Рассчитываем расстояние до этих ближайших вершин, прибавляя начальный вес оценки и длину дороги, если оно оптимальней (меньше) текущей – заменяем вес оценки на полученное значение.
- Посещенную вершину больше не рассматриваем.
- Выбираем непосещённые вершины с наименьшей оценкой и считаем расстояния от соседних с ней вершин по тому же алгоритму.
- Шаги повторяются, пока на графе есть непосещенные точки.
- Находим самый кратчайший путь.
Введем условие задачи: допустим, у нас есть 6 городов: A, B, C, D, E, F, соединенные дорогами. Числа возле ребер – это расстояние между городами. Найдем кратчайший путь из города А в город С (рисунки 1,2,3,4,5,6,7,8).
Рисунок 1 – Использование алгоритма Дейкстры, шаг 1.
Шаг 1. Установим для каждой вершины первоначальную оценку пути до А. Для самой А оценка будет равна ноль, т.к. чтобы пройти из А в А нам понадобится ноль км. Остальным вершинам присвоим бесконечность, т.к. пока мы не знаем их значения.
Рисунок 2 – Использование алгоритма Дейкстры, шаг 2.
Шаг 2. Рассмотрим соседние с A вершины, то есть те, которые связаны с А рёбрами напрямую. Это B и E, их расстояния до А равны 7 и 4 соответственно. Так как эти значения, очевидно, меньше бесконечности, обновим их на схеме. Вершину А будем считать посещённой – закрасим её и больше не будем рассматривать.
Рисунок 3 – Использование алгоритма Дейкстры, шаг 3.
Шаг 3. Теперь перейдём к непосещённой вершине с наименьшим расстоянием до А. Это вершина E. Соседние с ней непосещённые вершины – F и D. Их расстояния до А будут равны оценке E (то есть расстоянию от E до А) плюс веса рёбер от E до этих вершин.
Для вершины F: 4 + 3 = 7
Для вершины D: 4 + 8 = 12
Полученные расстояния 7 и 12 меньше предыдущих оценок (меньше бесконечности), поэтому запишем их возле вершин F и D. Вершину E будем считать посещённой (закрасим её).
Рисунок 4 – Использование алгоритма Дейкстры, шаг 4.
Шаг 4. Дальнейшее рассмотрение вершин осуществляется по аналогии: алгоритм выбирает непосещённые вершины с наименьшей оценкой и считает расстояния от соседних с ней вершин до А. Продолжается это до тех пор, пока алгоритм не вычислит кратчайшие расстояния до А для всех вершин.
Выбираем вершину между нерассмотренными вершинами В, F и D с наименьшей оценкой. Это вершины B и F, равные 7.
Рассмотрим вершину В. Из В можно попасть в F и C. Дорога, ведущая в F из В равна оценке В плюс длина дороги, то есть, ВF = 7+2 = 9, что больше первоначальной оценки F = 7, следовательно, пусть A-B-F длиннее пути A-E-F, менять вес оценки не будем. Еще одна дорога, ведущая из В – это дорога ВС, равная 7+5 = 12, что меньше бесконечности, поэтому обновим оценку вершины С. Вершина В рассмотрена, закрасим ее.
Рисунок 5 – Использование алгоритма Дейкстры, шаг 5.
Рассмотрим вершину F. Из F есть 2 дороги, ведущие к нерассмотренным вершинам: C и D. Пройдем к непосещенной вершине С. Вес оценки плюс длина дороги для вершины С из F будет равна: 7+6=13, что больше раннее поставленного веса 12 из вершины В. Соответственно, менять вес оценки не будем. Дальше пройдем к вершине D из F. Путь будет равен: 7+9=16, что больше раннее рассмотренной оценки, которая равнялась 12 из вершины Е, соответственно путь FD невыгоден, вес оценки менять не будем. Вершину F рассмотрели.
Рисунок 6 – Использование алгоритма Дейкстры, шаг 6.
Рассмотрим вершину D. Из D одна дорога, ведущая к вершине С. Ее путь равен оценке D+11=12+11=23, что больше веса оценки 12, который был получен из вершины В. Менять не будем. Вершину D рассмотрели.
Рисунок 7 – Использование алгоритма Дейкстры, шаг 7.
Можно сделать вывод, что наикратчайший путь из вершины А в вершину С – это путь AB-BС=7+5=12.
Рисунок 8 – Использование алгоритма Дейкстры, шаг 8.
Таким образом, на основе данного алгоритма строится кратчайший маршрут в онлайн-картах, что помогает предприятию сократить и оптимизировать маршрут, затратив меньше времени и средств на доставку груза.
1. Kirillov A.V. Osnovy logistiki: uchebnoe posobie / A.A. Kirilov. – Samara: Izdatel'stvo Samarskogo universitet, 2021. – 88 s. – Tekst: elektronnyy. – URL: https://repo.ssau.ru/bitstream/Uchebnye-izdaniya/Osnovy-logistiki-94642/1/Kirillov%20A.V.%20Onovy%20logstiki%202021.pdf?ysclid=m99f4he0qu412549914 (data obrascheniya: 09.04.2025).
2. Shumaev V.A. Osnovy logistiki: uchebnoe posobie / V.A. Shumaev – M.: Yuridicheskiy institut MIIT, 2016. – 314 s. – Tekst: elektronnyy. – URL: https://www.miit.ru/content/Oblozhka.pdf?id_vf=79906&ysclid=m99e2skp5h766267499 (data obrascheniya: 09.04.2025).
3. Krylatkov P.P., Kuznecova E.Yu., Kozhushko G.G., Mineeva T.A. Logi-stika promyshlennogo predpriyatiya: uchebnoe posobie / P.P. Krylatkov. – Eka-terinburg: Izdatel'stvo Ural unta, 2016. – 176 s. – Tekst: elektronnyy. – URL: https://elar.urfu.ru/bitstream/10995/42415/1/978-5-7996-1830-8_2016.pdf (data obrascheniya: 09.04.2025).
