Badanie porównawcze ACO, Dijkstry i NN pod kątem efektywności tras w sieciach zbiórki odpadów

Dlaczego ważne są mądrzejsze trasy śmieciarek

Za każdym samochodem wywozowym przejeżdżającym Twoją ulicą kryje się złożona łamigłówka: jak odwiedzić wiele koszy i dzielnic, jednocześnie przejeżdżając możliwie najmniej kilometrów. W miastach produkujących miliardy ton odpadów, przy rosnących kosztach paliwa i emisjach, nawet niewielkie poprawy w planowaniu tras mogą oszczędzić pieniądze, zmniejszyć zanieczyszczenie i odciążyć ruch. Artykuł stawia praktyczne pytanie dla współczesnych miast: spośród trzech popularnych metod wyznaczania tras dla śmieciarek, która rzeczywiście sprawdza się najlepiej, gdy sieci stają się większe i bardziej obciążone?

Trzy sposoby, by znaleźć drogę

Badanie porównuje trzy grupy metod wyznaczania tras, z których każda odzwierciedla inny styl podejmowania decyzji. Pierwsza, nazwana optymalizacją rojem mrówek (ACO), inspirowana jest tym, jak prawdziwe mrówki zostawiają i podążają za ścieżkami feromonowymi: obiecujące trasy są z czasem wzmacniane, podczas gdy słabsze zanikają. Druga, algorytm Dijkstry, to klasyczny przepis matematyczny, który zawsze znajduje najkrótszą ścieżkę w sieci, gdy warunki są stałe i znane. Trzecia, podejście Najbliższego Sąsiada (Nearest Neighbour), imituje szybkie ludzkie zgadywanie: z bieżącej pozycji po prostu idź do najbliższego nieodwiedzonego punktu, a następnie powtórz. Wszystkie trzy zastosowano do tego samego rodzaju abstrakcyjnej mapy miasta, gdzie skrzyżowania i punkty odbioru odpadów reprezentowane są jako węzły połączone drogami o kosztach odzwierciedlających odległość i korki.

Budowanie wirtualnych miast do testów

Zamiast polegać na jednym konkretnym mieście, autorzy konstruują syntetyczne sieci drogowe przypominające typowe układy miejskie. Sieci te są rozproszone — każdy punkt połączony jest tylko z kilkoma innymi — i obejmują zakres rozmiarów od 10 do ponad 50 lokalizacji, aby odzwierciedlić małe dzielnice aż po znaczne obszary miejskie. Odcinki dróg mają „koszty ważone przeciążeniem”, więc bardziej ruchliwe lub dłuższe odcinki są efektywnie droższe w użyciu. Na każdej z tych wirtualnych map trzy algorytmy mają znaleźć ścieżki o niskim koszcie między wybranym punktem startowym i końcowym. Aby porównanie było uczciwe, wszystkie trzy korzystają z tej samej struktury kosztów, a bardziej losowe metody uruchamiane są wielokrotnie, by badacze mogli zmierzyć zarówno ich średnią wydajność, jak i zmienność.

Co ujawniają testy bezpośrednie

Wyniki pokazują wyraźny wzorzec. W małych, średnich i dużych sieciach ACO konsekwentnie znajduje trasy o najniższym średnim koszcie całkowitym. Jego „mrówki” eksplorują, uczą się na podstawie doświadczeń i stopniowo koncentrują się na tańszych ścieżkach, co okazuje się szczególnie cenne w miarę wzrostu sieci i nasilania się różnic w kosztach dróg. Algorytm Dijkstry jest bardzo stabilny: dla tej samej mapy i kosztów zawsze zwraca tę samą trasę, z bardzo małą rozpiętością wyników. Jednak gdy uwzględnione są koszty ważone przeciążeniem i bardziej złożone układy, jego trasy są nieco droższe niż te znalezione przez dobrze dostrojone ACO. Metoda Najbliższego Sąsiada jest najszybsza w działaniu, ale wypada najgorzej: poprzez zawsze dążenie do najbliższego punktu, ma tendencję do pomijania mądrzejszych, długoterminowych skrótów i generuje najdroższe oraz najbardziej niespójne trasy.

Sprawdzanie, czy różnice są istotne

Aby upewnić się, że te różnice w wydajności nie są tylko przypadkowymi odchyleniami, autorzy wykorzystują narzędzie statystyczne znane jako test par Wilcoxona (Wilcoxon signed-rank test). Test ten porównuje sparowane wyniki algorytmów na tych samych instancjach sieci, nie zakładając, że dane mają rozkład normalny. Dla każdego badanych rozmiaru sieci test wskazuje, że oszczędności kosztów uzyskiwane przez ACO w porównaniu z Dijkstrą i Najbliższym Sąsiadem są istotne statystycznie, a nie przypadkowe. Jednocześnie miary rozrzutu pokazują kompromis między stabilnością a elastycznością: ścieżki Dijkstry niemal się nie zmieniają, podczas gdy wyniki ACO nieznacznie przesuwają się z biegu na bieg, gdy metoda eksploruje alternatywy, zanim ustabilizuje się w pobliżu najlepszych tras.

Co to oznacza dla miejskich ulic

Dla zarządców miast przekaz artykułu jest praktyczny i intuicyjny. Jeśli sieć drogowa jest mała, a warunki względnie stabilne, klasyczna metoda najkrótszej ścieżki, taka jak Dijkstra, jest prosta i niezawodna. Gdy sieci są większe, a przeciążenie lub inne koszty zmieniają się w przestrzeni, podejście inspirowane mrówkami może wydobyć zauważalnie tańsze trasy, choć wymaga większego nakładu obliczeniowego w tle. Szybka i prowizoryczna strategia Najbliższego Sąsiada, chociaż kusząca ze względu na szybkość, konsekwentnie pozostawia pieniądze i paliwo na stole. Ogólnie badanie dostarcza sprawdzonego przewodnika: wybieraj metody deterministyczne dla małych, przewidywalnych warunków, a preferuj adaptacyjne, oparte na rojach optymalizacje przy planowaniu opłacalnej i skalowalnej zbiórki odpadów w nowoczesnych, rozwijających się miastach.

Cytowanie: 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

Słowa kluczowe: zbiórka odpadów w mieście, optymalizacja tras, optymalizacja rojem mrówek, algorytmy najkrótszej ścieżki, logistyka inteligentnego miasta