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

点击翻译按钮获取中文摘要

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.