Modèle de Nagel-Schreckenberg

Dans le modèle de Nagel-Schreckenberg, une route est divisée en cellules . Dans le modèle original, ces cellules sont alignées sur une seule ligne dont les extrémités sont connectées de sorte que toutes les cellules forment un cercle (c'est un exemple de ce que l'on appelle des conditions aux limites périodiques ). Chaque cellule est soit une route vide, soit contient une seule voiture ; c'est-à-dire qu'une seule voiture ne peut pas occuper une cellule à la fois. À chaque voiture est attribuée une vitesse qui est un nombre entier compris entre 0 et une vitesse maximale (= 5 dans le travail original de Nagel et Schreckenberg).

Le temps est découpé en pas discrets, tout comme l’espace, ce qui permet de représenter le système sous la forme d’un automate cellulaire. Chaque cellule représente une portion de route équivalente à quelques longueurs de voiture, tandis que la vitesse maximale correspond à la vitesse limite autorisée. Le pas de temps est alors défini comme le temps nécessaire à une voiture roulant à cette vitesse maximale pour parcourir environ dix longueurs de voiture.

Ce modèle peut être vu comme un outil simplifié permettant de comprendre ou simuler les embouteillages, en illustrant comment les interactions locales entre véhicules proches entraînent des ralentissements.

À chaque pas de temps, le système évolue selon une procédure bien définie^[1].

À chaque étape, les quatre actions suivantes sont effectuées dans l’ordre, de la première à la dernière, et toutes sont appliquées à toutes les voitures. Dans chaque action, les mises à jour sont appliquées à toutes les voitures en parallèle.

1. Accélération : Toutes les voitures qui ne sont pas à la vitesse maximale voient leur vitesse augmentée d'une unité. Par exemple, si la vitesse est de 4, elle passe à 5.
2. Ralentissement : toutes les voitures sont vérifiées pour voir si la distance entre elles et la voiture qui les précède (en unités de cellules) est inférieure à leur vitesse actuelle (qui a des unités de cellules par pas de temps). Si la distance est inférieure à la vitesse, la vitesse est réduite au nombre de cellules vides devant la voiture – pour éviter une collision. Par exemple, si la vitesse d'une voiture est maintenant de 5, mais qu'il n'y a que 3 cellules libres devant elle, la quatrième cellule étant occupée par une autre voiture, la vitesse de la voiture est réduite à 3.
3. Randomisation : La vitesse de toutes les voitures dont la vitesse est d'au moins 1 est désormais réduite d'une unité avec une probabilité de p. Par exemple, si p = 0,5, alors si la vitesse est de 4, elle est réduite à 3 dans 50 % des cas.
4. Mouvement des voitures : Enfin, toutes les voitures sont déplacées vers l'avant du nombre de cellules égal à leur vitesse. Par exemple, si la vitesse est de 3, la voiture avance de 3 cellules.

Ces quatre actions sont répétées plusieurs fois, aussi longtemps que nécessaire pour étudier les éventuels embouteillages qui peuvent se former. Le modèle est un exemple d'automate cellulaire. Le modèle est conçu pour une voie unique où les voitures ne peuvent pas se dépasser ; il n'y a pas de dépassement.

Ci-dessus et à droite se trouve un graphique de la vitesse moyenne en fonction de la densité des voitures, obtenu à partir d'une simulation du modèle original de Nagel–Schreckenberg^[1]. Dans la limite déterministe, p = 0, la vitesse est constante à la vitesse maximale (ici 5) jusqu'à une densité ${\displaystyle \rho ={\frac {1}{\mathrm {vitesse~max} +1}}={\frac {1}{6}}\approx 0.167}$, auquel point il y a une discontinuité dans la pente due à l'apparition soudaine d'embouteillages. Ensuite, à mesure que la densité augmente, la vitesse moyenne diminue jusqu'à atteindre zéro lorsque la route est occupée à 100 %. Lorsque p = 0,3, et qu'il y a donc des diminutions aléatoires de la vitesse, alors à faible densité, la vitesse moyenne est bien sûr plus lente. Cependant, le fait que p > 0 déplace également la densité à laquelle les embouteillages apparaissent vers des densités plus faibles – les embouteillages apparaissent au niveau du genou dans la courbe qui pour p = 0,3 est proche de 0,15, et les décélérations aléatoires arrondissent la discontinuité de la pente trouvée pour p = 0 au début des embouteillages^[2].

À droite se trouve le résultat d’un exemple de simulation du modèle Nagel-Schreckenberg, avec une vitesse maximale de 5, une densité de voitures de 0,35 et une probabilité de décélération p = 0,3. C'est une route de 100 cellules. Les voitures sont représentées par des points noirs, et donc, par exemple, si la route n'avait qu'une seule voiture, le tracé serait blanc à l'exception d'une seule ligne noire de pente − 1/5 (vitesse maximale = 5). Les lignes ont des pentes plus raides, ce qui indique que les embouteillages ralentissent les voitures. Les petits embouteillages apparaissent sous forme de bandes sombres, c'est-à-dire de groupes de voitures qui sont collées et se déplacent lentement vers la droite. L'ondulation des bandes est due à l'étape de randomisation.

Ainsi, le modèle de Nagel-Schreckenberg inclut l’effet des voitures qui se gênent mutuellement et qui ralentissent ainsi mutuellement. La vitesse moyenne à cette densité est légèrement supérieure à 1, tandis qu'à faible densité, elle est légèrement inférieure à la vitesse maximale de 5. Cela montre également qu’il s’agit d’un phénomène collectif dans lequel les voitures s’entassent dans les embouteillages. En cas d'embouteillage, la répartition des voitures le long de la route devient très inégale.

Sans l'étape de randomisation (troisième action), le modèle est un algorithme déterministe, c'est-à-dire que les voitures se déplacent toujours selon un modèle défini une fois que l'état d'origine de la route est défini. Avec la randomisation, ce n’est pas le cas, comme c’est le cas sur une vraie route avec des conducteurs humains. La randomisation a pour effet d’arrondir une transition autrement nette^[2]. Juste en dessous de cette transition, le freinage d'une voiture dû à un ralentissement aléatoire peut ralentir les voitures qui la suivent, créant spontanément un embouteillage. Cette caractéristique d’une voiture freinant au hasard et provoquant un embouteillage est absente dans un modèle déterministe.

• Le modèle explique comment les embouteillages peuvent survenir sans influences extérieures, simplement à cause de la congestion sur une route.
• Il a été démontré que les variantes du modèle Nagel–Schreckenberg fournissent (avec une tolérance dans la plage d'espacement des embouteillages) exactement les mêmes résultats pour les trajectoires des véhicules que les modèles d'ondes cinématiques et les modèles linéaires de suivi de véhicule^[3].
• Pour une vitesse maximale de un (au lieu de cinq) et aucune probabilité de ralentissement, le modèle est égal à l'automate cellulaire 184 de Stephen Wolfram.
• Le modèle est minimaliste, c'est-à-dire que l'exclusion de tout élément de la définition du modèle entraînera immédiatement la perte de propriétés cruciales du trafic.

• Le modèle de Nagel-Schreckenberg a été développé lors du séjour de recherche de Nagel au Laboratoire national de calcul parallèle de Los Alamos. Le modèle de prévision des transports Transims est basé sur ces travaux.
• Dans le Land allemand de Rhénanie-du-Nord-Westphalie, le modèle Nagel-Schreckenberg a été utilisé comme base pour un système complet de prévision du trafic accessible en ligne.

• Portail des routes