Méthodes d’optimisation pour l’étude intégrée de problèmes décisionnels complexes – ATHENA

Notons A et B les deux problèmes de décision considérés.
• Supposons que les décisions pour A et pour B sont prises par la même instance (contexte centralisé) et que le contexte est statique (données connues et fiables). On peut aborder le problème de l’intégration de A et B par des méthodes de décomposition induites par la programmation linéaire (décomposition de Benders, décomposition lagrangienne,…). C’est l’objet de la tâche « Approches de décomposition ».
• Supposons que les activités A et B sont confiées à deux agents notés A et B. L’agent A peut avoir un certain objectif à atteindre ou à minimiser, qui n’est pas en rapport avec l’objectif de l’agent B. Toutefois, les décisions qui seront prises par l’agent A auront un impact sur les performances que pourra atteindre l’agent B et inversement. Il s’agit alors de construire une solution au problème intégré qui fournisse une solution de compromis acceptable par l’agent A et par l’agent B. La tâche « Approches multi-agents » se place dans ce contexte.
• Toujours en supposant que les problèmes sont confiés à des agents, on considère maintenant que la décision est distribuée. Autrement dit, l’agent A est autonome dans sa décision et l’agent B est autonome dans sa décision. L’objectif est alors de mettre au point les mécanismes de coopération nécessaires pour que les deux agents prennent des décisions qui conviennent globalement à tous, c’est-à-dire des décisions qui conduisent à un équilibre. La tâche « Approches coopératives » est consacrée à ce cas et fait le lien avec des questions classiques de la théorie des jeux coopératifs.
• Enfin, on suppose que le contexte est centralisé, et dynamique et soumis à de nombreuses incertitudes comme par exemple l’arrivée de nouvelles tâches à traiter, des incertitudes sur des paramètres, des aléas, etc. Dans ce contexte, la question principale porte sur la robustesse. C’est l’objet de la tâche « Approches robustes et flexibles – contexte dynamique ».

La stratégie de valorisation du projet repose principalement sur les publications des partenaires. Tous les membres du projet (à l’exception des plus jeunes) sont des chercheurs qui ont l’habitude de produire des articles dans les meilleures revues du domaine et certains ont une grande expérience éditoriale. Le thème de recherche est tout à fait porteur et les travaux peuvent – si les résultats sont là – fournir de bons résultats. Les revues visées sont celles dans lesquels les membres du projet ont l’habitude de publier, comme European Journal of Operational Research, Computers and Operations Research, International Journal of Production Economics, International Journal of Production Research, etc.

Le projet contribuera également à la formation de plusieurs étudiants de Master, par l’intermédiaire des 5 stages dont le financement est prévu dans le budget (3 à Heudiasyc et 2 au LAAS), sans compter les projets et stages des élèves ingénieurs de nos formations (UTC – Compiègne, ISIMA – Clermont-Ferrand, Polytech’Tours, INSA de Toulouse, ENSEEIHT – Toulouse), qui contribueront aussi à l’avancement des travaux, mais pour lesquels aucun budget spécifique n’a été demandé. Les formations d’ingénieurs ont toutes en fin de cursus des projets consistants pouvant être soit en relation avec des partenaires privés soit sur des sujets de recherche. Le projet fournira naturellement de beaux projets de recherche pour les élèves ingénieurs.

Dans le cadre des collaborations envisagées, celle concernant la préparation de chimiothérapies et leur distribution avec le CHRU de Tours peut avoir des retombées qui dépassent le cadre de la communauté de la recherche opérationnelle. Les collaborations dans le passé avec cette unité ont conduit à des publications dans le secteur pharmaceutique et à des communications dans des revues de vulgarisation professionnelles.

Les perspectives de recherche sont nombreuses car les problèmes potentiellement couverts par la thématique du projet sont nombreux, parce que les approches de résolutions sont multiples et que pour chaque approche, les méthodes utilisables sont nombreuses. Il y aura donc nécessairement de très nombreuses perspectives de recherche sur chacun des problèmes abordés.
Il y aura des perspectives intéressantes dans le domaine du transfert et de la valorisation. L’identification de cas réels et leur résolution reste un challenge difficile, mais important dans une démarche de chercheur opérationnel. Un premier cas d’application réel existe au CHRU de Tours pour la production et la distribution de chimiothérapie, et ce contexte concret peut tout à fait donner lieu à une mise en œuvre de ces travaux de recherche, moyennant un travail complémentaire (des algorithmes ne suffisent pas à une mise en œuvre, il faut aussi un partenariat industriel, des équipements, du développement spécifique, etc.).

