РАЗРАБОТКА МЕТОДИКИ ОПТИМИЗАЦИИ МАРШРУТИЗАЦИИ ГОРОДСКИХ ГРУЗОПЕРЕВОЗОК С ПРИМЕНЕНИЕМ ГИБРИДНОГО АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ И МЕТОДА ОТЖИГА

DEVELOPMENT OF A METHODOLOGY FOR OPTIMIZING URBAN FREIGHT ROUTING USING A HYBRID ANT COLONY OPTIMIZATION AND SIMULATED ANNEALING ALGORITHM

Levashova Sofia Andreevna

Student, Technological Institute (branch) of DSTU in Azov, Russia, Azov

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

Abstract. The article discusses the urgent problem of increasing the efficiency of cargo transportation in cities when logistics costs are rising and roads are overloaded. To reduce overall costs, including time and fuel, the author's routing optimization technique is proposed. It is based on combining the ant colony algorithm (ACO) and the annealing method (SA). The ACO has changed the way the pheromone is updated, and the SA uses a criterion that allows you to make decisions on time so as not to fall into the trap of not making the best decisions.

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

Keywords: vehicle routing; urban freight transportation; optimization; ant colony optimization; simulated annealing.

В современных условиях растущей урбанизации и объема электронной коммерции система городских грузоперевозок испытывает значительную нагрузку [1, c. 245]. Неэффективная маршрутизация приводит к росту логистических издержек, увеличению времени доставки, негативному воздействию на экологическую обстановку [2, c. 118]. Задача маршрутизации транспортных средств относится к классу NP-трудных задач, для решения которых традиционные точные методы неэффективны для крупномасштабных практических применений [4, c. 15]. В связи с этим актуальной является разработка новых и модификация существующих метаэвристических алгоритмов, позволяющих находить близкие к оптимальным решения за приемлемое время [5, c. 228]. Целью данного исследования является разработка и верификация гибридного алгоритма, сочетающего достоинства алгоритма муравьиной колонии и метода отжига для решения задачи оптимизации маршрутов городских грузоперевозок.

Формализована математическая модель задачи VRP с целью минимизации общей длины маршрута при соблюдении ограничений на грузоподъемность транспортных средств и временные окна обслуживания клиентов [3, c. 89].

Этап 1 (ACO): Реализован стандартный алгоритм муравьиной колонии для построения начальных маршрутов [5, c. 231]. Внесена модификация в правило локального обновления феромона, которая усиливает "наказание" за неэффективные переходы между точками, что ускоряет сходимость.

Этап 2 (SA): Полученные от ACO решения передаются на вход методу отжига [4, c. 312]. Используется адаптивный критерий принятия худших решений на начальных итерациях, что позволяет алгоритму "выпрыгнуть" из локального оптимума и исследовать более широкую область поиска.

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

Для тестирования методики использованы синтезированные данные, имитирующие реальную сеть доставки в городской среде [3, c. 95].

Проведено сравнительное тестирование гибридного алгоритма (ACO+SA), классического ACO и генетического алгоритма (GA).

Результаты: Гибридный алгоритм показал стабильно лучшие результаты.

Таблица 1.

Вычислительный эксперимент

В ходе проведенного исследования была успешно разработана и протестирована методика оптимизации маршрутов городских грузоперевозок на основе гибридного алгоритма. Подтверждена гипотеза о том, что комбинация ACO и SA позволяет преодолеть ограничения каждого из алгоритмов, используемых по отдельности [5, c. 245].

1. Предложенная гибридная методика демонстрирует на тестовых данных повышение эффективности на 8-12% по сравнению с классическими подходами [4, c. 325].

2. Модификация правила обновления феромона в ACO способствует более быстрому отказу от заведомо неэффективных решений [5, c. 238].

3. Адаптивный критерий в методе отжига эффективно противодействует преждевременной сходимости, обеспечивая более глубокий поиск в пространстве решений [4, c. 318].

Перспективы дальнейших исследований видятся в адаптации разработанной методики для решения динамической задачи VRP (с учетом изменения дорожной обстановки в реальном времени) и учете экологического фактора (минимизация выбросов CO2) [2, c. 156].