Ce mémoire traite l'intégration dynamique des opérations de gestion des stocks et du transport avec la présence d'un évènement perturbateur, qui est la livraison urgente sur appel imprévue. En s'inspirant du cadre général de l'industrie énergétique et la distribution de l'huile à chauffage en particulier, après une revue de littérature exhaustive des problèmes de tournées de véhicules dynamiques et stockage-routage, nous introduisons une nouvelle variante qui cadre le problème dynamique de stockage-routage avec livraisons sur appel. Notre démarche de traitement s'est devisée en deux grandes étapes. Une première étape, statique et déterministe, s'est focalisée sur la description et la formulation mathématique du problème en se basant sur la programmation linéaire mixte et une résolution exacte à travers l'algorithme de branch-and-cut. Pour le besoin de l'intégration dynamique des livraisons incertaines sur appel dans un temps d'exécution raisonnable, une deuxième étape dynamique s'est concentrée sur le développement d'une heuristique basée sur la recherche tabou avec la configuration de deux politiques dynamiques de contrôle qui étudient les possibilités d'insérer les visites dynamiques soit dans la route en cours d'exécution ou dans celle de la période suivante dans le cas échéant. 72 instances ont été générées, et des analyses ont été menées sur différents facteurs qui peuvent influencer le taux de service des clients dynamiques aussi que les coûts d'opération. / This thesis deals with the dynamic integration of inventory management and transportation operations with the uncertain event of unplanned deliveries following urgent calls. Inspired by the general framework of the energy industry and the distribution of heating oil, in particular, a comprehensive literature review of both problems of dynamic vehicle routing and inventory-routing are conducted. We then introduce a new variant, called the dynamic inventory-routing problem with customer requests. Our solution approach has been divided into two main steps. A static and deterministic first step focused on the mathematical description and formulation of the problem based on a mixed-integer programming model and the development of an exact solution approach through a branch and cut algorithm. Then, to dynamically integrate uncertain on-call deliveries in a reasonable execution time, a second dynamic step is established to develop a heuristic, based on tabu search, with the configuration of two dynamic control policies that consider the possibilities of inserting dynamic visits either in the route under the execution or in that of the following period. 72 instances are generated, and analyses are conducted on various factors that can influence the service level for dynamic customers and operation costs.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2017-2018 / Des études économiques récentes ont identifié la difficulté des personnes à prendre des décisions optimales lorsqu’il existe une corrélation entre différentes variables d’état (aléatoires), que l’on appelle maintenant dans la littérature «inattention envers la corrélation». Dans cet article, nous supposons que l’inattention envers la corrélation est un trait individuel d’une personne et nous proposons différentes mesures de cette caractéristique. Nous comparons différentes mesures en termes de corrélation à partir des résultats d’expériences de laboratoire. Nous présentons les applications de ces mesures dans des domaines précis. Mots clés : heuristiques et biais, inattention envers la corrélation, mesure. / Recent economic studies identified the difficulty of persons to make optimal decisions when there is correlation between (random) state variables, now referred to in the literatures as “correlation neglect.” In this article, we presume correlation neglect to be an individual trait of a person and propose different measures of this characteristic. We compare different measures in terms of their correlation based on results from laboratory experiments. We present applications of the measures in the field. Keywords : heuristics and biases, correlation neglect, measurement.

Le problème d'approvisionnement de stations d'essence consiste à livrer des carburants à l'aide d'une flotte de camions-citernes compartimentés en maximisant une fonction de revenu du transporteur. Il convient essentiellement de déterminer les quantités à livrer de chaque produit, de les affecter aux compartiments des véhicules et de construire les routes permettant leur livraison. Cette thèse comporte trois articles présentant chacun une version différente de ce problème d'approvisionnement. / Nous proposons, dans le premier article, une méthode exacte de résolution applicable au cas où la flotte est illimitée et le nombre de stations par route limité à deux. Le problème y est décomposé en un sous-problème d'affectation des produits aux compartiments des véhicules et un sous-problème de routage. L'affectation des produits aux compartiments repose sur un algorithme classique d'affectation dans un graphe bipartite suivi d'un test d'optimalité, et recourt éventuellement à la résolution d'un programme linéaire en nombres entiers. Puisqu'un voyage ne peut desservir plus de deux stations, le problème de routage est réduit à un problème de couplage de coût minimal clans un graphe non bipartite. Deux stratégies sont alors proposées : rechercher un chargement admissible des produits dans les compartiments pour tous les couples possibles de stations, puis résoudre le problème de couplage correspondant, ou générer les routes en résolvant le problème de couplage a priori pour ensuite tester l'existence d'un chargement admissible pour chacune, cette procédure étant répétée aussi longtemps qu'une route non admissible est générée. / Nous présentons dans le second article une heuristique appliquée au problème d'approvisionnement sur plusieurs périodes avec cette fois un nombre limité de camions-citernes. Dans cette version du problème d'approvisionnement, l'objectif est de déterminer pour chacjue période, les stations, les produits et les quantités à livrer, d'affecter les pioduits aux compartiments des camions-citernes et de construire les routes. L'affectation des stations aux différentes périodes est déterminée par un algorithme récursif incluant une procédure d'anticipation des livraisons. Nous proposons par ailleurs une procédure d'affectation des routes aux véhicules (route packing) par laquelle les routes sont affectées aux véhicules. / Dans le troisième article, nous nous intéressons à nouveau au problème monopé¬riode en intégrant cette fois la gestion des fenêtres de temps en dehors desquelles les livraisons ne peuvent avoir lieu. Nous y considérons par ailleurs le cas d'une flotte limitée et relaxons l'hypothèse de limitation des routes à deux stations. Une formulation différente de celle proposée dans le premier article est présentée. Elle repose sur une sélection de routes respectant les contraintes horaires à partir d'un ensemble de routes admissibles générées a priori et éventuellement présélectionnées. De cette formulation, deux heuristiques sont développées reposant sur une présélection des arcs du graphe c

