Régulation du Trafic aux Intersections : Prise en Compte des Véhicules Prioritaires

03/08/2016
OAI : oai:www.see.asso.fr:545:2009-1:17226
DOI :

Résumé

Régulation du Trafic aux Intersections : Prise en Compte des Véhicules Prioritaires

Métriques

32
6
150.1 Ko
 application/pdf
bitcache://2ecedd0dd64fe3129615dd9261983a2274564d8e

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2009-1/17226</identifier><creators><creator><creatorName>Abdeljalil Abbas-Turki</creatorName></creator><creator><creatorName>Abdellah El Moudni</creatorName></creator><creator><creatorName>Jia Wu</creatorName></creator></creators><titles>
            <title>Régulation du Trafic aux Intersections : Prise en Compte des Véhicules Prioritaires</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2016</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 3 Aug 2016</date>
	    <date dateType="Updated">Thu 11 Aug 2016</date>
            <date dateType="Submitted">Wed 19 Sep 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2ecedd0dd64fe3129615dd9261983a2274564d8e</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>29041</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Régulation du Trafic aux Intersections: Prise en Compte des Véhicules Prioritaires Jia WU, Abdeljalil ABBAS-TURKI et Abdellah EL MOUDNI Laboratoire Systéme et Transports Université de Technologie de Belfort-Montbéliard 90010 Belfort Cedex, France {jia.wu, abdeljalil.abbas-turki, abdellah.el-moudni} @utbm.fr Résumé— Dans cet article, nous proposons une nouvelle méthode pour gérer le trafic dans une intersection simplifiée. Nous considérons l’intersection comme étant une ressource partagée entre les véhicules des deux rues qui se croisent. Nous prenons en compte les vitesses d’approche des véhicules et les temps nécessaires au freinage et au démarrage. Ainsi, la commande des feux est mise en œuvre en observant chaque arrivée de véhicule d’une manière individuelle. En particulier, nous visons à traiter distinctement les véhicules prioritaires, tels que les bus ou les ambulances, des véhicules or- dinaires. Ceci nous conduit à considérer deux objectifs à la fois, à savoir, minimiser les temps d’attentes des véhicules prioritaires et évacuer au plu tôt tous les véhicules présents dans le carrefour. Enfin, cette approche peut être adaptée à des véhicules autonomes sans la présence de feux. Mots-clés—Gestion du trafic, Partage de ressources, Véhicules autonomes I. INTRODUCTION La congestion au niveau des carrefours est souvent associée à l’inconfort de conduite. Bien qu’effectivement la qualité de la conduite en dépende, les inconvénients de la congestion ne se limitent pas seulement à cet aspect. Si l’on s’intéressait au trafic dans son environnement urbain, la congestion serait par l’allongement des durées de parcours et par les accélérations qu’elle suscite une des causes importantes de la pollution. De plus, une congestion mal-maîtrisée discrédite une politique ur- baine soucieuse de la qualité de l’air. Partant de ce constat, plusieurs travaux de recherches ont tenté d’améliorer la régulation du trafic au niveau des carrefours. Nonobstant des progrès réalisés tels que la régulation adaptative et l’ajout des phases escamotables et prioritaires, le problème de congestion reste posé, ce qui requière de nouveaux efforts. L’évolution actuelle des technologies de l’information et de la télécommunication nous offrent de nouvelles issues en matière de régulation du trafic. A l’instar des autoroutes in- telligentes où l’augmentation de leur capacité s’avère réalis- able, ce travail tente de faire profiter les carrefours urbains des nouvelles technologies pour ce même objectif. Il s’agit d’utiliser la communication inter-véhiculaire et la communi- cation véhicule-infrastructure afin d’augmenter la capacité aux nœuds et d’optimiser la conduite par des consignes fournies aux conducteurs. Ceci minimisera sans doute la congestion et par conséquent réduira la pollution qui en découle. Cependant, pour aborder le problème des véhicules au- tonomes au niveau des carrefours, il est nécessaire d’utiliser une modélisation adaptée du trafic partageant l’espace conflictuel. Notre intention d’amélioration du trafic se heurte à la quasi- absence de modèles mathématiques adaptés. En effet, d’une part, les régulations adaptatives telles celles proposées dans TRANSYT [1], SCOOT [2],PRODYN [3],OPAC [4],SCAT [5] sont généralement basées sur l’estimation de la file d’attente ou sur une discrétisation des états du carrefour. La mesure du débit est la base de la régulation adaptative, ce qui sup- pose un traitement par estimation de variables macroscopiques. Ceci limite bien évidemment l’exploitation de la communica- tion inter-véhiculaire. D’autre part, les modèles actuellement proposés des véhicules autonomes sont basés sur une segmenta- tion de l’espace conflictuel en plusieurs rectangles autonomes [6], [7]. A cause de la complexité des interactions entre les véhicules et l’infrastructure, les approches supposent des mou- vements prévisibles, ce qui n’est ni réalisable ni vérifiable à présent. En effet, l’information sur la destination du véhicule est actuellement détenue pas le conducteur et sa communication au dispositif n’est pas pour l’heure actuelle systématique. Afin de s’affranchir de la difficulté de modélisation, nous avons suggéré un modèle présenté dans [8] qui peut permettre de partager la ressource, en toute sécurité. En outre, ce modèle permet une approche mésoscopique du trafic qui est plus fine que l’approche des files d’attente (macroscopique) et qui évite des détails sur le comportement des véhicules (microscopique) que nous ne possédons pas en temps réel. Ce modèle est basé sur les systèmes à évènements discrets et considère l’espace con- flictuel comme étant une ressource partagée. Il a servi de base aux travaux présentés dans [9], [10], [11]. Ces travaux visent à minimiser les temps d’évacuation des véhicules par des ap- proches optimales et approchées. Afin d’exploiter ce modèle dans un univers réaliste, ce papier aborde la problématique de l’adaptation de la commande asso- ciée à la présence des véhicules prioritaires dans une intersec- tion élémentaire. Puisque le modèle utilisé [8] permet d’étudier chaque arrivée de véhicule d’une manière individuelle, ce pa- pier abordera la formulation du problème d’accès des véhicules prioritaires. Plus précisément, il vise à affiner les approches présentées dans [9], [10], [11] pour traiter chaque véhicule dif- féremment. Il s’agit ici de distinguer le traitement des véhicules prioritaires de celui des véhicules ordinaires. Ce papier est organisé de la manière suivante. La section II donne la formulation du problème de régulation du trafic en présence de véhicules prioritaire. La section III présente briève- ment le modèle Réseau de Petri utilisé. La section IV décrit en détail la programmation dynamique que nous utilisons pour résoudre ce problème. La section V présente le processus de commande des feux. Les résultats de la simulation sont illustrés dans la section VI. e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 II. DÉFINITION DU PROBLÈME Dans le cadre d’une intersection classique, chaque mouve- ment du flux de circulation observe les feux dans l’ordre suivant: Rouge, Vert et Jaune. Un intervalle vert est suivi par un temps d’intervalle jaune indiquant que le véhicule doit s’arrêter, s’il ne peut pas assurer la sécurité. On peut noter que l’ensemble des mouvements de circulation obéit à la même règle, à savoir à la même succession de couleurs de feu. Cependant, dans le cadre de la commande des flux de circulation, le jaune n’est pas con- sidéré car il fait partie du temps du vert effectif. Ainsi, nous con- sidérons une intersection isolée biphasée avec feux contrôlables à chaque tronçon. L’intersection est une zone où plusieurs flux partagent un es- pace conflictuel représenté par le rectangle gris dans la Fig.1. Cet espace n’autorise pas le passage concomitant d’au moins deux flux de circulation notés flux concurrents. Nous prenons en compte un temps inter-véhiculaire minimum de p entre les véhicules appartenant au même flux. Les accès successifs au carrefour par deux véhicules appartenant à deux flux différents sont séparés par un intervalle temporel s différent de p. Évidem- ment, par mesure de sécurité et à cause des temps de freinages et d’accélération p < s. Dans la suite, nous nous intéressons seulement à deux flux concurrents. Chaque flux provient d’un tronçon a une seule voie. L’intersection possède un système de régulation qui com- munique avec l’équipement embarqué du véhicule. Lorsque le véhicule accède à une concurrente, l’équipement embar- qué informe le système de régulation en fonction de la vitesse autorisée sur le temps nécessaire au véhicule pour approcher l’espace conflictuel. 000000000 000000000000000000000000000 000000000000000000 000000000000000000000000000 111111111 111111111111111111111111111 111111111111111111 111111111111111111111111111 Rue 2 Rue 1 et le contrôle à l’intersection communication entre véhicules Fig. 1. Intersection élémentaire schématisée Soient Cj le temps d’évacuation du véhicule j (= le temps où véhicule j traverse l’intersection), rj son temps d’arrivée avec 1 ≤ j ≤ n, n étant le nombre de véhicules dans la zone de contrôle. Dans nos travaux précédents [9], nous avons proposé la pro- grammation dynamique pour minimiser le temps d’évacuation de tous les véhicules dans une intersection similaire. Il s’agit formellement de calculer: min{maxCj} (1) Les résultats de simulation ont montré que l’approche pro- posée améliore efficacement les performances d’une intersec- tion élémentaire. Dans la suite, nous abordons une situation plus compliquée. Il s’agit de considérer des véhicules avec des poids différents afin de distinguer les véhicules prioritaires (comme les ambulances, les voitures de police ou les véhicules propres) des véhicules ordinaires. Afin de privilégié les véhicules pri- oritaires, l’objectif de la commande n’est pas seulement de ré- duire le temps d’évacuation de tous les véhicules dans les rues en amont, mais aussi de minimiser le temps d’attente des véhicules particuliers. Par conséquent, deux critères de performance sont à prendre en compte, ce qui nous conduit à traiter un problème d’optimisation multicritère. [12] présente trois approches pour résoudre les problèmes multicritères: priori optimisation, interactive optimisation et posteriori optimisation. Les deux dernières méthodes supposent l’interaction avec le décideur pour effectuer respectivement un choix intermédiaire et définitif. Compte tenu des contraintes de calculs, la méthode priori optimisation est la plus adaptée à la régulation. En effet, le système de régulation doit proposer une seule solution en un temps court. La méthode priori opti- misation concatène deux critères f et g en une seule fonction objective composite notée F. F peux être linéaire, par exem- ple, F = αf + βg où α et β sont les coefficients qui indiquent l’importance des critères f et g. L’application de l’approche pri- ori optimisation donne la fonction objectif ci-dessous: min{α 1≤j≤n wj · Tj + β max Cj} (2) où Tj le temps d’attente du véhicule j, tel que Tj = Cj − rj et wj est le poids qui lui est attribué. Les valeurs attribuées à α et β sont laissées à la charge de l’exploitant du réseau urbain qui décide en fonction de la politique admise de la gestion du trafic. S’il préfère minimiser le somme du temps d’attente des véhicules prioritaires, il donne une valeur plus importante à α, à savoir α > β; et inversement, s’il accorde plus d’importance à la fluidité du trafic en général. Ceci est valable pour les poids des véhicules importants, à savoir wj. On donne un poids plus grand pour les véhicules urgents. Par exemple, les ambulances peuvent bénéficier d’un poids plus important que celui attribué aux véhicules propres. III. MODÉLISATION DU PROBLÈME Nous présentons le modèle RdP (Réseau de Petri) introduit dans [8] pour modéliser le problème d’optimisation relatif à l’intersection présentée dans la Fig.1. A. Modéle Réseau du Petri Ce modèle représente, d’une part,le systèmes de signalisation et d’autre part, les mouvements des véhicules. Il est composé de trois parties: R1, R2 et Gestion des feux. R1 et R2 décrivent respectivement le comportement des véhicules venant des rues 1 et 2 lorsqu’ils traversent l’intersection. La partie centrale con- cerne les comportements admissibles par le système en termes de commande de feux. pi représente le temps minimal inter véhicule entre les véhicules venant de la rues i. Ce temps est estimé en fonction des normes de sécurité et de la géométrie de l’infrastructure. Si un jeton est présent dans la place P1, cela signifie qu’un véhicule provenant de la rue1 traverse l’intersection. Il en est de même pour la place P2 en ce qui concerne les véhicules provenant de e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 la rue 2. Un jeton dans la place P1−2 indique qu’une phase de rouge intégral succède à une période de feu vert pour la rue 1 et inversement pour la place P2−1. Les temporisations s1−2 et s2−1 de ces places tiennent compte de la durée du rouge inté- gral. Elles incluent également la durée du feu jaune vif et le temps d’accélération du premier véhicule de la file qui s’apprête à recevoir le feu vert. Soulignons enfin qu’en agissant sur les transitions v, nous pouvons choisir de prolonger une phase ou, au contraire, de procéder à un changement de phase. Ainsi, ce modèle peut représenter à travers la commande sur les transi- tions v toutes sortes de régulation. La sémantique du modèle présenté dans la Fig.2 est détaillée dans le tableau I. R1 R2 v1 x1−2v2−1 v2 s2−1 x1 v1−2 s1−2 x2 x2−1 P2−1 P1−2 p1 p2 P2 u1 u2 y1 y2 P1 Gestion des feux Fig. 2. Modèle RdP d’une intersection avec rouge intégral TABLE I NOTATIONS Notation Signification ui(t), ui(k) le nombre de véhicules venant de la rue i prêt à traverser l’intersection jusqu’à la date t; le temps où le kème véhicule est prêt à traverser l’intersection vi(t), vi(k) le nombre de véhicules qui ont quitté l’intersection jusqu’à la date t; le temps où le kème véhicule de la rue i accède à l’intersection xi(t), xi(k) le nombre de véhicules qui ont traversé l’intersection jusqu’à la date t; le temps où le kème véhicule permet à d’autres véhicules de la rue i passer par l’intersection pi temps de sécurité pour véhicules provenant de la rue i si−j temps de rouge intégral succédant à une phase de vert pour la rue i et précédant une phase de vert pour la rue j vi−j la date de début de la kème phase de rouge intégral succédant à une phase de vert pour la rue i et précédant une phase de vert pour la rue j xi−j la date de fin de la kème phase de rouge inté- gral succédant à une phase de vert pour la rue i et précédant une phase de vert pour la rue j B. Formalisation du Problème A travers le modèle RdP, nous définissons ici le problème d’une manière formelle. Soit ni est le nombre des véhicules présents dans la rue i à l’instant t. Le temps nécessaire pour évacuer tous les véhicules venant de la rue i est: Ci = vi(ni) = vi(ui(t)) Donc pour évacuer les véhicules des deux rues revient à chercher: max(C1, C2) = max(v1(u1(t)), v2(u2(t))) = max(v1(n1), v2(n2)) Minimiser la somme des temps d’attente des véhicules prior- itaires revient à chercher: j wj · Tj = j wj · (vi(j) − ui(j)) où Tj = vi(j) − ui(j) est le temps d’attente d’un véhicule j appartenant à la rue i: Le système de régulation est informé sur le temps de présence des véhicules (ui(k)), les temps inter-véhiculaires admis (pi et s) et les poids attribués aux différents termes de la fonction ob- jectif (wj, α et β). Ainsi le problème est défini comme suit: Donnée du problème: ui(k), pi et s avec pi < s; wj, α, β Objectif: Calculer vi(k) pour k ∈ [1, ni], i ∈ [1, 2] min{α j wj · Tj + β max Ci} (3) Sous les contraintes suivants:    vi(k) ≥ 0 vi(k) ≥ ui(k) vi(k′ + 1) − vi(k′ ) ≥ pi, pour k′ ∈ [1, ni − 1] |vi(ki) − vj(kj)| ≥ s, pour ki ∈ [1, ni], kj ∈ [1, nj] et i = j, i, j ∈ [1, 2] IV. RÉSOLUTION DU PROBLÈME Nous proposons comme dans les travaux précédents une ap- proche basée sur la programmation dynamique. Cette approche garantit l’optimalité dans le cadre de la minimisation du temps d’évacuation des véhicules [13]. Pour généraliser cette approche au problème multicritère (3), nous procédons à la définition de la fenêtre de temps admissible. Ceci nous permet de limiter notre espace de recherche. A. Programmation dynamique D’abord, rappelons le principe de l’algorithme programma- tion dynamique. Il s’agit d’un algorithme qui décompose le problème d’origine en sous problèmes. La solution optimale du problème origine contient des solutions optimales aux sous problèmes. Chaque sous-problème est décomposé à son tour de la même manière jusqu’à l’arrivée au traitement de l’ensemble des sous problèmes élémentaires. Supposons que le problème posé est de traiter n arrivées de véhicules. Pour tout k ∈ [1, n] et tout tk ∈ T , F(k, tk) désigne le coût du problème : e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 • à la kème arrivée du véhicule • le dernier véhicule traverse l’intersection à l’instant tk • le coût de cette traversée est évalué à fk Puisque le dernier véhicule traité est k, le coût F(k, tk) peut être exprimé de la manière suivante: F(k, tk) = F(k − 1, tk−1) + fk où tk−1 < tk. Ainsi, F(k, tk) peut être décomposé en sous- problèmes de F(k − 1, tk−1). De la même manière, pour ré- soudre le problème F(k − 1, tk−1), nous avons besoin de con- tinuer la décomposition de F(k − 1, tk−1) en sous-problèmes du problème F(k − 2, tk−2). Cette décomposition se pour- suit jusqu’au problème F(1, t1). Le problème F(1, t1) peut être facilement traité. Ensuite, en inversant le processus de dé- composition, on obtient l’ordre de passage des véhicules pour le problème F(k, tk). A partir de ce principe, nous définissons dans ce qui suit la formulation des sous-problèmes traités. Soient les notations du tableau II. Soit G(q1, q2, g, t) le coût de la commande des feux quand nous avons q1 véhicules dans la rue 1 et q2 véhicules dans la rue concurrente, sous les contraintes suivantes: • Le dernier véhicule qui passe l’intersection appartient à la rue g • Le temps d’évacuation de ces véhicules est égal à t ∈ T . Bien évidemment t est le temps mesuré lorsque le dernier véhicule traverse l’intersection • t ≥ r(g,qg ); Sinon G(q1, q2, g, t) = ∞ T est la fenêtre de temps admissible pour t. Avant de présenter la stratégie de commande, nous utilisons les variables et les unités présentées dans le tableau II. Pour résoudre le problème, nous avons besoins, à chaque seconde, des informations sur la situation du trafic, comme le nombre de véhicules sur chaque route, le temps d’arrivée des véhicules et ainsi de suite. TABLE II NOTATIONS variable définition g l’indice de la rue, g = 1, 2 ng le nombre de vehicule dans la rue g (g, qg) le qg ème vehicule dans la rue g, 1 ≤ qg ≤ ng r(g,qg) le temps d’arrivée du véhicule (g, qg) p le temps inter-véhiculaire minimal admis pour sécurité w(g,qg) le poids du véhicule (g, qg) s l’intervalle de temps séparant les accès succes- sifs au carrefour par deux véhicules appartenant à deux flux différents Le processus de décomposition récursive est donné comme suit: Pour chaque élément G(q1, q2, g, t), G(q1, q2, g, t) = min t′∈T {G(q′ 1, q′ 2, g′ , t′ )} +α · w(g,qg ) · {t − r(g,qg)} + β · t (4) où q′ f = qf pour f = g, q′ g = qg − 1; et t′ ≤ t − p, pour g′ = g t − s, pour g′ = g La solution optimale est: min{G(n1, n2, 1, t1), G(n1, n2, 2, t2)} (5) où t1, t2 ∈ T , t1 ≥ r(1,n1) et t2 ≥ r(2,n2). On décrémente systématiquement les valeurs de q1 et q2 dans l’équation de récurrence (4), jusqu’à ce qu’ils atteignent les sous problèmes élémentaires avec q1 = 1 ou 0 et q2 = 0 ou 1. On les appelle les états initiaux de la récursivité. L’initialisation est nécessaire avant de commencer le proces- sus de décomposition qui s’arrête lorsqu’il ne reste qu’un seul véhicule sur la route. Pour notre problème, il y a deux cas qui peuvent être con- sidérés comme initiaux: G(1, 0, 1, t1),G(0, 1, 2, t2) avec t1 ≥ r(1,1) et t2 ≥ r(2,1). Évidement, il y a un seul élément appar- tenant à chaque cas. Cela signifie que le coût de chaque sous- problème est déja déterminé. Pour G(1, 0, 1, t1) et G(0, 1, 2, t2), G(1, 0, 1, t1) = α · w(1,1) · (t1 − r(1,1)) + β · t1 G(0, 1, 2, t2) = α · w(2,1) · (t2 − r(2,1)) + β · t2 (6) Le lecteur constate que G(0, q2, 1, t) et G(q1, 0, 2, t) (où q1 ∈ [1, n1] et q2 ∈ [1, n2]) ne sont pas détaillés. En effet, ces deux cas ne sont pas possibles car ils comportent une contradiction. Prenant par exemple G(1, 0, 2, t), d’une part, il indique qu’il n’y a pas de véhicule sur la route 2 et, d’autre part, il désigne que le dernier véhicule qui traverse l’intersection provient de cette rue. De la même façon, G(0, 1, 1, t) peut être écarté car il est impossible. Nous notons ces deux cas impossibles de la façon suivante: G(0, q2, 1, t) = ∞ G(q1, 0, 2, t) = ∞ (7) B. Définition de la fenêtre de temps T Dans cette partie, nous traitons du temps d’évacuation en généralisant le lemme proposé par Baptiste [14]. L’objectif est de proposer la borne inférieure tmin du temps t et la borne supérieure tmax du temps t pour réduire le nombre des éléments en T . Lemme 1. Le temps autorisé pour traverser l’intersection t est dans l’ensemble: T = {rj + µp + νs, j ∈ [1, n], µ ∈ [0, n − 1], ν ∈ [0, n − 1]} Preuve. Supposons que le dernier véhicule des véhicules 1, . . . , k traverse l’intersection au temps rj + µp + νs, où j ∈ [1, k], µ ∈ [0, k − 1], ν ∈ [0, k − 1]. En fonction de la présence du véhicule suivant, nous avons seulement deux cas possible. Le véhicule suivant est prêt à traverser l’intersection immédiatement après le dernier kème véhicule, ce qui est noté e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 cas 1. Le cas 2 se présente quand le véhicule qui suit n’est pas encore prêt à traverser l’intersection. • Cas 1: Puisque ∃j ∈ [1, k−1] et ∃µ ∈ [0, k−1], ν ∈ [0, k−1], le dernier véhicule des véhicules 1, . . . , k traverse l’intersection au temps rj + µp + νs . Donc, le véhicule k + 1 commence à traverser l’intersection au temps: – si le dernier véhicule des véhicules 1, . . . , k et k + 1 appar- tiennent à la même rue. rj + (µ + 1)p + νs – sinon rj + µp + (ν + 1)s • Cas 2: Le temps où k + 1 commence à traverser l’intersection est rk+1. Selon les deux cas, le lemme est valide pour le véhicule k+1. 2 Propriété 1. La borne inférieure tmin = (n1 + n2 − 2)p + s. Preuve. Supposons que tous les véhicules arrivent à l’intersection en même temps 0s. Tous les véhicules peuvent passer l’intersection l’un après l’autre en respectant la distance inter-véhiculaire p, ce qui fait (n1 + n2 − 2)p. Le nombre min- imal de changement des feux est 1, ce qui impose l’addition du temps s. 2 Propriété 2. La borne supérieure tmax = max{rj} + (n1 + n2 − 1)s Preuve. Supposons le premier véhicule traverse l’intersection au temps max{rj}. Le nombre maximal de changement de feux est n1 + n2 − 1. Donc, le dernier véhicule passe au temps: tmax = max{rj} + (n1 + n2 − 1)s 2 La complexité temporelle de l’algorithme est donnée par théorème 1. Théorème 1. La complexité temporelle de l’algorithme est en O(n2 max{max{rj}, n}), où n est le nombre de véhicules. Preuve. • Selon propriétés 1 et 2, le nombre de l’ensemble T est tmax − tmin + 1, ce qui fait max{rj} + (n − 2) × (s − p) + 1 = O(max{max{rj}, n}); • le nombre de tout les problèmes G(q1, q2, g, t) pour un t pré- cis [13] est O(n2 ); • le nombre de tout les problèmes G(q1, q2, g, t) est: O(n2 max{max{rj}, n}). 2 C. Exemple Nous présentons un petit exemple numérique pour illustrer l’algorithme. Les valeurs des paramètres de l’exemple sont présentées ci-dessous: Il y a 4 véhicules dans la rue. Les temps de leurs ar- rivées sont indiqués dans la Fig.3. Chaque véhicule admet 2s d’espace inter-véhiculaire minimal (correspondant àla régle- mentation actuelle). p = 2, s = 5; α = 0.8, β = 0.2 Les poids des véhicules sont : w(1,1) = 1, w(1,2) = 3; w(2,1) = 3, w(2,2) = 1; L’objectif de la commande des feux est: min{G(2, 2, 1, t1), G(2, 2, 2, t2)} où t1, t2 ∈ T et t1 ≥ 7, t2 ≥ 7. Le lemme 1 nous donne: T = {rj + u · p + v · s, j ∈ [1, 4], u ∈ [0, 3], s ∈ [0, 3]} = [0, 28] Les propriétés 1 et 2 nous informent: tmin = (n1 + n2 − 2)p + s = 9 tmax = max{rj} + (n − 1)s = 22 Donc, T = [9, 22] Pour chaque t ∈ T , le processus de décomposition du prob- lème en sous-problèmes organisées sous la form d’un arbre bi- naire est montré dans la Fig. 5. La commande optimale est représentée dans la Fig.4 avec maxCj = 12s et wj · Tj = 18. 4 Rue 1 Rue 2 0 2 6 8 10 t(s) : véhicule orinaire : véhicule prioritaire Fig. 3. Temps d’arrivée 00 0 0 0 00 00 0 00 00 0 0 0 00 0 0 0 00 0 00 0 0 0 0 11 1 1 1 11 11 1 11 11 1 1 1 11 1 1 1 11 1 11 1 1 1 1 00000000000000000000000 0000000000000000000000000000000000000000000000 11111111111111111111111 1111111111111111111111111111111111111111111111 0000000000000000000000 00000000000 1111111111111111111111 11111111111 0000000000000000000000 00000000000 1111111111111111111111 11111111111 00000 0000000000 00000 11111 1111111111 11111 4 Rue 1 Rue 2 0 2 6 8 10 t(s)12 14 : feux rouge Fig. 4. Ordre de passage optimal V. PROCESSUS DE COMMANDE DES FEUX Dans le processus de la commande des feux, il est possi- ble d’utiliser l’algorithme dans IV et l’algorithme proposé dans [9] qui utilise la programmation dynamique pour minimiser le temps d’évacuation de tous les véhicules. e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 Optimal (2, 2, 1) (2, 2, 2) (1, 2, 1) (1, 2, 2) (2, 1, 1) (2, 1, 2) (0, 2, 1) (0, 2, 2) (1, 1, 1) (1, 1, 2) (2, 0, 1) (2, 0, 2) (0, 1, 1) (0, 1, 2) (1, 0, 1) (1, 0, 2) Fig. 5. Décomposition du prolème pour t précis Lorsqu’un nouveau véhicule arrive dans la zone du contrôle, l’algorithme recalcule la stratégie optimale. Premièrement, il faut juger si les véhicules arrivés sont des véhicules prioritaires. En absence de véhicules prioritaire, on choisit l’algorithme avec l’objectif min{maxCj} pour obtenir la stratégie opti- male. En leur présence, on choisit l’algorithme avec l’objectif min{ wj · Tj + maxCj} de manière à obtenir une stratégie optimale. Si aucun véhicule se présente, le processus de commande continue la planification adoptée précédemment. N YN Y Commande Optimale véhicle prioritaire? nouveau véhicle? min{ wj · Tj +maxCj} min{maxCj} Fig. 6. Commande du trafic aux niveau de l’intersection VI. RÉSULTATS DE SIMULATION Dans cette section, nous présentons les résultats de simulation pour la commande des feux d’une intersection simple. Nous utilisons VISSIM pour simuler le comportement des véhicules. Les simulations sont effectuées sur un Pentium IV 2.40 Ghz. Le débit de la rue 1 est λ1 véh/s (nombre de véhicules par sec- onde) et celui de la rue 2 est λ2 véh/s. Ces deux débits doivent satisfaire la condition suivante : 0 < λ1 + λ2 < 0.5 véh/s. l’approche traditionnelle basée sur les débits [15] est comparée à notre approche. Nous supposons que les arrivées des véhicules obéissent la distribution de Poisson. Nous appliquons le modèle de mou- vement véhiculaire présenté dans le modèle suivant [15]. Par 0 0.1 0.2 0.3 0.4 0.5 0 5 10 15 20 Somme de debit [veh/s] Tempsd’attentmoyen[s] Cycle fixe Notre methode Fig. 7. Temps d’attente moyen 0 0.1 0.2 0.3 0.4 0.5 0 1 2 3 4 5 6 7 8 9 Somme de debit [veh/s] Longueurdelafilled’attentemoyen[veh] Cycle fixe Notre methode Fig. 8. Longueur de la file d’attente moyen conséquent, l’accélération, le freinage et temps de réaction du conducteur (≈ 1s) sont détenues pour la simulation. La durée de la simulation est 4 minutes. On évalue la perfor- mance par deux critères: le temps d’attente moyen et la longueur moyenne de la file d’attente. Chaque point dans cette figure représente la moyenne des valeurs de plusieurs simulations. Fig.7 montre le temps d’attente moyen par véhicule dans les deux rues. On constate que notre méthode réduit efficacement les temps d’attente moyens. Les résultats du nombre moyen de véhicules en attente à chaque seconde sur les deux rues sont montrés dans Fig.8. Lorsque le débit est inférieur à 0.3 véh/s, les longueurs moyenne de file d’attente de deux méthodes sont presque le même, cependant, lorsque le débit augmente, notre méthode offre un meilleur rendement. Ces expériences prouvent que notre approche peut efficace- ment réduire le temps d’attente des véhicules dans les deux rues. Ainsi, notre approche permet d’évacuer les véhicules le plus tôt possible, ce qui est évident car le modèle est plus précis. Ces expériences prouvent que notre approche peut efficace- ment réduire le temps d’attente des véhicules dans les deux rues. Ainsi, notre approche permet d’évacuer les véhicules le plus tôt plus possible, ce qui est évident car le modèle est plus précis. e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35 VII. CONCLUSION Dans ce papier nous avons étendu notre méthode de régula- tion des carrefours à la prise en considération des véhicules pri- oritaires. Ceci nous a mis face à deux objectifs, à savoir, réduire le temps d’attente de ces véhicules et évacuer au plus tôt tous les autres véhicules. Afin de répondre aux exigences du temps réel, nous avons extrait un seul objectif. Nous avons aussi étendu l’algorithme de commande. Les résultats de simulation mon- trent qu’il reste intéressant de considérer les véhicules d’une manière individuelle dans les hypothèses d’une intersection élé- mentaire. Ces résultats encourageants nous ouvrent plusieurs perspectives de recherche. Nous citons à titre d’exemple la généralisation de l’approche à un carrefour complexe tel ren- contré dans la réalité. RÉFÉRENCES [1] Chard B.M. et Lines C.J. Transyt-the latest developments. Traffic engi- neering and control, 28:387–390, 1987. [2] Dennis I.Robertson et R.David Bretherton. Optimizing networks of traffic signals in real time-the scoot method. IEEE Transacations on Vehicular Technology, 4(1):11–15, February 1991. [3] J.J.Henry, J.L.Farges, et J.Tuffal. The prodyn real time traffic algorithm. Proc. 4th IFAC/IFORS Conf. Control Transportation System, pages 305– 309, 1983. [4] A.G.Sims et K.W.DOBINSON. Implementation of the opac adaptive con- trol strategy in a traffic signal network. IEEE Intelligent Transactions Sys- tems Conference Proceedings, pages 25–29, August 2001. [5] A.G.Sims et K.W.DOBINSON. The sydney coordinated adaptive traf- fic(scat) system philosophy and benefits. IEEE Transactions on vehicular technology, VT-29:130–137, May 1980. [6] Dresner Kurt et Stone Peter. Traffic intersections of the future. The Twenty- First National Conference on Artificial Intelligence, NECTARTrack (AAAI 06), pages 1593–1596, 2006. [7] Dresner Kurt et Stone Peter. Multiagent traffic management: a reservation- based intersection control mechanism. Autonomous Agents and Multiagent Systems,2004.AAMAS 2004.Proceedings of the Third International Joint Conference on, pages 530–537, 2004. [8] Aurélien Corréïa, Abdeljalil Abbas Turki, Rachid Bouyekhf, et Abdellah El Moudni. A (max,+)-linear model for the analysis of urban traffic net- works. in 10th IEEE international conference on Emerging Technologies and Factory Automation (ETFA), Catania, Italy, Sept, 2005. [9] Jia Wu, Abdeljalil Abbas Turki, Aurélien Corréïa, , et Abdellah El Moudni. Discrete intersection signal control. IEEE International Con- ference on Service Operations and Logistics and Informatics 2007, pages 1–6, 2007. [10] Jia Wu, Abdeljalil Abbas Turki, Aurélienand Corréïa, et Abdellah El Moudni. Controlling a discrete model of twocascading intersec- tions. Workshop International: Logistiiaue & Transport 2007, Nov 18-20, Sousse, Tunisie. [11] Jia Wu, Abdeljalil Abbas Turki, et Abdellah El Moudni. Régulation du trafic aux intersections: Prise en compte des véhicules prioritaires. Con- férence Internationale Francophone d’Automatique, Sep 3-5, 2008, Bu- carest, Roumanie. [12] T’Kindt De Vincent et Billaut Jean-Charles. Multicriteria SchedulingThe- ory, Models and Algorithms. Springer, 2002. [13] Jia Wu, Abdeljalil Abbas Turki, et Abdellah El Moudni. Discrete methods for urban intersection traffic controlling. IEEE Transactions on Intelligent Transportation Systems,submitted. [14] P.Baptise. Batchin identical jobs. Math. methods Oper. Res. 52(2000) 355-367. [15] Simon Cohen. Ingénierie du trafic routier:éléments de théorie du trafic et applications. Presse de l’Ecole nationale des points et chaussées, 1993. e-STA copyright 2009 by see Volume 6, N°1, pp 29 - 35