Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$85,000.00
Méthodes d'optimisation mathématiques pour les grands problèmes d'horaires de véhicules et de personnel
EF 2012-13
Résumé
Les travaux de mon équipe au cours des 30 dernières années ont contribué fortement à créer à Montréal une grappe industrielle en optimisation d'horaires de véhicules et de personnel. Nos travaux ont entre autres développé le savoir-faire sur l'application industrielle de la génération de colonnes qui permet de traiter les contraintes complexes dans des sous-problèmes et de traiter un problème maître de coordination en considérant seulement un nombre réduit de variables à la fois. Ils ont aussi porté sur la réduction dynamique de l'ensemble des contraintes à considérer simultanément.
Une réduction par un facteur de 100 a été obtenue pour les problèmes de partitions et de 20 pour les problèmes linéaires généraux par rapport à CPLEX, le logiciel dominant sur le marché. Le premier objectif sera de spécialiser la méthode pour les contraintes de recouvrement généralisé et de multi-flot binaire pour atteindre aussi le facteur 100. Un second objectif est de développer une deuxième génération de la réduction qui ne nécessite pas la multiplication de la matrice originale par B-1 dont le temps croit avec la taille des problèmes, plus rapidement que celui des autres parties de l'algorithme. Un troisième objectif sera de poursuivre pour d'autres types de contraintes les travaux sur le simplexe en nombres entiers qui produit une suite de solutions entières de coûts décroissants. Le quatrième objectif porte sur la décomposition de Benders qui se prête bien à l'intégration de deux étapes d'un processus de décision ou l'ajout des facteurs stochastiques. La recherche portera sur l'accélération du traitement des sous-problèmes avec le parallélisme et la relaxation des coupes dans le problème maître quand elles deviennent nombreuses et en partie inactives.
Le traitement de problèmes plus grands et l'intégration de nouveaux facteurs devraient permettre de développer une nouvelle génération de logiciels de gestion de véhicules ou de personnel permettant des gains de productivité significatifs par rapport aux logiciels actuels. Ceci contribuera à maintenir l'avantage concurrentiel de la grappe industrielle canadienne qui commercialise ces logiciels sur le marché mondial.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
167049-2012
Name nom
Soumis, François
Department département
Mathématiques et 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
2012
Competition year année de concours
2012
Award amount
85000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
1
Nb partie
5
Application title
Méthodes d'optimisation mathématiques pour les grands problèmes d'horaires de véhicules et de personnel
Keyword
NSERC
Application summary
Les travaux de mon équipe au cours des 30 dernières années ont contribué fortement à créer à Montréal une grappe industrielle en optimisation d'horaires de véhicules et de personnel. Nos travaux ont entre autres développé le savoir-faire sur l'application industrielle de la génération de colonnes qui permet de traiter les contraintes complexes dans des sous-problèmes et de traiter un problème maître de coordination en considérant seulement un nombre réduit de variables à la fois. Ils ont aussi porté sur la réduction dynamique de l'ensemble des contraintes à considérer simultanément.
Une réduction par un facteur de 100 a été obtenue pour les problèmes de partitions et de 20 pour les problèmes linéaires généraux par rapport à CPLEX, le logiciel dominant sur le marché. Le premier objectif sera de spécialiser la méthode pour les contraintes de recouvrement généralisé et de multi-flot binaire pour atteindre aussi le facteur 100. Un second objectif est de développer une deuxième génération de la réduction qui ne nécessite pas la multiplication de la matrice originale par B-1 dont le temps croit avec la taille des problèmes, plus rapidement que celui des autres parties de l'algorithme. Un troisième objectif sera de poursuivre pour d'autres types de contraintes les travaux sur le simplexe en nombres entiers qui produit une suite de solutions entières de coûts décroissants. Le quatrième objectif porte sur la décomposition de Benders qui se prête bien à l'intégration de deux étapes d'un processus de décision ou l'ajout des facteurs stochastiques. La recherche portera sur l'accélération du traitement des sous-problèmes avec le parallélisme et la relaxation des coupes dans le problème maître quand elles deviennent nombreuses et en partie inactives.
Le traitement de problèmes plus grands et l'intégration de nouveaux facteurs devraient permettre de développer une nouvelle génération de logiciels de gestion de véhicules ou de personnel permettant des gains de productivité significatifs par rapport aux logiciels actuels. Ceci contribuera à maintenir l'avantage concurrentiel de la grappe industrielle canadienne qui commercialise ces logiciels sur le marché mondial.