<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité :diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ?D'automatiser la préparation des métaheuristiques ?En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ?C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche :l'heuristique de la Gestalt.</p><p><p><p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p><p><p><p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Cette thèse se déroule au sein du projet ToDo (Time versus Optimality in discrete Optimization ANR 09-EMER-010) financé par l'Agence Nationale de la Recherche. Nous nous intéressons à la résolution exacte et approchée de deux problèmes de graphes. Dans un souci de compromis entre la durée d'exécution et la qualité des solutions, nous proposons une nouvelle approche par partition en cliques qui a pour but (1) de résoudre de manière rapide des problèmes exacts et (2) de garantir la qualité des résultats trouvés par des algorithmes d'approximation. Nous avons combiné notre approche avec des techniques de filtrage et une heuristique de liste. Afin de compléter ces travaux théoriques, nous avons implémenté et comparé nos algorithmes avec ceux existant dans la littérature. Dans un premier temps, nous avons traité le problème de l'indépendant dominant de taille minimum. Nous résolvons de manière exacte ce problème et démontrons qu'il existe des graphes particuliers dans lesquels le problème est 2-approximable. Dans un second temps nous résolvons par un algorithme exact et un algorithme d'approximation le problème du vertex cover et du vertex cover connexe. Puis à la fin de cette thèse, nous avons étendu nos travaux aux problèmes proches, dans des graphes comprenant des conflits entre les sommets. / This thesis takes place in the project ToDo 2 funded by the french National Research Agency. We deal with the resolution of two graph problems, by exact and approximation methods. For the sake of compromise between runtime and quality of the solutions, we propose a new approach by partitioning the vertices of the graph into cliques, which aims (1) to solve problems quickly with exact algortihms and (2) to ensure the quality if results with approximation algorithms. We combine our approach with filtering techniques and heuristic list. To complete this theoretical work, we implement our algorithms and compared with those existing in the literature. At the first step, we discuss the problem of independent dominating of minimum size. We solve this problem accurately and prove that there are special graphs where the problem is 2-approximable. In the second step, we solve by an exact algorithm and an approximation algorithm, the vertex cover problem and the connected vertex cover problem. Then at the end of this thesis, we extend our work to the problems in graphs including conflicts between vertices.

Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes. / This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.

L’accroissement des profits, à travers l’amélioration de la productivité et la réduction des pertes de matières, représente un objectif primordial pour les entreprises industrielles. Dans cette thèse, nous nous intéressons à la résolution d’un problème industriel complexe réel avec des contraintes de temps. Nous nous sommes intéressés, tout d’abord, à un objectif principal, soit la minimisation des dates de fin de production, suivi d’un objectif secondaire qui est la minimisation des quantités de déchets non recyclables. Dans un premier temps, nous avons modéliséle problème par des modèles mathématiques, que nous avons résolu à l’aide d’un solveur. Dans un second temps, nous avons proposé une méthode approchée en forme d’algorithmes évolutionnistes. Cette méthode est appliquée aux deux objectifs mentionnés ci-dessus séparément. Une troisième méthode est ensuite appliquée à l’objectif principal, à savoir une méthode arborescente approchée. Nous avons testé les algorithmes proposés sur des instances inspirées d’un cas réel ; issues d’une entreprise du secteur agroalimentaire et sur des instances inspirées de la littérature. / Increasing profits, through the improvement of productivity and minimizing waste, is a primary objective for industrial companies. In this thesis, we are interested insolving a real complex industrial problem with time constraints. Firstly, we were interested in minimizing completion time (Cmax). Secondly, we focused on minimizing of non-recyclable waste. As a first step, we formulated the problem by mathematical models, which we solved using a solver. In a second step, we proposed an approximate method in the form of evolutionary algorithms. Both methods were applied to the two objectives mentioned above separately. Then, a third method which is a tree-search algorithm was applied only to the main objective. We tested the proposed algorithms on instances inspired from a real case; from an agri-food business, and also on instances inspired from the literature.

