Муравьиный алгоритм в 1С для поиска оптимального маршрута

26.03.25

Разработка - Математика и алгоритмы

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Муравьиный алгоритм в 1С для поиска оптимального маршрута
.epf 7,07Kb
17
17 Скачать (1 SM) Купить за 1 850 руб.

Внимание, на скриншоте пошаговая инструкция, куда добавлять данные при проверке. На примере добавил 3 города и расстояния между ними. Обработка должна работать в любой базе на платформе 1с v8.3, так как все процедуры и функции свои, тестировалось в 1С:ERP Управление предприятием 2 (2.5.13.82)  

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

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

Основные принципы муравьиного алгоритма:

  • Муравьи: Агенты, которые ищут решение задачи.
  • Феромоны: Информация, которая остается на пути муравьев и влияет на выбор других муравьев.
  • Испарение феромонов: Феромоны со временем испаряются, что позволяет алгоритму “забывать” неоптимальные пути и исследовать новые варианты.
  • Эвристическая информация: Дополнительная информация о задаче, которая помогает муравьям принимать более обоснованные решения (например, расстояние между городами при оптимизации маршрутов).

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

  • Задача коммивояжера (TSP): Поиск кратчайшего маршрута, проходящего через все заданные города по одному разу.
  • Задача маршрутизации транспорта (VRP): Оптимизация маршрутов для нескольких транспортных средств, доставляющих товары клиентам.
  • Задачи планирования и расписания: Оптимизация последовательности выполнения задач, распределение ресурсов и т.д.
  • Задачи кластеризации и классификации: Группировка данных по определенным признакам.

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

Для реализации муравьиного алгоритма в 1С необходимо:

  1. Представить задачу в виде графа: Города или точки доставки – это вершины графа, а расстояния между ними – ребра графа.
  2. Создать структуру для хранения информации о феромонах: В 1С можно использовать структуру или соответствие для хранения информации о количестве феромонов на каждом ребре графа.
  3. Реализовать функции для:
    • Построения маршрута муравья: Функция должна выбирать следующий город для посещения на основе информации о феромонах и эвристической информации (расстоянии).
    • Расчета длины маршрута: Функция должна вычислять общую длину маршрута, пройденного муравьем.
    • Обновления феромонов: Функция должна изменять количество феромонов на ребрах графа в зависимости от качества маршрутов, пройденных муравьями.
  4. Запустить алгоритм на определенное количество итераций: На каждой итерации муравьи строят новые маршруты, обновляют феромоны, и алгоритм сходится к оптимальному решению.
&НаСервере
Функция ПостроитьМаршрутМуравья(Города, МатрицаРасстояний, Альфа, Бета)

    Маршрут = Новый Массив();
    НепосещенныеГорода = Новый Массив();
    Для Каждого Город Из Города Цикл
        НепосещенныеГорода.Добавить(Город);
    КонецЦикла;

    // Выбираем начальный город случайным образом
    ГСЧ = Новый ГенераторСлучайныхЧисел();
    ИндексНачальногоГорода = Цел(ГСЧ.СлучайноеЧисло(0, НепосещенныеГорода.Количество() - 1));
    НачальныйГород = НепосещенныеГорода[ИндексНачальногоГорода];
    Маршрут.Добавить(НачальныйГород);
    НепосещенныеГорода.Удалить(ИндексНачальногоГорода);

    // Строим маршрут, пока есть непосещенные города
    Пока НепосещенныеГорода.Количество() > 0 Цикл
        СледующийГород = ВыбратьСледующийГород(Маршрут[Маршрут.Количество() - 1], НепосещенныеГорода, МатрицаРасстояний, Альфа, Бета);
        Маршрут.Добавить(СледующийГород);
        НепосещенныеГорода.Удалить(НепосещенныеГорода.Найти(СледующийГород));
    КонецЦикла;

    Возврат Маршрут;

КонецФункции

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

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

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

