Cette thèse porte sur la modélisation du trafic dans les réseaux routiers et comment celle-ci est intégrée dans des modèles d'optimisation. Ces deux sujets ont évolué de manière plutôt disjointe: le trafic est prédit par des modèles mathématiques de plus en plus complexes, mais ce progrès n'a pas été incorporé dans les modèles de design de réseau dans lesquels les usagers de la route jouent un rôle crucial. Le but de cet ouvrage est d'intégrer des modèles d'utilités aléatoires calibrés avec de vraies données dans certains modèles biniveaux d'optimisation et ce, par une décomposition de Benders efficace. Cette décomposition particulière s'avère être généralisable par rapport à une grande classe de problèmes communs dans la litérature et permet d'en résoudre des exemples de grande taille. Le premier article présente une méthodologie générale pour utiliser des données GPS d'une flotte de véhicules afin d'estimer les paramètres d'un modèle de demande dit recursive logit. Les traces GPS sont d'abord associées aux liens d'un réseau à l'aide d'un algorithme tenant compte de plusieurs facteurs. Les chemins formés par ces suites de liens et leurs caractéristiques sont utilisés afin d'estimer les paramètres d'un modèle de choix. Ces paramètres représentent la perception qu'ont les usagers de chacune de ces caractéristiques par rapport au choix de leur chemin. Les données utilisées dans cet article proviennent des véhicules appartenant à plusieurs compagnies de transport opérant principalement dans la région de Montréal. Le deuxième article aborde l'intégration d'un modèle de choix de chemin avec utilités aléatoires dans une nouvelle formulation biniveau pour le problème de capture de flot de trafic. Le modèle proposé permet de représenter différents comportements des usagers par rapport à leur choix de chemin en définissant les utilités d'arcs appropriées. Ces utilités sont stochastiques ce qui contribue d'autant plus à capturer un comportement réaliste des usagers. Le modèle biniveau est rendu linéaire à travers l'ajout d'un terme lagrangien basé sur la dualité forte et ceci mène à une décomposition de Benders particulièrement efficace. Les expériences numériques sont principalement menés sur un réseau représentant la ville de Winnipeg ce qui démontre la possibilité de résoudre des problèmes de taille relativement grande. Le troisième article démontre que l'approche du second article peut s'appliquer à une forme particulière de modèles biniveaux qui comprennent plusieurs problèmes différents. La décomposition est d'abord présentée dans un cadre général, puis dans un contexte où le second niveau du modèle biniveau est un problème de plus courts chemins. Afin d'établir que ce contexte inclut plusieurs applications, deux applications distinctes sont adaptées à la forme requise: le transport de matières dangeureuses et la capture de flot de trafic déterministe. Une troisième application, la conception et l'établissement de prix de réseau simultanés, est aussi présentée de manière similaire à l'Annexe B de cette thèse. / The subject of this thesis is the modeling of traffic in road networks and its integration in optimization models. In the literature, these two topics have to a large extent evolved independently: traffic is predicted more accurately by increasingly complex mathematical models, but this progress has not been incorporated in network design models where road users play a crucial role. The goal of this work is to integrate random utility models calibrated with real data into bilevel optimization models through an efficient Benders decomposition. This particular decomposition generalizes to a wide class of problems commonly found in the literature and can be used to solved large-scale instances. The first article presents a general methodology to use GPS data gathered from a fleet of vehicles to estimate the parameters of a recursive logit demand model. The GPS traces are first matched to the arcs of a network through an algorithm taking into account various factors. The paths resulting from these sequences of arcs, along with their characteristics, are used to estimate parameters of a choice model. The parameters represent users' perception of each of these characteristics in regards to their path choice behaviour. The data used in this article comes from trucks used by a number of transportation companies operating mainly in the Montreal region. The second article addresses the integration of a random utility maximization model in a new bilevel formulation for the general flow capture problem. The proposed model allows for a representation of different user behaviors in regards to their path choice by defining appropriate arc utilities. These arc utilities are stochastic which further contributes in capturing real user behavior. This bilevel model is linearized through the inclusion of a Lagrangian term based on strong duality which paves the way for a particularly efficient Benders decomposition. The numerical experiments are mostly conducted on a network representing the city of Winnipeg which demonstrates the ability to solve problems of a relatively large size. The third article illustrates how the approach used in the second article can be generalized to a particular form of bilevel models which encompasses many different problems. The decomposition is first presented in a general setting and subsequently in a context where the lower level of the bilevel model is a shortest path problem. In order to demonstrate that this form is general, two distinct applications are adapted to fit the required form: hazmat transportation network design and general flow capture. A third application, joint network design and pricing, is also similarly explored in Appendix B of this thesis.

