Сравнительный анализ метаэвристических алгоритмов для задачи маршрутизации транспорта с ограничениями

eISSN 2311-2468 Обзорная статья / Review article

EDN:

Национальный исследовательский Мордовский государственный университет,

Задача маршрутизации транспортных средств (Vehicle Routing Problem, VRP) является одной из основных проблем в сфере современной транспортной логистики1. В классическом виде она заключается в том, чтобы найти самый выгодный способ объезда цепочки клиентов силами имеющегося автопарка. Главная задача оптимизации, как правило, сводится к минимизации общих логистических затрат: сокращения суммарного пробега машин, уменьшение расхода топлива или минимизация количества задействованных автомобилей.

Сложность VRP заключается в том, что она относится к классу NP-трудных задач комбинаторной оптимизации, то есть с ростом количества точек доставки число возможных вариантов их обхода растет лавинообразно [1]. Если для 5–6 клиентов оптимальный путь еще можно найти обычным перебором, то для реальных логистических задач на 15 и более точек точный расчет занимает слишком много времени.

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

– грузоподъемность – у каждого транспортного средства есть фиксированный максимальный вес груза, поэтому суммарный объем заказов на одном маршруте не должен превышать эту емкость;

– лимит доступного автопарка – количество машин, доступных для выполнения заказов, строго ограничено, следовательно, алгоритм должен распределить точки по маршруту так, чтобы уложиться в заданное число машин;

– обязательное покрытие всех точек, при котором алгоритм обязан построить маршруты так, чтобы все точки из заданного списка были обслужены; пропуск или дублирование визитов не допускаются.

Цель исследования – выполнение сравнительного анализа эффективности метаэври-стических подходов к решению задачи маршрутизации транспорта с ограничениями для определения наиболее оптимальных сценариев их применения.

ОБЗОР ЛИТЕРАТУРЫ

Многообразие реальных логистических сценариев привело к появлению многочисленных вариаций VRP. Некоторые исследователи предлагают систематические классификации этих вариантов, другие – классифицируют различные типы задач маршрутизации, основываясь на их ограничениях2 [2; 3]. Среди наиболее изученных вариантов – задачи с временными окнами, многодеповые системы, двухуровневые маршруты, а также задачи с погрузкой и доставкой.

Из-за вычислительной сложности VRP основным инструментом решения стали метаэвристические методы, анализ популярных разновидностей, включая генетический и алгоритм муравьиной колонии использовались в исследовании [4]. Генетический алгоритм ( Genetic Algorithm , GA ), моделирующий механизмы естественного отбора для случайного подбора и вариации искомых параметров, демонстрирует высокую эффективность благодаря работе с целой популяцией решений и способности к глобальному исследованию пространства поиска [5]. Алгоритм муравьиной колонии ( Ant Colony

• 2    Lazarova K.L., Stojkovik N., Stojanova A.I., Bande M.C. Metaheuristics Methods for Solving Capacity Vehicle Routing Problem: An Overview. XV International Conference on Information Technology and Development of Education ITRO. Zrenjanin : Technical Faculty “Mihajlo Pupin”, 2024. P. 72–78. https://www.tfzr.uns.ac.rs/itro/ Zbornik%20ITRO%202024.pdf

356 Технические науки

Optimization , АСО ) основан на поведенческих инструментах децентрализованной самоорганизующейся колонии и так же часто применяется для решения задач VRP и других комбинаторных задач оптимизации.

В настоящее время исследования все чаще отходят от использования алгоритмов в их чистом виде в пользу гибридных подходов, комбинирующих сильные стороны обоих методов. Так, в работе показано, что гибридная модель ACO-GA для задачи с временными окнами и разнородным парком демонстрирует значительное улучшение значений целевой функции по сравнению с отдельным ACO на всех размерах наборов данных3. Гибридизация может заключаться не только в последовательном применении операторов, но и в более глубокой интеграции, например, в учете генетической информации агентом муравьиного алгоритма при принятии решения о выборе пути [6].

