Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd Easton / This thesis introduces the Bay Crane Scheduling (BCS) problem and related BCS algorithm. The purpose of this algorithm is to optimize the assignment of jobs to overhead cranes as well as the sequence in which each crane performs its assigned jobs. This problem is unique from other Overhead Crane Scheduling (OCS) problems through its increased complexity. Up until now, OCS problems involve a set number of cranes operating in a single common area, referred to as a bay, and are unable to pass over each other. The BCS problem involves a varying number of active cranes operating in multiple bays. Each crane is allowed to move from one bay to the next, through specific locations called bridges. This is crucial to completing certain “special” jobs that require two cranes operating in unison to transport an item. The BCS algorithm employs two continuous time simulations in conjunction with an initial job-assignment algorithm and a Simulated Annealing (SA) improvement heuristic in order to minimize the non-productive crane time, while avoiding overloading any crane. To the extent of the author’s knowledge, this is the first time a continuous time simulation has been used to model an OC system. The BCS algorithm was originally developed for a large manufacturing facility, and when it was tested against the facility’s current scheduling methods, it shows a 20% improvement in the overall active crane time required to complete equivalent set of jobs. This improved efficiency is crucial to the manufacturing facility being able to increase its production rate without the addition of new cranes. In addition, BCS is statistically shown to be superior to the current strategy. The results from BCS are substantial and practitioners are encouraged to utilize BCS’s methodologies to improve other overhead crane systems.

De nos jours, les plateformes portuaires cherchent à massifier leurs capacités de projection de conteneurs vers et à partir de leurs réseaux hinterland en misant sur les modes ferroviaires et fluviaux. Cela pour évacuer plus rapidement un volume quasi croissant de conteneurs livré par voie maritime et d’éviter les situations indésirables, tels que les situations d'asphyxie. De plus, les plateformes portuaires ont pris conscience que leur attractivité aux yeux des prestataires logistiques dépend non seulement de leur fiabilité et de leurs qualités nautiques mais également de leur capacité à offrir une desserte massifiée de leur hinterland. Contrairement à ce qui a pu être observé en Europe, la part du transport massifié a quasiment stagné au Havre dans les dernières années. A cet effet, le port du Havre a mis en place un terminal multimodal de conteneurs lié par rail et par voie navigable à un hinterland riche et dense en population (Bassin parisien, Marchés européens), et par des navettes ferroviaires aux autres terminaux maritimes du port Havre. L’intérêt économique et stratégique de ce nouveau terminal est de renforcer la position du Grand Port Maritime du Havre au niveau national, européen et mondial, et d’un point de vue écologique, diminuer l’utilisation excessive du routier en misant sur les modes moins polluants. Dans cette thèse, les efforts se focalisent sur la modélisation et la simulation du déroulement des opérations de manutention et d’allocation de ressources dans un terminal à conteneurs et particulièrement l’ordonnancement des portiques de manutention. Étant donné qu’un terminal à conteneurs est un système complexe, nous avons d’abord défini une démarche de modélisation qui facilite le processus de construction du modèle de simulation. Cette démarche est un processus itératif permettant de raffiner le modèle au fur et à mesure des étapes de développement réalisées. Les différentes étapes de développement sont liées par une série de diagrammes qui permet d’exprimer de façon claire les éléments et les relations formant le modèle de simulation. Ensuite, nous avons intégré dans notre modèle deux stratégies de non-croisement de portiques au niveau de la cour ferroviaire du terminal multimodal. Le but de ces stratégies est la minimisation des temps et des mouvements improductifs pour améliorer la performance et la productivité des portiques de manutention. La première stratégie est basée sur des règles de mouvement et sur la collaboration et coopération entre agents portiques. Tandis que la deuxième stratégie est basée sur une heuristique. Ces deux solutions ont été testées en utilisant l’outil de simulation AnyLogic et les résultats obtenus montrent la qualité de nos solutions. Concernant le problème d’ordonnancement des portiques de la cour fluviale, nous l’avons étudié en utilisant un couplage Optimisation-Simulation. Dans ce problème les temps de chargement et de déchargement de conteneurs et les temps de déplacement des portiques entre les baies sont considérés comme incertains. Le couplage est composé d’une méta-heuristique colonie de fourmis et d’un modèle de simulation à base d’agents. Chaque solution (une séquence de tâches) trouvée par l’algorithme d'optimisation est simulée et évaluée pour déterminer les nouvelles durées des tâches qui seront ensuite injectées comme données d’entrée de l’algorithme avant l’itération suivante. / Nowadays, seaports seek to achieve a better massification share of their hinterland transport by promoting rail and river connections in order to more rapidly evacuate increasing container traffic shipped by sea and to avoid landside congestion. Furthermore, the attractiveness of a seaport to shipping enterprises depends not only on its reliability and nautical qualities but also on its massified hinterland connection capacity. Contrary to what has been observed in Europe, the massification share of Le Havre seaport has stagnated in recent years. To overcome this situation, Le Havre Port Authority is putting into service a multimodal hub terminal. This terminal is linked only with massified modes to a rich and dense geographical regions (Ile de France, Lyon), and with rail shuttles to the maritime terminals of Le Havre seaport. The aim of this new terminal is to restrict the intensive use of roads and to provide a river connection to its maritime terminals (MTs) that do not include a river connection from the beginning. In this study, we focus on the modeling and the simulation of container terminal operations (planning, scheduling, handling …) and particularly crane scheduling in operating areas. Designing multi-agents based simulation models for the operation management of a complex and dynamic system is often a laborious and tedious task, which requires the definition of a modeling approach in order to simplify the design process. In this way, we defined a top-down approach with several steps of specification, conception, implementation and verification-validation. This approach is an iterative process that allows the model to become more complex and more detailed. In this thesis, we pay more attention to crane scheduling problem in operating areas. For the rail-rail transshipment yard of the multimodal terminal, we designed two anti-collision strategies that aim to minimize unproductive times and moves to improve crane productivity and to speed up freight train processing. These strategies are tested using multi-method simulation software (Anylogic) and the simulation results reveal that our solutions are very satisfactory and outperform other existing solutions. With regard the fluvial yard, the stochastic version of crane scheduling problem is studied. The problem is solved with a mixed Optimization-Simulation approach, where the loading and unloading times of containers and travel times of cranes between bays are considered uncertain. The used approach is composed of an Ant Colony Optimization (ACO) metaheuristic coupled to an agent-based simulation model. Each solution (a tasks sequence) found by the optimization algorithm is simulated and evaluated to determine the new tasks’ periods which will then be injected as input to the ACO algorithm before the next iteration. The coupling is executed until the difference between the last iterations is too low.