La théorie des systèmes autopoïétiques, lancée par les biologistes Humberto Maturana et Francisco J. Varela, permet de décrire scientifiquement les principes organisationnels communs à tous les êtres vivants. Les principes autopoïétiques s’appliquent aussi, à l’état formel, à la vie psychique et à la vie sociale, comme le sociologue Niklas Luhmann a pu le montrer. Puisque la psychanalyse et la psychothérapie analytique se situent au carrefour du psychique et du relationnel, nous cherchons à expliciter les principes autopoïétiques qui sous-tendent leur théorie et leur pratique. En ce sens, la thèse est une comparaison critique des aspects essentiels de la psychothérapie analytique avec les principes généraux du vivant. Le travail se divise en trois chapitres, présentés sous forme d’articles scientifiques théoriques. Dans le premier chapitre, nous montrons comment le cadre et le processus analytique entretiennent une relation symbiotique, à la manière de la relation qu’entretient la membrane cellulaire avec les organites qu’elle contient. Ce faisant, nous mettons en évidence la clôture opérationnelle du cadre-processus analytique et nous argumentons que cela en fait un système social autopoïétique à part entière. Nous soulignons ensuite comment cette conceptualisation redéfinit la tâche éthique et pratique du clinicien, qui doit veiller à limiter les risques que l’environnement psychothérapeutique fait courir à l’autonomie du cadre-processus analytique. Nous poursuivons dans le second chapitre l’exploration des conséquences de notre proposition, à savoir que le clinicien et le patient puissent être amenés à nuire ou à résister au cadre-processus ; et que le cadre-processus, comme système autonome, puisse être lui-aussi amené à résister à ses participants. Il s’ensuit un besoin de comprendre les rapports de résistance entre ces systèmes, nous amenant à nous appuyer fermement sur le concept de couplage structurel issu de la théorie des systèmes autopoïétiques. Ce point de vue relance la réflexion sur le rôle de la subjectivité et de l’intersubjectivité en thérapie analytique et nous amène à privilégier une attitude clinique valorisant l’interaction autonome de tous les systèmes impliqués. Le troisième chapitre s’attaque de front à la question du transfert et du contre-transfert qui se profilait déjà à travers les chapitres précédents. En insistant sur le caractère radicalement inconscient du (contre)transfert, nous en proposons une redéfinition comme une forme particulière de couplage structurel entre les participants de la psychothérapie. En nous appuyant sur cette conceptualisation nouvelle, nous approfondissons la notion de communication analytique afin d’en montrer le potentiel thérapeutique. La recherche se termine par une contextualisation de ses principales conclusions dans le domaine plus large des soins de santé mentale. Enfin, nous soulignons non seulement les avantages et les limites de la thèse, mais également ses potentialités futures, comme l’ouverture vers une théorie générale de la psychothérapie. / The theory of autopoietic systems, pioneered by biologists Humberto Maturana and Francisco J. Varela, makes it possible to scientifically describe the organizing principles common to all living beings. Autopoietic principles also formally extend to psychic and social life, as argued the sociologist Niklas Luhmann. Since psychoanalysis and analytic psychotherapy are grounded in both the psychic and the relational domain, we aim to explicit the autopoietic principles underlying their theory and practice. In this respect, the thesis compares the essential aspects of analytic psychotherapy with the general principles of living systems. The work is divided into three chapters, presented as theoretical scientific articles. The first chapter shows how the analytic setting and analytic process maintain a symbiotic relationship, much like the relationship between the cell membrane and the organelles it contains. We thus describe the operational closure of the setting-process and argue that this makes it a full-fledged autopoietic social system. We then draw attention to how this conceptualization redefines the ethical and practical task of the clinician, who must limit the risk of environmental pressures disrupting the autonomy of the analytic setting-process. In the second chapter, we continue to explore the consequences of our proposal, arguing that the clinician and the patient may resist the setting-process of analytic psychotherapy; and that the setting-process, as an autonomous system, can also resist its participants. There follows a need to understand the resistances between these systems, leading us to rely on the concept of structural coupling derived from the theory of autopoietic systems. This original point of view fuels reflection on the role of subjectivity and intersubjectivity in analytical therapy and leads us to favor a clinical position that values the autonomous interaction of all the systems involved. The third chapter tackles head-on the problem of transference and countertransference that has already been looming over the previous chapters. By insisting on the radically unconscious character of (counter) transference, we suggest redefining it as a particular form of structural coupling between the participants of psychotherapy. From this new conceptualization, we deepen the notion of analytic communication and highlight its therapeutic potential. The research ends with a contextualization of its main findings in the broader field of mental health care. Finally, we underline not only the advantages and the limits of the thesis, but also future possibilities such as moving towards a general theory of psychotherapy.