&НаСервере
Функция ВыбратьСледующийГород(ТекущийГород, НепосещенныеГорода, МатрицаРасстояний, Альфа, Бета)

    // Выбираем следующий город с учетом расстояния
    ЛучшийГород = "";
    ЛучшееРасстояние = -1;

    Для Каждого Город Из НепосещенныеГорода Цикл
        Ключ = ТекущийГород + "_" + Город;
        Расстояние = МатрицаРасстояний[Ключ];

        Если ЛучшийГород = "" ИЛИ Расстояние < ЛучшееРасстояние Тогда
            ЛучшийГород = Город;
            ЛучшееРасстояние = Расстояние;
        КонецЕсли;
    КонецЦикла;

    Возврат ЛучшийГород;

КонецФункции

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

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

&НаСервере
Функция РассчитатьДлинуМаршрута(Маршрут, МатрицаРасстояний)

    Длина = 0;
    Для Индекс = 1 По Маршрут.Количество() - 1 Цикл
        Город1 = Маршрут[Индекс - 1];
        Город2 = Маршрут[Индекс];
        Ключ = Город1 + "_" + Город2;
        Длина = Длина + МатрицаРасстояний[Ключ];
    КонецЦикла;

    Возврат Длина;

КонецФункции 

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

Функция ЗапуститьМуравьиныйАлгоритм является основной функцией, которая координирует работу всех остальных функций и реализует логику муравьиного алгоритма:

&НаСервере
Функция ЗапуститьМуравьиныйАлгоритм(Города, МатрицаРасстояний, КоличествоМуравьев, КоличествоИтераций, Альфа, Бета)

    // 1. Инициализация
    ЛучшийМаршрут = "";
    ЛучшаяДлина = 0;

    // 2. Основной цикл алгоритма
    Для Итерация = 1 По КоличествоИтераций Цикл

        // a) Создаем муравьев и строим их маршруты
        МаршрутыМуравьев = Новый Массив();
        Для Муравей = 1 По КоличествоМуравьев Цикл
            Маршрут = ПостроитьМаршрутМуравья(Города, МатрицаРасстояний, Альфа, Бета);
            МаршрутыМуравьев.Добавить(Маршрут);
        КонецЦикла;

        // b) Оцениваем маршруты муравьев и выбираем лучший
        Для Каждого Маршрут Из МаршрутыМуравьев Цикл
            ДлинаМаршрута = РассчитатьДлинуМаршрута(Маршрут, МатрицаРасстояний);

            Если ЛучшийМаршрут = "" ИЛИ ДлинаМаршрута < ЛучшаяДлина Тогда
                ЛучшийМаршрут = СтрСоединить(Маршрут, " -> ");
                ЛучшаяДлина = ДлинаМаршрута;
            КонецЕсли;
        КонецЦикла;

        // (В этой упрощенной версии мы не обновляем феромоны)

    КонецЦикла;

    // 3. Возвращаем результаты
    Результаты = Новый Структура("Маршрут, Длина", ЛучшийМаршрут, ЛучшаяДлина);
    Возврат Результаты;

КонецФункции

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

Основные данные для алгоритма вызовем при создании обработки:

&НаСервере
Процедура ЗапуститьАлгоритмНаСервере()
	// 1. Задаем параметры алгоритма (программно)
    КоличествоМуравьев = 10;
    КоличествоИтераций = 100;
    Альфа = 1;
    Бета = 2;

    // 2. Создаем список городов (программно)
    Города = Новый Массив();
    Города.Добавить("Город1");
    Города.Добавить("Город2");
    Города.Добавить("Город3");

    // 3. Создаем матрицу расстояний (программно)
    // (Заполните матрицу расстояний своими значениями)
    МатрицаРасстояний = Новый Соответствие();
    МатрицаРасстояний.Вставить("Город1_Город2", 10);
    МатрицаРасстояний.Вставить("Город1_Город3", 15);
    МатрицаРасстояний.Вставить("Город2_Город1", 10);
    МатрицаРасстояний.Вставить("Город2_Город3", 8);
    МатрицаРасстояний.Вставить("Город3_Город1", 15);
    МатрицаРасстояний.Вставить("Город3_Город2", 8);

    // 4. Запускаем алгоритм
    Результаты = ЗапуститьМуравьиныйАлгоритм(Города, МатрицаРасстояний, КоличествоМуравьев, КоличествоИтераций, Альфа, Бета);

    // 5. Выводим результаты в окно сообщений
    Сообщить("Лучший маршрут: " + Результаты.Маршрут);
    Сообщить("Длина маршрута: " + Результаты.Длина);
