Optimisation des tournées de véhicules dans le cadre de la logistique inverse : modélisation et résolution par des méthodes hybrides

Th. doct.--Informatique--Orléans, 1997. / Bibliogr. p. 133-140. Résumé. 1997 d'après la déclaration de dépôt légal.

Les diagrammes de décision Multi-valués (MDD) sont des structures de données efficaces et largement utilisées dans les domaines tels que la vérification, l’optimisation et la programmation dynamique. Dans cette thèse, nous commençons par améliorer les principaux algorithmes tels que la réduction de MDD, permettant aux MDD de potentiellement compresser exponentiellement des ensembles de tuples, ou la combinaison de MDD, tels que l’intersection ou l’union. Ensuite, nous proposons des versions parallèles de ces algorithmes ainsi que des versions permettant de travailler avec la version non déterministe des MDD. De plus, dans le domaine des MDD relâchés, un domaine de plus en plus étudié, nous définissons les notions de réduction et combinaison relâchés, ainsi que leurs algorithmes associés. Nous résolvons le problème de l’échantillonnage des solutions d’un MDD avec respect de loi de probabilité tels que des fonctions de probabilité de masse ou des chaines de Markov. Pour permettre d’utiliser les MDD dans les solveurs de programmation par contraintes, nous proposons de nouveaux propagateurs pour toutes les contraintes basées sur des MDD, améliorant les performances des algorithmes existants, puis nous en introduisons une nouvelle contrainte, la contrainte de channeling. Grâce à eux, nous montrons que nous pouvons reformuler plusieurs contraintes et en définir de nouvelles tout en étant basés sur des MDD. Finalement nous appliquons nos algorithmes à des problèmes industriels réels de génération de texte et musique, et de modélisation de réservoir de pétrole. / Multivalued Decision Diagrams (MDDs) are efficient data structures widely used in several fields like verification, optimization and dynamic programming. In this thesis, we first focus on improving the main algorithms such as the reduction, allowing MDDs to potentially exponentially compress set of tuples, or the combination of MDDs such as the intersection of the union. We go further by designing parallel algorithms, and algorithms handling non-deterministic MDDs. We then investigate relaxed MDDs, that are more and more used in optimization, and define the notions of relaxed reduction or operation and design efficient algorithms for them. The sampling of solutions stored in a MDD is solved with respect to probability mass functions or Markov chains. In order to combine MDDs with constraint Programming, we design the propagators of all the types of MMDD constraints in solvers, and introduce a new one, the channeling constraint. These new propagators outperform the existing ones and allow the reformulation of several other constraints such as the dispersion constraint, and even to define new ones easily. We finally apply our algorithm to several real world industrial problems such as text and music generation and geomodeling of a petroleum reservoir.

Ce mémoire traite de la résolution de problèmes d’ordonnancement à l’aide de la programmation par contraintes. Il s’intéresse principalement aux contraintes globales et particulièrement à la contrainte cumulative. Il passe en revue les règles permettant de la filtrer et les principaux algorithmes qui les appliquent. Il explique le Edge-Finder de Vilím et son arbre cumulatif. Il propose un algorithme plus performant et plus général pour appliquer les règles découlant du raisonnement énergétique. Le mémoire traite du cas particulier où toutes les tâches sont de durée identique. Pour modéliser efficacement ce type de problèmes, on y conçoit la contrainte multi-inter-distance. L’algorithme d’ordonnancement de López-Ortiz et Quimper est adapté pour réaliser un algorithme qui applique la cohérence de bornes. La contrainte multi-inter-distance s’avère efficace à résoudre le problème de séquençage des atterrissages d’avions du banc d’essai d’Artiouchine et Baptiste. / This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.

