A Swarm Approach to Public Transit Using On-demand Routing in a Slime-Mold-Inspired Framework

Résumé technique : Une approche en essaim pour le transport public utilisant le routage à la demande dans un cadre inspiré par la moisissure visqueuse

Énoncé du problème
Les systèmes de transport à la demande (DRT - Demand-Responsive Transit) offrent une alternative flexible aux systèmes de transport de masse traditionnels à itinéraires fixes, particulièrement dans les communautés suburbaines et rurales à faible densité où les itinéraires fixes ne parviennent souvent pas à assurer un accès adéquat. Cependant, les implémentations actuelles de la DRT souffrent fréquemment de coûts d'exploitation élevés, d'une faible fiabilité et de taux d'échec importants. Les approches de routage actuelles reposent généralement sur une planification centralisée utilisant des algorithmes de plus court chemin (par exemple, basés sur Dijkstra) ou des métaheuristiques (par exemple, algorithmes génétiques, optimisation par colonies de fourmis). Ces méthodes peinent à gérer l'échelle et l'imprévisibilité de la demande en temps réel, où les itinéraires prévus deviennent rapidement sous-optimaux. De plus, les systèmes centralisés font face à des charges de calcul et de communication qui deviennent infaisables pour de grands réseaux sous une utilisation élevée. Le défi central consiste à concevoir un mécanisme de routage distribué et évolutif qui s'adapte dynamiquement à la demande des passagers, minimise les distances de marche et optimise l'utilisation des véhicules sans dépendre d'un contrôle centralisé.

Méthodologie
Les auteurs proposent un nouveau système de transport distribué piloté par l'algorithme RAPID, une méthode de routage bio-inspirée modélisée d'après les comportements de recherche de chemin efficaces de la moisissure visqueuse Physarum polycephalum. Le système fonctionne sans contrôle centralisé, utilisant la communication locale du réseau pour créer et maintenir des gradients de demande à travers le réseau routier.

La méthodologie est structurée autour de trois composantes principales :

1. Mécanisme d'enchères : Lorsqu'un passager demande un trajet, les véhicules candidats génèrent des enchères basées sur une fonction de récompense. La valeur de l'enchère ($B_{i,p}$) pour le véhicule $i$ prenant le passager $p$ est calculée en utilisant le temps d'attente normalisé, la distance du plus court chemin et la charge actuelle de passagers, pondérés par des paramètres ajustables ($\alpha, \beta, \gamma, \delta, \sigma, \epsilon$). Le véhicule ayant la valeur d'enchère maximale est assigné au passager.
2. Routage inspiré de la moisissure visqueuse (RAPID) : Au lieu de calculer des chemins fixes, les véhicules naviguent en fonction de gradients de demande locaux. Chaque nœud du réseau maintient une valeur de demande ($d_{p,n}$) et une valeur de référence ($r_{p,n}$), où les valeurs de référence sont fixées à 10 aux lieux de prise en charge et de dépose, et à 0 ailleurs. La demande se propage entre les nœuds voisins en fonction de paramètres de diffusion, de relaxation et d'inertie ($\zeta, \eta, \mu$). La demande cumulative à un nœud est pondérée par le temps d'attente du passager. Les véhicules décident localement de leur prochain mouvement en se dirigeant vers le nœud adjacent présentant la valeur de demande la plus élevée, permettant au système de réagir en temps réel aux conditions changeantes.
3. Transferts dynamiques : Pour optimiser davantage l'efficacité, le système permet aux passagers de changer de véhicule si cela réduit leur temps de trajet attendu. Un transfert est initié uniquement si l'amélioration cumulative des valeurs d'enchères pour les passagers concernés dépasse un seuil ($\theta$) et que le passager n'a pas dépassé une limite de transfert maximale ($\tau$).

Cadre de simulation
Les auteurs ont implémenté une simulation multi-agents utilisant des réseaux de rues réels dérivés d'OpenStreetMap pour trois environnements distincts : la zone suburbaine de Rutherford, NJ ; la zone urbaine de Newark, NJ ; et la zone semi-rurale de Wayne, NJ. La simulation compare l'approche basée sur RAPID à un benchmark de transport à itinéraire fixe dérivé des données de NJ Transit.

• Agents : Passagers (suivi de la localisation, de la destination, des transferts et des horodatages) et Véhicules (suivi de la position et des passagers assignés).
• Paramètres : Un algorithme génétique a été utilisé pour optimiser les paramètres de la fonction d'enchère et les seuils de transfert, avec une fonction de fitness équilibrant le temps de livraison moyen et l'écart type des temps de livraison.
• Conditions : Les simulations ont duré 100 minutes avec une flotte de 10 véhicules (capacité de 30 passagers chacun) dans le scénario de base, avec des tests supplémentaires faisant varier la taille de la flotte et la capacité des véhicules tout en maintenant une capacité totale constante de 300 passagers.

Résultats clés
Les résultats de la simulation indiquent que l'approche basée sur RAPID surpasse de manière significative le système à itinéraire fixe dans tous les environnements testés :

• Taux de livraison des passagers : Le système RAPID a augmenté le nombre de passagers livrés par rapport à l'approche à itinéraire fixe de 28,2 % à Rutherford (suburbain), 49,0 % à Newark (urbain) et 101,4 % à Wayne (semi-rural).
• Temps de marche : Le système a réduit le temps de marche moyen des passagers de plus de 75 % dans tous les scénarios (85,5 % à Rutherford, 84,7 % à Newark et 76,8 % à Wayne).
• Configuration de la flotte : Le système a démontré une flexibilité dans la composition de la flotte, montrant que les configurations avec de nombreux petits véhicules offraient souvent des temps de livraison plus rapides que peu de véhicules plus grands, à condition que la capacité totale reste constante.

Signification et revendications
L'article affirme que l'approche basée sur RAPID offre une solution décentralisée et évolutive aux limites des systèmes de DRT actuels. En imitant la prise de décision décentralisée d'une moisissure visqueuse, le système atteint une grande efficacité et fiabilité sans la surcharge de calcul d'une planification centralisée. Les auteurs soutiennent que cette approche est particulièrement adaptée aux environnements ruraux et suburbains où le transport à itinéraire fixe est souvent inefficace.

Le travail contribue à :

1. La conception d'un nouvel algorithme de routage de transport public bio-inspiré.
2. Le développement d'un cadre de simulation flexible intégrant des données de réseaux de rues réels.
3. La fourniture de preuves empiriques initiales suggérant qu'un routage à la demande piloté par essaim peut considérablement améliorer le débit de transport et l'accessibilité (spécifiquement en réduant les distances de marche) par rapport aux réseaux traditionnels à itinéraires fixes.

Les auteurs reconnaissent des limites, notamment l'absence de modélisation de la congestion du trafic, l'utilisation d'une demande de passagers générée aléatoirement plutôt que des modèles de déplacement réels, et l'absence d'analyse de coût. Ils notent que les travaux futurs se concentreront sur la validation du système avec des simulations à plus grande échelle, l'intégration de la dynamique du trafic et l'évaluation de la rentabilité.