Le problème d’approvisionnement conjoint (JDP) proposé est un problème de planification des tournées de livraisons sur un horizon de temps décomposé en périodes élémentaires, l’horizon de temps étant la période commune de livraison de tous les produits,. La donnée de ces paramètres permet d’obtenir une formulation linéaire du problème, avec des variables de décision binaires. Le modèle intègre aussi des contraintes de satisfaction de la demande à partir des stocks et des quantités livrées, des contraintes sur les capacités de stockage et de transport.Afin de résoudre aussi le problème de choix des tournées de livraison, il est nécessaire d'introduire dans le modèle des contraintes et des variables liées aux sites visités au cours de chaque tour. Il est proposé de résoudre le problème en deux étapes. La première étape est le calcul hors ligne du coût minimal de la tournée associé à chaque sous-ensemble de sites. On peut observer que pour tout sous-ensemble donné de sites, le cycle hamiltonien optimal reliant ces sites à l'entrepôt peut être calculé à l'avance par un algorithme du problème du voyageur de commerce (TSP). Le but ici n'est pas d'analyser pleinement le TSP, mais plutôt d'intégrer sa solution dans la formulation de JRP. .Dans la deuxième étape, des variables binaires sont associées à chaque tour et à chaque période pour déterminer le sous-ensemble de sites choisi à chaque période et son coût fixe associé. / The proposed joint delivery problem (JDP) is a delivery tour planning problem on a time horizon decomposed into elementary periods or rounds, the time horizon being the common delivery period for all products. The data of these parameters provides a linear formulation of the problem, with binary decision variables. The model also incorporates the constraints of meeting demand from stock and the quantities supplied, storage and transport capacity constraints.In order to also solve the problem of choice of delivery rounds, it is necessary to introduce in the model several constraints and variables related to the sites visited during each round. It is proposed to solve the problem in two steps. The first step is the calculation of the minimum off-line cost of the tour associated with each subset of sites. One can observe that for any given subset of sites, the optimal Hamiltonian cycle linking those sites to the warehouse can be calculated in advance by a traveling salesman problem algorithm (TSP). The goal here is not to fully analyze the TSP, but rather to integrate its solution in the formulation of the JRP. In the second stage, binary variables are associated with each subset and each period to determine the selected subset of sites in each period and its associated fixed cost.

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces. / In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature.

Ce manuscrit présente des travaux visant à intégrer un module d'ordonnancement (ProSched) à l'environnement de modélisation et simulation dynamique hybride PrODHyS dans le but d'automatiser la génération de scénarii de simulation de procédés discontinus sur la base d'une recette et d'une liste d'ordres de fabrication (OF). La méthodologie développée repose sur une approche mixte optimisation/simulation. Dans ce cadre, trois points essentiels ont été développés dans ces travaux : - tout d'abord, concevoir et développer des composants réutilisables (classes de recette) permettant de modéliser de manière hiérarchisée et systématique le déroulement des opérations unitaires. Pour cela, les notions de jeton Task et de macro-place paramétrable ont été introduites dans les RdPDO et permettent de décrire les recettes à réaliser par assemblage de ces composants prédéfinis. - ensuite, définir un modèle mathématique générique d'ordonnancement basé sur un formalisme de représentation bien établi (le R.T.N.) qui permet de modéliser les principales caractéristiques d'un procédé discontinu et de fournir l'ensemble des données d'entrée nécessaires au modèle de simulation. Pour cela, un modèle PLNE basé sur la formulation Unit Specific Event a été mis en œuvre. - enfin, définir l'interface existant entre le modèle d'optimisation et le modèle de simulation, à travers la notion de place de pilotage et de centre de décision au niveau du simulateur. Dans ce cadre, différentes stratégies de couplage sont proposées. Les potentialités de cette approche sont illustrées par la simulation d'un procédé complet. / This thesis presents works which aim to incorporate a scheduling module (ProSched) to an environment for modeling and dynamic hybrid simulation PrODHyS in order to automate the generation of scenarios for simulation of batch processes based on a recipe and a list of production orders (OF). The methodology developed is based on a mixed optimization / simulation approach. In this context, three key points have been developed in this work: - First, design and develop reusable components (recipe classes) for the hierarchical and systematic modeling of the sequencing of unit operations. For this, the notions of Task token and macro-place have been introduced in the RdPDO formalism and allow the modeling of recipes by assembling these predefined components. - Secondly, define a generic mathematical model of scheduling based on a well defined graphical formalism (RTN) that models the main characteristics of batch processes and provide all input data necessary to the simulation model. For this, a MILP model based on the Unit Specific Event formulation has been implemented. - Finally, define the interface between the optimization model and the simulation model through the concept of control place and decision-making center at the simulator level. In this context, various strategies of mixing optimization and simulation are proposed. The potential of this approach is illustrated by the simulation of a complete manufacturing process

