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

Почему важны более разумные маршруты для вывоза мусора

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

Три подхода к поиску пути

Исследование сравнивает три семейства методов маршрутизации, каждое отражает свой стиль принятия решений. Первый, называемый оптимизацией муравьиной колонии (ACO), вдохновлён тем, как настоящие муравьи оставляют и следуют феромонным тропам: перспективные пути со временем упрочняются, а слабые — угасают. Второй, алгоритм Дейкстры, — классический математический рецепт, который всегда находит кратчайший путь в сети, когда условия фиксированы и известны. Третий, подход ближайшего соседа (Nearest Neighbour), имитирует быструю человеческую догадку: из текущего положения идите к ближайшей непосещённой точке и повторяйте. Все три применяются к одному и тому же абстрактному карте города, где перекрёстки и точки сбора отходов представлены узлами, соединёнными дорогами с затратами, отражающими расстояние и загруженность.

Построение виртуальных городов для тестирования идей

Вместо опоры на один конкретный город авторы строят синтетические дорожные сети, напоминающие типичные городские планировки. Эти сети разрежены: каждая точка связана лишь с несколькими другими, и включают диапазон размеров — от 10 до более чем 50 локаций, чтобы имитировать маленькие районы и крупные городские зоны. У дорожных сегментов есть «веса с учётом загруженности», поэтому более загруженные или длинные дороги фактически дороже в использовании. На каждой из этих виртуальных карт трём алгоритмам даётся задача найти низкозатратные пути между выбранной начальной и конечной точками. Чтобы сравнение было честным, все используют одну и ту же базовую структуру затрат, а более стохастические методы прогоняются многократно, чтобы исследователи могли измерить и среднюю производительность, и изменчивость результатов.

Что показали очные испытания

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

Проверка статистической значимости различий

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

Что это означает для городских улиц

Для городских менеджеров вывод статьи одновременно практичен и интуитивно понятен. Если дорожная сеть невелика и условия относительно стабильны, классический метод кратчайшего пути, такой как Дейкстра, прост и надёжен. Когда сети крупнее и загруженность или другие затраты меняются в пространстве, подход, вдохновлённый муравьями, может обеспечить заметно более дешёвые маршруты, хотя за этим стоит большая вычислительная работа. Быстрый и грубый метод ближайшего соседа, хотя и привлекателен своей скоростью, постоянно оставляет деньги и топливо на столе. В целом исследование даёт проверенное руководство: выбирайте детерминированные методы для небольших предсказуемых условий, а при планировании эффективного и масштабируемого вывоза отходов в современных растущих городах отдавайте предпочтение адаптивной оптимизации на основе роя агентов (swarm-based).

Цитирование: Anitha, R., Parthiban, A. Comparative study of ACO, dijkstra, and NN for routing efficiency in waste collection networks. Sci Rep 16, 13346 (2026). https://doi.org/10.1038/s41598-026-42866-5

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