Современные тенденции в области решения VRP также характеризуются учетом экологических факторов, в частности, появляются варианты задачи, в которых одним из критериев решения является минимизация выбросов [7]. В этом контексте активно развиваются подходы, объединяющие GA и ACO с методами машинного обучения для улучшения инициализации, адаптивного выбора операторов и повышения эффективности в динамических условиях реального мира. Таким образом, эволюция методов решения VRP идет по пути создания все более сложных систем, где генетические и муравьиные алгоритмы играют центральную роль.

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

МАТЕРИАЛЫ И МЕТОДЫ

В качестве базового алгоритма, с работой которого сравниваются метаэвристические алгоритмы используется жадный алгоритм [8]. Его концепция строится на пошаговом поиске локально оптимального решения. Для математического описания процесса вводится граф G = ( V , E ), V = {0,1,…, n }, базовыми элементами которого являются вершины, обозначающие координаты клиентов и центрального склада (депо), а также ребра { d_ij }, характеризующие расстояния между ними. Каждому клиенту i присваивается определенная величина спроса q_i – вес груза, который необходимо доставить. Вместимость машин обозначена через Q .

Непосещенные клиенты образуют множество U = {1,…, n }. Расчет всегда начинается из центрального депо cur = 0. Выбирается первая доступная фура из автопарка, ее текущая загрузка load приравнивается к нулю, а сама она помещается в стартовую координату графа. Из текущей точки алгоритм просматривает непосещенные вершины графа и находит среди них ближайшую

j^* =arg m _{j ∈} i _U n d cur , j ^.

Перед тем как направить туда автомобиль, система выполняет проверку жесткого ограничения по грузоподъемности. Если вес заказа нового клиента вместе с уже загруженным

• ³    Metaheuristic and Reinforcement Learning Techniques for Solving the Vehicle Routing Problem: A Literature Review [Online]. Journal of Traffic and Transportation Engineering (English Edition) : site. URL: https://jtte.chd.edu.cn/article/ id/2d453e1a-80c9-4d0f-b3cf-9ac04842281c (acsessed: 13.08.2026).

Technical sciences 357

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

load +q ≤ Q .

j

После успешной проверки точка j * добавляется в текущий маршрут, баланс свободного места в фуре уменьшается на величину заказа клиента load = load +q_j * , множество непосещенных клиентов обновляется U = U \ { j *}. Текущее положение машины обновляется cur = j * и поиск следующего ближайшего соседа пойдет уже из этой новой координаты. Процесс циклически повторяется до тех пор, пока абсолютно все клиенты на графе не будут обслужены, т.е. U = 0 .

В отличие от жадного алгоритма, генетический алгоритм оперирует популяцией P = { x ₁,…, x_N } альтернативных решений (особей) одновременно [9].

Для успешного применения генетического алгоритма к задачам VRP ключевое значение имеет кодирование данных и последовательное выполнение основных эволюционных этапов. Каждое решение (маршрут для всех доступных фур) кодируется в виде «хромосомы», которая представляет собой перестановку чисел – номеров точек доставки. Декодирование в маршруты для VRP выполняется динамически с учетом грузоподъемности. Начальная популяция создается случайным образом, однако для повышения эффективности системы в нее может внедряться базовое решение, полученное с помощью жадного алгоритма.

Каждая особь в популяции должна быть оценена с точки зрения ее качества. В данной работе оценивается общая длина маршрутов L и нарушение ограничений по числу машин. Если требуемое число машин m превышает доступный парк M , вводится штраф

F(x) = L ( x )(1 + а • max ( Qm^M )),

M где α – подбираемый коэффициент штрафа. Чем меньше F(x), тем выше приспособленность.

Случайно выбирается турнирная группа размера k , из которой побеждает особь с минимальным F. Процесс повторяется для выбора двух родителей. Такой подход позволяет сохранять высокое генетическое разнообразие и не дает алгоритму слишком быстро зациклиться на одном решении.

Классическое скрещивание, применяемое в стандартных генетических алгоритмах, не подходит для задач маршрутизации, так как оно может привести к дублированию одних точек и пропуску других. Для решения этой проблемы используется специализированный оператор OX. Из родителя P ₁ случайным образом копируется непрерывный блок точек доставки и переносится на те же позиции в хромосому потомка. Остальные позиции заполняются элементами P ₂, в порядке их появления, исключая уже взятые. Это гарантирует, что все клиенты будут посещены ровно по одному разу.