Plusieurs paradigmes de programmation existent pour aider à résoudre des problèmes d'optimisation combinatoire, l'un d'entre eux étant la programmation par contraintes. L'idée de ce paradigme consiste à modéliser le problème à résoudre à l'aide de contraintes, c'est-à-dire des déclarations qui forcent les variables du problème à respecter une relation mathématique. Les contraintes des problèmes ont habituellement des paramètres qui permettent de préciser la relation mathématique à respecter et des variables de décision qui représentent les variables pour lesquelles la relation mathématique doit s'appliquer. Bien qu'intéressant en soi, la programmation par contraintes peut également s'étendre sur d'autres concepts, notamment la modélisation automatique. L'acquisition ou apprentissage de contraintes consiste à apprendre les différentes contraintes, incluant les valeurs des paramètres, qui peuvent expliquer un ensemble d'exemples fournis. L'apprentissage de contraintes peut être utile dans plusieurs situations, comme l'apprentissage de structures d'horaires d'hôpitaux à l'aide d'anciens exemples d'horaires. L'apprentissage de contraintes est encore un domaine nouveau pour lequel les stratégies doivent encore être adaptées ou développées. Les techniques d'acquisition existantes varient en genre, incluant des méthodes qui créent des solutions artificielles pour interagir avec un utilisateur ou des approches qui se basent sur des analyses mathématiques rigoureuses de solutions pour faire des choix sans jamais communiquer avec l'utilisateur. Dans ce mémoire, nous explorons une nouvelle méthode pour performer l'acquisition de contraintes. Le critère principal de la méthode développée est basé sur le nombre de solutions du modèle considéré et utilise des outils de dénombrement. Notre technique performe bien sur les problèmes essayés et ouvre la porte à une nouvelle manière d'apprivoiser les problèmes d'acquisition de contraintes. / Several programming paradigms exist to help solve combinatorial optimization problems, one of them being constraint programming. The idea of this paradigm is to model the problems to solve using constraints, i.e. statements that force the variables of the problem to respect a mathematical relation. The constraints of a problem usually have parameters that allow to specify the mathematical relationship to be respected and decision variables that represent the variables on which the mathematical relationship must be applied. Although interesting in itself, constraint programming can also expand on other concepts, such as the automatisation of the modeling process. Constraints acquisition consists in learning the different constraints, including parameter values, which can explain a set of examples provided. Constraint acquisition can be useful in multiple situations, such as learning structures in schedules for hospitals using old schedules. Constraint learning is still a new area for which strategies still need to be adapted or developed. The existing techniques of acquisition varies widely in style, including methods that create artificial solutions to interact with a user or approaches which are based on complex mathematical analyzes of real solutions to make choices without ever communicating with the user. In this thesis, we explore a new method to perform the acquisition of constraints. The main criterion of the developed method is based on the number of solutions of the considered model and uses tools of model counting. Our technique works well on proven problems and opens the door to a new way of approaching acquisition constraint problems.

Titre de l'écran-titre (visionné le 4 décembre 2023) / Nous étudions un problème apparaissant dans le système de santé qui consiste à affecter des chirurgiens à des salles d'opération d'un hôpital. Ce problème se survient notamment à l'Hôpital Général de Brockville et nous a été rapporté par notre partenaire industriel : Thales Digital Canada. L'affectation des chirurgiens à des salles d'opération est sujette à différentes contraintes. Les salles doivent être adéquatement équipées pour combler les besoins du chirurgien. La demande pour chaque spécialité de chirurgien doit être couverte. Les salles d'opération doivent être utilisées à leur plein potentiel. Finalement, les chirurgiens devraient avoir des horaires réguliers, c'est-à-dire qu'ils doivent être les plus semblables possible d'une semaine à l'autre. Ce problème a été étudié dans la littérature scientifique, mais comme c'est souvent le cas avec les problèmes de recherche opérationnelle en milieu médical, ce problème a seulement été étudié avec des variations qui ne conviennent pas à l'Hôpital Général de Brockville. Conséquemment, nous expliquons ce qui est fait de façon similaire et ce qui est fait différemment dans la littérature. Ce mémoire présente une méthodologie qui utilise la programmation par contraintes pour affecter des chirurgiens à des salles d'opération. Un logiciel spécialisé a été développé pour créer des horaires de tailles variables. Ce logiciel prend en entrée un ensemble de besoins et affecte ensuite les chirurgiens aux salles d'opération. Une recherche à voisinage large améliore itérativement la solution jusqu'à ce que sa qualité soit satisfaisante. Les expériences que nous avons conduites démontrent que l'on obtient une solution satisfaisante en seulement quelques minutes. Ces horaires améliorent significativement le taux d'utilisation des salles d'opération. Nous avons comparé deux versions de notre logiciel et nous avons démontré qu'aucune ne domine l'autre. Nous proposons comme travaux futurs de combiner ces deux versions en une seule afin de tirer avantage des deux techniques. / We study a problem arising in the health system that consists of assigning surgeons to operating rooms in a hospital. This problem occurs at the Brockville General Hospital and was brought to us by our industrial partner Thales Digital Canada. The assignment of surgeons to operating rooms is subject to different constraints. The rooms must be properly equipped to satisfy the needs of the surgeon. The demand for each surgeon specialty must be fulfilled. The operating room should be used at their full potential. Finally, surgeons should have regular schedules, i.e. they should have similar schedules week after week. This problem is studied in the literature, but as it is often the case with operation research problems that occur in the health system, it was studied with variations that are not suited for the Brockville General Hospital. We therefore explain what is done similarly and what is done differently in the literature. This thesis introduces a methodology that utilizes constraint programming to allocate operating rooms to surgeons. A specialized software has been developed to create schedules of variable lengths. This software takes as input a set of requirements and generates a schedule that assign surgeons to operating rooms. A Large Neighbourhood Search iteratively improves the solution until the quality of the solution is satisfactory. The experiments conducted demonstrate that one can obtain satisfactory results in a few minutes. These schedules significantly enhance the utilization rate of operating rooms. We compared two versions of our software and showed that none dominates the other. However, we propose as a future work that these two versions could be combined into one in order to take advantage of both techniques.