A comprehensive study on berth and quay crane scheduling problems at container terminals at seaports is provided. Problems related to both multi-user terminals, where the terminal operator and liner carriers are different parties, and dedicated terminals, where liner carriers lease the terminal, are considered. A lower bound and an effective meta-heuristic algorithm are proposed for a dynamic variant of the Berth Allocation Problem (BAP). The Multiple Berth Allocation Problem (MBAP) is also introduced. Different crane scheduling methods used by terminal operators are analyzed and a tabu search algorithm is designed for a new variant of the Quay Crane Scheduling Problem (QCSP). The Simultaneous Berth and Quay Crane Scheduling Problem (BQCSP) is introduced with a lower bound analysis and an efficient solution method. A computational analysis is performed which exposes the substantial benefit of simultaneous planning over the hierarchical approach currently used by terminal operators. The tactical level Voyage and Berth Scheduling Problem (VBSP) is defined and a mathematical model based on multi-commodity network flow is presented. Constraints related to transshipments, terminal time windows and service level requirements are incorporated into the model, and how to modify instance data to increase schedule reliability is discussed.

Rail-road terminals are the chain links in intermodal rail-road transportation where standardized load units (containers, swap bodies and trailers) are transfered from trucks to trains and vice versa. We consider three subproblems of the operational planning process at rail-road terminals that terminal operators are facing in their daily operations. These are the optimization problems storage planning, load planning and crane planning. The aim of storage planning is to determine load unit storage positions for a set of load units in a partially filled storage area. Here, different restrictions like non-overlapping of stored load units have to be respected. The objective of storage planning is to minimize the total transportation costs and the number of load units that are not stored at the ground level. For the load planning we assume a scenario of overbooked trains. So, the aim of load planning is to assign a subset of the load units that are booked on a train to feasible positions on the wagons such that the utilization of the train is maximized and the costs for the handling in the terminal are minimized. For the feasible positioning of load units length and weight restrictions for the wagons and the train have to be respected. For the load planning of trains we consider a deterministic version and a robust approach motivated by uncertainty in the input data. The last considered optimization problem is the crane planning. The crane planning determines the transfer of the load units by crane between the different transportation modes. For each crane a working plan is computed which contains a subset of the load units that have to be handled together with individual start times for the transfer operations. For the load units which have to be transfered in the terminal, storage and load planning compute destination positions (inside the terminal). These destination positions are part of the input for the crane planning. The main objective of crane planning is to minimize the total length of the empty crane moves that have to be performed between successive transports of load units by the cranes. We provide MIP-models for all three subproblems of the operational planning process at rail-road terminals. For the storage and crane planning we also propose fast heuristics. Furthermore, we present and compare computational results based on real world data for all subproblems. The main contributions of this thesis concern load and storage planning. For the deterministic load planning we provide the first model that represents all practical constraints including physical weight restrictions. For the load planning we furthermore present robustness approaches for different practical uncertainties. For the storage planning we provide complexity results for different variants. For the practical setting we developed a heuristic which is able to compute solutions of high quality in a small amount of runtime.