Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Les modèles de conception des chaînes logistiques sont devenus de plus en plus complexes, à cause de l'environnement économique incertain et l'introduction de nouveaux critères de décision tels que : l'aspect environnemental, l'aspect social, l'aspect législatif, l'aspect économique, la satisfaction du client et la prise en compte des risques. Répondre aux changements qui touchent les chaînes logistiques exige de composer avec des incertitudes et des informations incomplètes. Configurer des chaînes logistiques multicritères avec prise en compte des incertitudes peut garantir la continuité des activités de l'entreprise.L'objectif principal de cette thèse est la conception de chaînes logistiques multicritères qui résistent aux changements et l'instabilité des marchés. Le manuscrit de cette thèse s'articule autour de sept principaux chapitres:1 - introduction.2 - Etat de l'art sur la conception des chaînes logistiques.3 -Conception des chaînes logistiques multicritères en mesure de répondre aux nouveauxcritères économiques, sociaux, environnementaux et législatifs.4 - Conception des chaînes logistiques multi-objectifs.5 - Développement d'une heuristique de résolution des problèmes de conception deschaînes logistiques de taille réelle.6 - Conception des chaînes logistiques avec prise en compte des incertitudes.7 - Conclusions et perspectives. / This thesis contributes to the debate on how uncertainty and concepts of sustainable development can be put into modern supply chain network and focuses on issues associated with the design of multi-criteria supply chain network under uncertainty. First, we study the literature review , which is a review of the current state of the art of Supply Chain Network Design approaches and resolution methods. Second, we propose a new methodology for multi-criteria Supply Chain Network Design (SCND) as well as its application to real Supply Chain Network (SCN), in order to satisfy the customers demand and respect the environmental, social, legislative, and economical requirements. The methodology consists of two different steps. In the first step, we use Geographic Information System (GIS) and Analytic Hierarchy Process (AHP) to buildthe model. Then, in the second step, we establish the optimal supply chain network using Mixed Integer Linear Programming model (MILP). Third, we extend the MILP to a multi-objective optimization model that captures a compromisebetween the total cost and the environment influence. We use Goal Programming approach seeking to reach the goals placed by Decision Maker. After that, we develop a novel heuristic solution method based on decomposition technique, to solve large scale supply chain network design problems that we failed to solve using exact methods. The heuristic method is tested on real case instances and numerical comparisons show that our heuristic yield high quality solutions in very limited CPU time. Finally, again, we extend the MILP model presented before where we assume that the costumer demands are uncertain. We use two-stage stochastic programming approach to model the supply chain network under demand uncertainty. Then, we address uncertainty in all SC parameters: opening costs, production costs, storage costs and customers demands. We use possibilistic linear programming approach to model the problem and we validate both approaches in a large application case.