No description available.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.

Les problèmes de localisation-routage à deux échelons (2E-LRP) sont devenus un domaine de recherche important dans le domaine de la logistique et de la gestion de la chaîne d'approvisionnement. Le 2E-LRP représente un problème d'optimisation dans les systèmes de distribution non dirigés, visant à organiser le transport de marchandises entre les plateformes et les clients par le biais d'installations intermédiaires appelées satellites. Ce problème implique de prendre des décisions simultanées concernant l'emplacement d'un ou deux niveaux d'installations (plateformes et/ou satellites) et de créer un ensemble limité d'itinéraires aux deux échelons afin de répondre efficacement à toutes les demandes des clients. Récemment, la communauté scientifique s'est intéressée de plus en plus à l'étude et à la résolution de problèmes plus réalistes. Cet intérêt provient de la reconnaissance du fait que les systèmes de distribution du monde réel sont caractérisés par une multitude de complexités et d'incertitudes qui ont un impact significatif sur l'efficacité opérationnelle, la rentabilité et la satisfaction des clients. Les chercheurs ont reconnu la nécessité d'aborder ces complexités et incertitudes pour développer des solutions pratiques et efficaces. Cette thèse comprend trois études différentes, chacune correspondant à un article de recherche autonome. Dans les trois articles, nous nous concentrons sur différents 2E-LRP riches qui comprennent plusieurs attributs en interaction. Ces variantes du problème sont appelées problèmes de localisation-routage à deux échelons et à attributs multiples (2E-MALRP). Pour analyser l'influence des incertitudes sur les solutions optimales et les processus de prise de décision, nous considérons à la fois les perspectives déterministes et stochastiques. Cette approche nous permet de mieux comprendre le comportement de ces problèmes complexes. Le premier document de recherche abordé dans cette thèse se concentre sur un problème de localisation-routage déterministe à deux échelons et à attributs multiples avec synchronisation de la flotte dans les installations intermédiaires (2E-MALRPS). Le cadre du problème comprend divers facteurs, notamment la demande de marchandises multiples dépendant du temps, les fenêtres temporelles, le manque de capacité de stockage dans les installations intermédiaires et la nécessité de synchroniser les flottes opérant à différents échelons. Dans le 2E-MALRPS, tous les paramètres, tels que les demandes des clients, les temps de trajet et les coûts, sont connus avec certitude. Dans cet article, nous introduisons le cadre du problème, présentons une formulation de programmation en nombres entiers mixtes et proposons un cadre de découverte de discrétisation dynamique comme méthode de résolution du problème. Le deuxième article de cette thèse traite du problème de localisation-routage à deux échelons en cas de demandes stochastiques et corrélées (2E-MLRPSCD). Contrairement au 2E-MALRPS, le 2E-MLRPSCD prend en compte les incertitudes liées aux demandes des clients, ainsi que la corrélation entre ces demandes. Nous formulons le problème sous la forme d'un modèle de programmation stochastique en deux étapes. Au cours de la première étape, des décisions sont prises concernant la conception des installations satellites, tandis qu'au cours de la deuxième étape, des décisions de recours déterminent la manière dont les demandes observées sont servies. Nous proposons une métaheuristique de couverture progressive comme méthode de résolution. Dans cette approche, nous incorporons deux structures de population dans le cadre de la couverture progressive. Ces structures renforcent la diversité des décisions de conception obtenues pour chaque sous-problème de scénario et fournissent des informations pertinentes pour améliorer la qualité de la solution. En outre, nous introduisons et comparons trois nouvelles stratégies différentes pour accélérer la recherche de l'espace de solution pour le problème stochastique. Finalement, le troisième article présenté dans cette thèse se concentre sur un problème de localisation-routage multi-attributs à deux échelons avec des temps de trajet stochastiques (2E-MALRPSTT). Le 2E-MALRPSTT combine un problème multi-attributs riche avec des éléments stochastiques, en particulier en considérant des temps de trajet stochastiques. Pour traiter le problème stochastique complet, un cadre de couverture progressive (PH) est proposé en s'appuyant sur les lignes directrices méthodologiques définies dans notre deuxième article pour le 2E-MLRPSCD. En outre, une heuristique basée sur la décomposition est introduite pour accélérer le cadre PH, et deux nouvelles stratégies d'agrégation sont présentées pour accélérer le processus de consensus concernant les décisions de la première étape. Les contributions présentées dans cette thèse couvrent divers aspects de la modélisation et des méthodologies de solution pour les 2E-MALRP riches, à la fois d'un point de vue déterministe et d'un point de vue stochastique. Les trois articles inclus dans cette thèse démontrent l'efficacité des approches proposées à travers des campagnes expérimentales étendues, mettant en évidence leur efficacité de calcul et la qualité des solutions, en particulier dans les cas difficiles. En abordant les aspects déterministes et stochastiques de ces 2E-MALRP, cette thèse vise à contribuer à l'ensemble des connaissances en optimisation de la logistique et de la chaîne d'approvisionnement, à répondre aux besoins importants de la littérature actuelle et à fournir des informations importantes pour les systèmes de distribution à deux échelons dans divers contextes. / The Two-Echelon Location-Routing Problems (2E-LRPs) have emerged as a prominent research area within the field of logistics and supply chain management. The 2E-LRP represents an optimization problem in undirected distribution systems, aiming to streamline freight transportation between platforms and customers through intermediate facilities known as satellites. This problem involves making simultaneous decisions concerning the location of one or two levels of facilities (platforms and/or satellites) and creating a limited set of routes at both echelons to effectively serve all customer demands. In recent years, there has been a growing interest among the scientific community in studying and solving more realistic problem settings. This interest arises from the recognition that real-world distribution systems are characterized by a multitude of complexities and uncertainties that significantly impact operational efficiency, cost-effectiveness, and customer satisfaction. Researchers have acknowledged the need to address these complexities and uncertainties to develop practical and effective solutions. This dissertation comprises three distinct studies, each serving as a self-contained research article. In all three articles, we focus on different rich 2E-LRPs that encompass multiple interacting attributes. These problem variants are referred to as two-echelon multi-attribute location-routing problems (2E-MALRPs). To analyze the influence of uncertainties on optimal solutions and decision-making processes, we consider both deterministic and stochastic perspectives. This approach allows us to gain insights into the behavior of these complex problem settings. The first research paper addressed in this thesis focuses on a deterministic two-echelon multi-attribute location-routing problem with fleet synchronization at intermediate facilities (2E-MALRPS). The problem setting encompasses various factors, including time-dependent multicommodity demand, time windows, lack of storage capacity at intermediate facilities, and the need for synchronization of fleets operating at different echelons. In the 2E-MALRPS, all parameters, such as customer demands, travel times, and costs, are known with certainty. In this paper, we introduce the problem setting, present a mixed-integer programming formulation, and propose a dynamic discretization discovery framework as the solution method to address the problem. The second paper in this thesis addresses the two-echelon multicommodity location-routing problem with stochastic and correlated demands (2E-MLRPSCD). In contrast to the 2E-MALRPS, the 2E-MLRPSCD takes into account uncertainties related to customer demands, as well as the correlation among these demands. We formulate the problem as a two-stage stochastic programming model. In the first stage, decisions are made regarding the design of satellite facilities, while in the second stage, recourse decisions determine how the observed demands are allocated and served. We propose a progressive hedging metaheuristic as the solution method. In this approach, we incorporate two population structures within the progressive hedging framework. These structures enhance the diversity of the design decisions obtained for each scenario subproblem and provide valuable insights for improving the solution quality. Additionally, We also introduce and compare three different novel strategies to accelerate the search for the solution space for the stochastic problem. Finally, the third paper presented in this thesis focuses on a multi-attribute two-echelon location-routing problem with stochastic travel times (2E-MALRPSTT). The 2E-MALRPSTT combines a rich multi-attribute problem setting with stochastic elements, specifically considering stochastic travel times. To address the complete stochastic problem, a progressive hedging metaheuristic is proposed building on the methodological guidelines defined in our second paper for the 2E-MLRPSCD. Furthermore, a decomposition-based heuristic is introduced to accelerate the PH framework, and two novel selection strategies are presented to expedite the consensus process regarding the first-stage decisions. The contributions presented in this thesis encompass various aspects of modeling and solution methodologies for rich 2E-MALRPs from both deterministic and stochastic perspectives. The three articles included in this thesis demonstrate the effectiveness of the proposed approaches through extensive experimental campaigns, highlighting their computational efficiency and solution quality, particularly in challenging instances. By addressing the deterministic and stochastic aspects of these 2E-MALRPs, this thesis aims to contribute to the broader body of knowledge in logistics and supply chain optimization, fill important gaps in the present literature and provide valuable insights for two-echelon distribution systems in diverse settings.

Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.

