AMI. 3356.8 __ ,_ HEC MONTREAL 3, AFFILIEE A L'UNIVERSITE DE MONTREAL La gestion en temps réel d’un feu de circulation dans le contexte des systémes de transport intelligents par Aidée Carriére Sciences de la gestion Mémoire présenté en vue de lobtention du grade de maitrise és sciences (M. Sc.) Novembre 2005 © Aidée Carriére, 2005© DECLARATION DE L'ETUDIANTE, DE L'ETUDIANT ETHIQUE EN RECHERCHE AUPRES DES ETRES HUMAINS. Recherche sans collecte directe d'informations Cette recherche n‘impliquait pas une collecte directe d'informations auprés de personnes (exemples : entrevues, questionnaires, appels téléphoniques, groupes de discussion, tests, observations participantes, communications écrites ou électroniques, etc.) Cette recherche niimpliquait pas une consultation de documents, de dossiers ou de banques de données existants qui ne font pas partie du domaine public et qui contiennent des informations sur des personnes, @ Titre dela La gestion en temps réel dun feu de circulation dans le recherche contexte des Systémes de transport intelligents Nom de ’étudiante, Aidée Carriere de étudiant Signature Date Drecton administrative - Déc. 2003 - PI2CYCLEMSOFomnulare déaraton de fetus sans do:Sommaire Les foux de circulation ont été créés afin de gérer le déplacement des véhicules @ Fintérieur d'un carrefour et ainsi prévenir les accidents. Les premiers modéles de gestion des feux de circulation utilisaient information provenant de données historiques afin d'optimiser les plans de feux. A cause de la grande variabilité des conditions de circulation, les résultats trouvés a partir de ces modéles donnaient seulement de bons résultats dans les situations correspondant a la moyenne des conditions de trafic. L'avénement des systémes de transport intelligent (STI) a permis optimisation des feux de circulation en temps réel. Les STI permettent de déceler la présence des véhicules & un carrefour & aide de différents types de détecteurs, ce qui a permis l'adaptation des feux de circulation en fonction de la demande. Les modéles de gestion des feux les plus récents font appel aux STI Nous étudions ici le probleme de ‘optimisation en temps réel des feux de circulation @ un carrefour en utilisant information fournie par un STI. Nous proposons un modéle mathématique dont lobjectif est de minimiser le temps de séjour total des usagers dans le carrefour. Le modéle doit tenir compte de la compatibilité des flux afin d'éviter les conflits entre les véhicules. II doit aussi empécher que le temps dattente total d'un véhicule ne dépasse un certain seuil d'attente maximal. L’approche de résolution utilisée pour ce modéle est la méthode de recherche a voisinage variable.Afin de tester notre modéle, nous avons congu un simulateur qui remplit deux fonctions : il permet de simuler l'entrée des véhicules a l'aide d’une loi de Poisson et de modéliser le comportement des véhicules dans le cartefour. Notre modéle a été testé sur plusieurs types de carrefours dans différentes conditions de circulation et les résultats ont démontré que notre approche est trés prometteuse. L’analyse de nos résultats nous permet de conclure que dans tous les cas testés, notre plan de feux permet d'avoir de meilleurs résultats comparativernent a un modele statique simple.Table des matiéres Chapitre 1 - Introduction... : bd Eee Chapitre 2 — Synthése des travaux existants .. 2A IMWFOGUCHION....scsssessssseenee ea 2.2 Terminologie. 2.3 Systémes de transport intelligents... 8 2.4 Recension des travaux antérieurs 10 Chapitre 3 — Définition du probléme..... 26 3.1 Gestion d'une intersection dans un contexte de STI et énoncé 26 29 3.3 Illustration de ‘approche et liens avec les travaux antérieur ...30 du probleme 3.2 Formulation mathématique du probléme réduit......... 3.4 Simulation, Chapitre 4 - Approche de résolution GA iinWrod con etAiisrh ccistsHatid. toate tnotdecta cts cnttose 4.2 Les méthodes de recherche a voisinage variable ........ 4.3 Obtention du plan de feux... 4.4 Définition des différents voisinages utilisés par le VND. 4.4.1 Changement de fiux dans une phase donnée 4.4.2 Echange de phases dans le plan de feux ... 4.4.3 Changement de durée de phases... 4.4.4 Elimination d'une phase..4.5 Stratégie de gestion des changements de voisinage ..........46 Chapitre 5 — Résultats numériques .......- te ee ta tecag) 5.1 Introduction. 5.2 Critére de performance 5.3 Simulation des conditions de circulation aux carrefours.. 5.3.1 Caractéristiques de trafic 5.3.2 Caractéristiques des carrefours 5.3.3 Hypotheses de la simulation... 5.3.4 Caractéristiques des différents tests 5.3.5 Caractéristiques de la méthode de PFA. 5.3.6 Spécifications supplémentaires..... 5.4 Détermination du plan de feux statique de référence....... @ 5.5 Expérimentation numérique... 5.5.1 Influence du type de carrefour et des conditions de trafic .....58 5.5.2 Impact d'un changement brusque des conditions de trafic....65 5.5.2.1 Changement sur un seul flux. en 6S, 5.5.2.2 Changement sur plusieurs approches — « Test Centre Bell » 67 5.5.3 Sensibilité aux variations du paramétre de temps diattente maximum 70 5.5.4 Analyse de limpact respectif des différents voisinages du VND..... 72 Chapitre 6 - Conclusion.. 74 Bibliographie... i078)Liste des figures Figure 1.1: Une artére dans espace temps. Figure 3.1 : Carrefour & 10 UX... Figure 4.1 : Carrefour & 10 flux... Figure 5.1 : Carrefours utilisés pour les simulations. Figure 5.2: 15 minutes de saturation de catégorie 1 Figure 5.3 : 15 minutes de saturation de catégorie 0 Figure 5.4 : Flux utilisant le plan de feux adaptatif et le plan de feux statique pour le « Test du Centre Bell » "W 31 40 52 66 67Liste des tableaux Tableau 2. Tableau 3.1: Tableau 3.2: Tableau 4.1 Tableau 4.2: Tableau 4.3 : Tableau 4.4 : Tableau 4.5 : Tableau 5.1: Tableau 5.2: Tableau 5.3 : Tableau 5.4: Tableau 5.5 : Tableau 5.6 : Tableau 5.7: Tableau 5.8 : Tableau 5.9: Tableau 5.10 Tableau synthése des différents systémes de gestion des feux de circulation... 25 Exemple d'un plan de feux statique. 32 Exemple d'un plan de feu adaptatit 33 Tableau de compatibilité pour un carrefour comprenant 10 flux.. 41 Plan de feux pour un carrefour a 10 flux 43 Echange de phases dans un plan de feux. Changement de durée de phases...... Retrait de la phase 3... Catégorie des différents lambdas utilisés .. Description détaillée des tests............ 5 plans de feux statique. Résultats aprés une simulation d'une HeUte.....osese 58 Résultats obtenus pour les 3 carrefOUrS ......seeeeeseeee 59 Détail du test E 60 Tableau comparatif du PFA et du PFS avec la fonction objectif ajustée. 62 Regroupement des tests comparables...... 63 Résultats pour le « test du Centre Bell » i ee : Performance du « test du Centre Bell»... ft 7OTableau 5.11: Tableau 5.12: Moyenne des résultats des différentes instances des tests en modifiant le temps maximal de la contrainte ou en éliminant la contrainte... ag! Statistique des différents voisinages utilisés .........73Remerciements Je tiens a remercier Monsieur Patrick Soriano, mon directeur de recherche, ainsi que Monsieur Michel Gendreau, de leur soutien indéfectible et de leur encouragement tout au long de ce processus. Merci également @ Monsieur Frangois Guertin et a Monsieur Serge Bisaillon qui m’ont permis de m'améliorer en programmation. Gardez votre joie de vivre! Jiaimerais aussi remercier les personnes concemées pour leur patience dans l'accomplissement de ce mémoire. Ce mémoire est dédié 4 mon pére, ma source d’inspiration. Merci maman chérie, toi qui as su m’encourager et qui me guide dans mon épanouissement. Quant a toi grand frére, tu es toujours 1a, tout simplement. Merci! Et toi Bianca, ma bonne amie, merci de ta grande générosité et de ton amitié Enfin, a Pascal, mon amour, merci de ta complicité. Merci également de ce leitmotiv : « La vie me donne ce que jattends d’elle ». Je t'aime!Chapitre 1 - Introduction Les feux de circulation constituent le moyen le plus répandu de gérer le flux des automobiles aux carrefours routiers (tant en milieu urbain que tural). Leur rdle est de rendre fluide le déplacement des automobiles et de rendre ceux-ci le plus sécuritaire possible en prévenant les accidents entre véhicules et impliquant des piétons. Plusieurs méthodes ont été utilisées afin de gérer efficacement les feux de circulation. Au tout début, le changement des feux était réalisé manuellement [17], puis des systémes automatisés ont été introduits et avec le temps, ceux-ci sont devenus de plus en plus sophistiqués. Certains d'entre eux sont dailleurs basés sur des modéles mathématiques plus ou moins complexes et sont commercialisés depuis plusieurs années. De tels modéles sont utilisés dans de nombreuses villes a travers le monde. Depuis quelque temps, la gestion de Ia circulation en général et celle des feux de circulation en particulier ont grandement évolué suite & lavenement des systémes de transport intelligents (STI). Ces systémes permettent, a l'aide de différents types de détecteurs, de déceler la présence de véhicules a un carrefour et de recueillir en temps réel une foule d'informations sur la circulation routiére : la vitesse des véhicules, la distance entre deux véhicules, etc. Les modales de gestion des feux de circulation les plus récents font appel aux STI afin d’optimiser le contrdle des feux de circulation en temps réel, c’est-a-dire que les feux de circulation a un carrefour s'adaptent a la demande au fur et & mesure que celle-ci varie dans le temps.Les systémes automatisés traditionnels [17] fonctionnent de fagon a co que chaque flux dans un carrefour se voit accorder un temps de vert, de jaune et de rouge prédéterminé, Le temps alloué pour passer du début du feu vert au jaune, puis au rouge et ensuite revenir au début du feu vert est appelé le temps de cycle. Celui-ci est une donnée associée a un cartefour et sera donc la méme pour tous les flux transitant 4 un méme cartefour. Plusieurs flux dans un carrefour peuvent se voir accorder le feu vert en méme temps si les véhicules qui les composent peuvent circuler sans risque daccident (on dira alors que ces flux sont compatibles), c'est ce qu'on appelle une phase. Par exemple, une phase pourrait avoir deux flux, un premier flux nord-sud et un second flux sud-nord. II existe alors, pour un carrefour, la possibilité d’avoir au moins deux phases ou méme davantage. L’enchainement de plusieurs phases compose ce qu'on appelle le plan de feux. Les systémes non adaptatifs utilisent information provenant de données historiques afin de déterminer les paramétres de gestion de flux de [intersection [17]. lls sont donc incapables de s'ajuster automatiquement aux changements observés dans les conditions de circulation alors que dans le contexte des STI, les feux de circulation peuvent étre contrélés en temps réel. Ils permettent donc l'ajustement des plans de feux en fonction des conditions de trafic observées en allouant le feu vert aux différents flux pour un intervalle de temps adapté @ leurs besoins. lls ont ainsi remis en question l'utilisation des cycles et la définition traditionnelle des phases. Cette remise en question a permis une plus grande flexibilité dans le contréle des feux. Dans le cadre de ce mémoire, nous nous proposons d’étudier le contréle des feux de circulation dans un contexte oul les cycles sont éliminés et ol la notion de phase est modifiée. L'objectif principal est detrouver une méthode qui permette de minimiser le temps de séjour total des usagers a un carrefour en temps réel en faisant appel aux STI afin de détecter la présence des véhicules au carrefour. Nous avons décidé de nous limiter & optimisation d'un seul carrefour, probléme qui est en soit déja complexe. L’optimisation en temps réel d'un réseau composé de plusieurs carrefours est encore plus complexe puisque tous les carrefours a I'intérieur de celui-ci sont interdépendants. Beaucoup d'améliorations sont encore possibles sur optimisation d'un seul cartefour et nous espérons que nos travaux constitueront une étape vers le développement de systémes permettant de gérer les feux sur des réseaux étendus. Les différents modéles de gestion de feux de circulation commercialisés qui seront présentés sont en fait des systémes qui permettent, a l'aide de divers modules, de controler un ou plusieurs feux de circulation . Ces modules peuvent entre autres optimiser la gestion des feux, simuler le comportement des véhicules, prédire leur arrivée au carrefour, optimiser les feux verts entre les différents carrefours, etc. Ces modules peuvent s'avérer trs complexes. Nous ne discuterons que du fonctionnement global de ces modéles puisque l'information publiée a leur sujet est tras sommaire. Le but de notre mémoire est en fait de créer un module d'optimisation qui pourrait étre intégré dans ces systémes dans le but d'améliorer leur performance. Puisque [information nécessaire afin de reproduire les modeles commercialisés et de les tester n'est généralement pas disponible, nous devrons évaluer nos méthodes en comparant les résultats qu’elles obtiennent a ceux obtenus par un plan de feux statique. N’ayant pas acoés a des données réelles, nous avons également di développer un module de simulation informatique afin de « reproduire » les conditions de circulation pouvant étre observées dans différents types decarrefours et ainsi pouvoir évaluer la performance en temps réel des méthodes de controle proposées dans ce mémoire. Ce mémoire comporte six chapitres. Le prochain chapitre décrit plus en detail le sujet du mémoire. Le deuxiame chapitre porte sur la synthése des travaux existants. Il inclut également une section qui traite de la terminologie nécessaire afin de mieux comprendre la problématique du contréle des feux de circulation. Le troisieme chapitre énonce les différentes hypotheses du probléme et le probléme a résoudre. On y présente également une formulation mathématique du probleme. Le chapitre quatre présente l'approche de résolution proposée ainsi que les diverses variantes testées. Les résultats obtenus suite a Vexpérimentation numérique sont présentés et analysés dans le chapitre cing qui est suivi de la conclusion.Chapitre 2 — Synthése des travaux existants Dans ce chapitre, nous passerons en revue plusieurs définitions de termes nécessaires a la compréhension du contenu de ce mémoire ainsi que les méthodes de gestion qui ont été mises en place depuis apparition des premiers feux de circulation. Ensuite viendront les différents modéles et approches mathématiques qui ont 616 proposés afin de résoudre les problemes de gestion de Ia circulation. Nous finirons en examinant plus en détail les différents systémes, plus particulirement leur module d'optimisation, qui ont été commercialisés et qui sont maintenant utilisés un peu partout dans le monde. Les formulations des modéles mathématiques commercialisés n’étant pas disponibles au public, nous ne ferons qu'une description conceptuelle de leur fonctionnement en nous basant sur les informations publiées a leur sujet.2.1 Introduction Avant 1923, la gestion des feux de circulation était accomplie manuellement [17]. Ainsi, tout changement au niveau des feux était basé sur instinct des contréleurs. Peu a peu, des systémes plus sophistiqués furent utilisés afin d’automatiser ces taches en ayant comme objectif de minimiser le temps d'attente des usagers, de maximiser le nombre de véhicules pouvant circuler sur le feu vert, etc. Le premier concept utilisé de fagon courante est le concept de feux a contréle automatique fixe qui comprend des phases prédéterminées avec des temps de cycles, des temps de vert et de décalages fixes. Ces termes seront définis plus précisément dans la section suivante. Pour un carrefour donné, tous ces paramétres qui permettent de gérer la circulation d'un carrefour sont calculés sur la base de données historiques. IIs ne peuvent évidemment pas tenir compte de la situation réelle au carrefour a un instant donné. Cette approche est encore trés utilisée de nos jours et semble encore la plus répandue a travers le monde, méme dans les pays industrialisés. Les problémes de gestion des feux de circulation comportent beaucoup de facteurs qui rendent le probleme trés complexe, ceci est la raison principale qui motive le recours a des heuristiques. Tout au long de ce chapitre, plusieurs modéles seront décrits. Llinformation sur ces différents modéles provient de Braban et Boillot [6] qui ont fait une synthése sur les différents systemes de gestion des feux en temps réel existant en milieu urbain. Plusieurs autres notions ont été titées du cours de « Dynamique de la circulation CIV6706 » donné & Ecole Polytechnique de Montréal par le professeur K. Baass [2].2.2 Terminologie Plusieurs termes doivent étre définis afin de bien décrire la situation ot la problématique. Cette section explique entre autres les termes communs a chaque modéle de gestion des feux de circulation Un carrefour est défini comme étant une intersection de plusieurs rues ou différents flux de véhicules doivent circuler de maniére ordonnée. Un ensemble de carrefours constitue un réseau. Chaque carrefour possede un cycle qui correspond au temps alloué pour passer du début du feu vert au feu jaune, puis au feu rouge et ensuite revenir au début du feu vert. Le temps accordé au feu vert et au feu rouge peut varier selon la demande de chaque carrefour. Par contre, le temps accordé au feu jaune est une donnée fixe, qui est habituellement entre 2,5 et 3 secondes. La prise de décision quant au changement ou non de I'état des feux de circulation au rouge ou au vert par rapport a leur situation présente est-ce qu'on appelle la commutation du feu de circulation. Tel que mentionné au chapitre précédent, une phase correspond a un ensemble de flux qui ont droit au feu vert en méme temps. C'est-a-dire, qu'une phase pourrait avoir deux flux, un premier flux nord-sud et un second flux sud-nord. Un changement de phase survient lorsqu’au moins un des flux change de statut, c’est-a-dire qu'il passe du vert au rouge ou du rouge au vert. Un carrefour peut avoir deux phases ou davantage. La séquence finie des différentes phases effectuant la commutation des feux d'un carrefour compose le plan de feux pour un temps de cycle prédéterminé. Un groupe de véhicules qui traverse un carrefour en méme temps est un peloton de véhicules. Plusieurs modeéles adoptent une stratégie visant & maximiser la taille des pelotons de véhicules et & minimiser leur nombre diarréts a un feu rouge sur une artére donnée en ajustant lestemps de vert de plusieurs carrefours sur cette artére. Cette stratégie est connue sous le nom de synchronisation. Elle peut aussi étre définie comme étant optimisation du décalage. Une intersection est dite saturée lorsqu'un véhicule doit attendre plus d'une phase pour traverser le carrefour comme on pourra observer un peu plus loin. Plusieurs modéles présents dans la littérature ajustent la definition du degré de saturation afin de mieux définir le probleme auquel ils s'appliquent. Nous allons done préciser cette notion au besoin a travers ce chapitre. La notion de degré de saturation est reli¢e au nombre maximal de véhicules que peut contenir un trongon sans que ceux-ci soient forcés de s'arréter & un feu rouge. Une artére principale est une artére ol! fon retrouve une plus grande concentration de circulation et un degré de saturation plus élevé alors qu'une artére secondaire correspond aux approches moins importantes en terme de quantité de circulation et a un degré de saturation moins élevé. En général, le degré de saturation sera plus élevé pour une artere principale que pour une artére secondaire. La demande des différents flux est proportionnelle au degré de saturation. La demande et le degré de saturation sont plus élevés aux heures de pointe qu'aux périodes hors pointe, 2.3 Systémes de transport intelligents La recherche au niveau de la gestion des feux de circulation a connu une trés grande popularité depuis les années 1960 jusqu’aux années 1980. Aprés cette période, ce domaine de recherche a été un peu délaissé. Larrivée des systémes de transport intelligents (STI) a relancé ' information sur l'évolution de l'état de la circulation aux carrefours. Ceci tude de la gestion des feux de circulation en permettant l'utilisation de a amené la possibilité d'optimiser les décisions de commutation a un carrefour donné en fonction de ces informations. Dans les systémesdécentralisés, certaines informations peuvent éventuellement étre échangées d'un carrefour a autre mais généralement la majorité deentre eux ne tiennent compte que de l'information provenant du carrefour local pour leur optimisation. Les STI centralisés relient les différents carrefours du réseau entre eux afin de rendre possible !échange d'information. Le partage de ces informations permet alors doptimiser les décalages des décisions de commutation entre les carrefours en fonction du changement des conditions de trafic ce qui permet une meilleure qualité de la gestion de la circulation mais au prix d'une complexité beaucoup plus élevée que pour les systémes décentralisés. Comme on peu le voir, les possibilités qu’amene Futiisation des STI sont nombreuses et débouchent sur de nouveaux problemes d'optimisation. Les premiers détecteurs de conditions de trafic en temps réel utilisés pour gérer les feux de circulation étaient sonores et ont été introduits dés 1927 [17]. Afin d'étre décelés et d’avoir du temps de vert, les véhicules devaient klaxonner en arrivant au carrefour. Cette méthode n’était utilisée que lorsque la circulation des flux était faible. Depuis cette 6poque, les détecteurs ont évolué et on retrouve maintenant aux carrefours des réseaux équipés de STI des boucles a détection magnétique, & détection photoélectrique, a détection infrarouge, ainsi que les détecteurs vidéo. Ces appareils permettent de recueilir information sur le déplacement des véhicules et ainsi prévoir leur déplacement futur. On peut donc envisager d'utiliser ces informations afin d'améliorer la gestion des carrefours. Les systémes de feux adaptatifs et semi-adaptatifs sont tous deux des systémes qui utilisent des données en temps réel. Ces systémes peuvent détecter la présence de véhicules d'un flux donné dans un carrefour et leur donner priorité au vert. Un systéme adaptatif détecte10 les véhicules sur tous les flux du carrefour et peut done s'ajuster la demande sur l'ensemble du carrefour. Le systeme semi-adaptatit n’a des détecteurs que sur les artéres principales. II ne s’ajuste done qu’a la demande de ces derniers. Les artéres secondaires ayant une demande moins élevée ne sont généralement pas équipées de détecteurs. Leur temps de vert sera done ajusté en fonction des conditions observées dans les artéres principales et non des leurs, ce qui peut réduire la fiuidité de la circulation pour ces approches. 2.4 Recension des travaux antérieurs Morgan et Little [19] ont proposé un modele permettant de maximiser le nombre de véhicules passant sur une artére sans s’arréter au feu rouge, done d'optimiser les décalages des différents feux localisés le long d'une artére. Depuis, ce modéle est aussi connu sous le terme doptimisation de la bande verte. L'objectif du modéle est d'augmenter la taille du peloton de véhicules pouvant passer sur l'artére (et ce dans les deux sens). Pour chaque carrefour du réseau, on dispose du temps de cycle ainsi que de la proportion de temps de vert pour les flux de Vartare. Ce sont des données du probleme. La figure 1.1 représente une artére dans l'espace temps. Nous avons alors trois feux de circulation, le premier situé & une distance de 0 metre, le deuxidme a 150 metres ot le demier a 300 metres. Les axes de notre graphique représentent les changements du feu vert au feu rouge pour les trois carrefours. Les carrés noirs représentent le feu rouge pour un feu de circulation et les espaces blancs situés au-dessus représentent le feu vert. La bande verte est illustrée par la largeur des lignes et c'est ce que Morgan et Little essayent d'optimiser. Ceci dit, le premier véhicule partira du premier carrefour @ 60 secondes et puis celui-ci pourra se rendre jusqu’au troisiéme carrefour sans arrét. Ceci" est vrai pour tous les véhicules qui partent du premier carrefour pendant son premier temps de vert. Figure 1.1 - Une artére dans espace temps Temps Distance Pour résoudre le probléme, Morgan et Little procedent par 'énumeration de toutes les possibilités afin de trouver la meilleure solution, c’est-a- dire de trouver quelle combinaison de feu vert permet d'avoir la bande verte la plus importante. La méthode consiste choisir la premiére intersection et rendre a tour de réle tous les autres feux sur cette artére vert et ensuite rouge. Ensuite, & partir de lintersection ainsi identifiée, il détermine quelle est la bande verte la plus grande. On dit alors que ce feu est critique puisque état de tous les autres flux dépend de lui. I utilise ensuite la méme méthode sur la deuxiéme intersection et continue ainsi de suite pour tous les feux. Dans notre exemple, on pourrait alors allouer du temps de vert au temps zéro et puis réajuster notre graphique pour nous donner une différente largeur au niveau de la bande verte. La solution qui permet de trouver la plus grande bande verte est retenue. Morgan et Little ont remarqué qu’ils devaient concentrer leurs efforts sur la maximisation du passage des véhicules dans un sens de circulation12 et ceci, aux dépens de l'autre puisqu'll était trés difficile doptimiser les deux sens @ la fois. Le modéle de Morgan et Little a ensuite été repris par plusieurs chercheurs afin d'en améliorer certains aspects ou de tenir compte de nouvelles notions : les piétons, les véhicules de transport en commun, le changement de vitesse des véhicules entre les carrefours, le virage & gauche et a droite, etc. Brooks [9] a repris le méme probléme et les mémes hypotheses que Morgan et Little. I! détermine la bande verte maximale en utilisant le plus petit temps de vert de tous les carrefours (i.e. feux). Ceci est le concept de borne supérieure. Le modéle sélectionne donc le feu ayant le plus petit temps de vert et le rend critique. A partir de celui-ci, on ajuste les autres feux en leur donnant soit le vert ou le rouge afin de maximiser la bande verte. La méthode de Brooks est plus rapide puisqu’elle ne construit qu'une seule solution mais en utilisant dés le départ le carrefour ayant le plus petit temps de vert. Le modéle de Morgan et Little fait une énumération de toutes les solutions possibles alors que le modele de Brooks permet de trouver la solution la plus intéressante dés la premiere itération. Certains modeles de gestion des feux de circulation ont été commercialisés. Ceux-ci utilisent soit des capteurs qui déterminent la position des véhicules en temps réel, soit une méthode qui permet de simuler le déplacement des véhicules ou bien les deux. Le premier modéle commercialisé a été TRANSYT — Traffic Network Study Tool [22] - est un modéle a temps fixe qui fonctionne avec des données historiques et suppose que les débits sont constants. Il permet optimisation des décalages et de la répartition des durées de vert. Le cycle est, dans ce cas, une donnée qui est commune a chaque carrefour du réseau. Le module d'optimisation, cherche & minimiser un13 indice de performance. Cet indice est une fonction de la somme de tous les véhicules a larrét sur l'ensemble des intersections considérées ainsi que la somme du nombre moyen de véhicules dans les files dattente pour chaque flux a chaque intersection. Le modéle utilise un histogramme de flux qui permet d’évaluer les déplacements des véhicules selon une fonction de dispersion. La méthode consiste déterminer le décalage optimal d'un carrefour en considérant que les décalages des autres carrefours sont fixes. Une fois un carrefour optimisé, on passe au prochain carrefour en considérant encore une fois que les décalages des autres carrefours est fixe pour cette « itération » et ainsi de suite. La méme méthode est utilisée pour la durée de vert. La solution optimale est trouvée en utilisant une méthode de descente. Cette méthode consiste a passer d’une solution 4 une autre en vérifiant si la nouvelle solution est meilleure que la solution précédente. Si oui, on l'adopte, sinon on passe a la prochaine itération.. Plusieurs solutions incluant un plan de feux et des décalages sont construites pour différentes périodes de la journée et les degrés de saturation leur correspondant. Ceux-ci sont emmagasinés dans des biblioth@ques. Une solution optimale est ensuite sélectionnée dans les bibliothéques soit: par commutation manuelle, par la programmation horaire ou en analysant le degré de saturation de Fétat réel des carrefours du réseau et en implantant le plan de feux et le décalage « optimal » obtenu pour les conditions de circulation les plus proches de colles observées. SCOOT - Split Cycle and Offset Optimization Technique - a été développé entre 1972 et 1980 [13, 23, 24]. C’est un systéme adaptatif qui permet optimisation en temps réel de la répartition des temps de vert, des temps de cycle ainsi que des décalages de feux de circulation @ Tintérieur d'un réseau. Les capteurs utilisés dans ce cas, sont des14 boucles magnétiques situées en amont du carrefour. L'emplacement des capteurs est un aspect primordial au bon fonctionnement du réseau mais qui dépasse largement le cadre de ce mémoire. Nous ne traiterons done pas ici ni ne ferons de recension de la littérature scientifique traitant de cette question. Le débit et la durée d'ocoupation des véhicules aux carrefours proviennent des capteurs et cette information est mise a jour quatre fois par seconde. La durée d’occupation des véhicules est tout simplement une donnée qui permet d'estimer le nombre moyen de véhicules en arrét et permet ainsi de prédire, avec I'état du plan de feux ainsi que de la vitesse a laquelle la file d'attente se décharge, si la file d'attente est sous-estimée. Linformation provenant des capteurs est utilisée afin de générer un histogramme de flux [18] qui est en fait une prédiction du comportement des véhicules afin de gérer les feux en tenant compte des véhicules déja dans le carrefour. Unistogramme permet d'estimer les files d'attente, les arréts et les retards des véhicules. SCOOT se base sur une division du réseau en plusieurs zones disjointes. Le nombre total de carrefours pouvant étre traité est cependant limité. Le cycle des carrefours a lintérieur de chaque zone est identique. SCOOT prédit les retards et les arréts des véhicules en utilisant information des capteurs. La fonction objectif du module d'optimisation est un indice de performance que l'on définit comme étant la somme pondérée des deux facteurs suivants : le nombre de véhicules arrétés sur tous les flux du carrefour et la longueur de la file d'attente sur tous les flux. Deux constantes sont utilisées afin de pondérer la somme des véhicules arrétés et la proportion du temps d'un cycle ol! les détectours sont occupés. Les détecteurs sont dits « occupés » lorsquiils, détectent la présence de véhicules. Le calibrage de ces constantes n’étant pas discuté dans les articles, il ne sera donc pas traité dans ce mémoire.15 Le module d'optimisation de SCOOT permet 'ajustement du plan de feux contrairement a une optimisation comme le dit son nom en misant sur de petites variations de la durée du cycle, de la durée du vert et des décalages. Le modéle prend en considération les files d'attente ainsi que le degré de saturation de chacune des artéres dans le but de le rendre inférieur a 90 %. Dans ce modéle, le degré de saturation est tout simplement le rapport entre le débit moyen et le débit maximum des véhicules pouvant traverser lartére. Plus celui-ci se rapproche de 100 %, plus grand devient le risque de congestion. SCOOT prédit les longuours des files d'attente [14] sur les artéres avec l'information des capteurs et en prenant comme hypothese que la vitesse des véhicules est une constante préalablement fixée. Juste avant deffectuer un changement, une vérification est faite pour s'assurer que la bonne décision est prise; on vérifie alors quelques secondes avant d'effectuer un changement, s'il est préférable de faire changer état du feu a l'instant prévu ou quelques secondes avant ou aprés. La décision est prise en considérant ce que le changement aura comme effet sur indice de performance, done sur le degré de saturation de lartére. Chaque carrefour appartenant & une zone possade le méme cycle alors que la proportion qu’occupe le temps de vert l'intérieur du cycle lui est propre. Les contraintes du modéle sont les suivantes : chaque temps de cycle et chaque temps de feu vert doivent étre compris entre un minimum et_un maximum prédéterminés. D’autres éléments ont aussi été étudiés par la suite [4]: la détection dincidents, la priorité donnée aux véhicules de transport en commun, change d'information entre les carrefours voisins et l'accumulation de véhicules sur plusieurs artéres. Cette accumulation est tout simplement Faugmentation des files d'attente aux carrefours en amont par une16 réduction de leurs temps de vert afin de réduire engorgement d'un carrefour donné. SCOOT permet d'optimiser le changement de l'état des feux de plusieurs carrefours a l'intérieur d'une zone sur un horizon a court terme. Le cycle pour chacun de ses carrefours est identique ce qui permet une moins grande flexibilité. Les petites variations au niveau du temps de vert, des cycles et des phases diminuent ladaptivité du modéle. Ce modéle a permis des améliorations intéressantes lors de tests mais il ne semble pas étre capable de gérer des problémes de grande taille et les articles consultés ne mentionnent pas l'adaptivité du modele lors de sursaturation des conditions de trafic. |! serait alors intéressant de remplacer le module d'optimisation de SCOOT par le notre afin d’évaluer augmentation de performance qui en résulterait SCATS — Sydney Coordinated Adaptive Traffic System [16], un autre modéle commercialisé, a été développé dans les années 1980 en Australie. I fait lui aussi varier la répartition de vert, les décalages et les durées de cycle afin de minimiser les retards et les arréts. Ce modéle comporte trois modes de fonctionnement différents : le mode dynamique qui utilise les données réelles pour optimiser chaque sous-systéme, le mode dynamique isolé ou les données réelles sont utilisées mais ou chaque carrefour fait sa propre optimisation et le mode en temps différé oi! les plans sont prédéterminés selon la journée et le moment de la journée. Les capteurs utilisés sont des boucles magnétiques implantées a chaque carrefour qui servent & déterminer le débit & un carrefour donné ainsi que le temps d’inoccupation des carrefours pendant la durée de vert. La vitesse instantanée ainsi que les écarts entre les véhicules sont aussi enregistrés. On se sert de toutes ces données pour calculer le17 degré de saturation qui représente ici le rapport entre le temps de feu vert nécessaire afin de vider le flux et le temps de vert total accordé Lobjectit du module d'optimisation est de minimiser la somme des retards et des arréts pour chaque carrefour. Pour le cas dynamique, le réseau est optimisé dans son ensemble contrairement a chaque carrefour individuellement. Le réseau est divisé en sous-systémes qui comportent eux-mémes plusieurs carrefours voisins qui fonctionnent tous sur le méme cycle. On utilise le carrefour ayant le plus grand degré de saturation pour évaluer quel plan de répartition de feu sera adopté. La durée du cycle est déterminée en se basant sur le temps de parcours des véhicules, sur le débit du carrefour le plus achalandé et sur son degré de saturation, La durée de cycle est une donnée qui peut changer constamment mais qui ne peut varier de plus de 6 secondes a la fois. Elle doit respecter plusieurs contraintes, notamment se situer entre un minimum et un maximum prédéterminé et avoir une valeur moyenne de cycle qui assure une bonne coordination du carrefour. Ce modeéle permet aussi, s'il y a une quantité importante de véhicules sur le carrefour, d’augmenter le cycle maximal du carrefour par une valeur de cycle prédéterminé. SCATS fonctionne avec des bibliotheques : durée de vert, décalages intemes, décalages exteres. Ces bibliothéques contiennent des données deja calculées qui ont été créées pour différentes conditions de circulation. SCATS permet de changer le critére d'optimisation pour chaque mode de circulation différent. Par exemple, pour la circulation de nuit, SCATS cherche a minimiser les arréts, alors qu'en période de pointe il cherche & maximiser les débits. Le fonctionnement de SCATS se fait de la facon suivante : les données des détecteurs sont utilisées pour calculer le degré de saturation pour chacun des différents plans provenant des bibliothéques. Le plan permettant le degré de saturation le plus petit est choisi et est utilisé aux feux de circulation. Cette18 méthode est utilisée pour la répartition de vert, pour la durée des cycles ainsi que pour les décalages. rité accordée SCATS a ensuite été adapté afin de tenir compte de la pri aux autobus et aux tramways. Les améliorations futures prévues (20, 21] devraient tenir compte de la prédiction de l'évolution de la circulation pour ensuite déterminer la prédiction de la demande sur un ou plusieurs cycles. SCOOT et SCATS [16] sont des systémes qui permettent des modifications au niveau de certains paramétres afin de minimiser un objectif composé des retards et du nombre d’arréts. Leur faiblesse vient du fait quils fonctionnent de fagon a faire des modifications par rapport aux données qui sont mesurées et n'essayent pas de prédire lentrée des nouveaux véhicules dans le carrefour. SCOOT prédit cependant le comportement des véhicules qui se retrouvent déja a lintérieur du carrefour a l'aide de son histogramme de flux. Celui-ci est mis a jour réguligrement avec les nouvelles données provenant des capteurs. SCATS consiste plutét a calculer le degré de saturation avec information provenant des capteurs et ainsi ajuster les conditions de circulation a aide des différents plans contenus dans les bibliothéques. lis réagissent done & tat présent du systéme, c'est-a-dire la situation présente aux carrefours mais n’anticipent pas l'évolution de cette situation. Diautres modéles ont été congus afin d’améliorer les conditions de circulation pour d'autres types de véhicules comme par exemple les véhicules de transport en commun, sans pour autant désavantager la circulation des véhicules privés. Ces modéles, bien que touchant clairement au domaine de la gestion de la circulation, ne seront pas détaillés ici car les problémes quils visent a résoudre sont trop éloignés19 de celui traité dans ce mémoire. Par la suite, les modéles sont ensuite devenus de plus en plus sophistiqués du point de vue de la détection de véhicules, de la prédiction et simulation des véhicules ainsi que de la gestion des feux de circulation. Les modéles plus récents font appel a la programmation dynamique. PRODYN — Programmation dynamique — a été congu au début des années 1980 [8,12]. C'est un systéme qui contient un module doptimisation. Celui-ci permet de déterminer, au fur et & mesure, et pour chaque carrefour donné, s'il est avantageux de faire la commutation des feux. II détermine une séquence « optimale » des feux en abandonnant la notion de cycle ce qui veut dire que le temps de vert accordé @ chaque flux a lintérieur d'une phase n'est pas fixe. Ce module utilise la programmation dynamique afin de résoudre le probléme. II fait appel a trois capteurs de boucles magnétiques : run implanté au début de l'artére, Pautre & une cinquantaine de metres de lintersection et le troisieéme sur la ligne de feu. Les données fournies par les captours permettent : d'estimer la longueur de la file d’attente, de prédire les arrivées futures, de connaitre le débit et finalement, de mesurer la présence d'un véhicule. Toutes ces données servent a déterminer l'état du feu. Dans son module d'optimisation, PRODYN cherche & minimiser le retard total approximé par la longueur des queues calculées sur chaque flux pour tous les carrefours. L'optimisation se fait sur un horizon de 75 secondes discrétisé en 15 unités de temps de 5 secondes chacune. A chaque unité de temps, dans un contexte d'horizon glissant, une décision doit étre prise : doit-on faire un changement sur I’état du feu ou non? Cette décision est prise en tenant compte des décisions des unités de temps précédentes.20 PRODYN détermine quel flux aura le feu vert partir des informations suivantes : ’état actuel du systéme, lévolution future prévue du systeme et le critére d'optimalité. Le module d'optimisation a comme contrainte un temps de vert minimum et maximum et une longueur maximale des files d'attente. PRODYN a done été développé pour optimiser un carrefour isolé mais son modéle a ensuite été amélioré afin de modéliser un réseau en échangeant de l'information entre carrefours voisins de fagon soit centralisée, soit décentralisée [1]. Le modéle peut aussi étre adapté pour tenir compte des piétons. OPAC — Real Time Optimization Policies for Adaptive Control [10] a été développé en 1982. Tout comme PRODYN, son module d'optimisation détermine, a chaque instant, si une commutation doit étre faite et ceci sur un horizon déterminé. Par contre, OPAC ne semble étre appliqué qu’au niveau local d'un carrefour isolé. Ce systéme nécessite des capteurs, des boucles magnétiques placées au début de chaque artare. Le module d'optimisation cherche @ minimiser 'indice de performance qui correspond & la somme du temps total d'attente des véhicules. 1! prend premiérement un horizon de longueur fini que l'on découpe en un nombre fini de pas de temps de durée de 5 secondes. La prédiction de Varrivée des véhicules est connue sur un horizon de 50 a 100 secondes. La fonction objectif tient compte du temps total d’attente pour les 3 prochains pas. Il existe trois différentes versions du module d'optimisation d’OPAC. La version 1: la programmation dynamique qui détermine toutes les commutations possibles sur un horizon. Ceci implique qu’a chaque 5 secondes, on détermine s'il y a une commutation ou non pour un horizon donné. Ces décisions peuvent étre représentées par un arbre de décision. La version 2: la Pseudo-Programmation Dynamique estat une application en temps réel qui découle de la version 1. La distinction par rapport & la version précédente est quill faut au moins faire une commutation sur I'horizon et au plus en faire trois. Ceci devient alors une recherche séquentielle ol toutes les possibilités doivent étre considérées. Les deux premidres versions supposent que les arrivées sont connues sur tout 'horizon. La premiére version a un coi trés élevé en terme de temps de calcul, c'est pour cette raison qu'elle ne peut étre appliquée dans une situation en temps réel. La version 2 reste lourde en terme de temps de calcul mais elle est moins codteuse que la version 1 ce qui lui permet d'étre utilisée on temps réel. La version 3: optimisation par horizon glissant est plus particuliére car elle procéde par optimisations successives sur une partie de I'horizon de planification qu'on appellera la fenétre d’optimisation qu'on met a jour au fur et a mesure jusqu'a avoir couvert tout horizon. Les bornes de la fenétre étant choisies, on extrait l'information au sujet de la situation correspondant a cette fenétre a partir des données fournies par les capteurs. Avec cette information et le modéle de prédiction, on fait loptimisation des commutations de vert du carrefour. Puis on décale la fenétre d'optimisation d'un certain pas de temps prédéterminé et on recommence le processus jusqu’a avoir optimisé la commutation sur tout horizon de planification. MOVA — Microprocessor Optimized Vehicle Actuation [25] a été développé durant les années 1980. C’est un systéme qui optimise la gestion des feux mais au niveau des carrefours isolés. Ce systeme est muni de deux capteurs par voie, l'un situé 40 metres des lignes de feu et autre & 100 métres qui permet de détecter les conditions de circulation saturées. Le module doptimisation de MOVA a comme objectif de minimiser les retards et les arréts. Il permet de mesurer Tintervalle entre deux véhicules pour déterminer s'il est nécessaire ‘apporter une correction au statut du feu en se basant sur le degré de22 saturation. MOVA reconnait d'autre part lorsqu'une file d'attente ne s'écoule pas. A ce moment, un changement automatique se fait pour choisir une méthode maximisant la capacité. MOTION — Method for the Optimization of Traffic Signals In On-line controlled Neworks [26] est un systéme qui obtient information nécessaire a son optimisation par r'entremise de trois capteurs situés de fagon stratégique : le premier a 40 metres, un autre & 100 métres et le dernier & 200 matres. Le module d'optimisation est en fait une structure modulaire hiérarchisée qui comprend le niveau stratégique, le niveau tactique et le niveau opérationnel. Premiérement, finformation ayant trait & la détermination des temps de vert est envoyée a chaque carrefour. En fonction des informations calculées, un temps de cycle commun est imposé a chaque carrefour. Ce temps de cycle est recalculé pour tenir compte des différentes données de chaque carrefour. Le décalage est ensuite déterminé avec l'aide d'un indicateur de performance. Deux possibilités s‘offrent pour déterminer le décalage, minimiser les retards ou assurer une coordination des plans de feux en début de vert. Ce niveau est répété chaque 10 a 15 minutes. Le niveau tactique détecte les incidents et modifie ensuite les plans de feux. Le niveau opérationnel est la modification du temps de vert compte tenu des différentes contraintes. Ce systéme permet également de tenir compte de la priorité accordée aux autobus. A notre connaissance, le systéme le plus récent est CRONOS — Control of Networks by Optimization of Switchovers [3]. Il a été développé en 1990. Tout comme PRODYN, il élimine la notion de cycle. II permet en plus d'éliminer la notion de phase prédéfinie, ce qui veut dire que la ‘séquence des flux ayant le vert n'est pas constante dans le temps mais change selon les besoins de la circulation. Pour ce faire, on doit déterminer la compatibilité des différents flux pour ne pas mettre en23 conflit des flux qui pourraient engendrer un accident. Le systeme permet aussi de modéliser selon deux différentes approches : l'approche centralisée et approche décentralisée. Les capteurs utilisés sont des capteurs @ caméras vidéo qui prennent les mesures de la circulation chaque seconde ou & quelques secondes diintervalles. Si des boucles magneétiques sont déja implantées au niveau des carrefours traités, information venant de ceux-ci sera également utilisée, CRONOS est composé de trois modules différents : prévision, simulation et optimisation. Le module de prévision permet de prédire les arrivées sur les différents flux. Lorsque lapproche centralisée est utilisée, les arrivées sur les flux sont calculées a partir de l'information provenant des autres carrefours. Si 'approche décentralisée est utilisée, Varivée des véhicules est déterminée en utilisant information provenant du module de simulation. Le module de simulation permet de déterminer les déplacements des différents véhicules en se basant sur certaines hypotheses qui ne sont malheureusement pas disponibles dans la documentation du produit. Ce module permet aussi de modéliser accumulation des véhicules aux différents carrefours en considérant espace occupé par les véhicules dans chaque flux et ainsi permet de tenir compte des effets de blocage dus a la présence d'un trop grand nombre de véhicules dans une ou plusieurs approches. Le module d'optimisation permet de minimiser le temps total d'attente de ensemble des véhicules présents dans le ou les carrefours en utilisant lalgorithme de Box [5, 15] qui permet l'optimisation simultanée de plusieurs intersections. Cet algorithme permet de trouver le maximum (minimum) d'une fonetion non linéaire ayant des contraintes d'inégalité non lingaires en générant premiérement un certain nombre de points24 réalisables ainsi que d'autres points générés aléatoirement. Le centroide de tous ces points est ensuite calculé. Si les points choisis ne respectent pas les contraintes, ils sont déplacés d'une distance 6 a Vintérieur du domaine réalisable ou tout simplement déplacés d'une valeur égale a la moitié de la distance du centroide trouvé afin de les rendre réalisables. La fonction objectif est ensuite évaluée en chacun des points et celui nous donnant la plus petite (grande) valeur est remplacé par un nouveau point en utilisant la formule suivant By =O (Rie %)) + Ke ol! .,, représente le nouveau point et x, 'ancien point, a la distance de déplacement, et x, le centroide des points. Si, aprés plusieurs itérations, le point qui donne la plus petite (grande) fonction objectif est toujours le méme, le point est déplacé de la moitié de la distance du centroide en tenant toujours compte des contraintes. Si aprés y rations consécutives, la valeur de la fonction objectif différe de B pour tous les points, on arréte le module d’optimisation. C'est le critére d’arrét de la méthode. CRONOS a été trés perforant lors de différents tests. Toutefois, Valgorithme de Box sur lequel il repose est une « heuristique » optimisation globale qui est a priori un peu dépassée et qui n’exploite aucunement la structure du probleme a résoudre. Des améliorations seraient peut-6tre possibles en ayant recours a des heuristiques modemes potentiellement plus efficaces telles la recherche a voisinage variable.Tableau 2.1 Tableau synthése des différents systémes de gestion des feux de circulation NOM OBJECTIF MODULE D'OPTIMISATION Morgan et Little] (Optimisation des décalages de (différents flux sur une artere. (Maximise la bande verte (Optimisation des décalages de [Maximise la bande verte Brooks différents flux sur une artere. [Optimisation des décalages at de la |Mininise Nindice de Iéparttion des durées de ver. lperformance : la somme de lous les véhicules a rarrét sur ltensemble des intersections TRANSYT Iconsidérées ainsi que la lsomme du nombre moyen de \véhicules dans les files \dattente pour chaque flux & Ichaque intersection. i [Optimisation de a réparition des [Minimise indice de temps de vert, des temps de oycle et _|performance : la somme les décalages des feux de circulation a |pondérée du nombre de SCOOT _ |fintérieur dun réseau. \véhicules arrétés sur tous les flux du carrefour et a longueur (do la file Gattonte sur tous les fiux (Optimisation de Ta réparition de vert, [Minimise la somme des scars [#8 décalages et les durées de cycle. retards et des arréts pour haque carrefour dans un (Optimisation du temps de vert et du [Minimise le retard total \décalage. lapproximé par la longueur des: eroom Pete ere Hux pour tous les carrefours.. (Optimisation de ia commutation des [Minimise findice de opac {eux pour chaque carrefour dans un performance : la somme du réseau. lemps total dattente des Pe Rae véhicules. (Optimisation de la gestion des feux au [Minimise les retards et los MOVA _hriveau des carrefours isolés. larréts, (Optimisation du temps de vert et du [Minimise les retards ou assure| MOTION |décalage. lune coordination des plans de feux en début de vert (Optimisation du temps de vert et du [Minimise le temps total cronos éalage \fattente de ensemble des \vehicules présents dans le ou les carretours.Chapitre 3 - Définition du probleme Ge chapitre décrit le probléme traité dans ce mémoire ainsi que son contexte. Il est constitué de trois sections : la premiére est consacrée & Ténoneé du probléme et de approche de résolution étant donné le contexte de gestion en temps réel, la deuxiéme présente le modéle mathématique devant étre résolu a chaque étape, la troisiéme fera état d'une illustration de notre approche ainsi que des différents liens entre notre approche avec les travaux antérieurs et la quatrime présente notre modéle de simulation concu afin de suivre l'évolution des véhicules a lintérieur du carrefour. 3.1 Gestion d’une intersection dans un contexte de STI et énoncé du probleme Un plan de feux statique (PFS) est utile lorsqu’on posséde une certaine information historique sur Parrivée des véhicules. II peut étre construit et optimisé @ l'aide de données moyennes sur la circulation qui ont été prises sur une longue période de temps. L'arrivée des STI a permis davoir accés a information du temps d’arrivée des véhicules, de leur vitesse, etc. en temps réel. Ces demiéres informations sont moins pertinentes lorsqu'un PFS est utilisé un carrefour puisqu'il ne sera pas capable de s’ajuster a la variabilité naturelle des flux. Par conséquent, il ne peut réagir aux conditions changeantes de la circulation, il ne pourra done que les subir. Ceci engendre des solutions jugées moyennement satisfaisantes. Cependant, un plan de feux adaptatif (PFA) sera capable