Algorithmes pour un guidage optimal des usagers dans les réseaux de transport

Quelques définitions et notions liées au trafic

     Ces éléments classiques et généraux, on peut les trouver aussi d’une manière détaillée dans [1].
 La demande individuelle de déplacement : est le déplacement qu’un usager souhaite à réaliser. Cette demande est supposée réalisable au moins par rapport aux possibilités offertes par le réseau de relier son origine i à sa destination j.
 La demande globale de déplacement : est la somme des demandes individuelles. On la note généralement sous la forme d’une matrice de demande, appelée matrice Origine-Destination (OD).
 Le débit : on le note généralement Dij (t), il définit la demande de l’origine i vers la destination j à l’instant t.
 L’émission : notée Ei(t) c’est la demande totale à l’origine i, avec Ei(t) = ∑ Dij (t) j.
 L’attraction : notée Aj(t) désigne la demande totale vers la destination j, avec Aj(t) = ∑ Dij (t) i.
 L’option : notée p indique toute possibilité de déplacement entre une origine i et une destination j. Les options peuvent être décrites sous la forme d’itinéraires, de variantes ou autre.
 Le point de choix : est un lieu ou les usagers peuvent choisir entre différentes options pour atteindre leur destination. Les points de choix correspondent à des nœuds de réseau (les interactions sur un réseau réel).
 L’affectation du trafic : est le processus qui associe une demande de déplacement à une répartition de cette demande entre plusieurs options.
 Le réseau d’affectation : est le réseau sur lequel les usagers conçoivent leur déplacement c.à.d. celui sur lequel ils appréhendent les différentes options et effectuent leurs choix d’option.
 Le coefficient d’affectation : la proportion de la demande utilisant une option donnée est appelée coefficient d’affectation relatif a cette option. On note donc γpij (t) le coefficient d’affectation définissant la proportion de la demande de l’origine i vers la destination j qui empreinte l’option p à l’instant t. D’après la conservation des véhicules appliquée en un point de choix , ces coefficients vérifient la relation ∑ γpij (t)p∈Enij = 1, ∀ i, j, n, t.
 Le Modèle : un modèle est une représentation simplifiée d’une partie du monde réel qui se concentre sur certains éléments considérés comme importants d’un point de vue particulier. Les modèles sont, par conséquent, spécifiques au problème et au point de vue.
 Le guidage : se réfère à la proposition d’un ensemble de chemins ou de stratégies de cheminement entre un nœud origine et un nœud destination d’un réseau, en optimisant une fonction objective soumise à la demande de trafic et aux contraintes de capacité.

Modèles microscopiques de l’écoulement du trafic

     Les techniques de modélisation du trafic routier permettent aux gestionnaires des réseaux de transport de mieux exploiter leurs infrastructures et représentent ainsi des outils d’aide à la décision. En effet, les modèles permettent la prédiction de l’état du trafic. En prévenant les congestions et en détectant les incidents et accidents, ils offrent la possibilité de traiter et intervenir dans des délais de temps réduits. Comme nous l’avons précisé dans la section précédente il existe plusieurs types de modèles à différentes échelles qu’il convient de choisir en fonction du phénomène physique que l’on cherche à comprendre. Selon qu’on s’intéresse à l’écoulement global du trafic sur un réseau routier ou à des interactions locales entre quelques véhicules lors d’un changement de direction ou à l’approche d’une intersection, la question de spécification du niveau de détail est primordiale. Pour une raison liée à l’objectif des travaux de notre thèse, nous n’allons aborder dans cette section que les modèles microscopiques qui reflètent le comportement individuel des conducteurs interagissant avec les véhicules environnants. Avant d’exposer les différents modèles de cette famille, nous commençons d’abord par introduire les variables de base au niveau microscopique (le niveau du véhicule).

