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

Cette thèse s’intéresse au cas d’un port maritime dans lequel des terminaux à conteneurs coopèrent afin de fournir un meilleur service global. Pour coordonner les opérations entre les terminaux, un modèle et plusieurs méthodes de résolution sont proposés. L’objectif est de minimiser les temps de rotation des navires aux longs cours, des navires caboteurs, des barges fluviales et des trains. Une solution au modèle fournit une affectation des véhicules de transport de conteneurs aux terminaux, ce qui inclue les camions, ainsi qu’une allocation de ressources et des intervalles temporels pour leurs prises en charge et pour celles de leurs conteneurs. Pour obtenir des solutions au modèle, une formulation du problème comme un programme linéaire en variables mixtes est proposée, ainsi que plusieurs heuristiques basées sur la programmation mathématique. Une méthode de planification en horizon glissant est introduite pour la gestion dynamique avec prise en compte des incertitudes. Des expériences numériques sont conduites avec des milliers d’instances réalistes variées, dont les résultats indiquent la viabilité de notre approche. Des résultats démontrent qu’autoriser la coopération entre terminaux augmente significativement la performance du système. / This thesis deals with the case of a maritime port in which container terminals are cooperating to provide better global service. In order to coordinate operations between the terminals, a model and several solving methods are proposed. The objective is to minimize turnaround times of mother and feeder vessels, barges and trains. A solution to the model provides an assignment of container-transport vehicles to the terminals, including trucks, as well as an allocation of resources and time intervals to handle them and their containers. To obtain solutions to the model, a mixed-integer programming formulation is provided, as well as several mathematical programming based heuristics. A rolling horizon framework is introduced for dynamic management under uncertainty. Numerical experiments are conducted on thousands of various realistic instances. Results indicate the viability of our approach and demonstrate that allowing cooperation between terminals significantly increases the performance of the system.

Dans ce mémoire, nous nous intéressons à l’optimisation des mouvements improductifs de chargement/déchargement, appelés shiftings, dans les problèmes de transport. Dans le premier contexte,nous introduisons le problème de shifting dans le cas du voyageur de commerce. Notre objectif est de chercher un circuit hamiltonien qui optimise à la fois le coût distance et le coût shifting. Nous proposons une modélisation mathématique du problème, puis, nous adaptons la métaheuristique d’optimisation par colonies de fourmis sous sa forme séquentielle et parallèle pour le résoudre. Dans le deuxième contexte, nous abordons le problème d’optimisation des plans de chargement et d’arrimage des conteneurs dans des barges. Ce problème consiste à chercher l’emplacement le plus convenable de chaque conteneur dans les barges de façon à faciliter son déchargement dans la chronologie des ports à visiter. D'abord, nous introduisons une modélisation mathématique du problème dans le cas d’une seule barge ou différents ports du trajet ont des coûts shiftings non-uniformes. L’objectif est d’optimiser le coût total de shiftings, la stabilitélongitudinale de la barge et celle transversale. Ensuite, nous généralisons le problème au cas d’un système de convoi de barges. Nous proposons, d’abord, un modèle mathématique en nombres entiers, dans lequel, nous considérons l’aspect multi-objectif en optimisant le nombre de shiftings, la stabilité du convoi et le nombre de barges utilisées dans le convoi. Puis, nous adaptons la méthode nsga-II en se basant sur les heuristiques du problème de bin-packing.L'ensemble des résultats obtenus est évalué en utilisant des mesures de performances adaptées au problème. / This work outlines the optimization of unproductive loading/unloading movements, called shiftings, in transport problems. in the first context, we introduce the shifting in the case of the traveling salesman problem. our goal is to find a hamiltonian circuit that optimizes both distance and shifting costs. we propose a mathematical modeling of the problem, and then we adapt the ant colony optimization metaheuristic in its sequential and parallel form to solve it. in the second context, we address the 3d container stowage planning problem of barges. this problem consists in finding the most suitable location of each container in the barge in order to facilitate its retrieval in the chronology of ports to be visited. firstly, we introduce a mathematical modeling of the problem in the case of a single barge where different ports are of non-uniform operational costs. the main objective is to optimize the total shiftings fees, the longitudinal stability of the barge and the transverse one. then, we generalize our problem to the case of barge convoy systems. we first propose a suitable mathematical modeling, in which, we consider the multi-objective aspect by optimizing the total number of shiftings, the convoy stability and the number of the real-used barges in the convoy. in order to solve this new variant, we propose a novel adaptation of the multi-objective evolutionary algorithm nsga-ii (non-dominated sorting genetic algorithm-ii) based on a set of heuristics introduced by the bin-packing problem resolution methods. the numerical results are evaluated using performance measures adapted to theproblem.

