Soutenance mémoire
État de l’art : la variabilité des temps de parcours
La variabilité des temps de parcours est une notion qui focalise de plus en plus l’attention des spécialistes de l’ingénierie du trafic, chercheurs comme gestionnaires de réseaux de transport, au regard de l’impact qu’elle peut avoir sur les choix d’itinéraire des usagers. À ce titre, ce premier chapitre va s’attacher à expliciter sa signification ainsi qu’à déterminer les grands enjeux qui y sont liés en matière d’amélioration des réseaux de transport. L’interrogation première associée à cette problématique concerne la fiabilité de la qualité de service, et donc des temps de parcours, qui est devenue un critère aussi important que la gestion des capacités, de la sécurité ou la gestion budgétaire pour les exploitants de réseaux de transport [12]. Il est communément admis de distinguer la fiabilité selon deux points de vue : celui du gestionnaire du réseau et celui des usagers du réseau. Le premier juge la fiabilité à l’aune de la qualité du service proposé, quel que soit le mode de transport et le réseau considéré, ou le moment auquel il est emprunté [42]. Il est d’ailleurs soutenu dans cette démarche par les pouvoirs publics, qui érigent la fiabilité au rang d’objectif prépondérant [16]. L’usager du réseau, quant à lui, considère la fiabilité au regard du temps passé sur le trajet, et notamment l’incertitude associée au temps de parcours [20]. Les auteurs s’étant penchés sur le sujet définissent ainsi la fiabilité des temps de trajet en fonction de l’appartenance du moment d’arrivée à un intervalle de temps spécifié à l’avance [42, 43]. A ce propos, Emam et al. [43] ont proposé une nouvelle définition de la fiabilité permettant de considérer directement la vitesse expérimentée: un tronçon sur lequel les automobilistes peuvent rouler à la vitesse maximale autorisée sur le parcours (et donc, réaliser le temps de parcours minimal) est jugé 100% fiable.
Variabilité des temps de parcours
Collecte des données de temps de parcours
Quelle que soit l’approche retenue pour modéliser la variabilité des temps de parcours, il est nécessaire d’obtenir des jeux de données suffisamment représentatifs des conditions de circulation. Pour ce faire, plusieurs techniques sont utilisées : les premières collectes de données ont consisté à questionner des individus sur des trajets hypothétiques, et à leur faire évaluer le coût qu’ils pensaient subir du fait de retards ou d’incertitudes quant au temps de parcours. Par la suite, les techniques de recueil directes ou indirectes ont fait leur apparition. Elles consistent à mesurer les temps de parcours au moyen de différents dispositifs technologiques (boucles électromagnétiques, GPS, véhicules-traceurs, voire Bluetooth). Une distinction est ainsi faite entre les enquêtes de préférences déclarées (« Stated Preference ») et les mesures directes des préférences (« Revealed-Preference »), tantôt objectives ou subjectives. Une revue de littérature assez détaillée est fournie par Carrion et al. [20]. Une autre approche destinée à alimenter les modèles considère les techniques de simulation comme les plus pertinentes : elle est fondée sur le principe selon lequel les précédentes méthodes de collecte sont coûteuses, et amènent même potentiellement des problèmes de représentativité statistique. Quelques travaux utilisant la simulation seront ainsi également détaillés dans une troisième et dernière sous-section.
Enquêtes de préférences
Plus connue sous le terme de Stated-Preference (SP), cette classe de mesure renvoie à une méthodologie de collecte de donnée par enquêtes, lors desquelles les individus sont interrogés sur leur préférence en fonction de trajets hypothétiques. Typiquement, une enquête de type SP requiert un choix par l’individu entre deux trajets dont les caractéristiques principales sont la durée moyenne estimée, différentes réalisations montrant la variabilité subie sur celui-ci et enfin le coût supporté pour l’emprunter. Cette approche se décline récemment jusqu’aux procédés de ludification, visant à évaluer les comportements des usagers aux moyens de jeux reproduisant des conditions de conduite réelles. Dans notre contexte, il a été question d’appréhender les préférences individuelles entre temps de parcours et variabilité, au travers d’une fonction objectif optimisée par le biais d’un programme linéaire [77]. Par la suite, il a été question de construire un ratio de fiabilité rapportant la valorisation du temps de trajet à celle de sa variabilité [13]. La méta-analyse de Carrion et al. [20] recense les réalisations de cet indicateur dans l’état de l’art : les auteurs ont ainsi identifié 68 mesures différentes s’établissant entre 0.08 et près de 3.29, pour une valeur moyenne d’environ 1.2. La valeur monétaire associée au temps de parcours moyen est ainsi supérieure à celle de la variabilité à hauteur de 20%, mais la différence reste minime et suggère l’importance de cette dernière dans les décisions des individus. Armstrong et al. [4] ont bien insisté sur le caractère subjectif de cette évaluation au sein des fonctions d’utilité individuelle. Une méta-analyse proposée par Abrantes et al. [2] apporte également des éléments de réponse en synthétisant l’évaluation économique et les élasticités-prix des éléments constitutifs des déplacements (étapes, modes, spécificités locales, caractéristiques individuelles).
De nombreuses études ont cherché à déterminer les niveaux de préférence individuelle via une enquête de type SP. Jackson et al. [77] ont initialement proposé une forme simple de comparaison entre deux trajets hypothétiques caractérisés par un temps habituel et un délai possible . Un individu était alors caractérisé en fonction de son aversion au risque, qui l’orientait tantôt vers un parcours « sûr », tantôt vers un autre plus risqué où un retard pouvait survenir. Par la suite, d’autres auteurs ont proposé de nouvelles formes d’enquêtes dans lesquelles la présentation des alternatives s’est raffinée, impliquant d’autres modes de transport, la notion de coût monétaire, ou encore la mise en valeur plus claire des incertitudes sur les temps de trajet. Des alternatives caractérisées par des temps de parcours moyens ont également été proposées, de manière à pousser l’individu à choisir explicitement entre des niveaux différents de variabilité. À titre d’exemple, il est possible de citer deux contributions ayant proposé des designs originaux : d’un côté, Bates et al. [8] se sont penchés sur une problématique ferroviaire, et ont proposé une présentation circulaire des réalisations de temps de parcours, pour éviter toute impression d’ordre dans la liste de réalisations, et donc éviter l’introduction d’un biais dans la réponse. D’un autre côté, Hollander [72] a réalisé une enquête dans le cadre d’un service de bus interurbain basé à York, en Angleterre, dans laquelle il propose un choix entre deux services de bus différenciés par des couleurs. Dans cette dernière étude, les temps de parcours sont représentés par des barres dont la longueur et la position dépendent de la date de départ et de la durée du trajet.
Collecte de données sur le terrain
Cette seconde catégorie de collecte réfère à des temps de parcours réels. Des enquêtes comparables à celles évoquées dans le paragraphe précédent existent qui correspondent à des mesures réelles, le terme consacré étant Revealed-Preference, ou RP. La quantification de la variabilité est alors tantôt issue de la perception des individus sur leurs trajets passés (on parle ici de mesure subjective), tantôt issue de dispositifs techniques installés sur le bord des voies de transport ou à l’intérieur des véhicules (on parle alors de mesure objective) [20]. La première catégorie est assez peu présente dans la littérature, ce qui pourrait s’expliquer par le niveau de fiabilité des mesures, à corriger par un facteur aléatoire matérialisant l’erreur d’estimation propre à chaque individu. Au sein du corpus de publications étudiées, seule la contribution de Börjesson et al. [16] propose une méthode assimilable à la première approche. Ainsi, les auteurs ont transmis un questionnaire aux usagers des lignes de métro et de train sur l’agglomération de Stockholm afin d’obtenir des renseignements sur leurs trajets personnels. Cependant, cette partie de l’étude a essentiellement servi de première étape pour la suite de l’étude, qui a consisté en une enquête de type SP dont les alternatives était calées sur le trajet personnel des répondants : les notions de temps de parcours, de date de départ ou de coût étant relatives à celles rencontrées réellement par les individus. Les méthodes objectives de type RP sont également peu nombreuses, eu égard à la difficulté d’obtenir des données mettant en concurrence deux routes différentes [20]. Il est tout de même possible d’identifier deux séries d’études utilisant la technique d’enquête des préférences révélées : une première série focalisée sur la route SR91 en Californie (par exemple, [96]) et une seconde série centrée sur un tronçon situé à Minneapolis, dans le Minnesota (voir par exemple [21]). La particularité de ces deux axes est qu’ils permettent aux utilisateurs un choix entre une route gratuite classique, potentiellement sujette à de la congestion, et une route à péage de type High Occupancy Toll, dont le tarif évolue avec le niveau de fréquentation pour assurer une circulation la plus fluide possible. Il est alors possible de considérer qu’un utilisateur empruntant le péage juge le gain de temps et de fiabilité obtenu plus précieux que la valeur du ticket d’entrée sur la route payante.
|
Table des matières
Introduction générale
I Modélisation statistique des temps de parcours et de leur variabilité
1 État de l’art : la variabilité des temps de parcours
1.1 Variabilité des temps de parcours
1.1.1 Collecte des données de temps de parcours
1.1.2 La variabilité à l’aune des préférences individuelles
1.2 Indicateurs de performance statistique
1.2.1 Approche synthétique de la construction d’un indicateur de fiabilité
1.2.2 Recherche de lois de probabilité pour les temps de parcours
2 Modélisation statistique des temps de parcours
2.1 Lois de Halphen et estimation par les ratios de moments
2.1.1 Construction du diagramme de ratios des moments
2.1.2 Système de Halphen et diagramme de ratio de moments
2.1.3 Estimateurs des paramètres des lois de la famille de Halphen
2.1.4 Autres lois usuelles pour la modélisation des temps de parcours
2.2 Méthodologie de la modélisation statistique des temps de parcours
2.2.1 Présentation des données empiriques
2.2.2 Temps de parcours, ou délais ?
2.3 Les ratios de moments comme métriques de fiabilité
2.3.1 Mesurer la fiabilité avec des indicateurs simples
2.3.2 Classification des indicateurs de fiabilité des temps de parcours
2.3.3 Évolution temporelle des distributions de temps de parcours
2.4 Ajustement des temps de parcours sur un segment
2.4.1 Éléments méthodologiques
2.4.2 Résultats d’ajustement
2.5 Extension de la modélisation à l’échelle de l’itinéraire
2.5.1 Méthodologie
2.5.2 Analyse empirique de la loi d’une somme de distributions
Contributions de la partie I
II Les modèles statistiques des temps de parcours dans le calcul du plus court chemin
3 État de l’art : les PCC stochastiques
3.1 Définition du problème et forme de la fonction objectif
3.1.1 Travaux fondateurs
3.1.2 Formulation LET
3.1.3 Formulation SSPP
3.1.4 Formulation SPOTAR/SOTA
3.1.5 Autres variantes rencontrées
3.2 Méthodes de résolution
3.2.1 Programmes d’optimisation mathématique
3.2.2 Algorithmes de programmation dynamique
3.2.3 Algorithmes d’étiquetage
3.2.4 Autres techniques rencontrées
3.3 Représentation du poids des arcs dans le graphe
3.3.1 Utilisation de modèles probabilistes pour les poids des arcs
3.3.2 Corrélations entre les temps de parcours au sein du réseau
3.3.3 Approche par scénario
4 Calcul du PCC stochastique et lois de probabilité
4.1 Plus courts chemins stochastiques
4.1.1 Arcs stochastiques
4.1.2 Opérations de base sur les arcs stochastiques
4.1.3 Dominance stochastique et politiques de routage
4.1.4 Algorithme SPOTAR
4.2 Eléments méthodologiques et plan d’expérience
4.2.1 Présentation générale et vocabulaire
4.2.2 Facteurs de l’analyse
4.2.3 Indicateurs de comparaison
4.3 Résultats de l’analyse de sensibilité
4.3.1 Comparaison des chemins proposés par les modèles stochastiques
4.3.2 Comparaison entre modèle déterministe et modèles stochastiques
4.3.3 Proportion d’arcs communs entre les chemins optimaux
4.3.4 Évaluation des temps de calcul
Contributions de la partie II
III Mise en œuvre du calcul du plus court chemin stochastique pour des calculateurs d’itinéraires
5 Accélérer le calcul du PCC avec les CH
5.1 Phase de pré-traitement : hiérarchisation des nœuds
5.1.1 Critères de classement
5.1.2 Hiérarchisation des nœuds
5.1.3 Contraction du graphe et ajout de raccourcis
5.1.4 Raffinements algorithmiques
5.2 Phase de résolution de requêtes
5.2.1 Précisions liminaires
5.2.2 Algorithme de résolution de requêtes dans un graphe hiérarchisé
5.3 Extension au cas des graphes dynamiques
5.3.1 Fonctions de temps de parcours
5.3.2 Solutions algorithmiques
6 Implémentation des CH et analyse de sensibilité
6.1 Paramétrage des contractions hiérarchiques
6.1.1 Définition de la fonction de hiérarchisation
6.1.2 Sorties du modèle
6.2 Évaluation du paramétrage
6.2.1 Décomposition de la variance
6.2.2 Optimisation du temps de calcul global
6.3 Résultats empiriques
6.3.1 Données utilisées
6.3.2 Analyse des résultats par rapport aux coefficients de priorité
6.3.3 Recherche d’un ensemble optimal de coefficients
6.3.4 Mise en œuvre opérationnelle : graphe Ile-de-France (Mappy)
7 Extension stochastique des CH
7.1 Construction des chemins optimaux dans les graphes stochastiques
7.1.1 Opérations sur les chemins
7.1.2 Opérations sur les politiques de routage
7.2 Adaptation des contractions hiérarchiques aux graphes stochastiques
7.2.1 Phase de requêtage
7.2.2 Phase de pré-traitement : hiérarchisation et contraction
7.3 Résultats expérimentaux
7.3.1 Résultats de la technique d’accélération
7.3.2 Comparaisons avec une résolution sans accélération
7.3.3 Vers la recherche du chemin à temps de parcours garanti
Contributions de la partie III
Conclusion générale