Titre de l'écran-titre (visionné le 21 mars 2024) / L'ordonnancement en milieu agroalimentaire est complexe. En effet, les planificateurs doivent prendre en compte de nombreuses contraintes comme les allergènes, la disponibilité des ingrédients et de la main-d'oeuvre. Ceci devient rapidement une tâche complexe, surtout quand les horaires de production doivent être refaits à la moindre perturbation (nouvelle commande, retard dans l'arrivée des matières premières, etc.). C'est pourquoi il est naturel de faciliter la tâche de ceux-ci grâce à des outils d'aide à la décision comme des modèles d'optimisation. Les problèmes d'ordonnancement de la production sont étudiés depuis longtemps dans la littérature scientifique. Plus récemment, Ku et Beck ont démontré le potentiel du paradigme de la programmation par contraintes sur le problème d'ordonnancement d'atelier (Job-shop Scheduling Problem). Ceci et le fait que très peu d'articles combinent l'utilisation de la programmation par contraintes aux problèmes d'ordonnancement dans le milieu agroalimentaire ont motivé ces travaux de recherche. Dans ce mémoire, l'utilisation de la programmation par contraintes sur des problèmes d'ordonnancement tirés de l'entreprise Biscuits Leclerc a été étudiée. Également, d'autres techniques d'optimisation comme la recherche locale à voisinage large ont été utilisées. Les contributions de la recherche sont autant au niveau scientifique en remplissant un trou existant dans la littérature qu'au niveau industriel en résolvant un problème auquel fait face Biscuits Leclerc quotidiennement. / The scheduling in the food industry is complex. Indeed, planners must take into account many constraints such as the presence of allergens, the availability of ingredients, and employees. This quickly becomes a complex task, especially when production schedules have to be redone at the slightest disruption (new orders, delays in the arrival of raw materials, etc.). This is why it is natural to make their task easier with the help of decision support tools such as optimization models. Production scheduling problems have been studied for a long time in the scientific literature. More recently, Ku and Beck demonstrated the potential of the constraint programming paradigm on the Job-shop Scheduling Problem. This and the fact that very few articles combine the use of constraint programming with scheduling problems in the food industry have motivated the current research work. In this master thesis, the use of constraint programming on scheduling problems taken from the company Biscuits Leclerc have been studied. Also, other optimization techniques such as Large Neighborhood Search were used. The contributions of the research are as much at the scientific level by filling an existing gap in the literature as at the industrial level by solving a problem that Biscuits Leclerc faces in their everyday life.