La contribution des changements d’usage des sols aux émissions de gaz à effet de serre d’origine anthropique est estimée à 17% pour la décennie 2000, en grande partie liée à la déforestation. L’un des facteurs principaux de ces changements est l’expansion des terres agricoles pour les besoins locaux de développement, mais également sous l’effet des exportations stimulées par la mondialisation. Pour cette raison, des préoccupations nouvelles surgissent quant aux effets des politiques sur l’usage des sols par le biais des marchés internationaux. Ce travail présente trois illustrations concrètes où ces effets peuvent être d’ampleur conséquente : i) l’intensification de l’agriculture dans les pays en voie de développement, ii) les accords commerciaux, et iii) les politiques d’agrocarburants. Les résultats montrent que pour chacune de ces politiques, les réponses des marchés sont susceptibles de jouer un rôle déterminant dans le bilan des gaz à effet de serre. L’atténuation du changement climatique par l’intensification des cultures conduit à des réductions d’émissions, mais l’effet rebond de la demande pourrait annuler une part substantielle des bénéfices attendus sur les surfaces de terres cultivées. L’exemple d’un possible accord entre l’Union européenne et le Mercosur montre les effets négatifs que peut induire la libéralisation de certains produits agricoles, si des mesures d’accompagnement adéquates ne sont pas mises en place. Enfin, l’effet des changements indirects d’affectation des sols est susceptible d’effacer une part substantielle des réductions d’émissions alléguées aux agrocarburants. Les réponses de l’affectation des sols aux différentes politiques dépendent néanmoins de nombreux paramètres comportementaux, et il est difficile d’en fournir une estimation chiffrée précise. Plusieurs approches de modélisation sont utilisées ici pour quantifier ces effets et explorer les intervalles de confiance découlant des estimations actuelles de la littérature économétrique. La prise en compte de cette externalité dans l’évaluation des politiques publiques nécessite des approches nouvelles intégrant mieux les différents niveaux d’incertitude sur ces effets. / Land use change is estimated to have generated 17% of anthropogenic greenhouse gas emissions in the 2000s, a large part coming from deforestation. The main driver of these emissions is expansion of agricultural activities, for the need of local development in tropical regions. However, they have also been caused by the dynamics of globalisation which has stimulated agricultural trade flows. Thus, today, there are new concerns with respect to how agricultural policies are influencing land use changes in other parts of the world through international market responses. In this work I consider three concrete illustrations of where these effects can be of significant magnitude: i) agriculture intensification in developing countries, ii) trade agreements, and iii) biofuel policies. I find that for each of these policies, market responses are likely to play a significant role in the final greenhouse gas emission balance. Mitigation of emissions through agricultural intensification could have quite beneficial outcomes, but the rebound effect on the demand side would offset a large part of greenhouse gas emission savings attributable to the land sparing effect. With the example of a possible EU-MERCOSUR trade agreement, I also show the adverse effect of liberalising certain specific agricultural products closely connected to land use change dynamics without adequate accompanying measures. Last, the indirect land use change effect of biofuels is likely to offset a large part of their alleged GHG emission savings. Land use change responses depend on many behavioural parameters, however, and providing precise estimates constitutes a challenge. I use different modelling approaches to quantify their magnitude and extensively explore the level of confidence on the basis of current state of econometric findings.New approaches should be elaborated to take account of this externality in public policy assessments, together with an appropriate consideration of the uncertainty ranges associated with these effects.