Les terminaux à conteneurs utilisent les nouvelles technologies (EDI, RFID et GPS) pour échanger des données avec leurs partenaires, pour localiser les conteneurs et leurs équipements dans le terminal, et pour automatiser des tâches. Dans cette thèse, nous montrons comment ces informations peuvent être utilisées dans la gestion des opérations.La première partie utilise les informations sur les volumes annoncés pour affecter des ressources internes dans le but de minimiser le retard global au terminal. Nous représentons cette problématique à l'aide d'un problème de flot que nous implémentons comme programme linéaire mixte. Une étude de cas est réalisée pour un terminal du Grand Port Maritime de Marseille. En outre, nous combinons le problème d'affectation de ressources avec le dimensionnement d'un système de rendez-vous. Ceci permet de minimiser le retard global.La deuxième partie utilise les informations sur les conteneurs à retirer et leurs emplacements pour optimiser le déstockage. Le but est de retirer tous les conteneurs d'une rangée en minimisant le nombre de repositionnements parasites. Nous améliorons un modèle binaire, proposons une approche exacte de type branch and price - avec un sous-problème binaire et deux variantes d'un sous-problème énumératif - et en dérivons une approche heuristique - avec un sous-problème heuristique. L'approche exacte ne résout que les petites instances ; l'approche heuristique obtient des résultats satisfaisants mais devra être améliorée. Nous nous intéressons aussi à la version dynamique du problème où les informations sur les conteneurs à retirer arrivent petit à petit et comparons différentes stratégies de repositionnement. / Container terminals use intelligent freight technologies (e.g., EDI, RFID and GPS) to exchange data with their partners, to locate containers and equipment within the terminal, and to automate tasks. This thesis illustrated, via two examples, how this data may be used to optimize operations at the terminal.The first part uses information on announced volumes to allocate internal handling equipment. The objective is to minimize overall delays at the terminal. The problem is represented as a network flow problem and implemented as a linear mixed integer programming model. A case study for a terminal at the Grand Port Maritime de Marseille is carried out. We also showed that combining the allocation problem with the dimensioning of a truck appointment system may reduce overall delays at the terminal. The second part uses information on announced container retrievals and container positions to improve retrieval operations. The objective is to retrieve containers from a bay in a given sequence with a minimum number of parasite relocations. We improve an existing binary programming model and introduce an exact branch and price approach - with a binary subproblem and two variants of an enumerative subproblem - and a heuristic branch and price approach - with a heuristic subproblem. The exact approach solves only small instances; the heuristic approach performs well on several instances, but should be improved further. We also deal with a dynamic version of the problem where the retrieval order becomes revealed over time and evaluate different relocation strategies for this case.

Le but de ce travail est l'étude du problème de gestion de flot de conteneurs et de véhicules dans un réseau multimodal. Nous proposons une formulation du problème sous forme d'un modèle mathématique réaliste qui prend en considération les différents aspects liés au transport et au stockage des conteneurs et dont l'objectif est de minimiser le coût global de transport. Pour la résolution des grandes instances une approche de résolution bi-niveaux est proposée. Dans un premier niveau nous construisons un modèle agrégé plus facile à résoudre pour en extraire les décisions liées aux déplacements des trains et des barges ainsi qu'une borne duale de notre problème de base. Ces informations sont utilisées dans un deuxième niveau pour avoir des solutions de bonne qualité de notre problème par rapport aux solutions données par CPLEX en résolvant directement le modèle de base. Des résultats numériques sur des instances générées aléatoirement sont présentés et ils prouvent l'intérêt de l'approche de résolution proposée dans cette thèse. / The aim of this work is the study of the problem of managing the flow of containers and vehicles in a multimodal network. We propose a formulation of the problem under the form of a realistic mathematical model that takes into account the different aspects related to container transport and storage and whose objective is to minimize the overall cost of transport. For large-scale resolution, a two-level resolution approach is proposed. In a first level we build an aggregated model easier to solve to extract the decisions related to the movements of trains and barges as well as a dual terminal of our basic problem. This information is used in a second level to have good quality solutions of our problem compared to the solutions given by CPLEX by directly solving the basic model. Numerical results on randomly generated instances are presented and prove the value of the proposed resolution approach.