Moukrim A., Quilliot A., Toussaint H., An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration, EJOR (2015).
A. CHEREF, J-C. BILLAUT, C. ARTIGUES, Une approche robuste pour un problème d'ordonnancement et de VRP intégrés, 15ème congrès de la Société de la Société Française de Recherche Opérationnelle et d'Aide à la Décision Roadef’2014, Bordeaux, février 2014.
A. CHEREF, T. BOUCHARD, J-C. BILLAUT, C. ARTIGUES, Un algorithme tabou pour résoudre, grâce aux groupes d’opérations permutables, un problème d’ordonnancement et de routing robuste, 10ème Conférence Internationale de MOdélisation, Optimisation et SIMulation - MOSIM’14 - 5 au 7 Novembre 2014 – Nancy
Azeddine Cheref, Alessandro Agnetis, Christian Artigues, Jean-Charles Billaut, Problème d’ordonnancement et de distribution intégrés, in ROADEF 2015
Afifi, S. and Guibadj, R.-N. and Moukrim, A. New Lower Bounds on the Number of Vehicles for the Vehicle Routing Problem with Time Windows 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014., Cork, Irlande, vol. 8451, pp. 422-437, series: LNCS, 2014
N. Chaabane Fakhfakh, C. Briand and M-J. Huguet. A Multi-Agent Min-Cost Flow problem with Controllable Capacities - Complexity of Finding a Maximum-Nash Equilibrium. Proceedings of International Conference on Operations Research and Enterprise Systems (ICORES 2014), pp. 27-34 (2014) – Best paper award
Leticia Vargas, Nicolas Jozefowiez, Sandra Ulrich Ngueveu: A Selector Operator Based Adaptative Large Neighborhood Search for the Covering Tour Problem, in LION 9 to appear in LNCS
N. Chaabane, C. Briand and M-J. Huguet. Finding Stable flows in multi-agent Networks under an equal-sharing policy. International Network Optimization Conference, INOC 2015 (accepté)

L’optimisation de processus décisionnels complexes fait l’objet d'études en recherche opérationnelle et en optimisation mathématique depuis de nombreuses années. Souvent, les problèmes abordés sont issus d’un découpage implicite des problématiques, qui a été fait compte tenu de la nature des problèmes et de la complexité évidente qu’il y a à vouloir les traiter conjointement. Ces problèmes sont abordés de façon très précise et la difficulté réside dans la façon de les faire communiquer. Par exemple dans le contexte de la chaîne logistique, les décisions en termes de production sont fortement liées aux décisions de gestion de stock ainsi qu’à la politique de distribution des produits. Les problèmes sont toutefois le plus souvent abordés de façon disjointe. Récemment, grâce aux progrès des techniques d’optimisation, aux logiciels performants mis à la disposition des chercheurs et aux avancées matérielles, il est désormais possible d’aborder des problèmes d’une très grande complexité. Par exemple, aborder certains problèmes décisionnels de façon intégrée plutôt que de façon séparée est désormais possible et il est établi que cela permet d’obtenir des solutions qui présentent un plus grand intérêt.
L’objectif du projet est d’aborder des problèmes d’optimisation complexes de façon intégrée, à un niveau opérationnel (par exemple ordonnancement de la production et routage des véhicules). Afin que l’étude soit complète, plusieurs contextes sont envisagés. On considère tout d’abord que la décision est centralisée et que l’environnement est statique, autrement dit que les données sont connues de façon certaine et qu’elles ne varient pas dans le temps. Les techniques d’optimisation combinatoire basées sur la programmation mathématique et faisant appel à la décomposition sont alors privilégiées pour chercher des solutions optimales ou proches de l’optimum. On considère dans un deuxième temps que la décision est centralisée et que l’environnement est statique, mais que les problèmes décisionnels intégrés ont des objectifs différents, éventuellement conflictuels. Alors, les approches de type multi-agents (dans le sens « agents en compétition ») sont privilégiées et des solutions de compromis sont cherchées. Dans un troisième temps, toujours dans un environnement statique, on considère cette fois que la décision est distribuée et que chacun des problèmes qui sont intégrés est sous la responsabilité d’un décideur autonome. Il faut alors étudier les mécanismes de coopération entre décideurs et trouver des solutions équilibrées. Enfin, dans une dernière partie, on considère que l’environnement est dynamique, autrement dit que les paramètres du problème peuvent changer au cours du temps. La solution proposée est donc perturbée, et il faut chercher, en fonction de la définition des incertitudes, à mettre au point des méthodes pour trouver des solutions qui sont robustes.
Quatre partenaires sont impliqués dans le projet : le Laboratoire d’Informatique de l’Université de Tours, le laboratoire Heudiasyc de l’Université de Technologie de Compiègne, le LAAS-CNRS de Toulouse et le LIMOS de l’Université de Clermont-Ferrand. Le projet doit durer 48 mois et le principal financement demandé est composé de 2 thèses co-encadrées (LI-LAAS et LIMOS-Heudiasyc).