Un simulateur pour l'analyse du choix d'itinéraire dans les déplacements personnels

  • Thierry AERTS
  • Jean-Christophe CASTIAUX
  • Bernard FORTZ

    Thèse de l'étudiant: Master typesMaster en sciences mathématiques

    Résumé

    Ce mémoire s'inscrit dans le cadre de la recherche sur la modélisation du trafic urbain. Il s'agit de l'étude et de l'implémentation d'un simulateur dynamique, qui permettra d'analyser le choix d'itinéraire que fait un utilisateur. Ce simulateur corrige les modèles mathématiques déjà existants, mais limités dans le sens où ils ne tiennent pas compte des facteurs psychologiques et autres dans la détermination du chemin que va utiliser une personne pour se rendre d'un en droit à un autre.

    Dans un premier temps, nous étudierons la modélisation mathématique du trafic urbain. Après avoir vu comment représenter un réseau urbain sous forme de graphe et les fonctions de performance mesurant le coût lié à l'utilisation d'un arc de ce graphe, nous passons en revue les différentes sortes d'équilibre que l'on peut utiliser et nous motivons notre choix pour l'Equilibre Utilisateur. Cette définition de l'équilibre fait intervenir le fait qu'un utilisateur a une perception parfaite du réseau dans lequel il évolue, ce qui n'est jamais le cas en pratique.

    Nous introduisons le modèle en quatre étapes, qui est celui utilisé par la majorité des modèles mathématiques dans ce domaine. La première étape est celle de génération. Elle consiste à déterminer, pour chaque zone du réseau, le nombre de trajets partant et aboutissant à cette zone. Cette étape se fait généralement sur base d'études sociologiques et autres. La deuxième étape est celle de distribution. Elle consiste à déterminer, pour chaque origine et chaque destination possible, le nombre de trajets reliant ces deux zones. On obtient alors une matrice, appelée matrice Origine-Destination, dont l'élément (i,j) contient le nombre de trajets partant de la zone i et aboutissant à la zone j. Plusieurs façons de créer cette matrice sont étudiées : la méthode de Furness, les modèles gravitaires et les modèles entropiques. La troisième étape est celle du choix modal. Elle consiste à déterminer quelle proportion de personnes utilisent des moyens de transport individuels ou collectifs. Cette étape ne nous concerne pas directement, vu qu'on ne s'intéresse qu'au transport individuel. La quatrième étape est celle d'assignation. Elle consiste à assigner, sur chaque arc du graphe, un flot représentant le nombre de personnes utilisant cet arc. C'est cette étape qui retiendra le plus notre attention. On cherche à déterminer les flots à assigner pour que le réseau soit en équilibre.

    On introduit pour cela la transformée de Beckman, qui modélise le problème de recherche de l'équilibre d'un réseau. Au niveau de la résolution de ce problème, plusieurs méthodes sont abordées. Après avoir rappelé un algorithme de recherche des plus courts chemins dans un graphe et ce qu'est l'assignation "tout ou rien", nous introduisons deux heuristiques : la restriction de la capacité et l'assignation incrémentale. Malheureusement, celles-ci ne s'avèrent pas compétentes, car elles n'engendrent pas une situation d'équilibre satisfaisant à la définition de l'équilibre que l'on s'est donné. C'est cette méthode que nous avons implémentée dans un premier temps pour assigner des flots sur un réseau.

    Un autre problème est alors abordé : celui du calcul du plus court chemin avec pénalité pour arrivée en avance ou en retard. On étudie le problème ainsi qu'un algorithme de résolution, qui sera implémenté afin de calculer le score d'un utilisateur du simulateur.

    La deuxième partie de ce mémoire concerne l'implémentation de la méthode de Frank et Wolfe pour calculer les flots d'équilibre d'un réseau, ainsi que la réalisation d'un simulateur dynamique. Pour calculer la matrice Origine-Desination d'un réseau, nous utilisons un programme déjà existant (City) qui utilise un fichier contenant les données de la phase de génération. Nous avons alors implémenté la méthode de Frank et Wolfe, afin d'assigner les flots sur chaque arc du réseau. Nous disposons donc d'un réseau urbain dont les flots sont ceux d'équilibre, que le simulateur utilisera comme "toile de fond". Voici une description de ce simulateur :

    Dans un premier temps, l'utilisateur choisit un noeud origine et un noeud destination. Il est alors invité à entrer une approximation du temps qu'il mettra pour aller de cette origine à cette destination. L'algorithme de recherche du plus court chemin avec pénalité pour arrivée en avance ou en retard permettra de calculer un score basé sur cette approximation. Lorsque ces choix sont faits, l'utilisateur commence sont parcours dans le réseau. La route sur laquelle il se trouve est affichée à l'écran. Des panneaux et des points de repère lui permettent de se repérer dans le réseau. A l'arrivée d'un carrefour, il doit choisir la route sur laquelle il veut se diriger. Dans certains cas, les arcs deviennent, à l'approche d'un carrefour, des bandes directionnelles, limitant de ce fait le choix (à l'utilisateur de changer de bande suffisamment tôt …). Les feux tricolores sont également implémentés, ainsi que la possibilité de visionner un parcours déjà effectué. Le but pour l'utilisateur est de rejoindre la destination prévue en un temps le plus proche possible de l'approximation qu'il a introduite au début. On pourra plus tard prévoir une gestion d'évènements apparaissant de façon aléatoire sur le réseau, tels que accidents et perturbations atmosphériques, afin d'étudier les réactions de l'utilisateur en fonction de ces évènements. On peut également songer à prévoir des systèmes d'information de l'état du réseau, tels que Radio Data System, In Vehicule Navigation System, téléguidage par satellite, …

    Le Groupe de Recherche sur le Transport de Namur pourra donc se baser sur ce mémoire pour construire un simulateur aussi réaliste que performant, voire futuriste, pouvant servir à l'amélioration de la situation du trafic dans nos villes.
    la date de réponsejuin 1993
    langue originaleFrançais
    L'institution diplômante
    • Universite de Namur
    SuperviseurPhilippe TOINT (Promoteur)

    Contient cette citation

    '