Непрерывный алгоритм искусственного роя пчёл для решения задачи размещения объектов без ограничений по мощности

Более умные способы размещения складов

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

Сложность выбора мест

Математическая формулировка задачи размещения складов называется задачей о размещении объектов без ограничений по мощности (uncapacitated facility location problem). Представьте список потенциальных мест, где вы могли бы открыть склады, каждое с фиксированной стоимостью открытия, и карту клиентов, каждому из которых должно быть назначено обслуживание ровно с одного открытого объекта по некоторой стоимости доставки. Цель — решить, какие объекты открыть и каких клиентов к ним прикрепить, чтобы сумма затрат на открытие и доставку была минимальна. Даже для компьютеров число возможных комбинаций взрывообразно растёт с увеличением сети, поэтому нужны хитрые стратегии поиска вместо грубой силы.

Учимся у способов кормёжки пчёл

Алгоритм искусственного роя пчёл (ABC) заимствует идеи из того, как настоящие пчёлы исследуют окружение. В алгоритме каждая «пчела» представляет одно возможное решение. Работающие пчёлы исследуют окрестности своего текущего решения, наблюдающие фокусируются на перспективных вариантах, а разведчики покидают плохие решения и перепрыгивают в новые области. ABC изначально был создан для настройки непрерывных числовых величин, как будто вы двигаете регулятор вверх или вниз. Однако решения в задаче размещения объектов являются по сути бинарными: открыть объект или нет; назначить клиента сюда или в другое место. Классический ABC потому испытывает трудности, если его не обернуть дополнительными механизмами для трансляции плавных чисел в решения типа вкл/выкл.

Преобразование гладкого поиска в устойчивые решения

Авторы предлагают вариант, который они называют непрерывным ABC, или cABC, сохраняющий плавный поиск оригинального метода, но способный естественно обрабатывать бинарные решения. Он позволяет алгоритму перемещаться в непрерывном пространстве от 0 до 1, рассматривая каждое значение как вероятность того, что объект открыт. Простое правило затем преобразует эти значения в чёткие решения «открыт» или «закрыт». Чтобы не начинать с плохого или узкого набора догадок, cABC использует «хаотический» паттерн для широкого разброса начальных решений по пространству поиска. Когда пробное решение предполагает, что вообще ни один объект не открыт, или иным образом нарушает ограничения, динамический процесс восстановления автоматически корректирует несколько его выборов, делая решение работоспособным, не уходя слишком далеко от перспективных областей.

Управляемый рой и адаптивные улучшения

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

Испытание роя пчёл

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

Что это значит для практического планирования

Проще говоря, эта работа даёт более надёжный «вдохновлённый пчёлами» инструмент для принятия решений о размещении складов, заводов или сервисных центров. Позволяя алгоритму думать в терминах плавных вероятностей и затем аккуратно переводить их в бинарные решения — при этом восстанавливая плохие догадки и поддерживая разнообразие — cABC исследует пространство решений и широко, и глубоко. В результате получается инструмент, который может находить более дешёвые схемы и делать это последовательно, что делает его сильным кандидатом для компаний и планировщиков, которым нужно проектировать экономичные распределительные сети в условиях сложной крупномасштабной логистики.

Цитирование: An, M., Xiang, W., Jiang, Y. et al. A continuous artificial bee colony algorithm for solving uncapacitated facility location problems. Sci Rep 16, 8780 (2026). https://doi.org/10.1038/s41598-026-37792-5

Ключевые слова: размещение объектов, роевой интеллект, метаэвристическая оптимизация, планирование логистики, искусственный рой пчёл