
Coordination par relais pour la collecte et livraison multi-robots économe en énergie
Une équipe de chercheurs a publié sur arXiv (identifiant 2509.14127, version 2, septembre 2025) un cadre de planification baptisé VCST-RCP (Voronoi-Constrained Steiner Tree Relay Coordination Planning), conçu pour coordonner des flottes homogènes de robots mobiles dans des missions de livraison multi-colis depuis un dépôt unique vers des destinations dispersées. L'algorithme opère en deux phases: la construction d'un réseau de relais sparse combinant des interfaces d'échange dérivées de diagrammes de Voronoï à une optimisation par arbre de Steiner, puis la génération des plannings de collecte, relais et livraison sous contraintes de capacité de charge et de temps de service. Sur des expériences menées à plusieurs échelles, VCST-RCP réduit la distance totale parcourue par la flotte de 31% en moyenne, avec des pics proches de 50%, par rapport à l'algorithme d'affectation Hungarian assignment, et surpasse significativement OR-Tools CVRP, le solveur de référence de Google. La significativité statistique est établie à p inférieur à 10^-3, et le gain d'efficacité de livraison, mesuré en colis par kilomètre parcouru, dépasse 50%.
Ces résultats intéressent directement les opérateurs de flottes AMR (robots mobiles autonomes) en intralogistique et en livraison de dernier kilomètre, où la distance parcourue est directement corrélée au coût énergétique et à l'usure matérielle. L'étude d'ablation incluse dans les travaux est particulièrement instructive: elle démontre que l'optimisation du placement des points de relais génère des gains substantiellement supérieurs à ceux obtenus par simple repartitionnement spatial, établissant le design des relais comme levier dominant de la performance système. Cela remet en question l'hypothèse implicite répandue chez les intégrateurs, selon laquelle le transport direct source-destination constitue la référence optimale par défaut. La scalabilité démontrée à différentes tailles de flotte est un argument supplémentaire pour une adoption industrielle.
Le problème MRPD (Multi-Robot Pickup and Delivery) est un classique de l'optimisation combinatoire en robotique, mais les architectures relay-based à grande échelle restent peu explorées. Hungarian assignment et OR-Tools CVRP, les deux références battues dans cette étude, sont précisément les solveurs utilisés par les éditeurs de WMS et les intégrateurs de flottes dans des environnements comme ceux d'Exotec (Roubaix), 6 River Systems ou Locus Robotics. Ce travail reste cependant un preprint arXiv, sans validation sur plateforme réelle annoncée: les gains en simulation sont solides, mais la transition sim-to-real, notamment face à la congestion dynamique et aux pannes robot en cours de mission, reste à prouver. Les extensions naturelles incluent des flottes hétérogènes et des dépôts multiples.
L'algorithme VCST-RCP, s'il est validé en environnement réel, pourrait réduire de ~30% les coûts énergétiques des flottes AMR d'acteurs européens comme Exotec (Roubaix) qui utilisent actuellement Hungarian assignment ou OR-Tools CVRP comme solveurs de référence.




