Полунин Сергей молод. Ему всего лишь по состоянию на февраль 2024-го, 34 года. Вместе с тем, в декабре 2023 года он попал в список доверенных лиц Владимира Путина на президентских выборах 2024 года.
Позняков Павел Андреевич
студент 4 курса,
Белорусский национальный технический университет
г. Минск, Беларусь
E-mail: pozniakoupavel@gmail.com
Научный руководитель – Лапковская Полина Игоревна
к.э.н., доцент кафедры «Экономика и логистика»
Белорусский национальный технический университет,
г. Минск, Беларусь
E-mail: p.lapkouskaya@gmail.com
The development of an application for optimizing the parameters
of international road freight transportation using Dijkstra's algorithm
Pazniakou Pavel Andreevich
4th grade student,
Belarusian national technical university
Minsk, Belarus
Scientific supervisor – Lapkovskaya Polina Igorevna
Candidate of Economic Sciences, associate professor of «Economics and logistics» department,
Belarusian national technical university,
Minsk, Belarus
Суть работы заключается в разработке экономико-математической модели с использованием алгоритма Дейкстры для нахождения кратчайшего тарифного расстояния между пунктами погрузки и разгрузки при планировании международных грузовых автомобильных перевозок. Практическая реализация проекта осуществляется при помощи языка программирования Python.
Ключевые слова: международная логистика, международные автомобильные перевозки, внешнеэкономическая деятельность, перевозки грузов.
The essence of the work is to develop an economic and mathematical model using Dijkstra's algorithm to find the shortest tariff distance between loading and unloading points when planning international road freight transportation. The practical implementation of the project is carried out using the Python programming language.
Key words: international logistics, international road transportation, foreign economic activity, cargo transportation.
Одним из современных направлений рационального использования транспортных средств является оптимизация планирования перевозок грузов с применением методов линейного программирования, и в частности в случае проектирования рациональных или оптимальных маршрутов с помощью экономико-математических методов оптимизации (ЭММ) [1, c.25].
Разработанная экономико-математическая модель обладает следующими конкурентными преимуществами:
- может быть применена на любом предприятии, занимающемся международными перевозками грузов;
- невысокая стоимость программного решения;
- в основе модели лежит экономико-математический метод оптимизации.
Рассмотрим ситуацию, когда осуществляется перевозка груза из Минска в Лейпциг. В Минске автомобиль загружается и едет в Колядичи на затаможивание. После затаможивания автомобиль через пограничные переходы транзитом едет через Польшу на растаможивание в Дрезден, и оттуда на разгрузку в Лейпциг. Для нахождения кратчайшего пути по тарифным расстояниям менеджер по перевозкам по указанию заказчика выставляет в программе следующие пункты: погрузки, затаможивания, растаможивания, выгрузки.
Учитывая возможные пограничные переходы между странами и тарифные расстояния между всеми пунктами маршрута, программа строит ориентированный сетевой граф (рисунок 1.1) и находит кратчайшее расстояние от пункта погрузки до пункта выгрузки.
Рисунок 1.1 – Основные пункты маршрута перевозки груза из Минска
в Лейпциг
Программа написана на языке Python. Дополнительно использовалась библиотека Pandas для работы с табличными данными. Для создания графического интерфейса программы использовался фреймворк Qt и библиотека PyQt. При запуске программы пользователь видит окно с графическим интерфейсом (рисунок 1.2).
Рисунок 1.2 – Окно с графическим интерфейсом
В меню «Файл» при выборе пункта «Открыть», либо при нажатии сочетания клавиш «Ctrl+O» пользователь может загрузить данные о пунктах и расстояниях между ними из файла (рисунок 1.3).
Рисунок 1.3 – Загрузка данных о пунктах и расстояниях между ними
Данные хранятся в формате csv (от англ. Comma-Separated Values – значения, разделённые запятыми). Всего присутствует 3 поля: Start – начало пути, Finish – конец пути, Distance – длина пути (рисунок 1.4).
Рисунок 1.4 – Данные с тарифными расстояниями
После выбора файла загружаются элементы выпадающего списка. В выпадающем списке менеджер по перевозкам выбирает пункты погрузки, затаможивания, растаможивания и выгрузки (рисунок 1.5).
Рисунок 1.5 – Элементы выпадающего списка
После выбора четырех пунктов маршрута пользователь может нажать на кнопку «Найти путь», после чего будет вычислен кратчайший путь из заданной начальной точки в конечную. Путь будет выведен в виде отрезков с пунктами на концах, которые необходимо преодолеть. Для каждого отрезка будет выведена его длина (тарифное расстояние). Также будет выведена общая длина маршрута (рисунок 1.6).
Рисунок 1.6 – Вычисление кратчайшего пути
Кратчайший путь вычисляется с помощью алгоритма Дейкстры, который позволяет найти кратчайшие пути из одной вершины в графе, во все остальные. Краткое описание алгоритма:
- изначально расстояние до каждой вершины равно бесконечности, а расстояние до начальной вершины равно нулю;
- берется еще не посещённая вершина с минимальным расстоянием до нее и обозначается как u;
- рассматриваются все вершины, в которые ведут ребра из u: берется очередная вершина, находится новое расстояние до нее из u, прибавив к расстоянию до u расстояние из u до этой вершины, если новое расстояние меньше существующего, то старое расстояние заменяется на новое;
- вершина u помечается как посещенная;
- берется новая не посещенная вершина, расстояние до которой минимально, пока все вершины не будут посещены.
В результате написания программного кода получился готовый программный продукт, который позволяет осуществлять международные грузовые автомобильные перевозки по наиболее оптимальным маршрутам за счет применения оптимизационного алгоритма Дейкстры.
Библиографический список:
- Плоткин Б.К., Делюкин Л.А. Экономико-математические методы и модели в коммерческой деятельности и логистике. – СПб.: Изд-во СПбУЭФ, 2015. – 345 с.