Чтобы алгоритм не застревал в локальных оптимумах, к полученным потомкам с вероятностью Pm применяется оператор мутации. В классических адаптивных GA вероятность мутации обычно привязывают к значению функции приспособленности или к разнообразию популяции. В работе представлен модифицированный механизм адаптивной мутации, зависящий от степени нарушения жесткого ограничения. Уровень недопустимости потомка r усредняется на основе показателей его родителей m -M r=

.

.

M

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

P m = P min + ( P max "  P min ) ' r , n swap =1 + [ r ’ ( L max “ ¹ ) ] ■

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

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

Алгоритм муравьиной колонии принадлежит к классу алгоритмов роевого интеллекта⁴. В контексте задачи VRP роль среды выполняет граф дорог, а средством обмена информацией служат виртуальные следы феромона, откладываемые алгоритмом на ребрах графа. Логика работы алгоритма строится на циклическом повторении следующих взаимосвязанных процессов. На каждой итерации t алгоритма колония из m муравьев строит маршруты из депо, последовательно выбирая следующего клиента. Вероятность перехода из i в j для муравья k определяется правилом:

p ik ( t )=

h ( t ) ] “ n Ы

I p

E i . J * . ( t ) ] “ -b ] ^p'

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

T At+1) = (1 -р)т At )+лт j где ре(0,1)- коэффициент испарения. Величина добавки Лтj суммируется по всем муравьям, прошедшим ребро (i,j), и пропорциональна качеству их маршрутов mQ

Ат ij = S / к=1 Lk если ребро использовано муравьем k, либо только для лучшего маршрута (элитная стратегия). Здесь Lk – общая длина маршрута муравья k, Q – константа. Испарение предотвращает преждевременную сходимость, а подкрепление направляет поиск к глобальному оптимуму [10].

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

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

• 1.    Сценарий «Подмосковье» – малая базовая задача, включающая 6 точек доставки и лимит в 2 фуры с максимальной вместимостью каждой в 100 единиц.

• 2.    Сценарий «Урал» – задача низкой сложности, состоящая из 8 клиентов и 2 доступных транспортных средств с повышенной грузоподъемностью до 240 единиц. Сценарий предназначен для оценки поведения локальных эвристик при небольшом увеличении плотности распределения точек и веса заказов.

• 3.    Сценарий «Поволжье» – тест средней сложности, содержащий 10 географических точек и ограничение в 3 фуры емкостью 130 единиц. Суммарный спрос всех клиентов равен 365, что вплотную приближается к максимальному пределу автопарка, создавая жесткие условия для балансировки.

• 4.    Сценарий «Сибирь» – высокоразмерная задача, включающая 12 клиентов и 3 фуры с лимитом грузоподъемности 175. Сценарий характеризуется большими расстояниями между точками, что позволяет наглядно увидеть стратегические ошибки жадного выбора и оценить качество работы глобальных эволюционных механизмов.

• 5.    «Большой тест» – максимальный по сложности комбинированный сценарий, состоящий из 15 точек доставки на юге России и лимита в 4 фуры емкостью 180 единиц. Данный тест важен для проверки алгоритмов на масштабируемость, скорость сходимости и стабильность результатов при поиске глобального оптимума в условиях жестких ограничений.

Оценка работы рассмотренных алгоритмов производилась по трем критериям: общая длина построенных маршрутов (дистанция), время выполнения расчета и корректность соблюдения всех логистических ограничений (реализуемость) [11]. Ограничения подобраны таким образом, чтобы исключить возможность обслуживания клиентов одной машиной. Это гарантирует, что алгоритмам в любом случае придется распределять граф на несколько независимых оптимальных маршрутов, строго контролируя лимиты вместимости автопарка.

РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

Результаты тестирования алгоритмов представлены в таблице.

Таблица. Результаты вычислительных экспериментов

Table. Results of computational experiments

Сценарий / Script	Дистанция / Distance			Время, мс / Time, mc			Реализуемость / Feasibility
	Жадный алгоритм / Greedy algorithm	ACO	GA	Жадный алгоритм / Greedy algorithm	ACO	GA	Жадный алгоритм / Greedy algorithm	ACO	GA
