Le défi croissant de la congestion de la circulation urbaine

Selon le 2022 INRIX Global Traffic Scorecard, le conducteur moyen aux États-Unis a perdu 51 heures de congestion, coûtant plus de 800 $ par conducteur en temps perdu et en carburant. Au-delà de la frustration personnelle, la congestion augmente les émissions de gaz à effet de serre, dégrade la qualité de l'air et réduit la productivité économique.

Parmi eux, la programmation dynamique se distingue par une technique mathématiquement rigoureuse pour prendre des décisions séquentielles optimales sous l'incertitude. En appliquant une programmation dynamique au contrôle du signal de circulation, les ingénieurs peuvent créer des systèmes qui ajustent en continu les chronométrages de signal en fonction des données des capteurs en direct, améliorant de façon spectaculaire le débit à travers les intersections et les réseaux entiers.

Comprendre la programmation dynamique

La programmation dynamique (DP) est un paradigme algorithmique qui résout les problèmes d'optimisation complexes en les transformant en sous-problèmes qui se chevauchent plus simplement. L'idée principale est de stocker les solutions aux sous-problèmes de façon à ce qu'elles ne soient calculées qu'une seule fois, une technique connue sous le nom de mémorisation.

Dans le contexte du contrôle de la circulation, DP traite la décision de la synchronisation du signal comme un processus de décision à plusieurs étapes. À chaque étape (généralement quelques secondes), le système observe l'état actuel de l'intersection – longueurs de file, nombre de véhicules, passages pour piétons – et choisit une action[ (p. ex., étendre la phase verte actuelle, passer au jaune, commencer une nouvelle phase). L'objectif est de minimiser un coût cumulatif, souvent total de retard ou de consommation de carburant, sur un horizon fini ou infini.

L'algorithme DP fonctionne en résolvant une équation de Bellman qui relie la valeur (coût prévu futur) d'être dans un état particulier au coût immédiat d'une action plus la valeur de l'état suivant résultant. Cette relation récursive permet au système de regarder vers l'avenir et de sélectionner des actions qui mènent à des résultats globaux optimaux, et non pas seulement des améliorations locales.

Propriétés clés de la programmation dynamique pour le trafic

  • Sous-structure optimale:[ Le plan de synchronisation optimal pour l'intersection entière peut être construit à partir de plans optimaux pour chaque intervalle de temps individuel.
  • [ Plusieurs scénarios de trafic différents partagent des sous-états similaires, de sorte que les valeurs calculées peuvent être réutilisées à travers le temps et les intersections.
  • Transitions déterministes ou stochastiques: DP peut gérer à la fois les modèles déterministes d'arrivée et les modèles probabilistes où les arrivées de véhicules suivent une distribution.

Application de la programmation dynamique dans le contrôle des signaux de circulation

L'application du DP au contrôle du signal de trafic nécessite une cartographie minutieuse de l'intersection du monde réel dans un modèle mathématique. Le système doit continuellement sentir l'environnement, le représenter comme un état, exécuter l'optimisation du DP, et mettre en œuvre l'action choisie.

Collecte de données sur le trafic et sensibilisation

Les données en temps réel sont le moteur de tout système de contrôle adaptatif des signaux. Les intersections modernes sont équipées d'un mélange de capteurs:

  • Les détecteurs de boucle inductifs intégrés dans le trottoir mesurent la présence et le nombre du véhicule.
  • Les caméras vidéo avec algorithmes de vision informatique détectent les véhicules, les classent et suivent les mouvements.
  • Les capteurs radar et lidar fournissent des positions et des vitesses de véhicule à haute résolution.
  • Les données du véhicule connecté (V2X) peuvent transmettre des emplacements GPS exacts et des trajectoires prévues.

Ces données sont agrégées au contrôleur d'intersection, souvent avec des latences inférieures à 100 millisecondes, pour former l'état actuel.

Représentation de l ' État

L'État doit saisir toutes les informations pertinentes pour prendre une bonne décision. L'état typique d'une intersection isolée comprend :

  • Nombre de véhicules en attente par voie ou approche.
  • Phase de signal actuelle et temps écoulé dans cette phase.
  • Taux d'arrivée des véhicules par les détecteurs en amont (prédictions à court terme).
  • Boutons d'appel piétons et statut actuel des piétons.
  • Drapeaux de jour ou d'événement spécial (p. ex., préemption du véhicule de secours).

Pour que l'espace d'état soit gérable, les ingénieurs discrétent souvent les flux en niveaux (p. ex. faible, moyen, élevé) ou utilisent un vecteur de longueur de file d'attente de longueur fixe.

Le processus décisionnel et l'algorithme dynamique de programmation

À chaque époque de décision (toutes les 1 à 5 secondes), le PDD évalue toutes les combinaisons possibles de phases de signal. Le nombre de phases possibles varie : une simple intersection en quatre phases (nord-sud, nord-sud, gauche, est-ouest, gauche est-ouest) pourrait avoir 6 à 10 transitions admissibles. Le PDD calcule le coût total prévu pour chaque action sur l'horizon de planification—généralement 30 à 120 secondes.

La fonction de coût est essentielle, notamment pour les objectifs suivants :

  • Minimiser le délai total du véhicule (secondes).
  • Minimiser le nombre d'arrêts (qui causent des déchets de combustible et des émissions).
  • Maximiser le débit[ (véhicules desservis par unité de temps).
  • Combinaison pondérée[ de retard, d'arrêt et d'émissions avec priorités.

Pour un système avec arrivées stochastiques, cela devient un processus de décision Markov (MDP), et la solution DP donne une politique mapping se dit aux actions. La politique peut être calculée hors ligne et stockée dans une table de recherche pour une utilisation en temps réel, ou résolue en ligne avec une approche de rotation-horizon.

Objectif d'optimisation : réduire les congestions et les temps d'attente

L'objectif ultime est de réduire le temps perdu pour tous les usagers de la route. Des études ont montré que la commande dynamique de signal basée sur la programmation peut réduire le délai moyen du véhicule de 20 à 40 % par rapport aux signaux à temps fixe, et de 10 à 15 % par rapport aux contrôleurs actionnés plus simples.

De plus, en réduisant le nombre d'arrêts et la durée de ralenti, les systèmes basés sur le PDD réduisent la consommation de carburant de 10 à 25 % et réduisent proportionnellement les émissions de CO2 et de NOx.

Avantages de l'utilisation de la programmation dynamique pour les signaux de trafic

L'adoption de programmes dynamiques dans le contrôle des signaux de circulation offre un large éventail d'avantages opérationnels et sociétaux.

Amélioration du débit de circulation

Les algorithmes DP s'adaptent en permanence aux temps verts pour répondre à la demande en temps réel, empêchant les verts gaspillés de se produire lorsqu'un signal reste vert pour une voie vide pendant que le trafic croisé s'accumule.

Réduction de la congestion aux heures de pointe

Pendant les heures de pointe, la demande dépasse de loin la capacité. DP aide à équilibrer les files d'attente entre les approches : il peut donner un temps vert supplémentaire à la direction la plus lourde jusqu'à ce qu'un goulot d'étranglement aval s'échappe, puis basculer pour soulager une autre approche.

Réponse adaptative aux changements de conditions

Comme le PDD réévalue toutes les quelques secondes, le système réagit immédiatement aux incidents, aux événements spéciaux ou aux surtensions soudaines de la circulation. Par exemple, si une voie est bloquée en raison d'un accident, le PDD détectera la capacité réduite et ajustera les phases pour détourner la circulation ou prolonger les verts parallèles.

Économies d'énergie et d'environnement

Le département américain de l'énergie estime que l'optimisation des signaux de circulation peut économiser 40 gallons d'essence par an et réduire les émissions connexes. Les systèmes basés sur le PDD amplifient ces économies en maintenant un calendrier efficace même pendant les périodes de pointe où les plans à temps fixe sont souvent trop prudents.

Élargissement vers les réseaux

Bien que le PDD soit le plus souvent appliqué aux intersections isolées, les mêmes principes peuvent être étendus au contrôle du corridor ou du réseau par des techniques de décomposition (p. ex., coordination des intersections adjacentes par échange de débits de frontières), ce qui permet aux villes de déployer progressivement le contrôle basé sur le PDD, en commençant par les nœuds les plus encombrés.

Défis et limites

Malgré son attrait théorique, la mise en œuvre de programmes dynamiques dans les systèmes de trafic réels fait face à plusieurs obstacles.

Complexité informatique

La malédiction de la dimensionnalité est le plus grand obstacle. Une intersection avec 8 approches, chacune ayant 5 niveaux de file d'attente possibles, crée un espace d'état de 58 = 390 625 états. Multiplier par 4 phases et un horizon de planification de 10 étapes de décision, et le DP devient calculablement coûteux.

  • Indiquer l'agrégation ou l'abstraction (par exemple, grouper des combinaisons de files d'attente semblables).
  • Programmation dynamique approximative (ADP) utilisant l'approximation de fonction ou des réseaux neuraux.
  • Accélération matérielle via les processeurs GPU ou dédiés.

Intégration avec les infrastructures existantes

La plupart des villes ont des contrôleurs de signaux vieux de plusieurs décennies qui utilisent un firmware propriétaire. Le remplacement des contrôleurs par des unités compatibles DP coûte cher. Une approche plus pratique consiste à ajouter un ordinateur de bord qui communique avec le contrôleur existant par des protocoles standard (NTCIP, STOP).

Qualité des données et fiabilité des capteurs

Les détecteurs échouent, les caméras vidéo peuvent être bloquées par le brouillard ou l'éblouissement solaire, et la pénétration du véhicule connecté est encore faible. Les systèmes robustes doivent intégrer la fusion de données et la détection de failles pour gérer avec grâce les mesures manquantes ou bruyantes.

Sécurité et facteurs humains

Le contrôle des signaux de circulation doit privilégier la sécurité par-dessus tout. Les algorithmes DP qui raccourcissent agressivement les temps jaunes ou sautent les phases pour optimiser le débit pourraient augmenter le risque d'accident. Par conséquent, toute mise en œuvre DP doit imposer des intervalles de dégagement minimums verts, jaunes et tout rouge définis par les normes MUTCD.

Exigences en temps réel en matière de calcul

Pour les grands espaces d'état, le PDD exact peut être trop lent. Les chercheurs ont développé le contrôle de l'horizon de rotation, où le PDD résout un horizon plus court (par exemple, 10-15 secondes) et replanifie chaque étape, en approximant la politique optimale d'horizon infini.

Orientations futures : approches hybrides et apprentissage automatique

La prochaine génération de contrôle intelligent des signaux de circulation est susceptible de combiner programmation dynamique et apprentissage machine pour surmonter les limitations actuelles et atteindre une gestion encore plus intelligente.

Renforcement de l'apprentissage (RL) et programmation dynamique

L'apprentissage du renforcement est directement lié au PDD : les deux résolvent les PDM. Les algorithmes de RL profonds modernes (tels que DQN, PPO et SAC) peuvent gérer les espaces d'état haute dimension en utilisant des réseaux neuronaux pour approximer la fonction ou la politique de valeur.

Les systèmes hybrides utilisent le PDD pour fournir une base solide ou pour guider l'exploration, tandis que le RL peaufine la politique par des essais et des erreurs de simulation. Par exemple, une politique optimale du PDD pour un modèle simplifié peut être utilisée pour initialiser un agent de RL, accélérer la formation et garantir un comportement sûr.

Contrôle prédictif avec prévisions à court terme

La combinaison de DP et de modèles de prédiction de l'apprentissage automatique (p. ex., les réseaux neuronaux LSTM pour le flux de trafic) permet au système d'anticiper les surtensions. Au lieu de réagir à l'accumulation de files d'attente, le DP peut ajuster les chronométrages pour tenir compte des pelotons prévus. Cette approche, appelée module prédictive control (MPC), utilise DP comme optimisation de base, mais alimente les taux d'arrivée prévus.

Plusieurs essais sur le terrain ont montré que les signaux de circulation basés sur les MPC surpassent les systèmes purement réactifs, en particulier dans les couloirs avec des pelotons synchronisés. Une étude de cas à Pittsburgh utilisant le Rapid Flow Technologies Surtrac system[ (basée sur DP et RL) a permis de réduire de 25 % le temps de déplacement et de 21 % les émissions.

Coordination basée sur le cloud et Big Data

Chaque intersection gère un DP local pour son propre contrôle, mais les serveurs cloud calculent des décalages optimaux et des séquences de phase pour des corridors entiers en utilisant l'optimisation globale (p. ex., en utilisant DP pour le problème de coordination avec un modèle grossier). Cette approche hiérarchique s'évalue bien et peut intégrer les données de trafic à l'échelle de la ville à partir d'applications mobiles, de traces GPS et de flux de centres de gestion du trafic.

Intégration avec les véhicules autonomes

La pénétration du véhicule autonome (AV) peut évoluer. Le DP peut être étendu pour gérer les communications véhicule-infrastructure (V2I), ce qui permet au signal de demander que les AV règlent la vitesse pour toucher les fenêtres vertes. Le DP contrôlerait alors non seulement les phases de signal, mais aussi les vitesses proposées pour les véhicules connectés, créant ainsi une optimisation coopérative qui maximise le débit tout en minimisant les arrêts.

Conclusion

En modélisant l'intersection comme un processus de décision séquentiel et en résolvant pour des politiques de synchronisation optimales, DP réduit de façon significative la congestion, les émissions et les temps de déplacement. Les déploiements et la recherche dans le monde réel continuent de repousser les limites, en répondant aux défis de complexité informatique, de fiabilité des capteurs et d'intégration par des méthodes hybrides qui combinent DP et apprentissage automatique.

Pour les villes qui ont des problèmes de blocage, investir dans le contrôle des signaux basé sur le PDD est une stratégie de levier élevé. Il utilise l'infrastructure de capteurs existante et peut être déployé de façon progressive, avec des retombées immédiates sur la mobilité et la durabilité.