Réseau routier et génération des données de trafic

Systèmes utilisant des algorithmes génétiques

  Un algorithme génétique est une technique utilisée pour trouver des solutions à certains problèmes d’optimisation. Elle utilise des techniques inspirées de la sélection naturelle telles que la sélection, la recombinaison et la mutation. Chacune des solutions peut être représentée par un chromosome dans lequel est codée une solution du problème. À partir d’une population initiale de chromosomes, on sélectionne les meilleures solutions sur lesquelles sont effectuées les opérations de recombinaison et de mutation. Ces opérations fournissent une nouvelle génération de chromosome qui sera à son tour sujet aux trois opérations précédentes. Répétant ces étapes à plusieurs reprises, le principe de sélection naturelle est imité, trouvant de génération en génération, de meilleures solutions. Un mécanisme de niche peut être utilisé afin d’assurer que la population recherche dans différents espaces de solution. Dans le domaine militaire, un planificateur du nom de FOX-GA a été décrit par Hayes et al. [6]. Conçu pour assister les services de renseignements militaires, il contribue à la prise de décision sur un champ de bataille conventionnel (en campagne). En d’autres mots, il élabore des plans de bataille. FOX-GA a l’avantage d’offrir au commandant en place un plus grand nombre de plans alternatifs que les méthodes traditionnelles dans ce domaine : soit jusqu’à une quinzaine de plans au lieu des trois usuels (axe du centre, de gauche et de droite). Sa capacité de générer un grand nombre de plans jugés adéquats dans un court délai représente donc l’une des forces de ce planificateur. Un algorithme génétique est nécessaire à FOX-GA pour obtenir un tel résultat. L’algorithme contient un mécanisme de niche afin d’assurer la diversité des plans proposés. L’algorithme permet d’éliminer certaines combinaisons illégales, c’est-à-dire donnant des plans impossibles, en réparant les chromosomes erronés suivant des contraintes de faisabilités [7]. La justesse des plans est évaluée au moyen de simulations effectuées contre six plans ennemis créés par un expert. Ceux-ci n’étant pas évolutifs, le planificateur trouvera la faille dans les six plans et l’exploitera. Ceci constitue un handicap puisque l’ennemi n’effectuera pas nécessairement l’un des six plans suggérés. Le générateur de plan co-évolutionnaire proposé par Suantak et al. [8] vient pallier à cette faiblesse. Contrairement au modèle proposé précédemment, il permet une évolution à la fois des plans amis et ennemis. Ainsi, deux systèmes utilisant chacun un algorithme génétique s’opposent, générant tour à tour un meilleur plan exploitant les failles de son opposant.

Systèmes multiagents

  La littérature fait état d’une méthode de planification de plus en plus utilisée pour résoudre des problèmes complexes. Il s’agit des systèmes multiagents. Comme son nom l’indique, un système multiagent est composé de plusieurs d’agents autonomes interagissant entre eux dans le même environnement. Un agent peut être un robot, un programme informatique, un processus ou encore un être humain. L’important est que tous puissent communiquer entre eux efficacement. Lorsque les agents coopèrent entre eux, ils forment un système capable de formuler des plans dans des environnements très complexes. En d’autres mots, si plusieurs agents formulent des plans pour eux-mêmes, ils peuvent par la suite les partager et les coordonner afin de créer un plan global de qualité. Certains auteurs [10-12] ont qualifié un tel processus de coordination ou synergie. Ce type d’architecture apparaît particulièrement intéressant dans le cas qui nous préoccupe puisqu’il permettrait de coordonner plusieurs unités. Afin de maximiser la coordination entre les agents et plus particulièrement la fusion de plans venant de deux ou de plusieurs agents, une hiérarchisation des plans est couramment utilisée [10;13;14]. Lorsque qu’un plan effectué par un agent donne des résultats supérieurs ou semblables au plan venant d’un deuxième agent et que les coûts sont moindres, ces deux plans peuvent être fusionnés. Ainsi, le meilleur agent effectuera le plan et le second agent pourra être libéré de ce travail et ainsi remplir d’autres tâches. Sachant qu’un plan est constitué d’une série d’actions dont le nombre est parfois élevé, le plan devient difficile à définir et, par conséquent, à fusionner. Par contre, en utilisant une représentation à plusieurs niveaux d’abstraction (ou représentation hiérarchique), il est possible de travailler avec les informations les plus pertinentes et de descendre, au9 besoin, dans la hiérarchie (vers le niveau le moins abstrait). Cette technique facilite grandement le calcul

