Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$31,900.00

Nouveaux modèles et algorithmes en optimisation combinatoire et en théorie des graphes

EF 2007-08

Résumé
L'objectif principal de ma recherche est de développer des outils mathématiques permettant de résoudre des problèmes complexes de grande taille en tenant compte des principales contraintes rencontrées en pratique. Les domaines visés sur lesquels ces recherches auront le plus d'impact sont la confection d'horaires de personnel et de transport. Je privilégie les trois axes de recherche suivants.1. La plupart des problèmes d'optimisation combinatoire ne peuvent pas être résolus en temps polynomial. La taille des problèmes pour lesquels il est possible de déterminer une solution optimale est ainsi souvent très petite en comparaison avec la taille des problèmes rencontrés en pratique. J'ai pour objectif d'accroître la taille des problèmes pouvant être résolus de manière exacte en un temps raisonnable.2. De nombreux problèmes d'horaires peuvent être modélisés en termes de coloration des sommets ou des arêtes d'un graphe, avec quelques contraintes supplémentaires. J'ai pour objectif, entre autres, d'étendre les modèles de coloration existants pour la prise en compte des durées non uniformes des tâches à planifier. Dans ce cas, pour éviter d'interrompre la réalisation d'une tâche, les couleurs (périodes) affectées aux sommets ou aux arêtes doivent satisfaire des contraintes de consécution.3. Une variante peu étudiée mais souvent rencontrée en pratique du problème de l'optimisation des tournées de véhicules est celle où un profit est associé à chaque client et où le temps à disposition pour réaliser les tournées est limité, ce qui signifie qu'il faut choisir les clients à visiter tout en maximisant le profit ou la différence entre le profit et les coûts de transport. Je compte combler cette lacune en développant de nouveaux algorithmes (exacts et heuristiques) pour une résolution efficace de ces problèmes.
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
105384-2007
Name nom
Hertz, Alain
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
2007
Competition year année de concours
2007
Award amount
31900
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
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
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
Nouveaux modèles et algorithmes en optimisation combinatoire et en théorie des graphes
Keyword
NA
Application summary
L'objectif principal de ma recherche est de développer des outils mathématiques permettant de résoudre des problèmes complexes de grande taille en tenant compte des principales contraintes rencontrées en pratique. Les domaines visés sur lesquels ces recherches auront le plus d'impact sont la confection d'horaires de personnel et de transport. Je privilégie les trois axes de recherche suivants.1. La plupart des problèmes d'optimisation combinatoire ne peuvent pas être résolus en temps polynomial. La taille des problèmes pour lesquels il est possible de déterminer une solution optimale est ainsi souvent très petite en comparaison avec la taille des problèmes rencontrés en pratique. J'ai pour objectif d'accroître la taille des problèmes pouvant être résolus de manière exacte en un temps raisonnable.2. De nombreux problèmes d'horaires peuvent être modélisés en termes de coloration des sommets ou des arêtes d'un graphe, avec quelques contraintes supplémentaires. J'ai pour objectif, entre autres, d'étendre les modèles de coloration existants pour la prise en compte des durées non uniformes des tâches à planifier. Dans ce cas, pour éviter d'interrompre la réalisation d'une tâche, les couleurs (périodes) affectées aux sommets ou aux arêtes doivent satisfaire des contraintes de consécution.3. Une variante peu étudiée mais souvent rencontrée en pratique du problème de l'optimisation des tournées de véhicules est celle où un profit est associé à chaque client et où le temps à disposition pour réaliser les tournées est limité, ce qui signifie qu'il faut choisir les clients à visiter tout en maximisant le profit ou la différence entre le profit et les coûts de transport. Je compte combler cette lacune en développant de nouveaux algorithmes (exacts et heuristiques) pour une résolution efficace de ces problèmes.