A travers cette thèse, nous montrons l'importance de la modélisation et de la coopération de métaheuristiques pour la résolution de problèmes réels en bioinformatique. Pour ce faire, deux problèmes ont été étudiés : le premier dans le domaine de la protéomique pour l'identification de protéines à partir de données spectrales et le second dans le domaine de l'analyse structurale de molécules pour le problème du docking moléculaire flexible. Ainsi, pour le premier problème, un nouveau modèle basé sur une comparaison directe des bases de données protéiques avec les données expérimentales brutes a été mise en place. L'approche associée a été intégrée au sein d'un moteur d'identification par empreinte de masse peptide appelé ASCQ_ME. Ce modèle d'identification a permis ensuite de proposer et de valider une modélisation pour le problème de " de novo protein sequencing " qui consiste à retrouver la séquence d'une protéine à partir seulement des données expérimentales. Il s'agit d'un modèle en trois étapes appelé SSO pour " Sequence ", " Shape " et " Order ". Après une étude de chacune de ces étapes, SSO a été implémenté et testé à travers trois métaheuristiques collaborant de manière séquentielle. Pour le second problème, une étude des nouvelles modélisations multi-objectives a été menée et a conduit à la définition d'un ensemble de huit modèles différents testés à l'aide d'algorithmes génétiques multi-objectifs parallèles. Une douzaine de configuration d'opérateurs génétiques ont été testé afin de mettre en évidence l'efficacité de l'hybridation des algorithmes génétiques avec des recherches locales. Pour chacune des parties, l'implémentation et la mise en place des collaborations fut possible grâce à la plateforme ParadisEO et notamment grâce à mes contributions à la partie ParadisEO-MO dédiée aux métaheuristiques à base de solution unique. L'ensemble de ces travaux a été soutenu par le PPF BioInformatique de l'Université des Sciences et Technologies de Lille et le projet ANR Dock.

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 ?