Le transport fluvial de conteneurs constitue une activité économique importante qui suscite un intérêt grandissant de la part de scientifiques. Considéré comme durable et économique, le transport par barge a été identifié comme étant une alternative compétitive pour le transport de marchandises, en complément des modes traditionnels de transport, routier et ferroviaire. Néanmoins, les travaux de recherche en rapport avec la planification et le management du transport par barge, en particulier dans le contexte du transport intermodal, sont encore peu abondants. Le but de cette thèse est d’apporter une contribution dans ce domaine, par la proposition de modèles et de méthodes de planification et gestion avancées, dans le cadre d’un système d’aide à la décision pour le transport de conteneurs par barge développé pour accompagner les opérateurs de transport. La méthodologie proposée fait appel à des concepts et principes de gestion du revenu, des ressources et des services de transport pour la conception de plans de services réguliers avec horaires, au niveau tactique. Les opérateurs de transport peuvent ainsi offrir des plans de transport avec des services plus flexibles pour leurs clients, tout en assurant un meilleur niveau de fiabilité. Plus de demandes de transport pourront ainsi être satisfaites, avec globalement une plus grande satisfaction des chargeurs. Une originalité importante proposée par notre approche est l’utilisation de principes et techniques de gestion du revenu (segmentation du marché, classes tarifaires...) aussi bien au niveau opérationnel de la modélisation qu’au niveau tactique. Les problèmes d’optimisation sont formalisés sous forme de modèles de programmation linéaire mixte en nombres entiers (PLNE), implémentés et testés sous différentes configurations de réseaux de transport et différents scénarios de demandes, et ce pour chaque niveau de décision. Au niveau tactique, une nouvelle approche de résolution, combinant la recherche adaptative à voisinage large (ALNS) et la recherche taboue, est proposée pour résoudre des problèmes PLNE de grande taille. Une plateforme de simulation, qui intègre les niveaux tactique et opérationnel de prise de décision, est proposée pour la validation du système d’aide à la décision sous différentes configurations : différentes topologies du réseau physique, différents paramètres pour la gestion du revenu, différents degrés de précision caractérisant les prévisions de demande. Pour l’analyse des résultats numériques ainsi obtenus, plusieurs types d’indicateurs de performance sont proposés et utilisés. / Barge transportation is an important research topic that started to draw increasing scientific attention in the recent decade. Considered as sustainable, environment-friendly and economical, barge transportation has been identified as a competitive alternative for freight transportation, complementing the traditional road and rail modes. However, contributions related to barge transportation, especially in the context of intermodal transportation, are still scarce. The objective of this thesis is to contribute to fill this gap by proposing a reactive decision support system for freight intermodal barge transportation from the perspective of the carriers. The proposed system incorporates resource and revenue management concepts and principles to build the optimal set of scheduled services plans at the tactical level. Carriers may thus benefit from transportation plans offering increased flexibility and reliability. They could thus serve more demands and better satisfy customers. One novelty of the approach is the application of revenue management considerations (e.g., market segmentation and price differentiation) at both operational and tactical planning levels. The optimization problems are mathematically formalized and mixed integer linear programming (MILP) models are proposed, implemented and tested against various network settings and demand scenarios, for each decision level. At the tactical level, a new solution approach, combining adaptive large neighborhood search (ALNS) and Tabu search is designed to solve large scale MILP problems. An integrated simulation framework, including the tactical and the operational levels jointly, is proposed to validate the decision support system in different settings, in terms of physical network topology, revenue management parameters and accuracy degree of demand forecasts. To analyze the numerical results corresponding to the solutions of the optimization problems, several categories of performance indicators are proposed and used.

Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes. / This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.

Nous étudions les systèmes de véhicules en libre service en aller-simple : avec emprunt et restitution dans des lieux éventuellement différents. La publicité promeut l'image de flexibilité et d'accessibilité (tarifaire) de tels systèmes, mais en réalité il arrive qu'il n'y ait pas de véhicule disponible au départ, voire pire, pas de place à l'arrivée. Il est envisageable (et pratiqué pour Vélib' à Paris) de relocaliser les véhicules pour éviter que certaines stations soient vides ou pleines à cause des marées ou de la gravitation. Notre parti-pris est cependant de ne pas considérer de "relocalisation physique" (à base de tournées de camions) en raison du coût, du trafic et de la pollution occasionnées (surtout pour des systèmes de voitures, comme Autolib' à Paris). La question à laquelle nous désirons répondre dans cette thèse est la suivante : Une gestion via des tarifs incitatifs permet-elle d'améliorer significativement les performances des systèmes de véhicules en libre service ?

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.