Les terminaux à conteneurs constituent des interfaces inter-modales essentielles pour le réseau de transport mondial. Une manutention efficace des conteneurs dans des terminaux est d'une importance cruciale pour la réduction des coûts de transport et la détermination des plans d'embarquement. Dans ce rapport de thèse, nous proposons principalement une approche de résolution distribuée à travers la description d'un modèle d'optimisation heuristique distribuée baptisé COSAH COntainer Stacking via multi-Agent approach and Heuristic methodqui permet de simuler, résoudre et optimiser l'espace de stockage disponible pour manier les départs et les arrivées des conteneurs dans un port fluvial ou maritime. Autrement dit, COSAH permet de minimiser le nombre total de mouvements parasites tout en respectant des contraintes dynamiques d'espace et de temps. Les performances de COSAH sont ensuite évaluées sur des instances générées aléatoirement, ainsi que des instances extraites de la réalité d'un port maritime tunisien : le port de Radès. En effet, nous avons procédé à une étude expérimentale implémentant et comparant COSAH à la version centralisée associée, toutes deux basées sur un algorithme de recherche non informée et un algorithme de recherche informée. Les résultats obtenus, présentés et illustrés, montrent l'efficacité de COSAH en particulier, et d'une méthode d'optimisation heuristique distribuée alliant les deux concepts : Agent et Heuristique, en général.

Le chargement/déchargement des conteneurs et leurs stockages provisoires dans le port est la plus importante et complexe tâche dans les terminaux portuaires. Elle est fortement liée au routage des grues de quai et son coût augmente considérablement surtout en absence d’une gestion efficace du terminal. Dans ce travail, nous étudions le problème de stockage des conteneurs (PSC). Il appartient à la catégorie des problèmes NP-difficiles et NP-complets. PSC consiste à déterminer un plan d’arrangement des conteneurs destinés à l’import et à l’export dans le port qui minimise les remaniements ultérieurs lors de leur transfert vers le bateau, camion ou train. En effet, le temps d'attente des camions des clients, le temps de transfert des grues de quai et le temps nécessaire au chargement/déchargement du navire sont avantageusement réduits. PSC est généralement étudié en considérant un seul type de conteneur. Cependant, plusieurs types de conteneurs sont utilisés dans les ports maritimes (dry, réfrigérés, toit ouvert,...). En outre, le problème de stockage de conteneurs peut être traité de façon statique ou dynamique (date d’arrivée et de départ des conteneurs incertains).L’objectif de cette thèse est de résoudre le PSC statique et le PSC dynamique pour un seul et plusieurs types de conteneurs en utilisant deux métaheuristiques : l’algorithme génétique, la recherche harmoniquePour vérifier la performance de chacune des approches proposées, une étude comparative des résultats générés par chaque méthode ainsi que celle de l’algorithme LIFO est établie / The loading and unloading of containers and their temporary storage in the container terminal are the most important and complex operation in seaport terminals. It is highly inter-related with the routing of yard crane and truck and their costs increased significantly especially without an efficient terminal management. To improve this process, an efficiency decision for the container storage space allocation must be taken.In this thesis, we studied the container storage problem (CSP). It falls into the category of NP hard and NP complete problems. CSP consists on finding the most suitable storage location for incoming containers that minimizes rehandling operations of containers during their transfer to the ship, truck or train. In fact, the wait time of customer trucks, the transfer time of yard crane and the Ship turnaround time are advantageously reduced.Generally, this problem is studied considering a single container type. However, this does not stand the problem under its real-life statement as there are multiple container types that should be considered, (refrigerated, open side, empty, dry, open top and tank). Often, containers arrive at the port dynamically over time and have an uncertain departure date (ship delayed, a ship down, delayed arrival of customer trucks…). Indeed, CSP must be studied in dynamic aspectThe objective of this thesis is to study Static CSP for a single and various container type and dynamic CSP for ONE and several container types and to propose solutions for each of them. Genetic algorithm and Harmony Search algorithm are used to solve these problems and we compare the results of each approach with the LIFO algorithm

