Direction de recherche : Michel MINOUX
Co-encadrement : NGUYEN Viet Hung

Modélisation et Optimisation des plans de feux - Application de la méthode de décomposition de Benders

L’objet principal de cette thèse, réalisée en collaboration avec la Société PHOENIX-ISI, consiste à développer un modèle de contrôle optimisé des feux de signalisation dans un réseau routier urbain. Il s’agit plus précisément de déterminer les plans de feux, c’est à dire pour chaque carrefour : durée du feu vert et décalage (offset) dans le cadre de réseaux de type axial (un itinéraire) ou de type maillé (par exemple, un quartier d’une agglomération). L’objectif (à minimiser) consiste à partir des données de circulation du réseau (débit entrant, répartition directionnelle des flux) et en utilisant un modèle de simulation de la propagation des flots de véhicules, à rechercher un plan de feux minimisant le retard total subi par les véhicules au cours de leur traversée du réseau. Le travail de recherche présenté ici se décompose en deux parties principales. La première partie consiste à développer un modèle de simulation de trafic permettant de représenter, de façon précise, l’écoulement des différents flux de trafic dans le réseau étudié pour un plan de feux quelconque fixé. La deuxième partie de la thèse est consacrée à la résolution algorithmique du problème MIP (problème en nombres entiers mixtes) élaboré dans la première partie. Nous proposons un algorithme basé sur la méthode de décomposition de Bender. Essentiellement, un tel algorithme doit résoudre un program linéaire de très grande taille à chaque itération afin de générer d’une coupe de Benders. Nous montrons que, pour notre problème MIP nous pouvons le faire de façon itérative (par une procédure de simulation inversée) et donc plus rapidement en exploitant une structure particulière de la matrice de contraintes. Nous présentons enfin une série d'expériences numériques prouvant l'efficacité de l'algorithme proposé.

Soutenance : 13/10/2010

Membres du jury :

Perny Patrice, Professeur, UPMC, LIP6
Lisser Abdel, Professeur, LRI, Université Paris-Sud 11, [Rapporteur]
Haj-Salem Habib, Directeur de recherche - HDR, INRETS/GRETIA, "Le Descartes 2" [Rapporteur]
Lebacque Jean-Patrick, Ingénieur Général des Ponts et Chaussées, INRETS/GRETIA, "Le Descartes 2"
Minoux Michel, Professeur, UPMC, LIP6
Nguyen Viet-Hung, Maître de Conférences, UPMC, LIP6

Publications 2010

• 2010
  • M. Ngo : “Modélisation et Optimisation des plans de feux - Application de la méthode de décomposition de Benders”, soutenance de thèse, soutenance 13/10/2010, direction de recherche Minoux, Michel, co-encadrement : Nguyen, Viet Hung (2010)