«Подмосковье» / “Podmoskovye”	90,990	89,330	89,330	0,029	6,129	12,540	Нет / No	Да / Yes	Да / Yes
«Урал» / “Ural”	185,700	206,030	206,030	0,014	7,171	9,328	Нет / No	Да / Yes	Да / Yes
«Поволжье» / “Volga area”	322,930	265,780	265,780	0,003	11,675	13,881	Да / Yes	Да / Yes	Да / Yes
«Сибирь» / “Siberia”	516,910	484,730	484,730	0,002	13,327	12,310	Да / Yes	Да / Yes	Да / Yes
«Большой тест» / “Big test”	349,710	327,680	321,010	0,002	18,612	14,188	Да / Yes	Да / Yes	Да / Yes

Источник : таблица составлена авторами по результатам исследования.

Source : the table was prepared by the authors based on the results of the study.

Отметим, что для сценария «Подмосковье» метаэвристические методы показали идентичный наилучший результат по качеству оптимизации, обнаружив маршрут длиной 89,330 единиц. При этом жадный алгоритм не справился с задачей: из-за локального выбора он сформировал недопустимое решение с дистанцией 90,990 с нарушением жестких ограничений по вместимости транспорта. Муравьиный алгоритм справился с расчетом почти в два раза быстрее генетического (6,129 мс против 12,540 мс).

Для сценария «Поволжье» все три алгоритма смогли построить корректные и реализуемые маршруты. Локальный поиск «ближайшего соседа» выдал наихудший результат по качеству (дистанция 322,930), в то время как генетический и муравьиный алгоритмы сошлись к одинаковому оптимальному значению длины пути – 265,780. Время работы ACO составило 11,675 мс, а генетического алгоритма – 13,881 мс.

В сценарии «Урал» жадный алгоритм вновь продемонстрировал нестабильность, выдав ошибку нарушения ограничений грузоподъемности. Генетический и муравьиный алгоритмы успешно распределили веса грузов по машинам, показав одинаковую итоговую дистанцию (206,030). Метод ACO вновь оказался несколько быстрее эволюционного подхода, завершив вычисления за 7,171 мс.

С ростом масштаба графа и расстояний между клиентами жадный алгоритм смог найти реализуемое решение, но его качество оказалось крайне низким (дистанция 516,910). В сценарии «Сибирь» метаэвристики продемонстрировали высокую стабильность, синхронно найдя более выгодный маршрут с длиной 484,730. На этой задаче генетический алгоритм впервые опередил ACO по скорости вычислений (12,310 мс против 13,327 мс).

На самом сложном комбинированном сценарии проявилось важное преимущество эволюционного подхода. Генетический алгоритм стал абсолютным лидером, найдя самый короткий маршрут длиной 321,010 за 14,188 мс. Алгоритм муравьиной колонии уступил ему как по качеству (дистанция 327,680), так и по времени выполнения, продемонстрировав худшую скорость работы (18,612 мс) из-за высокой вычислительной сложности обновления матрицы феромонов на большом графе.

ОБСУЖДЕНИЕ

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

Алгоритм муравьиной колонии продемонстрировал отличную скорость на малых и средних графах, но показал склонность к замедлению и застреванию в локальных опти-мумах на больших объемах данных. Суммарное время расчетов составило 57 мс, а общая дистанция – 1373,550.

Генетический алгоритм с адаптивной мутацией продемонстрировал наилучший баланс скорости и качества, обеспечив 100 % реализуемость и минимальную суммарную дистанцию во всех 5 тестовых конфигурациях, что согласуется с превосходством модифицированных эволюционных алгоритмов над классическими метаэвристиками [4; 5]. Полученные результаты подтверждают целесообразность его применения в крупномасштабных задачах с жесткими ограничениями.

Синтетические сценарии имитируют реальные логистические условия, однако не охватывают все разнообразие дорожной сети, сезонности спроса и динамических возмущений. Кроме того, дизайн исследования имеет статическую постановку. Данные ограничения задают направления дальнейших исследований: расширение набора данных, включение динамики и учет многокритериальности.

ЗАКЛЮЧЕНИЕ

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