Assignation du trafic

  Une fois la matrice OD connue, la seconde étape dans l’obtention de données de trafic consiste à assigner le trafic dans le réseau. Il s’agit de représenter la perception qu’ont les conducteurs du réseau pour les diriger par la suite vers le chemin qu’ils auraient pris, c’est à dire le chemin qu’ils perçoivent le plus court. Cette étape est réalisable à partir d’un processus itératif où une portion du trafic contenu dans la matrice OD est assignée à chaque incrément. Les valeurs du réseau sont modifiées à chaque incrément et un équilibre est ainsi créé dans l’ensemble des chemins du réseau. Lors des premiers incréments, les conducteurs auront tendance à utiliser les grandes artères, ceux-ci étant généralement plus rapides dû à une limite de vitesse supérieure. Par contre, quelques incréments plus tard, ces artères seront congestionnées et des routes secondaires seront favorisées. À la fin de l’assignation, lorsque l’équilibre est atteint, l’ensemble des chemins devrait avoir un temps de parcours similaire. Quatre catégories d’assignation semblent possibles. Chacune d’elles se distingue par le type de nombre utilisé pour représenter le temps de parcours perçu. La première catégorie, user equilibrium (UE) utilise des nombres discrets [24]. Il s’agit de la méthode la plus simple et la plus rapide. L’hypothèse voulant que les conducteurs aient une information parfaite du réseau est le principal défaut de cette méthode. La seconde catégorie, fuzzy user equilibrium (FUE), comme son nom l’indique, fait appel à des nombres flous [16;19;25;26]. Quoiqu’un peu plus lente d’exécution que la méthode UE, elle représente mieux la réalité. En effet, autant la perception qu’ont deux conducteurs du réseau est différente, autant le sera leur décision : deux conducteurs partant du même endroit et se dirigeant au même point ne prendront pas nécessairement le même chemin. La troisième catégorie, stochastic user equilibrium (SUE), utilise des lois de la probabilité pour évaluer les temps de parcours [27-29]. Elle possède sensiblement les mêmes avantages et inconvénients que la méthode FUE. Une dernière technique, appelée hybrid user equilibrium (HUE), s’avère une combinaison des deux précédentes [30]. Un nombre flou est translaté sur l’échelle du temps en fonction d’une variable aléatoire. Les résultats provenant de cette technique ne montrent pas d’avantages significatifs par comparaison aux méthodes précédentes. La figure suivante illustre les quatre méthodes d’assignation.

Algorithme d’assignation

  L’algorithme de génération du trafic nécessite quelques explications. Il s’agit d’une méthode itérative où des vagues successives de véhicules sont assignées par le chemin le plus court. Ainsi, à chacune des itérations, une portion du trafic contenue dans chacune des paires OD de la matrice est assignée suivant le chemin le plus court. Dans le cas qui nous concerne, la matrice OD faisant 43 par 43, 1 849 paires OD sont à assigner à chacune des itérations. La figure 3 illustre la logique avec laquelle procède l’algorithme d’assignation.L’algorithme comprend deux boucles. Une première boucle agit sur l’ensemble des paires OD. Elle est imbriquée dans une seconde boucle ayant la même fonction, maispour les incréments de temps. Ne voulant laisser aucun avantage à une paire OD en particulier, l’algorithme est conçu pour calculer l’ensemble des chemins les plus courts avant de modifier les données de trafic. Ceci étant, lors du calcul de son chemin le plus court, une pair OD a des conditions identiques (données de trafic) aux 1 848 autres paires de la même itération. L’implémentation s’est faite dans une perspective multitâche et est décrite à l’annexe 1. Étant donné l’énormité des calculs nécessaires, l’utilisation d’un ordinateur multiprocesseur était inévitable pour l’obtention de résultats dans un délai raisonnable. La recherche de chemin est traitée comme une tâche, de telle sorte que les 1 849 chemins à trouver pour chacune des itérations peuvent 1’être en parallèle. Il en va de même pour la modification des données de trafic. Pour obtenir les résultats de quatre heures de trafic, cela prend environ 4 jours à un superordinateur comprenant 32 processeurs cadencés à 800 MHz.