No description available.

Les trains qui transportent des conteneurs empilés (en deux niveaux) sont un élément important du reseau de transport nord-americain. Le probleme de chargement des wagons correspond un probleme operationnel d'utilisation rencontre dans les terminaux ferroviaires. Elle consiste optimiser l’affectation des conteneurs des emplacements spécifiques sur les wagons. Ce mémoire est centré sur un article scientifique traitant le chargement optimal publié dans le Journal Européen de Recherche Opérationnelle (Volume 267, Numéro 1, Pages 107-119, 2018). Nous avons formule un modele lineaire en nombres entiers (ILP) et apporte un certain nombre de contributions. Premierement, nous avons proposé une méthodologie générale qui peut traiter des wagons double ou simple empilement avec des «patrons» de chargement arbitraires. Les les patrons tiennent un compte des dépendances de chargement entre les plateformes sur un wagon donne. Deuxiemement, nous avons modéliser les restrictions du centre de gravité (COG), les regles d’empilement et un nombre de restrictions techniques de chargement associees certains types de conteneurs et / ou de marchandises. Les resultats montrent que nous pouvons resoudre des instances de taille realiste dans un d´elai raisonnable en utilisant un solveur ILP commercial et nous illustrons que le fait de ne pas tenir compte de la correspondance conteneurs-wagons ainsi que des restrictions COG peut conduire une surestimation de la capacité disponible. / Double-stack trains are an important component of the railroad transport network for containerized cargo in specific markets such as North America. The load planning problem embodies an operational problem commonly faced in rail terminals by operators. It consists in optimizing the assignment of containers to specific locations on the train. The work in this thesis is centered around a scientific paper on the optimization on load planning problem for double stack-trains, published in the European Journal of Operation Research (Volume 267, Issue 1, Pages 1-398) on 16 May 2018. In the paper, we formulated an ILP model and made a number of contributions. First, we proposed a general methodology that can deal with double- or single-stack railcars with arbitrary loading patterns. The patterns account for loading dependencies between the platforms on a given railcar. Second, we modeled Center of gravity (COG) restrictions, stacking rules and a number of technical loading restrictions associated with certain types of containers and/or goods. Results show that we can solve realistic size instances in reasonable time using a commercial ILP solver and we illustrate that failing to account for containers-to-cars matching as well as COG restrictions may lead to an overestimation of the available train capacity.

