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

Задача маршрутизации

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

Три подхода

МетодКак работаетПлюсыМинусы
Ближайший соседИз текущей точки идут в ближайшую непосещённуюПростой, считается вручнуюПоследние точки могут оказаться далеко
Метод сбереженийБерут отдельные рейсы и объединяют те, что дают наибольшую экономиюХорошо работает для развозки с ограничением по грузоподъёмностиНе учитывает окна без доработки
Муравьиный алгоритмМногократно строит маршруты, усиливая удачные участкиГибок для сложных ограниченийТребует настройки параметров и времени расчёта

Как работает муравьиный алгоритм

  1. На всех участках между точками задают начальное количество феромона.
  2. Каждый «муравей» строит маршрут, выбирая следующую точку с вероятностью, зависящей от длины участка (чем короче, тем лучше) и количества феромона (чем больше, тем лучше).
  3. После прохода всех муравьёв считают длину маршрутов.
  4. Феромон испаряется на всех участках, а на участках лучших маршрутов добавляется.
  5. Повторяют много итераций. Лучший найденный маршрут остаётся ответом.

Параметры: число муравьёв, число итераций, вес феромона, вес расстояния, скорость испарения. От настройки зависят качество и скорость.

Пример на пяти точках

Условный пример. Склад S и четыре адреса A, B, C, D. Расстояния в километрах: S-A 4, S-B 6, S-C 7, S-D 9, A-B 3, A-C 6, A-D 8, B-C 3, B-D 5, C-D 4.

Ближайший сосед: из S маршрут идёт в A (4), затем в B (3), в C (3), в D (4) и возвращается в S (9). Всего 23 км.

Другой порядок: S, A, B, D, C, S: 4 + 3 + 5 + 4 + 7 = 23 км. Порядок S, B, A, C, D, S: 6 + 3 + 6 + 4 + 9 = 28 км. Лучший из рассмотренных вариантов даёт 23 км. На пяти точках оптимум находится перебором всех порядков, муравьиный алгоритм здесь не нужен. На 50 точках перебор невозможен, и приходится применять эвристику. Расходы на пробег можно оценить в калькуляторе стоимости километра.

Когда муравьиный алгоритм оправдан

  • Много точек и сложные ограничения: окна, разные машины, обязательный порядок.
  • Расчёт повторяется ежедневно, и нужна автоматизация.
  • Хотите улучшить результат, который даёт простой метод.
  • Есть данные о реальных расстояниях и времени между точками.

Когда не нужен: 5–10 точек в день, фиксированные маршруты, отсутствие данных о расстояниях.

Что учитывать на практике

  1. Реальные расстояния и время по дорогам вместо прямых линий. Для этого используют картографические сервисы.
  2. Время обслуживания на точке: разгрузка, оформление документов, поиск парковки.
  3. Окна доставки и графики работы получателей.
  4. Режим труда и отдыха водителя: перерыв после 4,5 часа управления, суточный лимит.
  5. Грузоподъёмность и объём кузова: проверьте в калькуляторе паллет в машине.
  6. Платные дороги и дорожные сборы, которые входят в стоимость участка.

Готовые решения

Большинство курьерских служб использует готовые сервисы маршрутизации, в которых внутри работают эвристики разных типов. Обзор такого сервиса смотрите в материале о Яндекс Маршрутизации для курьерских служб, а подробности о сервисе 2ГИС Логистика. Об использовании метода в вашей компании читайте в материале про муравьиную логистику и работу алгоритма. Общие принципы планирования собраны в разделе Основы логистики.

Как сравнить результаты

  1. Возьмите реальный день работы с адресами и временем.
  2. Постройте маршрут вручную диспетчером.
  3. Постройте маршрут методом, который хотите проверить.
  4. Сравните пробег, время, количество машин, соблюдение окон.
  5. Повторите на 5–10 разных днях, чтобы исключить случайность.

Ориентир для оценки: при выигрыше меньше 3–5 % сложный алгоритм вряд ли окупится, при 10 % и выше при ежедневной работе внедрение обычно оправдано.

Частые вопросы

Гарантирует ли муравьиный алгоритм лучший маршрут?

Нет. Он находит хорошее решение за разумное время, но не доказывает, что оно оптимальное.

Почему алгоритм называют муравьиным?

В нём моделируется поведение муравьёв, которые оставляют на пути феромон и тем самым направляют других к кратчайшим дорогам.

Нужен ли такой алгоритм небольшой службе?

Чаще нет. Хватает готового сервиса маршрутизации и ручной корректировки.

Что лучше: сбережений или муравьиный?

Для типичной развозки с грузоподъёмностью метод сбережений достаточно хорош и прост. Муравьиный выигрывает при сложных ограничениях.

Читайте также

Проверено: октябрь 2026. Источники: описания алгоритмов оптимизации (метод ближайшего соседа, метод сбережений Кларка и Райта, алгоритмы муравьиных колоний), ЕСТР.

Раздел: Технологии и сервисы / Маршрутизация и оптимизация доставки

Похожие записи