Problèmes de reconfiguration des réseaux routiers urbains
Christophe Duhamel – Professeur agrégé, ISIMA, France
L'augmentation de la densité urbaine dans les villes de moyenne et grande taille induit une pression accrue sur les réseaux urbains publics (eau, électricité, assainissement, transport). Ces réseaux, et notamment le réseau routier urbain, ont une assise physique qui peut poser problème dans l'entretien et l'évolution dans le temps. Dans le cas du réseau routier, les impacts d'une inadéquation par rapport à des besoins croissants sont immédiats et les conséquences multiples : congestion, retards, pollution chimique, pollution sonore et dégradations, entre autre. Ce type de réseau se modélise naturellement sous la forme d'un graphe orienté fortement connexe. La forte connexité est une propriété fondamentale et nécessaire. Elle est d'autant plus critique que le réseau est faiblement maillé. C'est le cas notamment des centres historiques pour lesquels l'étroitesse des rues limite la possibilité de circulation dans les deux sens. C'est aussi une conséquence de politiques récentes en gestion urbaine qui visent à favoriser la présence de rues en sens unique.
Dans un premier temps, je présenterai le problème de recherche d'une forte orientation de coût minimal dans un graphe. Ce problème constitue le noyau des problèmes étudiés dans le cadre de ce projet. Il est NP-difficile pour la minimisation de la somme des plus courts chemins entre toute paire de sommets. Plusieurs modèles compacts peuvent être proposés. Ils permettent de résoudre des instances de taille limitée et ils seront comparés à une approche à base de génération de colonnes. Je présenterai aussi les résultats obtenus par un ensemble de métaheuristiques. Plusieurs extensions de ce problème ont également été étudiées. A titre d'exemple, la planification des déviations dans un réseau urbain en présence d'interruptions (arrêtés municipaux liés à des travaux de maintenance, des déménagements, des manifestations par exemple), la version multicritères et la considération de différents types de graphe et de leurs propriétés. Dans ce contexte, la restauration de la forte connexité est primordiale. Deux critères d'optimisation seront considérés : la somme des distances des plus courts chemins entre toute paire de sommet et le nombre d'arcs renversés. Un modèle bi-objectif sera proposé et les fronts Pareto-optimaux seront obtenus par la méthode epsilon-constraint. Des métaheuristiques multiobjectif adaptées au problème seront présentées. L'ensemble des méthodes ont été testées et comparées sur des instances réalistes.
J'aborderai les défis algorithmiques liés à la taille des instances, au grand volume de données dans le cas de l'analyse de trafic et des émissions de CO2. D'un point de vue mathématique, j'exposerai certains problèmes qui restent ouverts et je présenterai la problématique de l'enrichissement des métaheuristiques par des techniques développées en machine learning.
-----
Entrée gratuite.
Bienvenue à tous!
