Publié :mardi 9 juillet 2013

Par EDVAC

Chairman : Philippe Michelon, LIA, Université d'Avignon.

Speakers:  Rodrigo Acuna-Agost, Serigne Gueye, Philippe Michelon

La Recherche Opérationnelle est la discipline regroupant l'ensemble des techniques et des outils conceptuels nécessaires aux prises de décision. Support de l'être humain dans ses prises de décision, elle s'apparente donc à l'Intelligence Artificielle dans sa finalité. Ces deux disciplines partagent également un certain nombre de caractéristiques (elles sont intimement liées à l'Informatique et aux Mathématiques) et, parfois, s'attaquent à des problèmes similaires par des techniques différentes (SAT par exemple). Proches à bien des égards, donc, la Recherche Opérationnelle et l'Intelligence Artificielle n'en sont pas moins des disciplines à part entière, chacune ayant sa propre culture et ses références fondatrices. On peut ainsi espérer que, pour chacune des deux communautés, une meilleure connaissance de l'autre permettra de progresser, de faire jaillir de nouvelles méthodes de résolution et de franchir de nouvelles limites. On peut ainsi espérer suivre l'exemple de la Programmation par Contraintes : issue de l'Intelligence Artificielle, la PPC est maintenant reconnue par les chercheurs opérationnels comme un outil efficace s'intégrant parfaitement aux méthodes de Programmation Mathématique, les enrichissant considérablement. Réciproquement, des algorithmes de filtrage utilisés en PPC sont inspirés par des méthodes de Recherche Opérationnelle.  

Nous proposons par ce tutoriel de concourir au rapprochement de ces deux communautés en illustrant ce que peuvent être des travaux de chercheurs opérationnels. Nous avons opté pour une démarche par l'exemple en présentant des travaux sur des problématiques concrètes. C'est en effet de la nécessité de résoudre des problèmes de planification réels qu'est née la Recherche Opérationnelle, avant de développer ses propres outils et concepts. Présenter des applications réelles permet également de bien cerner la méthodologie, les méthodes et les apports d'une discipline. Nous avons opté pour des problématiques émanant d'un des plus grands champs d'application de la Recherche 

Opérationnelle : le transport.

Le tutoriel est ainsi composé de trois présentations, la première liée au transport aérien, la seconde au transport maritime et la dernière au transport ferroviaire.

Présentation 1 : Deux applications de la recherche opérationnelle pour la gestion des perturbations dans le domaine aérien.

Auteurs : Rodrigo Acuna-Agost, Baptiste Chatrain, Mourad Boudia, Semi Gabteni. 

Speaker : Rodrigo Acuna-Agost, Operations Research and Innovation Division, Société Amadeus

Résumé : Les compagnies aériennes opèrent des plans de vols optimisés afin de maximiser les revenus à long terme. Néanmoins, des perturbations, telles que des conditions climatiques sévères, des problèmes techniques de la flotte d’appareils ou encore des indisponibilités de l’équipage empêchent l’application de ces plans le jour des opérations. Ces plans doivent donc être révisés et adaptés pour tenir compte de ces imprévus.

Nous présentons deux problèmes liés à la gestion de perturbations dans le domaine aérien civile qui ont pour objectif final la minimisation de l’impact sur les passagers et les compagnies aériennes. 

Le premier modèle réadapte les horaires de décollages des avions afin de préserver, autant que possible, les connections des passagers en respectant les contraintes opérationnelles et en minimisant les retards et les annulations totales. L'originalité de ce modèle est la considération des flux de passagers dans le processus de réparation du plan de vol.

Ce premier modèle est complété par une deuxième approche qui permet de réaccommoder, de manière optimale, les passagers qui sont toujours en situation délicate relativement au plan réparé. La contribution principale de cette méthode, du point de vue scientifique, est la présentation d’une nouvelle technique de réduction de la complexité. Cette technique permet de construire un problème équivalent composé de moins de 4% du nombre total de variables de décision. Le but est de pouvoir travailler avec des jeux de données de grand taille, composés de centaines de vols et de milliers de passagers en respectant un temps de résolution acceptables pour cet type d’application.

Présentation 2 : Affectation de Navires dans les Terminaux Portuaires.

Auteurs : Serigne Gueye, Sophie Michel, Adnan Yassine

Speaker : Serigne Gueye, LIA, Université d'Avignon

Résumé : Organiser l'entrée de navires (porte-conteneurs) dans un terminal portuaire est une tâche quotidienne à laquelle se livre les gestionnaires portuaires. Une file de navires arrive au large du port à des heures estimées à priori, et il s'agit de leur attribuer une heure effective d'entrée (problèmatique d'ordonnancement) dans le terminal ainsi qu'une section d'accostage (problèmatique d'affectation) sur laquelle diverses opérations, dont celles dites de transbordement (chargement/déchargement de conteneurs), seront effectuées. La longueur limitée du quai et les temps nécessaires aux opérations font que tout navire n'a pas nécessairement une place dans le terminal à son approche du port, et devra attendre un certain temps avant de pouvoir entrer dans le terminal. Mais parallèlement, pour des raisons d'attractivité et d'efficacité économique, il est fortement souhaitable de diminuer au mieux leurs attentes (longueur des files) ainsi que le coût lié aux divers transferts de produits. Ce problème très pratique a fait l'objet d'études en recherche opérationnnelle suivant différentes variantes. Nous proposons ici l'analyse théorique et numérique d'une version particulière dans laquelle l'enjeu unique réside dans l'affectation. 

Après une présentation sommaire de la problèmatique globale (ordonnancement et affectation), nous nous intéresserons à un modéle permettant de résoudre le problème sans rentrer dans les détails techniques de sa résolution, mais en donnant tant que faire se peut quelques éléments de compréhension et les liens (au niveau résolution) avec la programmation par contraintes (PPC). Notammment, comment PPC et Programmation Linéaire en Nombres Entiers coopérent, dans le cadre d'un algorithme dit de "coupes", pour déterminer la meilleure affectation.

Présentation 3 : Réparation d'horaires ferroviaires.

Auteurs : Rodrigo Acuna-Agost, Philippe Michelon, Dominique Feillet, Serigne Gueye

Speaker : Philippe Michelon, LIA, Université d'Avignon

Résumé : Nous présentons à la fois un nouveau modèle et une nouvelle approche pour réparer un plan d'exploitation, préalablement calculé, perturbé par des incidents (panne de machines, etc.). Notre objectif est de minimiser la différence entre le plan initial et le nouveau plan.  Le modèle proposé comporte des variables binaires et un grand nombre de contraintes et ne sera que brièvement évoqué que pour souligner qu'il est d'une taille beaucoup trop importante pour être résolu par un solveur commercial, au moins dans le temps qui nous est imparti pour fournir une nouvelle solution. Nous avons ainsi développé une approche appelée SAPI (Analyse Statistique de la Propagation des Incidents) dont la caractéristique est d'estimer la probabilité qu'un événement (une étape de l'itinéraire d'un train) soit affecté par un incident survenu plus tôt et ailleurs dans le réseau. Il s'agit en réalité d'une méthode d'apprentissage. L'utilisation de ces probabilités permet de réduire considérablement l'espace de recherche des solutions et la taille du modèle et facilite l'obtention de très bonnes solutions dans un court laps de temps. La méthode a été testée avec deux réseaux différents situés en France et au Chili.