All issues

Вывозка лесоматериалов из удаленных лесозаготовительных районов Сибири характеризуется высоким уровнем транспортных издержек. Наличие протяженных участков грунтовых лесовозных дорог, сезонные ограничения (весенняя распутица, зимники) и значительные расстояния от лесосек до магистральных транспортных узлов (50–200 км) обусловливают необходимость систематического решения задачи рационального планирования маршрутов вывозки.

В настоящей работе предложена математическая модель двухэшелонной маршрутизации транспортных средств (2E-VRP), адаптированная к условиям вывозки лесоматериалов в макрорегионе Урала и Сибири. Модель учитывает переменные транспортные затраты (пробег лесовозов), фиксированные затраты на задействование каждой единицы техники ($c_{fix}$ = 30 000 руб./рейс) и ограничения грузоподъемности. Задача приведена к форме QUBO — квадратичной безусловной бинарной оптимизации; емкостные ограничения интегрированы посредством штрафного коэффициента $\lambda_{cap} = 500$. Такое представление обеспечивает совместимость модели с современными специализированными решателями (квантовыми отжигателями и цифровыми аннилерами).

Апробация модели выполнена на реальной географии Уральского и Сибирского федеральных округов: 207 узлов логистической сети, 65 предприятий-потребителей, 8 магистральных транспортных узлов. Предложенный трехстадийный алгоритм «Допустимость прежде всего» формирует допустимый маршрутный план за 1,7 с и обеспечивает снижение суммарных транспортных затрат на 69% относительно базового генетического алгоритма. Последующая оптимизация методом имитации отжига дополнительно улучшает значение целевой функции QUBO на 55%.

The haulage of timber from remote logging areas of Siberia is characterized by high transportation costs. Long stretches of unpaved logging roads, seasonal constraints (spring thaw and winter roads), and considerable distances from cutting areas to main transport hubs (50–200 km) make systematic route planning essential.

This paper proposes a mathematical model of the two-echelon vehicle routing problem (2E-VRP) adapted to timber haulage in the macro-region of the Urals and Siberia. The model incorporates variable transportation costs (truck mileage), fixed costs of using each vehicle ($c_{fix}$ = 30 000 RUB per trip), and vehicle-capacity constraints. The problem is transformed into a QUBO (quadratic unconstrained binary optimization) formulation; capacity constraints are integrated through the penalty coefficient $\lambda_{cap}$ = 500. This representation makes the model compatible with modern specialized solvers, including quantum annealers and digital annealers.

The model is tested on the real geography of the Ural and Siberian Federal Districts: 207 nodes in the logistics network, 65 customer enterprises, and 8 main transport hubs. The proposed three-stage “Feasible-First” algorithm constructs a feasible routing plan in 1.7 s and reduces total transportation costs by 69% relative to a baseline genetic algorithm. Subsequent simulated annealing further improves the QUBO objective value by 55%.

В данной работе проводится сравнительный анализ точного и эвристических алгоритмов, представленных методом ветвей и границ, генетическим и муравьиным алгоритмами соответственно, для поиска оптимального решения задачи коммивояжера на примере робота-курьера. Целью работы является определение времени работы, длины полученного маршрута и объема памяти, необходимого для работы программы, при использовании метода ветвей и границ и эволюционных эвристических алгоритмов. Также определяется наиболее целесообразный из перечисленных методов для применения в заданных условиях. В настоящей статье используются материалы проведенного исследования, реализованного в формате программы для ЭВМ, программный код для которой реализован на языке Python. В ходе исследования был выбран ряд критериев применимости алгоритмов (время работы программы, длина построенного маршрута и объем необходимой для работы программы памяти), получены результаты работы алгоритмов в заданных условиях и сделаны выводы о степени целесообразности применения того или иного алгоритма в различных заданных условиях работы робота-курьера. В ходе исследования выяснилось, что для малого количества точек ($\leqslant10$) метод ветвей и границ является наиболее предпочтительным, так как находит оптимальное решение быстрее. Однако при вычислении маршрута этим методом, при условии увеличения точек более 10, время работы растет экспоненциально. В таком случае более эффективные результаты дает эвристический подход с использованием генетического и муравьиного алгоритмов. При этом муравьиный алгоритм отличается решениями, наиболее близкими к эталонным, при увеличении точек более 16. Относительным недостатком его является наибольшая ресурсоемкость среди рассматриваемых алгоритмов. Генетический алгоритм дает схожие результаты, но при увеличении точек более 16 растет длина найденного маршрута относительно эталонного. Преимущество генетического алгоритма — его меньшая ресурсоемкость по сравнению с другими алгоритмами.

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

In this paper, a comparative analysis of the exact and heuristic algorithms presented by the method of branches and boundaries, genetic and ant algorithms, respectively, is carried out to find the optimal solution to the traveling salesman problem using the example of a courier robot. The purpose of the work is to determine the running time, the length of the obtained route and the amount of memory required for the program to work, using the method of branches and boundaries and evolutionary heuristic algorithms. Also, the most appropriate of the listed methods for use in the specified conditions is determined. This article uses the materials of the conducted research, implemented in the format of a computer program, the program code for which is implemented in Python. In the course of the study, a number of criteria for the applicability of algorithms were selected (the time of the program, the length of the constructed route and the amount of memory necessary for the program to work), the results of the algorithms were obtained under specified conditions and conclusions were drawn about the degree of expediency of using one or another algorithm in various specified conditions of the courier robot. During the study, it turned out that for a small number of points  $\leqslant10$, the method of branches and boundaries is the most preferable, since it finds the optimal solution faster. However, when calculating the route by this method, provided that the points increase by more than 10, the operating time increases exponentially. In this case, more effective results are obtained by a heuristic approach using a genetic and ant algorithm. At the same time, the ant algorithm is distinguished by solutions that are closest to the reference ones and with an increase of more than 16 points. Its relative disadvantage is the greatest resource intensity among the considered algorithms. The genetic algorithm gives similar results, but after increasing the points more than 16, the length of the found route increases relative to the reference one. The advantage of the genetic algorithm is its lower resource intensity compared to other algorithms.

The practical significance of this article lies in the potential possibility of using the results obtained for the optimal solution of logistics problems by an automated system in various fields: warehouse logistics, transport logistics, «last mile» logistics, etc.

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

The technique for solving the logistic task of fuel supply in the region, including the interconnected tasks of routing, clustering, optimal distribution of resources and stock control is proposed. The calculations have been carried out on the example of fuel supply system of the Udmurt Republic.