Étude comparative de l’ACO, de Dijkstra et du NN sur l’efficacité des itinéraires dans les réseaux de collecte des déchets

Pourquoi des itinéraires de collecte plus intelligents comptent

Derrière chaque camion poubelle qui passe dans votre rue se cache un casse-tête complexe : comment visiter de nombreuses poubelles et quartiers tout en parcourant le moins de distance possible. Avec des villes générant des milliards de tonnes de déchets et des coûts de carburant et des émissions en hausse, même de petites améliorations de l’itinéraire peuvent économiser de l’argent, réduire la pollution et alléger le trafic. Cet article pose une question pratique pour les villes modernes : parmi trois méthodes courantes pour calculer les itinéraires des camions de collecte, laquelle fonctionne réellement le mieux lorsque les réseaux deviennent plus grands et plus chargés ?

Trois manières de trouver un chemin

L’étude compare trois familles de méthodes de routage, chacune reflétant un style différent de prise de décision. La première, appelée optimisation par colonie de fourmis (ACO), s’inspire de la façon dont de vraies fourmis déposent et suivent des pistes de phéromones : les chemins prometteurs se renforcent avec le temps, tandis que les autres s’estompent. La seconde, l’algorithme de Dijkstra, est une recette mathématique classique qui trouve toujours le plus court chemin dans un réseau lorsque les conditions sont fixes et connues. La troisième, l’approche du plus proche voisin (Nearest Neighbour), imite une estimation humaine rapide : depuis votre position actuelle, allez simplement vers le point non visité le plus proche, puis recommencez. Les trois sont appliquées au même type de carte urbaine abstraite, où les intersections et les points de collecte sont représentés par des nœuds reliés par des routes dont les coûts reflètent la distance et la congestion.

Construire des villes virtuelles pour tester les idées

Plutôt que de s’appuyer sur une ville particulière, les auteurs construisent des réseaux routiers synthétiques qui ressemblent aux configurations urbaines typiques. Ces réseaux sont peu denses, chaque point étant connecté à seulement quelques autres, et couvrent une gamme de tailles de 10 jusqu’à plus de 50 emplacements pour mimer des petits quartiers jusqu’à des zones urbaines étendues. Les segments de route portent des coûts « pondérés par la congestion », de sorte que les routes plus fréquentées ou plus longues sont effectivement plus coûteuses à emprunter. Sur chacune de ces cartes virtuelles, les trois algorithmes doivent trouver des trajets à faible coût entre un point de départ et un point d’arrivée choisis. Pour maintenir une comparaison équitable, tous utilisent la même structure de coûts sous-jacente, et les méthodes plus aléatoires sont lancées de nombreuses fois afin que les chercheurs puissent mesurer à la fois leur performance moyenne et leur variabilité.

Ce que révèlent les confrontations

Les résultats montrent un schéma clair. Sur les réseaux petits, moyens et grands, l’ACO découvre systématiquement des itinéraires avec le coût total moyen le plus bas. Ses « fourmis » errent, apprennent de l’expérience et se concentrent progressivement sur des chemins moins chers, ce qui s’avère particulièrement utile à mesure que les réseaux grandissent et que les coûts routiers deviennent plus inégaux. L’algorithme de Dijkstra est extrêmement stable : donné la même carte et les mêmes coûts, il retourne toujours le même chemin, avec très peu de dispersion des résultats. Cependant, lorsque l’on prend en compte des coûts pondérés par la congestion et des configurations plus complexes, ses itinéraires sont légèrement plus coûteux que ceux trouvés par une ACO bien réglée. La méthode du plus proche voisin est la plus rapide à exécuter mais donne les pires résultats : en poursuivant toujours le point le plus proche suivant, elle a tendance à négliger des raccourcis plus astucieux à long terme et produit les itinéraires les plus chers et les plus incohérents.

Vérifier que les différences sont réelles

Pour s’assurer que ces écarts de performance ne sont pas de simples coups de chance dus à la variabilité aléatoire, les auteurs utilisent un outil statistique connu sous le nom de test des rangs signés de Wilcoxon. Ce test compare des résultats appariés des algorithmes sur les mêmes instances de réseau sans supposer que les données suivent une courbe en cloche. Pour chaque taille de réseau étudiée, le test indique que les économies de coût de l’ACO par rapport à Dijkstra et au plus proche voisin sont statistiquement significatives et non accidentelles. Parallèlement, les mesures de dispersion montrent le compromis entre stabilité et flexibilité : les chemins de Dijkstra varient à peine, tandis que les résultats de l’ACO fluctuent légèrement d’une exécution à l’autre lorsqu’elle explore des alternatives avant de se concentrer autour des meilleures routes.

Ce que cela signifie pour les rues de la ville

Pour les gestionnaires urbains, le message de l’article est à la fois pratique et intuitif. Si le réseau routier est réduit et que les conditions sont assez stables, une méthode classique de plus court chemin comme Dijkstra est simple et fiable. Lorsque les réseaux sont plus vastes et que la congestion ou d’autres coûts varient dans l’espace, une approche inspirée des fourmis peut obtenir des itinéraires sensiblement moins chers, même si elle demande plus de puissance de calcul en coulisses. La stratégie rapide et approximative du plus proche voisin, bien que séduisante par sa rapidité, laisse systématiquement de l’argent et du carburant sur la table. Globalement, l’étude fournit un guide éprouvé : choisissez des méthodes déterministes pour des contextes petits et prévisibles, mais privilégiez l’optimisation adaptative et basée sur l’essaim pour planifier une collecte des déchets rentable et évolutive dans des villes modernes en croissance.

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

Mots-clés: collecte des déchets urbains, optimisation des itinéraires, optimisation par colonie de fourmis, algorithmes du plus court chemin, logistique de ville intelligente