КонецПроцедуры

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

  • Реализовать обновление феромонов: Добавить логику для изменения количества феромонов на ребрах графа в зависимости от качества маршрутов, пройденных муравьями. Это позволит алгоритму сходиться к более оптимальным решениям.
  • Учитывать эвристическую информацию: В функции ВыбратьСледующийГород учитывать не только расстояние до следующего города, но и другие факторы, такие как стоимость доставки, время в пути и т.д.
  • Использовать более сложные стратегии выбора следующего города: Вместо простого выбора города с минимальным расстоянием можно использовать вероятностные методы выбора, учитывающие как феромоны, так и эвристическую информацию.
  • Настроить параметры алгоритма: Подобрать оптимальные значения параметров Альфа, Бета, КоличествоМуравьев, КоличествоИтераций для конкретной задачи.

Примеры практического применения муравьиного алгоритма в 1С:

  • Оптимизация маршрутов курьеров: Алгоритм может помочь курьерской службе оптимально распределить заказы между курьерами и построить для них наиболее короткие маршруты, чтобы сократить время доставки и снизить затраты на топливо.
  • Планирование посещений торговых представителей: Алгоритм может помочь торговым представителям оптимально спланировать свои визиты к клиентам, чтобы максимизировать количество посещений и увеличить объем продаж.
  • Оптимизация маршрутов сервисных инженеров: Алгоритм может помочь сервисным компаниям оптимально распределить заявки между инженерами и построить для них наиболее короткие маршруты, чтобы сократить время реагирования на заявки и повысить уровень обслуживания клиентов.
  • Оптимизация логистики на складе: Алгоритм может помочь оптимизировать перемещение товаров по складу, минимизируя расстояния и время на выполнение операций.

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

Проверено на следующих конфигурациях и релизах:

  • 1С:ERP Управление предприятием 2, релизы 2.5.17.101

Обработка. Муравьиный алгоритм. Анализ. Планирование

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 1C:Бухгалтерия Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    6350    stopa85    12    

39

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    11910    user1959478    56    

37

Математика и алгоритмы Разное Платформа 1С v8.3 1C:Бухгалтерия Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    6141    maksa2005    8    

26

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    14306    8    SpaceOfMyHead    20    

63

Математика и алгоритмы Программист Платформа 1С v8.3 1C:Бухгалтерия Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    7399    RustIG    9    

28

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    6553    gzharkoj    14    

25

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    9750    7    kalyaka    11    

45
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. RustIG 1845 26.03.25 18:15 Сейчас в теме
Очередное спасибо за освещение и поднятие подобных тем!
2. booksfill 27.03.25 09:55 Сейчас в теме
По-моему, очень интересно. Спасибо!

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

Интересней всего:
- "Добавить логику для изменения количества феромонов на ребрах графа в зависимости от качества маршрутов, пройденных муравьями. "

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

- Время работы алгоритма на реальных данных, скажем, 10 точек и 100 точек. С авторской оценкой критерия прерывания алгоритма.
Это важно, т.к. в реальной жизни эвристика может меняться в пределах нескольких часов - разный трафик, время разрешенное для проезда фур и т.п.
Кстати, к вопросу полезности ферромонов - не успеют они выветрится, как разошлем муравьев не теми маршрутами.
3. user1195929 57 27.03.25 10:29 Сейчас в теме
(2) Да. Добрый день. Добавлю всё, но чуть позже. Для статьи и начинающих пользователей этой информации достаточно к написанию кода и тестированию. Сделано максимально просто. Все те вопросы, которые Вы озвучили уже реализуются в моей новой обработке (появиться на инфостарте позже, но уже за стартмани, так как с теми вводными и результирующими данными (Вами озвученными) - это уже готовый продукт для организаций по поиску маршрутов). Советую посмотреть другие мои статьи по маршрутам, они так же сделаны просто, после создам итоговую статью о том как хочу их применить
Оставьте свое сообщение