La notion de "primitif" ou “trait élémentaire” est centrale dans l'étude du fonctionnement des systèmes perceptifs. Elle permet, d'une part, de déterminer la classe des propriétés de la stimulation sensorielle à partir desquelles le système visuel construit des percepts complexes. Elle permet, d'autre part, d'établir des liens explicatifs entre les phénomènes perceptifs étudiés à des niveaux d'analyse divers (tels que la neurophysiologie, les études comportementales et la phénoménologie perceptive). Le but de ce travail est de montrer à quel point cette notion est "imprégnée de théorie". À partir d'une revue de travaux philosophiques de référence et de contributions expérimentales récentes, ce travail vise à dégager les différents critères adoptés dans la littérature pour caractériser la notion de trait élémentaire, afin d'en éclaircir les incohérences d'usage et les enjeux théoriques majeurs dérivant de l'adoption de différents critères.

L'objet de cette thèse est l'étude d'un problème d'ordonnancement, dont le critère d'optimisation est la minimisation du nombre total de changements d'outils sur une machine flexible. Différents problèmes liés à l'outillage et pouvant constituer un obstacle au fonctionnement d'un atelier flexible sont brièvement examinés, (de la gestion de l'inventaire aux changements d'outils). Nous nous concentrons ensuite sur le problème d'ordonnancement avec gestion d'outils sur une seule machine: ce problème est NP-complet. Un premier aspect qui est la gestion off-line des outils est étudié: différents modèles sont proposés pour la minimisation des changements en fonction d'une séquence des tâches donnée. Dans ce cas, le problème est polynomial. Nous revenons ensuite au problème d'ordonnancement proprement dit, pour lequel plusieurs types de méthodes heuristiques sont décrites et comparées. La seconde partie du travail est consacrée à la gestion on-line des changements d'outils; elle se compose de deux chapitres: dans le premier, le modèle que nous allons utiliser est décrit en détail. Il s'agit de la modélisation des problèmes de k-serveurs. Le principe peut être résumé comme suit: sur un réseau de n clients potentiels, on dispose de k serveurs mobiles, avec lesquels on doit répondre on-line aux demandes unitaires et successives des clients, tout en optimisant les déplacements des serveurs. Ce problème est en étroite relation avec la gestion des mémoires en informatique. Dans le dernier chapitre, le modèle des k-serveurs «classique» est généralisé aux problèmes avec service par blocs de demandes, ce qui permet d'adapter l'algorithme de partitionnement, (fortement compétitif pour le service unitaire), au cas plus général des demandes groupées. Cet algorithme dont nous étudions les propriétés et la compétitivité est applicable à la gestion on-line des changements d'outils. Il sert de base à la construction d'une heuristique d'ordonnancement avec gestion d'outils. Cette dernière méthode se révèle très efficace comparée aux précédentes

Dans cette thèse, notre objectif est de présenter une nouvelle approche de résolution pour des problèmes d'ordonnancement de type job-shop. Les problèmes traités sont de grande taille, ce qui, du fait de la complexité du problème, ne permet d'envisager que l'utilisation d'heuristiques. Cette approche propose une alternative aux algorithmes basés sur des règles de priorité, généralement utilisés. Le principe de l'approche est de construire une succession d'ordonnancements partiels, en agrégeant les jobs les uns après les autres. L'agrégation consiste à insérer toutes les opérations du job à agréger sans changer l'ordre des opérations dans l'ordonnancement partiel précédent. Dans un premier temps, des méthodes issues de l'approche sont proposées pour résoudre le problème classique du job-shop. Ensuite, ces méthodes sont étendues pour traiter des problèmes de job-shop généralisé, ou l'affectation des opérations aux machines n'est pas fixée au départ. Pour finir, des problèmes de job-shop dynamiques et réactifs sont abordés. Dans ceux-ci, l'arrivée aléatoire de jobs et l'arrêt de machines sont pris en compte. Les méthodes agrégatives sont particulièrement bien adaptées à la résolution de ce type de problème.