Optimization study on container operations in maritime transportation

Abstract

This thesis studies optimization problems of container operations in maritime transportation. As the engine of global economic development, maritime transportation has been thriving for several decades. Container shipping has received the most attention among the problems in this industry. Containers facilitate smooth flow of goods across multiple transportation modes without direct freight handling during the course of shipping. Such shipping convenience is attributed to sophisticated container operations in coupled shipping systems, which include container source (warehouses and factories), terminals, and shipping vessels. The efficiency of container operations highly affects the efficiency of the entire shipping economy as well as its environmental benefits. Therefore, container operation-related optimization must be studied extensively. This thesis addresses container packing, pre-marshalling, and vessel stowage planning. In the chain of shipping industry, the first element is container packing. Dry cargoes are loaded into containers before they traverse the sea and appear on shelves of stores. Packing is a pivotal function in the efficient operation of supply chain. Thus, container packing problems are a hot topic in the research community. Many variants with different constraints, such as container-related, items-related, and load-related constraints, have been studied. This thesis first considers Single Container Loading Problem with Shipment Priority (SCLP-SP), in which all high-priority items must be loaded into the container before low-priority items. Shipment priority is commonly considered in real applications but has received little research attention. This thesis proposes a multi-round partial beam search method that explicitly considers shipment priority when evaluating the potential of partial solutions to solve SCLP-SP. Experiments on existing benchmarks suggest that the proposed approach is more effective than current methods. The average utilization is improved by almost 1%, and the running time is shorter than that of a state-of-the-art method. Given that existing benchmark data cover only weakly heterogeneous instances, the benchmark data are extended to strongly heterogeneous instances. Instances with various proportions of high-priority items are also generated to cover a wider spectrum of applications. After container packing, containers are transported from manufacturers to container terminal yards, where they await the arrival of ships. Yards are generally divided into blocks, each of which consists of several bays. A bay is a row of stacks that stand in a line. A stack is piled with containers vertically. Considering that containers within one stack can only be retrieved in a "first in-last out" manner, if the container to be fetched is not at the top of a stack, all the containers placed above it have to be relocated somewhere else before retrieving it. To avoid unnecessary container relocations when loading ships, pre-marshalling is conducted in cranes' idle time. Container Pre-Marshalling Problem (CPMP) aims to rearrange containers in a bay with the least movement effort; thus, in the final layout, containers are piled according to a pre-determined order. Previous researchers assumed that all the stacks in a bay are functionally identical. Such a classical problem setting is reexamined in this thesis. Moreover, a new problem, that is, CPMP with a Dummy Stack (CPMPDS), is proposed. In terminals that use gantry cranes, a bay includes a row of ordinary stacks and a dummy stack. The dummy stack is actually the bay space that is reserved for trucks. Therefore, containers can be shipped out of the bay. During the pre-marshalling process, the dummy stack temporarily accommodates containers as an ordinary stack. However, the dummy stack must be emptied at the end of pre-marshalling. In this thesis, a target-guided algorithm combined with two beam search strategies is proposed to handle both classical CPMP and new CPMPDS. Experimental results in terms of CPMP show that the proposed algorithm surpasses the best currently published algorithm. The required final layouts of CPMP are essentially driven by Container Vessel Stowage Planning Problem (CVSPP). CVSPP includes a series of problems that generally aims to decide container stowage orders in multiport voyages to ensure that full load vessels are safe at sea and loading and discharging costs are as low as possible. This thesis addresses a multi-objective problem to optimize the number of rehandles in conjunction with vessel stability. Vessel stability is interpreted by the language of optimization, that is, vessel imbalance should be minimized along transverse and longitudinal directions, and the center of gravity should be controlled. This work is the first to discuss a multi-port CVSPP that considers vessel stability. A two-step heuristic is proposed to solve CVSPP. Given that the benchmark data is lacking, a data set is generated for public access, and effects of different problem parameters on objective values are investigated.

Date of Award	15 Jul 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Leong Chye Andrew LIM (Supervisor)