Le problème d’ordre linéaire (LOP) a reçu beaucoup d’attention dans différents domaines d’application, allant de l’archéologie à l’ordonnancement en passant par l’économie et même de la psychologie mathématique. Ce problème est aussi connu pour être parmi les problèmes NP-difficiles. Nous considérons dans cette thèse une variante de (LOP) sous contrainte de cardinalité. Nous cherchons donc un ordre linéaire d’un sous-ensemble de sommets du graphe de préférences de cardinalité fixée et de poids maximum. Ce problème, appelé (FCLOP) pour ’fixed-cardinality linear ordering problem’, n’a pas été étudié en tant que tel dans la littérature scientifique même si plusieurs applications dans les domaines de macro-économie, de classification dominante ou de transport maritime existent concrètement. On retrouve en fait ses caractéristiques dans les modèles étendus de sous-graphes acycliques. Le problème d’ordre linéaire est déjà connu comme un problème NP-difficile et il a donné lieu à de nombreuses études, tant théoriques sur la structure polyédrale de l’ensemble des solutions réalisables en variables 0-1 que numériques grâce à des techniques de relaxation et de séparation progressive. Cependant on voit qu’il existe de nombreux cas dans la littérature, dans lesquelles des solveurs de Programmation Linéaire en nombres entiers comme CPLEX peuvent en résoudre certaines instances en moins de 10 secondes, mais une fois que la cardinalité est limitée, ces mêmes instances deviennent très difficiles à résoudre. Sur les aspects polyédraux, nous avons étudié le polytope de FCLOP, défini plusieurs classes d’inégalités valides et identifié la dimension ainsi que certaines inégalités qui définissent des facettes pour le polytope de FCLOP. Nous avons introduit un algorithme Relax-and-Cut basé sur ces résultats pour résoudre les instances du problème. Dans cette étude, nous nous sommes également concentrés sur la relaxation Lagrangienne pour résoudre ces cas difficiles. Nous avons étudié différentes stratégies de relaxation et nous avons comparé les bornes duales par rapport à la consolidation obtenue à partir de chaque stratégie de relâcher les contraintes afin de détecter le sous-ensemble des contraintes le plus approprié. Les résultats numériques montrent que nous pouvons trouver des bornes duales de très haute qualité. Nous avons également mis en place une méthode de décomposition Lagrangienne. Dans ce but, nous avons décomposé le modèle de FCLOP en trois sous-problèmes (au lieu de seulement deux) associés aux contraintes de ’tournoi’, de ’graphes sans circuits’ et de ’cardinalité’. Les résultats numériques montrent une amélioration significative de la qualité des bornes duales pour plusieurs cas. Nous avons aussi mis en oeuvre une méthode de plans sécants (cutting plane algorithm) basée sur la relaxation pure des contraintes de circuits. Dans cette méthode, on a relâché une partie des contraintes et on les a ajoutées au modèle au cas où il y a des de/des violations. Les résultats numériques montrent des performances prometteuses quant à la réduction du temps de calcul et à la résolution d’instances difficiles hors d’atteinte des solveurs classiques en PLNE. / Linear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from transportation and scheduling to economics and even archeology and mathematical psychology. It is classified as a NP-hard problem. Assume a complete weighted directed graph on V n , |V n |= n. A permutation of the elements of this finite set of vertices is a linear order. Now let p be a given fixed integer number, 0 ≤ p ≤ n. The p-Fixed Cardinality Linear Ordering Problem (FCLOP) is looking for a subset of vertices containing p nodes and a linear order on the nodes in S. Graphically, there exists exactly one directed arc between every pair of vertices in an LOP feasible solution, which is also a complete cycle-free digraph and the objective is to maximize the sum of the weights of all the arcs in a feasible solution. In the FCLOP, we are looking for a subset S ⊆ V n such that |S|= p and an LOP on these S nodes. Hence the objective is to find the best subset of the nodes and an LOP over these p nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution of the FCLOP is a complete cycle-free digraph on S plus a set of n − p vertices that are not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of the linear ordering problem as well as various exact and heuristic solution methods. The fixed cardinality linear ordering problem is presented for the first time in this PhD study, so as far as we know, there is no other study in the literature that has studied this problem. The linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature that can be solved by CPLEX in less than 10 seconds (when p = n), but once the cardinality number is limited to p (p < n), the instance is not anymore solvable due to the memory issue. We have studied the polytope corresponding to the FCLOP for different cardinality values. We have identified dimension of the polytope, proposed several classes of valid inequalities and showed that among these sets of valid inequalities, some of them are defining facets for the FCLOP polytope for different cardinality values. We have then introduced a Relax-and-Cut algorithm based on these results to solve instances of the FCLOP. To solve the instances of the problem, in the beginning, we have applied the Lagrangian relaxation algorithm. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable subproblem. Numerical results show that some of the relaxation strategies result better dual bound and some other contribute more in reducing the computational time and provide a relatively good dual bound in a shorter time. We have also implemented a Lagrangian decomposition algorithm, decom-6 posing the FCLOP model to three subproblems (instead of only two subproblems). The interest of decomposing the FCLOP model to three subproblems comes mostly from the nature of the three subproblems, which are relatively quite easier to solve compared to the initial FCLOP model. Numerical results show a significant improvement in the quality of dual bounds for several instances. We could also obtain relatively quite better dual bounds in a shorter time comparing to the other relaxation strategies. We have proposed a cutting plane algorithm based on the pure relaxation strategy. In this algorithm, we firstly relax a subset of constraints that due to the problem structure, a very few number of them are active. Then in the course of the branch-and-bound tree we verify if there exist any violated constraint among the relaxed constraints or. Then the characterized violated constraints will be globally added to the model. (...)