Light Robustness

     Une autre façon de détendre le conservatisme est donnée dans le concept de Light Robustness. Ce concept couple une optimisation robuste avec une approche simplifiée de programmation stochastique en deux étapes, et présente un certain nombre d’avantages importants en termes de flexibilité et de facilité d’utilisation. Cette approche à été proposée dans [85]. Ces auteurs ne sont intéressés que par des solutions qui ne sont pas trop conservatrices et, par conséquent, ajoutent une limite à la valeur nominale de la solution. Dans toutes les solutions qui satisfont cette contrainte, on choisit celle qui dévie moins les contraintes dans le pire des cas. Le concept a été appliqué à des problèmes de programmation linéaire et à des ensembles d’incertitude basés sur des intervalles. Dans une étude de cas, les auteurs de [85] montrent que leur approche convient aux problèmes de chronométrage. Depuis, l’idée de Light Robustness a été appliquée à un chronométrage rigoureux des chemins de fer dans [86], à l’information du calendrier dans [87]. Cette approche a été comparée à d’autres concepts de robustesse dans une étude sur le calendrier apériodique dans [89]. Light Robustness a également été mentionnée dans [102], et étudiée dans le cadre d’une approche unifiée pour la robustesse dans [90]. Dans [84], les auteurs ont étendu l’idée de Fischetti et Monaci et ont développé une notion générale de Light Robustness appelée Generalized Light Robustness qui s’applique à tous les types de problèmes d’optimisation et à des ensembles d’incertitude arbitraires.

Conclusion générale

      Les travaux réalisés dans cette thèse concernent le problème du guidage des usagers dans les réseaux routiers. Un algorithme de guidage a été développé et une nouvelle stratégie adaptative robuste a été proposée. Le travail a été basé sur un modèle de routage existant, qui est l’algorithme SOTA. Cet algorithme a été étendu pour tenir compte de la robustesse des stratégies de routage face à une faille qui peut survenir sur l’itinéraire. Afin d’inclure la possibilité ainsi que la performance d’éventuels détours alternatifs des chemins sélectionnés, le concept de fiabilité a été étendu en introduisant un nouvel indice de fiabilité. Les améliorations portées sur cet algorithme permettent de sélectionner un chemin optimal selon deux critères: la fiabilité du chemin en termes de temps de parcours et la robustesse du chemin en termes de flexibilité (c.-à-d. l’existence et la performance de détours alternatifs). L’algorithme développé a été testé en version statique (sans considérer la dynamique du trafic) et les simulations ont été exécutées sur le réseau connu de Sioux Falls. Ceci a permis de montrer quelques propriétés intéressantes de l’algorithme. L’algorithme de guidage robuste présenté dans ce travail a été ensuite combiné avec un modèle dynamique du trafic en boucle fermée, afin de voir comment l’algorithme réagit dynamiquement à l’état du trafic. Le simulateur de trafic microscopique SUMO (Simulation of Urban MObility) a été utilisé avec l’interface de contrôle du trafic TRACI (TRAffic Control Interface) sur laquelle l’algorithme de guidage proposé a été implémenté. Les résultats ont été illustrés sur le réseau Sioux Falls, et ont été comparés dans les deux aspects statique et dynamique, à ceux obtenus par l’approche SOTA de Samaranayake (2012). Ces résultats, aussi satisfaisant soient-ils, nous indiquent tout de même que la performance générale du réseau et de l’algorithme peut encore être améliorée en proposant une série de perspectives.

Table des matières