Les contraintes sont un moyen générique de représenter les règles qui gouvernent notre monde. Étant donné un ensemble de contraintes, une question centrale est de savoir s'il existe une possibilité de toutes les satisfaire simultanément. Cette problématique est au cœur de la programmation par contraintes, un paradigme puissant pour résoudre efficacement des problèmes qui apparaissent dans de nombreux domaines de l'activité humaine. Initialement dédiée, dans les années 1980, à la résolution de problèmes d'intelligence artificielle à variables entières, c'est dans les années 1990 que la programmation par contraintes a été employée à la résolution de problèmes à variables réelles. Cependant, les problèmes mixtes —utilisant à la fois variables entières et réelles— n'ont été que très peu considérés jusqu'ici par la programmation par contraintes. Dans cette thèse, nous nous plaçons du point de vue de la résolution de problèmes continus. Nous proposons et mettons en oeuvre différentes améliorations de ce cadre de résolution : • Intégration de la notion de recherche rigoureuse d'optimum au cadre classique de résolution sans objectif, afin de modéliser et résoudre un problème de conception en robotique ; • Collaboration de deux solveurs, l'un discret l'autre continu, plus efficace que chacun des outils pour résoudre les problèmes utilisant contraintes continues et contraintes discrètes ; • Comparaison des différentes modélisations et filtrages possibles de la contrainte globale discrète alldifferent, permettant de l'utiliser dans un solveur dédié au continu ; • Spécialisation des techniques de filtrage basées sur l'arithmétique des intervalles, augmentant la puissance de filtrage des contraintes arithmétiques discrètes et mixtes.

Nous proposons plusieurs techniques visant à résoudre en pratique le problème NP-complet de satisfaction de contraintes de manière générique. Nous distinguons deux grands axes de techniques de résolution de CSP : l'infrence et la recherche. Nous avons contribué l'amélioration des techniques d'inférence en nous concentrant sur la propriété centrale qu'est la consistance d'arc : optimisations des algorithmes de consistance d'arc, comportement de plusieurs algorithmes d'inférence aux bornes de domaines discrets, et enfin une alternative intéressante à la consistance de chemin : la consistance duale. Cette propriété nous a amené à concevoir des algorithmes de consistance de chemin forte très efficaces. La variante conservative de cette consistance est de plus plus forte que la consistance de chemin conservative, tout en restant plus rapide à établir en pratique.<br />Par ailleurs, nous avons également cherché à améliorer MGAC, tout d'abord en équipant celui-ci d'heuristiques de choix de valeurs. Nous nous sommes pour cela basés sur l'heuristique de Jeroslow-Wang, issue du problème SAT. En utilisant deux techniques de conversion de CSP vers SAT, nous montrons comment cette heuristique se comporterait sur un CSP. Enfin, nous avons cherché à utiliser une hybridation entre un algorithme de recherche locale basé sur la pondération des contraintes et un algorithme MGAC équipé de l'heuristique dom/wdeg, en exploitant les possibilités d'apprentissage de l'un et l'autre algorithmes.<br />De manière transversale, l'ensemble des techniques développées dans le cadre de cette thèse a amené à la réalisation d'une API pour le langage Java, capable de résoudre un CSP au sein d'une application Java quelconque. Cette API a été développée dans l'optique "boîte noire" : le moins de paramètres et d'expertise possibles sont demandés à l'utilisateur. Un prouveur basé sur CSP4J a concouru lors les compétitions internationales de prouveurs CSP avec des résultats encourageants.

La composition musicale utilise de plus en plus les outils informatiques, mais la question de l'interprétation des pièces soit résoule. Dans le cas des pièces électro-acoustiques sur support, enregistrement d'une organisation temporelle de sons, l'exécution des oeuvres se restreint à leur diffusion. A la différence des pièces instrumentales, un interprète ne peut modifier certains paramètres musicaux lors de l'exécution. Nous cherchons à définir un système de composition et d'exécution de pièces interprétables, en nous focalisant sur les modifications de dates d'événements de la partition. Nous proposons un formalisme de partitions interactives utilisant la programmation par contraintes pour définir l'organisation temporelle et les limites de l'interprétation. Nous présentons un modèle de machine abstraite pour l'exécution des partitions, basée sur les réseaux de Petri et la propagation de contraintes. Enfin, nous exposons quelques applications du système. / Abstract