Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$34,000.00
Optimisation dans les graphes et réseaux : modélisation et nouveaux développements théoriques et algorithmiques
FY 2012-13
Summary
L'objectif principal de ma recherche est de développer des outils en théorie des graphes permettant de modéliser et de résoudre des problèmes combinatoires complexes, en tenant compte de la majeure partie des 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 liés à la théorie des graphes 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. Je vise également à développer des heuristiques efficaces pour des instances de très grande taille.
2. De nombreux problème d'horaires peuvent être modélisés en termes de coloration des sommets ou des arêtes d'un graphe, avec des contraintes additionnelles. J'ai pour objectif d'étendre les modèles et algorithmes existants de coloration pour la prise en compte, entre autres, de la robustesse de l'horaire produit, de la non-uniformité des durées des tâches, de l'impossibilité d'interrompre certaines tâches lorsqu'elles ont débuté.
3. J'ai pour objectif de résoudre des variantes peu étudiées, mais importantes en pratique, des problèmes de confection de tournées de véhicules avec profit, dans lesquels le temps à disposition pour réaliser les tournées est limité (on doit donc sélectionner les clients à visiter). Les demandes des clients peuvent être situées sur les noeuds ou les arcs d'un réseau, et chaque client peut être desservi partiellement et par plusieurs véhicules.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
105384-2012
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
2012
Competition year année de concours
2012
Award amount
34000
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
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
Optimisation dans les graphes et réseaux : modélisation et nouveaux développements théoriques et algorithmiques
Keyword
NSERC
Application summary
L'objectif principal de ma recherche est de développer des outils en théorie des graphes permettant de modéliser et de résoudre des problèmes combinatoires complexes, en tenant compte de la majeure partie des 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 liés à la théorie des graphes 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. Je vise également à développer des heuristiques efficaces pour des instances de très grande taille.
2. De nombreux problème d'horaires peuvent être modélisés en termes de coloration des sommets ou des arêtes d'un graphe, avec des contraintes additionnelles. J'ai pour objectif d'étendre les modèles et algorithmes existants de coloration pour la prise en compte, entre autres, de la robustesse de l'horaire produit, de la non-uniformité des durées des tâches, de l'impossibilité d'interrompre certaines tâches lorsqu'elles ont débuté.
3. J'ai pour objectif de résoudre des variantes peu étudiées, mais importantes en pratique, des problèmes de confection de tournées de véhicules avec profit, dans lesquels le temps à disposition pour réaliser les tournées est limité (on doit donc sélectionner les clients à visiter). Les demandes des clients peuvent être situées sur les noeuds ou les arcs d'un réseau, et chaque client peut être desservi partiellement et par plusieurs véhicules.