Au cours de la dernière décennie, la complexité des applications a considérablement évolué afin de répondre aux besoins métiers émergeants. Leur conception implique une composition distribuée de composants logiciels. Ces applications fournissent des services à travers les interactions métiers maintenues par leurs composants. De telles applications sont intrinsèquement en évolution dynamique en raison de la dynamicité de leurs contextes. En effet, elles évoluent dans des environnements qui changent tout en présentant des conditions très dynamiques durant leur cycle de vie d’exécution. De tels contextes représentent une lourde charge pour les développeurs aussi bien pour leurs tâches de conception que de gestion. Cela a motivé́ le besoin de renforcer l’autonomie de gestion des applications pour les rendre moins dépendantes de l’intervention humaine en utilisant les principes de l’Informatique Autonomique. Les Systèmes Informatiques Autonomes (SIA) impliquent l’utilisation des boucles autonomiques, dédiées aux systèmes afin de les aider à accomplir leurs tâches de gestion. Ces boucles ont pour objectif d’adapter leurs systèmes à la dynamicité de leurs contextes, en se basant sur une logique d’adaptation intégrée. Cette logique est souvent donnée par des règles statiques codées manuellement. La construction de ces règles demande beaucoup de temps tout en exigeant une bonne expertise. En fait, elles nécessitent une compréhension approfondie de la dynamicité du système afin de prédire les adaptations précises à apporter à celui-ci. Par ailleurs, une telle logique ne peut envisager tous les scénarios d’adaptation possibles, donc, ne sera pas en mesure de prendre en compte des adaptations pour des situations précédemment inconnues. Les SIA devraient donc être assez sophistiqués afin de pouvoir faire face à la nature dynamique de leurs contextes et de pouvoir apprendre par eux-mêmes afin d’agir correctement dans des situations inconnues. Les SIA devraient également être capables d’apprendre de leur propre expérience passée afin de modifier leur logique d’adaptation en fonction de la dynamicité de leurs contextes. Dans ce manuscrit, nous abordons les lacunes décrites en utilisant les techniques d’Apprentissage par Renforcement (AR) afin de construire notre logique d’adaptation. Cependant, les approches fondées sur l’AR sont connues pour leur mauvaise performance lors des premières phases d’apprentissage. Cette mauvaise performance entrave leur utilisation dans le monde réel des systèmes déployés. Par conséquent, nous avons amélioré cette logique d’adaptation avec des capacités d’apprentissage plus performantes avec une approche AR en multi-pas. Notre objectif est d’optimiser la performance de l’apprentissage et de le rendre plus efficace et plus rapide, en particulier durant les premières phases d’apprentissage. Nous avons aussi proposé́ un cadriciel générique visant à aider les développeurs dans la construction d’applications auto-adaptatives. Nous avons donc proposé de transformer des applications existantes en ajoutant des capacités d’autonomie et d’apprentissage à leurs composants. La transformation consiste en l’encapsulation des composants dans des conteneurs autonomiques pour les doter du comportement auto-adaptatif nécessaire. Notre objectif est d’alléger la charge des tâches de gestion des développeurs et de leur permettre de se concentrer plus sur la logique métier de leurs applications. Les solutions proposées sont destinées à être génériques, granulaires et basées sur un standard connu, à savoir l’Architecture de Composant de Service. Enfin, nos propositions ont été évaluées et validées avec des résultats expérimentaux. Ils ont démontré leur efficacité en montrant un ajustement dynamique des applications transformées face aux dynamicités de leurs contextes en un temps beaucoup plus court comparé aux approches existantes / During the past decade, the complexity of applications has significantly scaled to satisfy the emerging business needs. Their design entails a composition of distributed and interacting software components. They provide services by means of the business interactions maintained by their components. Such applications are inherently in a dynamic evolution due to their context dynamics. Indeed, they evolve in changing environments while exhibiting highly dynamic conditions during their execution life-cycle (e.g., their load, availability, performance, etc.). Such contexts have burdened the applications developers with their design and management tasks. Subsequently, motivated the need to enforce the autonomy of their management to be less dependent on human interventions with the Autonomic Computing principles. Autonomic Computing Systems (ACS) implies the usage of autonomic loops, dedicated to help the system to achieve its management tasks. These loops main role is to adapt their associated systems to the dynamic of their contexts by acting upon an embedded adaptation logic. Most of time, this logic is given by static hand-coded rules, often concern-specific and potentially error-prone. It is undoubtedly time and effort-consuming while demanding a costly expertise. Actually, it requires a thorough understanding of the system design and dynamics to predict the accurate adaptations to bring to the system. Furthermore, such logic cannot envisage all the possible adaptation scenarios, hence, not able to take appropriate adaptations for previously unknown situations. ACS should be sophisticated enough to cope with the dynamic nature of their contexts and be able to learn on their own to properly act in unknown situations. They should also be able to learn from their past experiences and modify their adaptation logic according to their context dynamics. In this thesis manuscript, we address the described shortcomings by using Reinforcement Learning (RL) techniques to build our adaptation logic. Nevertheless, RL-based approaches are known for their poor performance during the early stages of learning. This poor performance hinders their usage in real-world deployed systems. Accordingly, we enhanced the adaptation logic with sophisticated and better-performing learning abilities with a multi-step RL approach. Our main objective is to optimize the learning performance and render it timely-efficient which considerably improves the ACS performance even during the beginning of learning phase. Thereafter, we pushed further our work by proposing a generic framework aimed to support the application developers in building self-adaptive applications. We proposed to transform existing applications by dynamically adding autonomic and learning abilities to their components. The transformation entails the encapsulation of components into autonomic containers to provide them with the needed self-adaptive behavior. The objective is to alleviate the burden of management tasks on the developers and let them focus on the business logic of their applications. The proposed solutions are intended to be generic, granular and based on a well known standard (i.e., Service Component Architecture). Finally, our proposals were evaluated and validated with experimental results. They demonstrated their effectiveness by showing a dynamic adjustment to the transformed application to its context changes in a shorter time as compared to existing approaches