Grant: Discovery Grants Program - Individual

Les problèmes d'itinéraires et d'horaires peuvent être formulés à l'aide de modèles de flot multi-commodités en nombres entiers avec des contraintes liantes et des variables de ressource. Les commodités représentent les types de véhicule ou d'équipage et chacune définit un chemin élémentaire sur un réseau espace-temps. On exploite la structure de ces modèles avec des méthodes de décomposition mathématique, la plus utilisée étant celle de Dantzig-Wolfe (génération de colonnes), méthode linéaire que nous avons adaptée pour des cas non-linéaires et en nombres entiers. *Nos découvertes récentes au GERAD (stabilisation des variables duales, algorithme amélioré du simplexe (IPS), agrégation dynamique de contraintes (DCA), règle du positive edge) nous permettent de reconnaitre que la dégénérescence primale en programmation linéaire peut devenir un avantage algorithmique alors qu'elle était considérée depuis 60 ans comme la difficulté la plus importante lors de la résolution des problèmes linéaires. Le projet de recherche consiste d'abord à examiner les effets obtenus sur les problèmes de réseau, notamment à développer un nouvel algorithme fortement polynomial pour cette classe de problèmes en exploitant les propriétés primales et duales du problème résiduel obtenu à chaque étape d'un processus itératif. Ce nouvel algorithme est semblable au Minimum mean cycle-canceling algorithm (MMCC) et réalise O(mn) phases sur un réseau avec m arcs et n noeuds. Les problèmes de réseau étant au cour de toutes les applications industrielles de confection de routes de véhicules et d'horaires d'équipes de travail, une meilleure compréhension des mécanismes de résolution de ceux-ci devrait par la suite nous permettre d'élaborer une nouvelle famille d'algorithmes exacts en programmation linéaire et entière. On devrait également voir un impact important sur le design des méthodes heuristiques au cour de tous les systèmes d'optimisation utilisés en pratique. Les développements réalisés seront intégrés à l'optimiseur GENCOL, moteur de plusieurs logiciels distribués mondialement par GIRO pour les horaires des chauffeurs d'autobus en transport urbain et scolaire, et par AD OPT pour la gestion des opérations en transport aérien et ferroviaire. *Enfin, l'analyse d'IPS et de DCA montre que ces méthodes séparent l'espace des contraintes d'un problème linéaire en deux sous-espaces vectoriels orthogonaux, différents selon la méthode utilisée. On peut généraliser ce résultat et obtenir que MMCC tout comme le simplexe primal sont issus d'une décomposition semblable. Nous déterminerons les propriétés de ce nouvel algorithme générique de décomposition de l'espace vectoriel qui, selon la base vectorielle utilisée, produit une algorithme qui peut cycler indéfiniment (simplexe primal), être fortement polynomial pour les problèmes de réseau (MMCC), donner un pivot non dégéné à chaque itération (IPS), ou représenter un compromis d'implantation efficace pour les problèmes de Set Partitioning (DCA).