Journal influence
Bookmark
Next issue
Aggregation and analysis of information from logistics companies to build a complex cargo transportation route
Abstract:The work is devoted to optimizing the construction of transportation routes in the field of cargo logistics. There are cases when cargo transportation between two cities by one transport company is more expensive than transportation by different companies with cargo transshipment at intermediate points. Information about such complex routes is of interest to both transport companies, which can find ways to reduce the cost of routes, and ordinary users looking for options for cheaper cargo delivery. The subject of the study is the automation of building the most profitable complex route for cargo transportation performed by several road and rail carriers and passing through intermediate points for transshipment (transfer of cargo). A distinctive feature of the research method used in this work is that it is based on the analysis of data from the calculator websites of carrier companies, which enable dynamical extraction of the transportation cost information is during a query process, as well as on heuristic approaches to building a complex route. The authors formulated the criteria for selecting potential transshipment points and their number. The proposed route cost estimation approach was tested on open data of 40 logistics companies, 9 cargo configurations and routes between 171 cities. As a result of the work, the authors proposed and tested a new heuristic algorithm for constructing a complex cargo transportation route and developed a software module. The test results have shown the effectiveness of the algorithm: using the proposed heuristics, in 10% of cases it is possible to build a complex route between cities, the cost of which might be significantly less than a simple one. The theoretical significance of the work lies in the development of a new algorithm for solving the problem of constructing a complex route for the transportation of goods, the practical significance lies in the implementation of a new module that will be implemented in the existing logistics service Cargotime.ru.
Аннотация:Работа посвящена оптимизации построения маршрутов перевозки в сфере логистики грузов. Существуют случаи, когда перевозка груза между двумя городами одной транспортной компанией оказывается дороже, чем перевозка разными компаниями с перевалкой груза в промежуточных точках. В информации о таких сложных маршрутах за-интересованы как транспортные компании, которые могут найти пути удешевления маршрутов, так и простые пользователи, ищущие варианты более дешевой доставки груза. Предмет данного исследования – автоматизация построения наиболее выгодного сложного маршрута перевозки груза, исполняемого несколькими автомобильными и железнодорожными перевозчиками и проходящего через промежуточные пункты, в которых осуществляется перевалка (передача груза). Отличительной особенностью метода исследования является то, что он основан на анализе данных с сайтов калькуляторов компаний-перевозчиков, из которых информация о стоимости перевозки извлекается в процессе запроса динамически, и на эвристических подходах к построению сложного маршрута. Были сформулированы критерии для выбора потенциальных точек перевалки и их числа. Предложенный подход к оценке стоимости маршрута протестирован на открытых данных 40 логистических компаний, 9 кон-фигурациях груза и маршрутах между 171 городом. В результате предложена и протестирована новая процедура поиска сложного маршрута перевозки груза и разработан программный модуль. Тестирование показало эффективность процедуры: с помощью предложенных эвристик в 10 % случаев возможно построить сложный маршрут между городами, стоимость которого будет существенно меньше простого. Теоретическая значимость работы заключается в создании новой процедуры для решения задачи построения сложного маршрута по перевозке груза, практическая – в реализации нового модуля, который будет внедрен в действующий логистический сервис Cargotime.ru.
Authors: Esin, M.S. (mse@dscs.pro) - St. Petersburg State University (Student of the Department of Informatics), St. Petersburg, Russia, Korepanova, A.A. (aak@dscs.pro) - SPb FRC RAS (Junior Researcher), St. Petersburg, Russia, Sabrekov, A.A. (aas@dscs.pro) - SPb FRC RAS (Junior Researcher), St. Petersburg, Russia | |
Keywords: software development, multimodal routes, transportation price aggregator, cargo delivery calculator, heuristic methods, logistics automation, route cost optimization |
|
Page views: 1328 |
PDF version article |
Многие логистические компании реализуют на своих сайтах специальные калькуляторы по расчету стоимости доставки груза. С их помощью клиент может самостоятельно рассчитать примерную стоимость перевозки своего груза, не разбираясь в сложных тарифах и не связываясь напрямую с компанией. Данные калькуляторы по параметрам груза, начальному и конечному пунктам маршрута перевозки вычисляют примерную стоимость и срок доставки, за которые компания готова перевезти груз [1]. Такой калькулятор позволяет посмотреть предложения только одной конкретной компании, на сайте которой расположен. С участием коллектива авторов данной статьи на сайте Cargotime.ru создан агрегатор калькуляторов стоимости перевозок, консолидирующий на одной странице данные о стоимости и сроках доставки груза, отправляя за-просы напрямую к калькуляторам 40 логистических компаний. Сопоставив данные из разных источников, агрегатор способен выбрать самое выгодное по стоимости и срокам предложение по перевозке груза, в то время как подобный маршрут, обеспеченный одной компанией, не всегда самый выгодный. Например, в отдельных городах могут оказаться локальные игроки, которые готовы сделать более выгодное предложение по транспортировке груза, то есть более дешевым может оказаться маршрут, выполняемый разными компаниями на разных отрезках пути. Допустим, пользователю нужно перевезти груз в 100 килограммов из Великого Новгорода в Комсомольск-на-Амуре. Он может воспользоваться услугами одной компании, однако более дешевым вариантом может оказаться перевозка двумя компаниями: одна из них перевезет груз на поезде до Хабаровска, оттуда будет совершена перевалка груза на транспорт другой компании, работающей только по Хабаровскому краю, которая довезет груз от Хабаровска до Комсомольска-на-Амуре дешевле. Также возможны ситуации, когда транспортировку между двумя городами ни одна компания полностью не обеспечивает (например, для доставки между ними необходимо воспользоваться двумя и более видами транспорта) или стоимость маршрута получается неоправданно высокой, потому что осуществляется непрофильными компаниями (например, перевозка многотонных грузов курьерской службой). В таких ситуациях, как правило, можно обнаружить сложный маршрут, обеспечиваемый несколькими компаниями, с перегрузом в городах-хабах. Найти такой маршрут вручную, перебирая промежуточные города, бывает крайне затруднительно. Информация о сложных маршрутах может быть полезна как транспортным компаниям, которые могут найти пути удешевления маршрутов, так и простым пользователям, заинтересованным в более дешевой доставке груза. Таким образом, актуальной видится задача построения наиболее выгодного сложного маршрута, исполняемого несколькими перевозчиками и проходящего через промежуточные пункты, в которых осуществляется перевалка (передача груза). На российском рынке не обнаружено открытого инструмента с подобной функциональностью. В статье предложены решения задачи построения сложных маршрутов на основе данных открытых калькуляторов компаний-автоперевозчиков и железнодорожных перевозчиков и описана разработанная архитектура программного модуля, планируемого для внедрения в действующий сервис Cargotime.ru. В перспективе данные наработки планируется использовать для реализации сервиса оптимизации мультимодальных маршрутов. Постановка задачи Назовем простым маршрут перевозки между двумя городами, обеспечиваемый одной компанией, сложным – маршрут, обеспечиваемый несколькими компаниями, с перегрузом (перевалкой) в городах-хабах. Отметим, что речь идет не о географии маршрутов и оптимизации навигации, а об оптимизации стоимости доставки груза через подбор цепочки компаний-перевозчиков и городов-хабов, в которых они реализуют свои услуги. Бывают случаи, когда можно найти сложный маршрут гораздо дешевле любого простого. Цель данного исследования – разработать процедуру поиска такого дешевого сложного маршрута между двумя точками по заданным параметрам груза. Для расчета стоимости маршрута пользователь вводит следующие данные о грузе или партии грузов: - габариты (длина, высота, ширина в метрах; натуральное число и положительная десятичная дробь); - вес (килограммы; натуральное число и положительная десятичная дробь); - стоимость страховки (рубли; натуральное число и положительная десятичная дробь); - начальный и конечный пункты доставки (город доставки; доставка от двери или от склада, до склада или до двери); - условия упаковки груза (обрешетка, пленка, коробка, мешки и т.д.). Стоимость перевозки груза транспортной компанией рассчитывается динамически на основе ее внутренних формул, которые обычно скрыты от пользователя, и может нелинейно зависеть от дополнительных услуг типа обрешетки и страховки груза, протяженности маршрута, направления, веса, объема и объемного веса груза. Также тарифы имеют тенденцию меняться со временем в зависимости от сезона, экономической ситуации в стране и прочих обстоятельств (например, стоимость грузоперевозок из Китая за три года выросла в 12,5 раза: https://deita.ru/article/529554). В рамках текущего исследования использованы данные калькуляторов со страниц компаний-перевозчиков, таким образом, нет данных о внутренних формулах расчета компаний, то есть нет априорной информации о стоимости перевозки груза между городами. Для поиска оптимального сложного маршрута для конкретного груза необходимо каждый раз динамически получать информацию с сайтов компаний-перевозчиков с помощью реализованных на них открытых калькуляторов стоимости доставки. Иными словами, пользователь вводит параметры груза, точки отправления и прибытия на разработанном ресурсе-агрегаторе – Cargotime.ru. Сервис отправляет запросы в 40 компаний-перевозчиков, парсинг по которым реализован на текущий момент, получает ответы о стоимости и времени доставки, и таким образом формируется пространство исходных признаков для процедуры. Количество запросов к онлайн-калькуляторам в единицу времени ограничивается компаниями-перевозчиками в целях обеспечения информационной безопасности. Релевантные работы Математические методы и алгоритмы активно применяются во множестве областей логистики. Одной из важнейших задач, для решения которых они используются, является оптимизация маршрута с точки зрения стоимости, времени, экологичности и т.д. К применяемым методам относятся методы нелинейного программирования [2, 3], а также различные алгоритмы на графах. Работа [4] посвящена модификации алгоритма А* с помощью муравьиного алгоритма для построения оптимального маршрута доставщика. Авторы [5] предложили метод решения задачи доставки грузовыми поездами в логистические центры по кратчайшему маршруту с помощью алгоритма Флойда–Уоршалла. В исследовании [6] предложена модификация алгоритма Дейкстры для оптимизации логистики промышленного парка. Работа [7] направлена на решение проблемы оптимизации маршрутов транспортных средств в логистике распределения сельскохозяйственной продукции с помощью муравьиного алгоритма. Авторы [8] используют их для оптимизации маршрута доставщика, которому необходимо посетить несколько точек доставки за день. В [9] алгоритмы на графах применяются для построения наиболее экологичного маршрута для водителей большегрузных транспортных средств, который позволит им экономить топливо. В работе [10] они используются для построения планировщика маршрута городского транспорта с учетом пробок. Наиболее близкой к теме настоящего исследования является работа [11]. В ней задача построения сложных маршрутов решается в рамках улучшения существующего механизма принятия логистических решений для одной крупной китайской транспортной 4PL-компании, которая строит цепочки перевозки грузов с помощью своих партнеров-перевозчиков. Для построения оптимальных маршрутов использован алгоритм Дейкстры, а также применены нечеткие комплексные оценки стоимости и сроков доставки. Особенностью использования данного подхода является то, что для его применения необходим априорно известный набор консолидированных данных о перевозчиках-партнерах компании, об их загруженности, стоимости перевозки различных грузов на разных участках пути. Для каждой перевозки строится граф, где в качестве вершин выступают точки возможной перевалки груза между перевозчиками, ребро отображает перевозку между двумя точками перевалки с помощью одного партнера-перевозчика, вес ребра – стоимость такой перевозки. В рамках текущего исследования доступа к подобным данным нет, источником данных о стоимости перевозки являются калькуляторы компаний-перевозчиков, стоимость перевозки не хранится нигде заранее, а получается динамически для каждого запроса пользователя, поэтому предложенный метод не решает поставленную задачу. Помимо графового подхода к построению сложного маршрута, существует показывающий высокую эффективность динамический подход. В статье [12] рассматриваются методы динамического программирования в задаче нахождения оптимального по времени или цене мультимодального маршрута. Алгоритм, как и в предыдущей работе, основан на использовании априорно известной информации о загруженности различных компаний, их тарифах и географии перевозок. Авторы [12] считают главным преимуществом динамического многошагового подхода к построению возможность в любой момент изменить маршрут из-за непредвиденных обстоятельств: из построения следует, что каждый подмаршрут итогового маршрута также является оптимальным. Данный метод имеет те же ограничения, что и предыдущий, и тоже не может быть применим для решения поставленной в рамках текущей работы задачи. В статье [13] указываются главные недостатки различных графовых и динамических оптимизаций: необходимость обладать данными о стоимости перевозки по всем отрезкам путей и невозможность предвидеть внешние факторы – воздействие погоды или дорожно-транспортную ситуацию. Решение задачи построения сложных маршрутов в рамках работы с общедоступными калькуляторами компаний не предполагает использование заранее агрегированного набора данных о тарифах и предложениях компаний. Следовательно, в условиях ограниченности ресурсов и невозможности оперативного получения исчерпывающего набора консолидированных данных о стоимости доставки всеми перевозчиками на всех возможных маршрутах предстоит решить задачу без использования указанных графовых, динамических и численных оптимизаций, однако в перспективе их применение в построении сложного маршрута весьма вероятно. Применение алгоритмов на взвешенных графах для построения сложных маршрутов Алгоритмы на взвешенных графах, такие как алгоритмы Дейкстры, Форда–Беллмана и Флойда–Уоршелла, активно применяются в задачах поиска кратчайшего пути [4–6]. Для использования графовых алгоритмов необходимо построить граф, на котором в качестве вершин выступают точки возможной перевалки груза между перевозчиками, ребро отображает наиболее дешевую перевозку между двумя точками с помощью одного перевозчика, вес ребра – стоимость такой перевозки. Как уже было отмечено, применение таких алгоритмов в исследуемой задаче затруднено, так как получить взвешенный граф, отражающий все предложения перевозчиков для перевозки конкретной конфигурации груза (то есть минимально необходимый набор данных), можно двумя способами: - получить данные на лету, отправив большое количество параллельных запросов к сайтам компаний; - извлечь предварительно собранные данные из БД. В первом случае нужно сделать большое число запросов к калькуляторам компаний, что ресурсозатратно и с высокой вероятностью приведет к блокировке запросов, превышающих относительно низкий лимит за короткое время. Эта блокировка обходится применением прокси-серверов, то есть равномерным распределением запросов по нескольким IP-адресам. Однако отправление одновременно большого числа запросов на серверы калькуляторов может вызвать нарушения их работоспособности. Кроме того, многие сайты используют системы защиты от автоматизированного сбора информации [14]: зачастую сайты способны определить первоначальный источник через хэдеры и куки запросов, а также идентифицировать роботизированное поведение, не свойственное пользователю браузера. Во втором случае для каждой конфигурации придется хранить огромное количество данных о предложениях компаний, которые быстро станут неактуальными, поскольку стоимость грузоперевозок зависит от сезона, политической и экономической ситуации в стране и мире (https://www.megaresearch.ru/knowledge_library/dinamika-cen-na-perevozki-tarifikaciya-osnovnyh-napravleniy-3125). Таким образом, на данном этапе использование алгоритмов на графах затруднительно ввиду сложности получения достаточного числа актуальных данных о стоимости перевозки разных грузов. В будущем планируется перейти к использованию подобных алгоритмов, однако на данном этапе решено от них отказаться и использовать эвристические методы. Для каждой перевозки необходимо динамически рассчитать стоимость перевозки груза разными компаниями между различными городами с помощью сайтов калькуляторов и на основе полученной информации составить сложный маршрут перевозки. Анализ логистических сетей В силу затрудненности использования в текущей задаче стандартных графовых и динамических оптимизаций возникает необходимость создания некоторой процедуры для поиска сложных маршрутов, которая опирается в основном на логические предположения об оптимальности решения, а не на исчерпывающий набор данных о стоимости перевозки разными компаниями на разных участках маршрута. Чтобы при построении сложного маршрута не перебирать все города России в качестве возможных точек перевалки, было решено отобрать некоторое множество городов, которые входят в транспортные сети перевозчиков чаще всего и через которые с наибольшей вероятностью с точки зрения экспертов будет проходить дешевый сложный маршрут. Использование в качестве промежуточных точек маршрута только этих городов позволит ускорить работу процедуры, а также сократить число запросов к калькуляторам доставки, то есть снизить нагрузку как на свой сервер, так и на серверы компаний-перевозчиков. Для отбора городов в список возможных точек перевалки были сформулированы следующие критерии: - объем складских помещений; - включенность в основные транзитные линии на территории России; - покрытие множеством отобранных городов всей карты России. В предположении, что объем складских помещений в городе коррелирует со степенью вовлеченности в транспортные сети, можно выделить 18 городов, объем складских поме-щений которых больше 150 тыс. кубометров (https://content.knightfrank.com/research/856/documents/ru/rynok-skladskoy-nedvizhimosti-rossii-2018-god-6193.pdf). Также было решено принять во внимание главные транзитные железнодорожные линии России. Перевозка грузов по железным дорогам – самый дешевый способ транспортировки грузов по суше, поэтому в перечень возможных точек перевалки необходимо включить крупные города, через которые проходят основные транзитные железнодорожные линии России (http://www.idost.ru/railroad/help/19/). В список вошли и крупные города Сибири и Дальнего Востока (Якутск, Иркутск, Южно-Сахалинск). Стратегии построения сложных маршрутов Представим задачу нахождения сложного маршрута в терминах теории графов. Рассмотрим населенные пункты как вершины, а пути между ними как взвешенные ориентированные ребра, где вес ребра – это стоимость самой дешевой доставки груза между двумя городами. Тогда множество всех населенных пунктов и путей между ними можно представить как полный ориентированный взвешенный граф (стоимость доставки в одну сторону может не совпадать со стоимостью в другую). Улучшением маршрута будем считать замену одного из ребер в маршруте на пару ребер, соединяющих начало и конец исходного ребра, причем суммарный вес двух ребер меньше веса исходного ребра. Тогда сложный маршрут с любым количеством ребер можно представить как композицию улучшений изначального простого маршрута, соединяющего два города. В статье предложены два эвристических подхода к улучшению маршрутов, первый из которых использует ближайшие к пунктам отправки и доставки крупные города, а второй основан на минимизации суммарного расстояния. Данные эвристики предполагают вычисление расстояния между городами. Поскольку решалась задача перевозки груза по земле (по железным и автомобильным дорогам), расстояния рассчитывались не по геодезическим линиям, а по дорогам. Для получения оптимизированных расстояний по крупным дорогам использован сторонний сервис MapBox Optimization. Было решено хранить в БД заранее рассчитанную информа-цию о расстояниях между городами, использованными при тестировании, потому что запросы на лету к стороннему сервису достаточно ресурсоемкие. Кроме того, возможны ситуации, когда выбранный крупный город не находится на пути к пункту доставки. То есть, чтобы попасть в промежуточный город, нужно сделать крюк. Скорее всего, сложный маршрут через такой город будет дороже простого, поэтому эти города при наличии альтернативных крупных решено не рассматривать. С помощью координат городов отправки и доставки, которые, как и оптимизированные расстояния, хранятся в БД, можно ограничить область между ними. В предложенной далее процедуре ограниченная область используется для того, чтобы при выборе промежуточного города сразу отсечь неподходящие, через которые нужно проезжать, следуя к городу доставки. На рисунке 1 проиллюстрирован принцип работы ограниченной области: сама область выделена черным цветом, а красный маршрут с высокой вероятностью длиннее и дороже зеленого, то есть является неоптимальным. Рассмотрим эвристические подходы к построению сложных маршрутов, а также саму процедуру поиска сложного маршрута, более выгодного, чем простой. Эвристика Nearest Major City (NMC). Первое рассматриваемое улучшение маршрута – замена ребра маршрута на пару смежных ре-бер, инцидентных вершине, соответствующей ближайшему к пункту отправки или доставки крупному городу (рис. 2). С помощью вычисленных оптимизированных расстояний и координат городов для пункта отправки (доставки) выбирается ближайший крупный город из ограниченной области, через который в дальнейшем будет проведен сложный маршрут. Данное улучшение опирается на предположение о том, что компании, специализирующиеся на перевозках в пределах пары федеральных округов, то есть имеющие наибольшее количество терминалов в этих округах, должны доставлять грузы до локальных населенных пунктов, которые вообще не обслуживаются остальными компаниями, а также предлагать более низкие цены по сравнению с остальными компаниями в этих округах. В таком случае часть маршрута будет пройдена по тарифам местных компаний, что имеет потенциал быть дешевле. Эвристика Minimal Total Distance (MTD). Второе улучшение основано на минимизации суммарного пройденного расстояния. Для поиска подходящего промежуточного города используются те же оптимизированные расстояния и координаты городов, что и в первом подходе: отыскивается минимум суммарной длины двух ребер, инцидентных вершине, соответствующей одному из городов из ограниченной области (рис. 3). Вершина, для которой достигается минимум, является искомой при таком эвристическом подходе. Улучшение ориентировано на минимизацию суммарного расстояния – чем меньше километраж, тем дешевле. По такому принципу работают некоторые калькуляторы: тарифов для конкретных направлений у них нет, а предварительная стоимость прямо пропорциональна расстоянию между городами или времени в пути. Процедура поиска выгодного сложного маршрута. Предлагается следующая процедура поиска сложного маршрута, использующего эвристики NMC и MTD. · Поступление набора данных о грузе на вход процедуре. · Поиск лучшего по стоимости простого маршрута, обеспеченного одной компанией, через параллельные запросы к онлайн-калькуляторам компаний. · Поиск в ограниченной области перевалочных пунктов среди отобранных 20 городов: - выбор ближайших к пунктам доставки перевалочных городов; - выбор промежуточного города, сумма расстояний до которого от точки отправления и точки доставки минимальна. · Построение сложного маршрута: для каждого звена выбирается лучшее предложение, стоимости суммируются: - маршрут через ближайший крупный к пункту отправки город; - маршрут через ближайший крупный к пункту доставки город; - маршрут через промежуточный крупный город. · Сравнение полученных сложных маршрутов с наиболее выгодным простым маршрутом. · Получение результата работы процедуры – самый выгодный по стоимости маршрут перевозки (один из найденных сложных или исходный простой). Полученную процедуру можно применять к любому ребру текущего сложного маршрута. Однако стоит учесть, что при каждом следующем улучшении количество ребер будет только расти, что может сказаться на практической пользе таких маршрутов: перевозка груза несколькими компаниями не только влечет за собой сопутствующие расходы на транспортировку между складами, перевалку, но и повышает риск потерять или повредить груз во время смены компаний. Важно соблюдать баланс между количеством итераций улучшения и степенью выгодности маршрута: если серьезное улучшение достигнуто уже на первых этапах, стоит остановиться и не тратить время и ресурсы на поиск маршрута с большим числом ребер. В рамках данного исследования, в частности, в тестировании, рассматривались маршруты с одним промежуточным городом. Первичное тестирование В качестве первичного тестирования предложенного решения по оптимизации маршрута планировалось проверить выгодность сложных маршрутов на 171 городе с населением не менее 50 тыс. человек по трем категориям грузов – легкие (до 50 кг), средние (до 500 кг) и тяжелые (до 10 т) для части грузовых компаний. Для каждой категории были сгенерированы габариты для трех случайных грузов. Точками перевалки для тестов стали 20 городов: Благовещенск, Владивосток, Воронеж, Екатеринбург, Иркутск, Казань, Краснодар, Москва, Нижний Новгород, Новосибирск, Омск, Пермь, Ростов-на-Дону, Самара, Санкт-Петербург, Тула, Уфа, Хабаровск, Челябинск, Чита. Указанные ограничения обусловлены доступностью ресурсов: тестирование всех населенных пунктов для большего числа конфигураций груза оказалось бы весьма долгим и затратным. Для тестирования использованы 40 калькуляторов компаний, парсинг которых реализован на сайте Cargotime.ru. Города выбирались по территориальному принципу небольшими группами, локализованными около одного из 20 крупных городов, чтобы проверить выгодность маршрута через ближайший крупный город (http://www.swsys.ru/uploaded/image/2023-2/2023-2-dop/18.jpg). Множество пар тестируемых городов можно представить как прямое произведение двух укрупненных групп городов. Сложные маршруты были построены для каждой такой пары и сопоставлены с простым маршрутом. На рисунках 4 и 5 приведена статистика по количеству случаев улучшения простых маршрутов сложными. Вертикальная ось – пары укрупненных групп городов, искусственно привязанных к одному крупному, горизонтальная – процент случаев, в которых сложный маршрут между городами, принадлежащими этим группам, выгоднее простого. Поясним диаграмму на примере: для каждого города из группы выбранных городов, находящихся около Санкт-Петербурга, был найден наиболее дешевый маршрут перевозки груза в каждый город из группы городов, находящихся около Новосибирска. Стоимость перевозки между любой парой городов была рассчитана для трех категорий грузов, по три груза в каждой категории. В итоге более чем в 40 % случаев для грузов, относящихся к категории «средние», то есть от 50 до 500 кг, был найден составной маршрут, оказавшийся дешевле прямого. Диаграмма на рисунке 4 отражает процент случаев улучшения простого маршрута сложным, а на рисунке 5 – ту же статистику, только для случаев существенного улучшения стоимости (минимум на 20 %). То есть для перевозок грузов между городами групп Санкт-Петербурга и Новосибирска более чем в 20 % случаев был найден составной маршрут, стоимость которого минимум на 20 % ниже стоимости прямого маршрута. Результаты, отображенные на второй диаграмме, имеют большие значения, так как калькуляторы вычисляют примерную стоимость и не учитывают, что строится сложный маршрут, для которого нужна транспортировка груза между компаниями, так что, выигрыш меньше 20 % стоимости будет потерян за счет стоимости перевалки груза, простоя груза в ожидании перевалки и других промежуточных операций и порождаемых рисков. Детали реализации тестового продукта Тестовый продукт реализован с помощью платформы Node.js, фреймворка NestJS и инструментов для работы с БД MySQL. На рисунке http://www.swsys.ru/uploaded/image/2023-2/2023-2-dop/19.jpg показаны основные модули, участвующие в работе сервиса. Клиент взаимодействует с сервисом через websocket-соединение, и по его запросу запускается Composite Route Resol-ver, который использует эвристики NMC и MTD, чтобы сгенерировать несколько наборов входных данных, отвечающих за определенные участки сложного маршрута, каждый из которых включает в себя город отправки, город доставки и информацию о перевозимых грузах. Calculator Executor получает эти входные данные и с помощью модулей Preprocessing Module, Packing Module, Postprocessing Module и Data Mining Module передает стоимость доставки и другую важную для пользователя информацию обратно в Composite Routing Mo-dule. Composite Route Resolver сравнивает сложные маршруты между собой и в случае, если один из них оказался выгоднее простого, уведомляет об этом пользователя. В основе Composite Route Generator лежит приведенная выше процедура поиска сложных маршрутов: он использует эвристики Nearest Major City и Minimal Total Distance. В БД хранятся матрица расстояний по дорогам между тестовыми городами, а также информация о координатах этих городов для реализации идеи с ограниченной областью. Матрица расстояний сформирована с помощью стороннего сервиса MapBox Optimization. Были рассмотрены аналоги, например, API Яндекс.Карт, который обладает низким лимитом бесплатных запросов, а также сервис Transportica.ru, сильно уступающий MapBox в скорости и удобстве работы с ответом. Выбор в пользу MySQL был сделан из-за возможности хранить таблицы БД почти неограниченных размеров, а также его частого использования для веб-разработки. Остановимся подробнее на модулях, участвующих в расчете (http://www.swsys.ru/uploaded/image/2023-2/2023-2-dop/21.jpg). Preprocessing Module отвечает за проверку каждой компании, от которой желательно получить предложения о доставке, на соответствие всем требованиям к грузу и пунктам отправки и доставки. Например, Company Countries Checker отвечает за то, что компания имеет представительства в странах городов отправки и доставки, Company Limits Checker проверяет, удовлетворяет ли груз грузовым лимитам компании, а Company Services Checker сопоставляет список дополнительных услуг, которые пользователь указал обязательными, со списком услуг, предоставляемых компанией. Актуализация данных о странах, лимитах и дополнительных услугах происходит через обращение к БД, где они периодически изменяются и дополняются вручную. Packing Module отвечает за эффективную упаковку грузов по партиям: иногда калькуляторы компаний не способны обработать большое количество грузов за один запрос, поэтому приходится разбивать грузы на небольшие партии с минимальными потерями в стоимости перевозки. Data Mining Module отвечает за сбор информации о предложениях перевозчиков из открытых источников, большинство из которых являются открытыми API, либо общедоступными запросами к сайту компании. Запросы отправляются параллельно примерно 40 компаниям России и ближнего зарубежья, и главная цель на данном этапе – привести полученные разнородные данные к одному виду. Postprocessing Module отвечает за отображение предложений на сайте: Exchange Rates Service следит за изменением курса валют, чтобы корректно сортировать предложения в разных валютах по стоимости, а Logo Names Service отвечает за логотипы компаний. Курсы валют в БД обновляются автоматически с помощью стороннего сервиса. Выводы В работе предложена процедура поиска сложного маршрута перевозки груза авто- и железнодорожными перевозчиками, основанного на использовании данных открытых калькуляторов сайтов логистических компаний. Отличительной особенностью является то, что поиск осуществляется в условиях информационного дефицита, когда нет исчерпывающего набора данных о стоимости перевозки различными компаниями и необходимо получать эти данные во время работы, что накладывает большие ограничения на используемый инструментарий. Из-за существующих ограничений процедура опирается прежде всего на эвристические методы. Было проведено первичное тестирование идеи построения сложных маршрутов, основанное на предложениях 40 грузовых компаний по трем категориям грузов на 171 населенном пункте. Результаты показали, что с помощью предложенных эвристик в 10 % случаев можно построить сложный маршрут между городами, стоимость которого будет существенно меньше простого. Не каждый маршрут получается оптимизировать, однако это уже яв-ляется хорошим результатом, поскольку в массе позволяет существенно экономить. Не очень большой процент обусловлен тем, что простой маршрут закономерно является наиболее выгодным в большинстве случаев: компании стремятся оптимизировать стоимость своих перевозок в конкурентной борьбе за клиентов. В перспективе разработанный метод планируется использовать для построения мультимодальных маршрутов. Его тестирование на авто- и железнодорожных перевозчиках обусловлено прежде всего тем, что такие компании имеют больше открытых калькуляторов, чем морские и авиаперевозчики, к работе с ними планируется перейти на следующих этапах исследования. Планируется запустить тестовый прототип на сайте Cargotime.ru, расширять список грузовых компаний, с которыми работает агрегатор, а также оценивать сопутствующие расходы на транспортировку груза между компаниями, чтобы учитывать их при расчете. Перспективой данной работы является и применение предложенных методов для построения мультимодальных маршрутов (маршрутов со сменой транспорта). Список литературы 1. Абрамов М.В., Есин М.С. Агрегация сведений и оценка параметров грузовых маршрутов в условиях информационного дефицита // ИБРР-2021: мат. конф. 2021. С. 328–329. 2. Huang K., Xu L., Chen Y., Cheng Q., An K. Customized bus route optimization with the real-time data. J. of Advanced Transportation, 2020, pp. 1–9. doi: 10.1155/2020/8838994. 3. Zhang Y., Kou X., Song Zh., Fan Y., Mohammed U., Jagota V. Research on logistics management layout optimization and real-time application based on nonlinear programming. Nonlinear Engineering, 2021, vol. 10, no. 1, pp. 526–534. doi: 10.1515/nleng-2021-0043. 4. Wei Z. High performance computing simulation of intelligent logistics management based on shortest path algorithm. Computational Intelligence and Neuroscience, 2022, pp. 1–10. doi: 10.1155/2022/7930553. 5. Keskin B., Özcan E. Floyd-Warshall algorithm in shortest path optimizations: example of logistics centers. Demiryolu Mühendisliği, 2022, no. 17, pp. 82–92. doi: 10.47072/demiryolu.1187884. 6. Taiping M., Renhang D., Peisi Z. Research of improved Dijkstra algorithm based park logistics scheduling. The Open Cybernetics & Systemics J., 2016, vol. 9, pp. 541–545. doi: 10.2174/1874110X01509010541. 7. Sun M., Pang D. Vehicle routing optimisation algorithm for agricultural products logistics distribution. IJADS, 2017, vol. 10, no. 4, pp. 327–334. doi: 10.1504/IJADS.2017.087175. 8. Jodh D., Padwal A., Gaikwad P., Shinde K.A. Route optimization for e-commerce logistic systems. IJARSCT, 2022, vol. 2, no. 1, pp. 813–816. doi: 10.48175/IJARSCT-5766. 9. Fanti M.P., Mangini A., Favenza A., Difilippo G. An Eco-Route planner for heavy duty vehicles. IEEE/CAA J. 10. Rothkrantz L. Hybrid dynamic route planners. Proc. CompSysTech'18, 2018, pp. 12–19. doi: 10.1145/3274005.3274012. 11. Wei-Qiong F. Fourth-party logistics optimization decision-making based on graph model with multi-dimensions. Information Tech. J., 2014, vol. 13, no. 6, pp. 1180–1185. doi: 10.3923/itj.2014.1180.1185. 12. Zavalishchin D., Popkov A. Dynamic programming method for optimization problem of multi-modal transportation. CEUR–WS Proc. Proc. MMIT, 2016, vol. 1825, pp. 118–122. 13. Ашихмина М.В., Городничев В.В. Унификация принятия логистических решений с использованием теории графов // Экономика, право и образование в условиях риска и неопределенности: тенденции и перспективы развития: матер. Междунар. науч.-практич. конф. 2016. С. 7–10. 14. Корепанова А.А., Бушмелев Ф.В., Сабреков А.А. Технологии парсинга на Node.js в задаче агрегации сведений и оценки параметров грузовых маршрутов посредством извлечения данных из открытых источников // Компьютерные инструменты в образовании. 2021. № 3. С. 41–56. Reference List 1. Abramov, M.V., Esin, M.S. (2021) ‘Aggregation of information and estimation of parameters of cargo routes in conditions of information deficit’, Proc. ISRR-2021, pp. 328–329 (in Russ.). 2. Huang, K., Xu, L., Chen, Y., Cheng, Q., An, K. (2020) ‘Customized bus route optimization with the real-time data’, J. of Advanced Transportation, pp. 1–9. doi: 10.1155/2020/8838994. 3. Zhang, Y., Kou, X., Song, Zh., Fan, Y., Mohammed, U., Jagota, V. (2021) ‘Research on logistics management layout optimization and real-time application based on nonlinear programming’, Nonlinear Engineering, 10(1), pp. 526–534. doi: 10.1515/nleng-2021-0043. 4. Wei, Z. (2022) ‘High performance computing simulation of intelligent logistics management based on shortest path algorithm’, Computational Intelligence and Neuroscience, pp. 1–10. doi: 10.1155/2022/7930553. 5. Keskin, B., Özcan, E. (2022) ‘Floyd-Warshall algorithm in shortest path optimizations: example of logistics centers’, Demiryolu Mühendisliği, (17), pp. 82–92. doi: 10.47072/demiryolu.1187884. 6. Taiping, M., Renhang, D., Peisi, Z. (2016) ‘Research of improved Dijkstra algorithm based park logistics scheduling’, The Open Cybernetics & Systemics J., 9, pp. 541–545. doi: 10.2174/1874110X01509010541. 7. Sun, M., Pang, D. (2017) ‘Vehicle routing optimisation algorithm for agricultural products logistics distribution’, IJADS, 10(4), pp. 327–334. doi: 10.1504/IJADS.2017.087175. 8. Jodh, D., Padwal, A., Gaikwad, P., Shinde, K.A. (2022) ‘Route optimization for e-commerce logistic systems’, IJARSCT, 2(1), pp. 813–816. doi: 10.48175/IJARSCT-5766. 9. Fanti, M.P., Mangini, A., Favenza, A., Difilippo, G. (2020) ‘An Eco-Route planner for heavy duty vehicles’, IEEE/CAA J. of Automatica Sinica, 8(1), pp. 37–51. doi: 10.1109/JAS.2020.1003456. 10. Rothkrantz, L. (2018) ‘Hybrid dynamic route planners’, Proc. CompSysTech'18, pp. 12–19. doi: 10.1145/3274005.3274012. 11. Wei-Qiong, F. (2014) ‘Fourth-party logistics optimization decision-making based on graph model with multi-dimensions’, Information Tech. J., 13(6), pp. 1180–1185. doi: 10.3923/itj.2014.1180.1185. 12. Zavalishchin, D., Popkov, A. (2016) ‘Dynamic programming method for optimization problem of multi-modal transportation’, CEUR–WS Proc. Proc. MMIT, 1825, pp. 118–122. 13. Ashikhmina, M.V., Gorodnichev, V.V. (2016) ‘Unification of logistic decision making using graph theory’, Proc. Intern. Sci. and Pract. Conf. Economics, Law and Education Under Risk and Uncertainty: Trends and Prospects, pp. 7–10 (in Russ.). 14. Korepanova, A.A., Bushmelev, F.V., Sabrekov, A.A. (2021) ‘Node.js parsing technologies in the task of aggregating information and evaluating the parameters of cargo routes by extracting data from open sources’, Computer Tools in Education, (3), pp. 41–56 (in Russ.). |
Permanent link: http://swsys.ru/index.php?page=article&id=5006&lang=en |
Print version |
The article was published in issue no. № 2, 2023 [ pp. 309-319 ] |
Perhaps, you might be interested in the following articles of similar topics:
- Разработка многоагентного ПК ИНТЭК-М для исследований проблемы энергетической безопасности
- Организационные проблемы реализации гибких подходов в разработке прикладного программного обеспечения
- Экспериментальный анализ точности и производительности разновидностей архитектур YOLO для задач компьютерного зрения
Back to the list of articles