Le Cloud est devenu une plate-forme très répandue pour le déploiement d'applications distribuées. Beaucoup d'entreprises peuvent sous-traiter leurs infrastructures d'hébergement et, ainsi, éviter des dépenses provenant d'investissements initiaux en infrastructure et de maintenance.Des petites et moyennes entreprises, en particulier, attirés par le modèle de coûts sur demande du Cloud, ont désormais accès à des fonctionnalités comme le passage à l'échelle, la disponibilité et la fiabilité, qui avant le Cloud étaient presque réservées à de grandes entreprises.Les services du Cloud peuvent être offerts aux utilisateurs de plusieurs façons. Dans cette thèse, nous nous concentrons sur le modèle d'Infrastructure sous Forme de Service. Ce modèle permet aux utilisateurs d’accéder à des ressources de calcul virtualisés sous forme de machine virtuelles (MVs).Pour installer une application distribuée, un client du Cloud doit d'abord définir l'association entre son application et l'infrastructure. Il est nécessaire de prendre en considération des contraintesde coût, de ressource et de communication pour pouvoir choisir un ensemble de MVs provenant d'opérateurs de Cloud publiques et privés le plus adaptés. Cependant, étant donné la quantité exponentiel de configurations, la définition manuelle de l'association entre application et infrastructure peut être un challenge dans des scénarios à large échelle ou ayant des contraintes importantes de temps. En effet, ce problème est une généralisation du problème de calcul de homomorphisme de graphes, qui est NP-complet.Dans cette thèse, nous adressons le problème de calculer des placements initiaux et de reconfiguration pour des applications distribuées sur potentiellement de multiples Clouds. L'objectif est de minimiser les coûts de location et de migration en satisfaisant des contraintes de ressources et communications. Pour cela, nous proposons des heuristiques performantes capables de calculer des placements de bonne qualité très rapidement pour des scénarios à petite et large échelles. Ces heuristiques, qui sont basées sur des algorithmes de partition de graphes et de vector packing, ont été évaluées en les comparant avec des approches de l'état de l'art comme des solveurs exactes et des méta-heuristiques. Nous montrons en utilisant des simulations que les heuristiques proposées arrivent à calculer des solutions de bonne qualité en quelques secondes tandis que des autres approches prennent des heures ou jours pour les calculer. / The Cloud has become a very popular platform for deploying distributed applications. Today, virtually any credit card holder can have access to Cloud services. There are many different ways of offering Cloud services to customers. In this thesis we especially focus on theInfrastructure as a Service (IaaS), a model that, usually, proposes virtualized computing resources to costumers in the form of virtual machines (VMs). Thanks to its attractive pay-as-you-use cost model, it is easier for customers, specially small and medium companies, to outsource hosting infrastructures and benefit of savings related to upfront investments and maintenance costs. Also, customers can have access to features such as scalability, availability, and reliability, which previously were almost exclusive for large companies. To deploy a distributed application, a Cloud customer must first consider the mapping between her application (or its parts) to the target infrastructure. She needs to take into consideration cost, resource, and communication constraints to select the most suitable set of VMs, from private and public Cloud providers. However, defining a mapping manually may be a challenge in large-scale or time constrained scenarios since the number of possible configuration explodes. Furthermore, when automating this process, scalability issues must be taken into account given that this mapping problem is a generalization of the graph homomorphism problem, which is NP-complete.In this thesis we address the problem of calculating initial and reconfiguration placements for distributed applications over possibly multiple Clouds. Our objective is to minimize renting and migration costs while satisfying applications' resource and communication constraints. We concentrate on the mapping between applications and Cloud infrastructure. Using an incremental approach, we split the problem into three different parts and propose efficient heuristics that can compute good quality placements very quickly for small and large scenarios. These heuristics are based on graph partition and vector packing heuristics and have been extensively evaluated against state of the art approaches such as MIP solvers and meta-heuristics. We show through simulations that the proposed heuristics manage to compute solutions in a few seconds that would take many hours or days for other approaches to compute.

Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ce document décrit de nouvelles modélisations et approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Nous étudions dans un premier temps plusieurs techniques de décomposition alliées à différentes méta-heuristiques basées sur des stratégies d'oscillation. Nous étudions ensuite le concept de fonctions dual-réalisables qui permettent d'obtenir des évaluations par défaut polynomiales pour des problèmes de conditionnement. Finalement, nous proposons des modèles originaux pour des problèmes de placement de rectangles. Nous utilisons ces modèles dans des méthodes de programmation par contraintes.

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

Le Problème de Transport à la Demande (PTD), consiste à prendre en charge le transport des personnes d'un lieu de départ vers un lieu d'arrivée. Il est caractérisé par un ensemble de demandes de transport et d'un nombre de véhicules disponible. L'ultime objectif dans ce travail de thèse est d'offrir une alternative optimisée au déplacement individuel et collectif. Le PTD est classé parmi les problèmes NP-difficile, la majorité des travaux de recherche ont été concentrés sur l'utilisation des méthodes approchées pour le résoudre.Ce problème est également multicritère, la solution proposée dans ce travail permet à la fois une réduction du temps de voyage et également de la distance parcourue. Dans cette thèse, nous proposons notre contribution à l'étude et à la résolution du problème de transport à la demande multicritère et dynamique en appliquant l'algorithme de recuit simulé multi-objectif. Une grande partie de notre travail concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un PTD. Ces approches utilisent une méthode multicritère qui s'appuie sur l'algorithme de recuit simulé. La modélisation du PTD est représentée par une architecture multi-acteurs. Cette architecture met en évidence l'aspect distribué du système ainsi que les interactions et les relations qui peuvent avoir lieu entre les différents acteurs. Nous présentons dans ce travail un Système Multi-Agents pour la planification des itinéraires des véhicules affectés au transport des voyageurs. Les agents de ce système utilisent le module d'optimisation développé dans la première partie

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.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.