Fonctionnement complet du module OptiEvents

  Les différentes parties du module ayant été discutées, passons maintenant à leur fonctionnement et aux relations qui les unissent. La meilleure façon d’exposer tous les mécanismes qui agissent dans le module est de procéder par un exemple. Supposons qu’un utilisateur entre dans le système et demande un chemin entre sa position actuelle et une destination quelconque. Si aucune menace n’est détectée, le système proposera à l’utilisateur le chemin le plus court ou le plus rapide, dépendamment de ses préférences. Ainsi, l’utilisateur se déplace suivant ce chemin. Pendant ce temps, l’OE vérifie la position de l’utilisateur ainsi que des différentes ressources et met à jour les attributs de la base de données. À un certain moment, une menace est repérée dans la ville. Automatiquement, le PHN de l’utilisateur vérifie si cette nouvelle menace peut perturber le parcours actuel. Dans ce but, le PHN fait appel aux données contenues dans l’OE. Plus particulièrement, il compare les valeurs des TTDM de l’utilisateur et de la menace pour les vertex du parcours de l’utilisateur. Si ceux de la menace sont plus petits que ceux de l’utilisateur (si la menace peut arriver avant l’utilisateur) alors nous avons possiblement un problème. Il doit donc trouver unefaçon d’éviter un contact entre les deux. Il envoie un message d’annonce de tâche à l’ensemble des agents, leur spécifiant ses demandes. Il spécifie l’ensemble des TP avec la menace s’y rattachant et leur demande d’empêcher cette menace d’arriver avant lui. Enfin, le PHN spécifie un temps limite pour soumettre les plans.Les différents agents reçoivent le message. S’ils sont disponibles, ils vérifient s’ils peuvent faire quelque chose pour aider l’utilisateur. Dépendamment du type de ressources, ils possèdent certaines actions envisageables. Pour chacune de ces actions, chacun des agents démarre un PBN. Les PBN fournissent les plans les plus simples. Si l’un de ces plans est en mesure de répondre à toutes les demandes de l’annonce de tâche, l’agent écrit à nouveau au PHN pour lui envoyer ce plan complet. Le PHN prendra alors la décision d’utiliser ou non ce plan. Dans l’affirmative, il renverra un message à l’ensemble des agents pour fermer le contrat contenu dans 1‘annonce de tâche précédente (terminant ainsi les recherches de plan par les PBN) et un second message contenant des ordres pour l’agent ayant trouvé le plan complet. Par contre, comme c’est généralement le cas, un plan simple ne pourra pas résoudre l’ensemble des problèmes causés par une menace. Il faudra plus souvent qu’autrement fusionner plusieurs plans partiels pour en obtenir un plus complexe, mais certes plus efficace. Ainsi, au fur et à mesure que les PBN trouvent des plans partiels, ils les envoient à l’UP relatif à l’utilisateur. Rappelons que l’UP a pour mission de fusionner plusieurs plans simples en un plan plus complexe. Si l’UP trouve un plan complet, il l’envoie au PHN pour que celui-ci prenne une décision. Si le PHN décide d’exécuter ce plan, il ferme le contrat et envoie les ordres d’une manière similaire à celle déjà vue. Par contre, il devra décomposer le plan en sous-plans, pour l’envoyer à toutes les ressources impliquées. Ceci est fait grâce à l’attribut sous-plans contenu dans l’objet plan. Par contre, si l’UP n’arrive pas à trouver un plan complet, il devra se contenter du meilleur plan partiel trouvé à l’heure limite fixée dans l’annonce de tâche. Les plans sont évalués en fonction de leur pointage. Si pendant l’exécution des ordres, des informations supplémentaires sont rapportées, alors les étapes précédentes sont répétées. Par exemple, si une seconde menace est repérée, le PHN recommencera en fonction des deux menaces. De la même manière, si la première menace est repérée à nouveau, le PHN devra encore vérifier sa planification ultérieure. En effet, peut-être certaines actions préalablement amorcées ne sont plus d’aucune utilité compte tenu des derniers renseignements. Peut-être ces ressources pourraient être utilisées autrement, d’où 1’utilité de recommencer la planification.

Table des matières

SOMMAIRE
ABSTRACT
REMERCIEMENTS
LISTE DES TABLEAUX
LISTE DES FIGURES
LISTE DES ABRÉVIATIONS ET DES SIGLES
INTRODUCTION
CHAPITRE 1 PLANIFICATION D’ACTIONS ET SIMULATION DE TRAFIC
1.1ÉTAT DE L’ART 
1.1.1Algorithme de planification
1.1.2Systèmes utilisant des algorithmes génétiques
1.2Systèmes multiagents
1.2.1 Simulation du trafic urbain
1.2.2 Matrice origine-destination
1.2.3 Assignation du trafic
1.2.4 Méthode de saisie de données réelles
1.3Simulation d’un barrage routier
1.4 Conclusion
CHAPITRE 2 RÉSEAU ROUTIER ET GÉNÉRATION DES DONNÉES DE TRAFIC
2.1 Réseau routier
2.2 Génération de données de trafic 
2.2.1Matrice OD
2.2.2Fonction vitesse-véhicules
2.2.3Algorithme d’assignation
2.3 Données réelles de la ville de Québec
2.4 Conclusion
CHAPITRE 3 SIMULATION D’UN BARRAGE ROUTIER 
3.1 Choix de l’algorithme de simulation
3.2 Description de l’algorithme de simulation 
3.2.1 Estimation de la matrice OD
3.2.2 Soustraction des véhicules
3.2.3 Réassignation
3.3 Réalisation du simulateur 
3.4 Conclusion
CHAPITRE 4 PLANIFICATION D’ACTIONS
4.1 Planificateur de haut niveau
4.2 Planificateur de bas niveau
4.3 Structure du module OptiEvents
4.3.1 Observateur d’environnement
4.3.2 Unificateur de plans
4.3.3 Communication
4.4 Fonctionnement complet du module OptiEvents 
4.5 Implémentation du module OptiEvents
4.6 Conclusion
CHAPITRE 5 RÉSULTATS ET DISCUSSION
5.1 Génération des données de trafic
5.2 Simulateurs de barrage routier 
5.3 Planificateur 
5.4 Conclusion
CHAPITRE 6 CONCLUSION ET RECOMMANDATIONS 
ANNEXE 1 Implémentation JAVA de la génération de trafic automobile
ANNEXE 2 Implémentation JAVA de la simulation d’un barrage routier
ANNEXE 3 Implémentation JAVA du module OptiEvents
ANNEXE 4 Algorithme de visualisation
BIBLIOGRAPHIE

Télécharger le rapport complet