Grants and Contributions:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

Depuis 35 ans mon équipe a développé le savoir-faire sur l'application industrielle de la génération de colonnes qui permet de considérer seulement un nombre réduit de variables à la fois. Ceci a permis de développer GENCOL le premier algorithme optimal pour les horaires de pilotes d’avion et les conducteurs d’autobus. Des réductions de coûts de l’ordre de 5% ont donné l’avantage compétitif à Giro et AD OPT et permis leur croissance au niveau mondial. Les recherches ont aussi porté sur la réduction dynamique de l’ensemble des contraintes à considérer simultanément et l’élimination temporaire de variables (algorithme IPS). Il a permis de traiter les problèmes de rotations d’équipages aériens une semaine à la fois (10 000 vols) plutôt qu’une journée type et une autre réduction de coût de l’ordre de 5%.
Un premier objectif porte sur l’algorithme ISUD un simplexe en nombres entiers. Il commence avec une solution entière et produit une suite de solutions qui s’améliorent jusqu’à atteindre une solution optimale. Il utilise aussi l’agrégation de contraintes et l’élimination de variables comme IPS. Des problèmes de chauffeurs d’autobus et de pilotes d’avion de 500 000 variables ont été résolus, dans 95% des cas, beaucoup plus rapidement qu’avec CPLEX un des meilleurs logiciels de Branch and Bound. Il faut développer de nouvelles idées pour traiter le 5% qui reste et ajouter la génération de colonnes pour traiter de plus grands problèmes. On vise les problèmes mensuels de 50 000 vols.
Un second objectif de recherche sera de développer un système utilisant l’intelligence artificielle (IA) pour estimer la probabilité que les arcs entre deux tâches fassent partie de la solution d’un problème de rotations d’équipages aériens. Cette information sera utilisée par IPS et ISUD pour agréger les taches et éliminer des arcs pour accélérer les algorithmes.
Finalement, poursuivre la recherche fondamentale et le développement du savoir-faire sur l'application industrielle de la décomposition de Benders. Nous l’appliquons à l’intégration des problèmes de rotations d’équipage et de blocs mensuels. C’est une décomposition de Benders ou le problème maître et le sous-problème sont résolus par génération de colonnes. Dans cette décomposition avec quatre niveaux, il faut répartir l’effort de calcul entre les niveaux pour ne pas mettre beaucoup de temps pour faire de petites améliorations à un niveau quand il y en a de grosses à faire ailleurs. Les coupes de Benders transférant de l’information du problème de blocs mensuels au problème de rotations sont construites avec une solution duale du problème de blocs. Il y a un nombre extrêmement grand de solutions duales dans ce problème. Nous proposons un problème d’optimisation pour choisir une solution qui est centrale pour stabiliser le processus.