Le présent mémoire porte sur l’entraînement de l’infanterie canadienne lors de la Deuxième Guerre mondiale jusqu’à l’invasion de la Sicile par les troupes alliées en 1943. Malgré une puissance militaire incomparable, les Alliés déployés sur le Front de l’Ouest eurent énormément de difficulté à vaincre une armée allemande déjà passablement affaiblie par le Front russe. Malgré des effectifs militaires inférieurs et l’absence d’appui aérien soutenu, les troupes hitlériennes résistèrent avec acharnement aux offensives initiées par les Alliés qui furent surclassés à maintes reprises par les divisions de la Wehrmacht. À cet effet, les troupes d’infanterie canadiennes ne firent pas exception. La contre-performance inhérente aux opérations offensives canado-britanniques en Europe fut la résultante de nombreux facteurs de nature tactique, opérationnelle et politico-stratégique. La présente recherche se penche spécifiquement sur la culture militaire, la constitution de la doctrine tactique britannique et le syllabus d’entraînement pré-déploiement des troupes d’infanterie de l’armée canadienne. Une fois ces éléments comparés au modus operandi tactique de la Wehrmacht, il ne fait aucun doute que la doctrine et l’entraînement des troupes d’infanterie canadiennes ne furent tout simplement pas aptes à assurer une suprématie tactique sans failles de l’armée canadienne sur le continent européen.