Canada Spends Logo

Explore our Budget 2026 analysis

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

FY 2024-25

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.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

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
2024
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
2950
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Applied mathematics
Research subject fr
Mathématiques appliquées
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names 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
Keywords
optimisation; décomposition; programmation mathématique; programmation en nombres entiers; génération de colonnes; décomposition de dantzig-wolfe; décomposition de benders; agrégation de contraintes; décomposition lagrangienne; 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.
École Polytechnique de Montréal - $50,000 Grant (2024… | Canada Spends