Introduction générale
Chapitre 1. Etat de l’art
Introduction
Partie 1. Variables et Modèles du trafic
1. Introduction
2. Quelques définitions et notions liées au trafic
3. Modélisation du trafic
3.1. La modélisation sur la base de gestion du temps
3.1.1. La modélisation statique
3.1.2. La modélisation dynamique
3.2. La modélisation sur la base des niveaux d’agrégation
3.2.1. La modélisation microscopique
3.2.2. La modélisation macroscopique
3.2.3. La modélisation mesoscopique
3.2.4. La modélisation sous-microscopique
3.3. Autres classification
3.3.1. La modélisation monomodale
3.3.2. La modélisation multimodale
3.3.3. La modélisation urbaine et interurbaine
3.4. Le modèle à quatre étapes
4. Les modèles microscopiques
4.1. Les variables de base des modèles microscopiques
4.2. Les principaux modèles microscopiques
4.2.1. Les modèles microscopiques longitudinaux
4.2.2. Les modèles microscopiques latéraux
5. Conclusion
Partie 2. Problèmes et algorithmes courants de plus court chemin
1. Introduction
2. Un bref historique sur la théorie des graphes
3. Notions et définitions générales
4. Méthodes de représentation d’un graphe
4.1. Liste des successeurs
4.2. Matrice d’adjacence
4.3. Matrice d’incidence
5. Le problème du plus court chemin
6. Graphes statiques
6.1. Graphes statiques déterministes
6.1.1. Définition
6.1.2. Problème du plus court chemin
6.1.3. Algorithme de résolution
6.2. Graphes statiques stochastiques
6.2.1. Définition
6.2.2. Problème du plus court chemin
6.2.3. Algorithme de résolution
7. Graphes dynamiques
7.1. Graphes dynamiques déterministes
7.1.1. Définition
7.1.2. Problème du plus court chemin
7.1.3. Algorithme de résolution
7.2. Graphes dynamiques stochastiques
7.2.1. Définition
7.2.2. Problème du plus court chemin
7.2.3. Algorithme de résolution
8. Conclusion
Partie 3. Optimisation robuste et critères de prise de décision dans un environnement incertain
1. Introduction
2. Les problèmes d’optimisations incertains
3. Concepts et critères de robustesse
3.1. Strict Robustness
3.2. Cardinality Contrained Robustness
3.3. Adjustable Robustness
3.4. Light Robustness
3.5. Recoverable Robustness
3.6. Regret Robustness
3.7. Quelques concepts de robustesse supplémentaires
3.7.1. Reliability
3.7.2. Soft Robustness
3.7.3. Comprehensive Robustness
3.7.4. Uncertainty feature optimization
4. Conclusion
Conclusion
Chapitre 2. Robust guidance
1. Introduction
2. Stochastic On Time Arrival (SOTA) problem
2.1. Formulation of SOTA problem with uncorrelated link travel-times
2.2. Formulation of SOTA problem with correlated link travel-times
2.3. An academic example
3. Robust guidance
3.1. Robust guidance without correlated link travel-times
3.1.1. Continuous-time formulation
3.1.1.1. The probability
3.1.1.2. The successor nodes
3.1.2. Discretization scheme of robust guidance algorithm
3.1.2.1. Complexity analysis
3.1.3. An academic example
3.1.4. Price of robust-optimality
3.2. Formulation of the algorithm in case of correlated link travel-times
4. How to fix the parameters ψp
5. Generalized algorithm for time-varying distributions
6. Static routing in Sioux Falls network
6.1. Scenario 1
6.2. Scenario2
7. Conclusion
Chapitre 3. Combination of the robust routing algorithm with dynamic traffic model
1. Introduction
2. How to proceed
3. Configuration of traffic simulation with SUMO
3.1. Edit and modify the network with JOSM
3.2. Import Sioux Falls network with NETCONVERT
3.3. Generate a single vehicle trips by OD2TRIPS
3.4. Generate a complete specification of the vehicles and their routes by DUA
3.5. Generate a sumo-Outputs by SUMO-GUI
3.6. Control by using Traffic Control Interface (TraCI)
4. The car-driver model
5. Dynamic travel-times estimation
5.1. Retrieve identifiers of 774 short edges
5.2. Calculate the estimated travel-times on the short edges
5.3. Calculate the travel-times on the big edges
6. Simulation procedure
7. Simulation results
8. Conclusion
Conclusion générale
Perspectives
Bibliographie

Télécharger le rapport complet