Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$50,000.00

Nouvelles méthodes de décomposition mathématiques pour les grands problèmes d'horaires de véhicules, de personnels et de production

EF 2023-24

Résumé
Depuis 40 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 les premiers algorithmes optimaux pour les horaires d'équipages aériens et de chauffeurs d'autobus. Des réductions de couts de l'ordre de 5% ont donné l'avantage compétitif à Giro et AD OPT et permis leur croissance au niveau mondial. Pour le problème de partitionnement, les recherches ont porté, sur la réduction dynamique de l'ensemble des contraintes à considérer simultanément et l'élimination temporaire de variables (algorithmes DCA) qui permet de traiter des problèmes plus grands. Elles ont aussi porté sur le simplexe en nombres entiers (ISUD) qui produit une suite de solutions entières de couts décroissants, ce qui permet d'améliorer la solution durant tout le temps disponible. Un premier objectif est de poursuivre les recherches sur ISUD pour passer de 2 000 à 20 000 contraintes. Il sera expérimenté sur les grands problèmes d'équipages aériens et sur les routes d'autobus en traitant simultanément 20 dépôts plutôt qu'un seul. Un second objectif du présent projet est de développer des algorithmes aussi efficaces que DCA et ISUD pour les problèmes de recouvrement généralisé ou il faut couvrir plusieurs fois chaque tâches (des agents de bord sur un vol). Un troisième groupe d'objectifs porte sur de nouvelles méthodes de décomposition pour des grands problèmes combinant plusieurs groupes de contraintes complexes. La génération de colonnes traite 2 niveaux, on va traiter 3 - 4 niveaux. On a d'abord l'intégration des problèmes de routes d'autobus et d'horaires de chauffeurs qui sont chacun résolus par génération de colonnes. On réalisera une décomposition lagrangienne ou on ajoute au problème d'autobus les couts réduits des chauffeurs et aux chauffeurs les couts réduits des autobus. On a ensuite l'ajout aux problèmes de rotations d'équipages aériens des blocs de contraintes demandant de garder les agents de bord en équipes durant une rotation ou demandant de répéter chaque rotation autant que possible durant le mois. On développera des décompositions qui échangent des informations entre ces nouvelles contraintes et le problème de base. On a aussi une nouvelle décomposition de Benders pour optimiser pour l'Office des Phosphates du Maroc, la chaine de transformation du minerai en plusieurs types d'engrais dans plusieurs usines, l'entreposage et le chargement des bateaux pour remplir des commandes. On remplace la linéarisation externe qui ajoute des contraintes par une linéarisation interne qui ajoute des variables dans le problème. On a finalement une décomposition pour le problème de planification de projet avec contraintes de ressource qui sera expérimenté sur l'entretien des navires de la marine canadienne. Ce projet combine des développements en science fondamentale et leur application sur de grands problèmes industriels.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2023-05706
Name nom
Soumis, François
Department département
Département de mathématiques et de génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
50000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Nouvelles méthodes de décomposition mathématiques pour les grands problèmes d'horaires de véhicules, de personnels et de production
Keyword
Agrégation de contraintes; Décomposition; Décomposition de Benders; Décomposition de Dantzig-Wolfe; Décomposition lagrangienne; Génération de colonnes; Optimisation; Programmation en nombres entiers; Programmation Mathématique; Transport aérien
Application summary
Depuis 40 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 les premiers algorithmes optimaux pour les horaires d'équipages aériens et de chauffeurs d'autobus. Des réductions de couts de l'ordre de 5% ont donné l'avantage compétitif à Giro et AD OPT et permis leur croissance au niveau mondial. Pour le problème de partitionnement, les recherches ont porté, sur la réduction dynamique de l'ensemble des contraintes à considérer simultanément et l'élimination temporaire de variables (algorithmes DCA) qui permet de traiter des problèmes plus grands. Elles ont aussi porté sur le simplexe en nombres entiers (ISUD) qui produit une suite de solutions entières de couts décroissants, ce qui permet d'améliorer la solution durant tout le temps disponible. Un premier objectif est de poursuivre les recherches sur ISUD pour passer de 2 000 à 20 000 contraintes. Il sera expérimenté sur les grands problèmes d'équipages aériens et sur les routes d'autobus en traitant simultanément 20 dépôts plutôt qu'un seul. Un second objectif du présent projet est de développer des algorithmes aussi efficaces que DCA et ISUD pour les problèmes de recouvrement généralisé ou il faut couvrir plusieurs fois chaque tâches (des agents de bord sur un vol). Un troisième groupe d'objectifs porte sur de nouvelles méthodes de décomposition pour des grands problèmes combinant plusieurs groupes de contraintes complexes. La génération de colonnes traite 2 niveaux, on va traiter 3 - 4 niveaux. On a d'abord l'intégration des problèmes de routes d'autobus et d'horaires de chauffeurs qui sont chacun résolus par génération de colonnes. On réalisera une décomposition lagrangienne ou on ajoute au problème d'autobus les couts réduits des chauffeurs et aux chauffeurs les couts réduits des autobus. On a ensuite l'ajout aux problèmes de rotations d'équipages aériens des blocs de contraintes demandant de garder les agents de bord en équipes durant une rotation ou demandant de répéter chaque rotation autant que possible durant le mois. On développera des décompositions qui échangent des informations entre ces nouvelles contraintes et le problème de base. On a aussi une nouvelle décomposition de Benders pour optimiser pour l'Office des Phosphates du Maroc, la chaine de transformation du minerai en plusieurs types d'engrais dans plusieurs usines, l'entreposage et le chargement des bateaux pour remplir des commandes. On remplace la linéarisation externe qui ajoute des contraintes par une linéarisation interne qui ajoute des variables dans le problème. On a finalement une décomposition pour le problème de planification de projet avec contraintes de ressource qui sera expérimenté sur l'entretien des navires de la marine canadienne. Ce projet combine des développements en science fondamentale et leur application sur de grands problèmes industriels.