A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Simulation of a multiterminal system for container handling

A generic simulation model structure for the design and evaluation of multiterminal systems for container handling is proposed. A model is constructed by combining three basic functions: transport, transfer, and stacking. It can be used for further detailing of the subsystems in the terminal complex while preserving the container flow patterns in the system. The modeling approach has been applied to the complete set of existing and future terminals in the Rotterdam port area, using forecasts of containers flows, statistical data from existing terminals, expert opinions, and conceptual designs of the new port area called “second Maasvlakte”. Experimental results including the requirements for deep-sea quay lengths, storage capacities, and equipment for interterminal transport are shown. Further traffic flows on the terminal infrastructure are determined, and the consequences of applying security scanning of containers are evaluated.     

An effective heuristic for scheduling a yard crane to handle jobs with different ready times

In land-constrained port container terminals, yard cranes are commonly used for handling containers in a container yard to load containers onto or unload containers from trucks. However, yard cranes are bulky, slow and need to move frequently between their work locations. As it is common that the container flow in a terminal is bottlenecked by yard crane operations, effective work schedules of yard cranes are needed to increase the terminal’s throughput. This article studies the problem of scheduling a yard crane to perform a given set of container handling jobs with different ready times. The objective is to minimize the sum of job waiting times. It is noted that the scheduling problem is NP-complete. This research develops a heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. The performance of the heuristic is evaluated by a set of test problems generated on the basis of real-life terminal operations data. Indeed, the computational results show that the proposed heuristic can find effective solutions for the scheduling problem.     

Deadlock handling for real-time control of AGVs at automated container terminals

In automated container terminals, situations occur where quay cranes, stacking cranes, and automated guided vehicles (AGVs), directly or indirectly request each other to start a specific process. Hence, all of the affected resources are blocked, possibly leading to the complete deadlock of individual cranes or AGVs. Particularly, AGVs are liable to deadlocks because they always need a secondary resource, either a quay crane or a stacking crane, to perform the pick-up and drop-off operations. Because usually no buffering of containers takes place at the interfaces between AGVs and cranes, the consequences of deadlocks are rather severe. Two different methods for the detection of deadlocks are presented. One is based on a matrix representation of the terminal system. The other directly traces the requests for the individual resources. To resolve deadlock situations arising in an automated container terminal, three different procedures are proposed. These procedures aim to modify the sequence of handling operations or to assign them to alternative resources so that conflicts between concurrent processes are resolved. The suitability of the concept is demonstrated in an extensive simulation study.     

Joint planning for yard storage space and home berths in container terminals

Yard planning is essential for efficient operations in container terminals, especially for ports with limited storage space. To improve the utilisation of space and the efficiency of container handling in a terminal, operators require flexible yard space planning strategies to manage job workloads and yard-to-berth transportation costs. In previous studies, the inter-related decision making process for berths and yards has normally been studied separately, and yard planning models are designed with deterministic inputs of berths, where many existing terminals are operating with sub-optimal efficiency. In this paper, we consider different policies of the scattered stacking strategy for export containers and analyse the entire cycle of container handling from yard block to home berth, where the home berth is a quay section which includes the preferred berthing place of a vessel upon its arrival. We analyse three stacking policies, namely exclusive, cross-area, and buffer-area stacking policies, and formulate the planning problem for yard storage and related home berths into MILP (mixed integer linear programming) models. Solutions are obtained with a two-stage approach method. The numerical analysis demonstrates that the workload imbalance can be significantly reduced by implementing either the cross-area or buffer-area container stacking policy.     

Comparison of vehicle types at an automated container terminal

At automated container terminals, containers are transshipped from one mode of transportation to another. Automated vehicles transport containers from the stack to the ship and vice versa. Two different types of automated vehicles are studied in this paper, namely automated lifting vehicles and automated guided vehicles. An automated lifting vehicle is capable of lifting a container from the ground by itself. An automated guided vehicles needs a crane to receive and deliver a container.In designing automated container terminals one have to consider the choice for a certain type of equipment. The choice for a certain type of equipment should be made by performing a feasibility and economic analysis on various types of equipment. In this paper, we examine effects of using automated guided vehicles and automated lifting vehicles on unloading times of a ship, with simulation studies. In choosing a certain type of equipment we have considered criteria such as unloading times of a ship, occupancy degrees and the number of vehicles required. 38% more AGVs need to be used than ALVs. From this specific study, we conclude that, by observing only purchasing costs of equipment, ALVs are a cheaper option than AGVs.To obtain an accurate analysis we have performed a sensitivity analysis. It can be concluded that the design of the terminal and technical aspects of quay cranes impact the number of vehicles required and as a result the choice for a certain type of equipment. Correspondence to: Iris F. A. Vis     

Online rules for container stacking

Container stacking rules are an important factor in container terminal efficiency. In this paper, we investigate two concepts to increase efficiency and compare them to several benchmark algorithms, using a discrete-event simulation tool. The first concept is to use knowledge about container departure times, in order to limit the number of reshuffles. We stack containers leaving shortly before each other on top of each other. The second concept is the trade-off between stacking further away in the terminal versus stacking close to the exit points and accepting more reshuffles. It is concluded that even the use of imperfect or imprecise departure time information leads to significant improvements in efficiency. Minimizing the difference in departure times proved to be important. It was also found that the trade-off between stacking further away in the terminal versus stacking close by the exit points and accepting more reshuffles leads to improvements over the benchmark.     

Dispatching vehicles in a mega container terminal

We consider a container terminal discharging and uploading containers to and from ships. The discharged containers are stored at prespecified storage locations in the terminal yard. Containers are moved between the ship area and the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to dispatch vehicles to the containers so as to minimize the total time it takes to serve a ship, which is the total time it takes to discharge all containers from the ship and upload new containers onto the ship. We develop easily implementable heuristic algorithms and identify both the absolute and asymptotic worst-case performance ratios of these heuristics. In simple settings, most of these algorithms are optimal, while in more general settings, we show, through numerical experiments, that these algorithms obtain near-optimal results for the dispatching problem.Research was supported in part by the Port of Singapore Authority (PSA).     

Generating scenarios for simulation and optimization of container terminal logistics

This paper introduces an approach for generating scenarios of sea port container terminals. The scenarios can be used as input data for simulation models. Furthermore, they can be employed as test data for algorithms to solve optimization problems in container terminal logistics such as berth planning and crane scheduling. A scenario consists of arrivals of deep sea vessels, feeder ships, trains, and trucks together with lists of containers to be loaded and unloaded. Moreover, container attributes such as size, empty, reefer, weight, and destination are included. The generator is based on a large number of parameters that allow the user to produce realistic scenarios of any size. The purpose of this paper is to outline the parameters that are important to produce realistic scenarios of high practical relevance and to propose an algorithm that computes scenarios on the basis of these parameters. The generator discussed here has been developed within the simulation project at the HHLA Container-Terminal Altenwerder in Hamburg, Germany. Nevertheless, its structure is general enough to be applied to any other terminal as well.This research project has been carried out for the HHLA Container-Terminal Altenwerder in Hamburg, Germany, when the author was with LOGAS Gesellschaft für logistische Anwendungssysteme, Hamburg, Germany.     

A beam search algorithm for the load sequencing of outbound containers in port container terminals

A beam search algorithm was applied to solve the load-sequencing problem in port container terminals. The algorithm was used to maximize the operational efficiency of transfer cranes and quay cranes (QCs) while satisfying various constraints on stacking containers onto vessels. The load-sequencing problem consisted of two decision-making subproblems. In the first subproblem, a pickup schedule was constructed in which the travel route of a transfer crane (TC) as well as the number of containers it must pick up at each yard-bay are determined. In the second subproblem, the load sequence for individual containers was determined. This study suggested a search scheme in which an algorithm to solve the second subproblem is imbedded into the algorithm for the first subproblem. Numerical experiments using practical data were performed to test the performance of the developed algorithm. Correspondence to: Kap Hwan KimThis study was supported in part by the Korea Science and Engineering Foundation through the Center for Intelligent and Integrated Port Management Systems (CIIPMS) at Dong-A University. Authors also appreciate Director In-Tae Baek in Korea Logistics Network Co. for his help during the data collection.     

Fleet sizing and vehicle routing for container transportation in a static environment

Busan is one of the busiest seaports in the world where millions of containers are handled every year. The space of the container terminal at the port is so limited that several small container yards are scattered in the city. Containers are frequently transported between the container terminal and container yards, which may cause tremendous traffic problems. The competitiveness of the container terminal may seriously be aggravated due to the increase in logistics costs. Thus, there exist growing needs for developing an efficient fleet management tool to resolve this situation. This paper proposes a new fleet management procedure based on a heuristic tabu search algorithm in a container transportation system. The proposed procedure is aimed at simultaneously finding the minimum fleet size required and travel route for each vehicle while satisfying all the transportation requirements within the planning horizon. The transportation system under consideration is static in that all the transportation requirements are predetermined at the beginning of the planning horizon. The proposed procedure consists of two phases: In phase one, an optimization model is constructed to obtain a fleet planning with minimum vehicle travel time and to provide a lower bound on the fleet size. In phase two, a tabu search based procedure is presented to construct a vehicle routing with the least number of vehicles. The performance of the procedure is evaluated and compared with two existing methods through computational experiments.Correspondence to: Pyung Hoi KooThis work was supported by Korea Research Foundation Grant. KRF-2001-003-E00080.     

Strategies for dispatching AGVs at automated seaport container terminals

Control of logistics operations at container terminals is an extremely complex task, especially if automated guided vehicles (AGVs) are employed. In AGV dispatching, the stochastic nature of the handling systems must be taken into account. For instance, handling times of quay and stacking cranes as well as release times of transportation orders are not exactly known in advance. We present a simulation study of AGV dispatching strategies in a seaport container terminal, where AGVs can be used in single or dual-carrier mode. The latter allows transporting two small-sized (20 ft) or one large-sized (40 ft) container at a time, while in single-mode only one container is loaded onto the AGV irrespective of the size of the container. In our investigation, a typical on-line dispatching strategy adopted from flexible manufacturing systems is compared with a more sophisticated, pattern-based off-line heuristic. The performance of the dispatching strategies is evaluated using a scalable simulation model. The design of the experimental study reflects conditions which are typical of a real automated terminal environment. Major experimental factors are the size of the terminal and the degree of stochastic variations. Results of the simulation study reveal that the pattern-based off-line heuristic proposed by the authors clearly outperforms its on-line counterpart. For the most realistic scenario investigated, a deviation from a lower bound of less than 5% is achieved when the dual-load capability of the AGVs is utilized.     

Inventory-based dispatching of automated guided vehicles on container terminals

This paper deals with automated guided vehicles (AGVs) which transport containers between the quay and the stack on automated container terminals. The focus is on the assignment of transportation jobs to AGVs within a terminal control system operating in real time. First, we describe a rather common problem formulation based on due times for the jobs and solve this problem both with a greedy priority rule based heuristic and with an exact algorithm. Subsequently, we present an alternative formulation of the assignment problem, which does not include due times. This formulation is based on a rough analogy to inventory management and is solved using an exact algorithm. The idea behind this alternative formulation is to avoid estimates of driving times, completion times, due times, and tardiness because such estimates are often highly unreliable in practice and do not allow for accurate planning. By means of simulation, we then analyze the different approaches. We show that the inventory-based model leads to better productivity on the terminal than the due-time-based formulation.     

Performance analysis of berth configurations at container terminals

The containerized trade market has been growing rapidly since its introduction. The capacity of ships and the amount of containers being transshipped at container terminals increases significantly. Terminals should handle their operations efficiently to provide the necessary capacity and customer service. In designing a container terminal, terminal management has to consider the choice for a certain type of berth. In this paper, we compare by means of a simulation study the performance of traditional one-sided marginal berths and indented berths. An indented berth enables quay cranes to unload and load containers from both sides of the ship. As a result, more quay cranes can work on a single ship. As main performance measure in this comparison we use the total vessel operation time required to unload and load a ship. This time depends next to crane productivity also on the efficiency of the transportation and storage and retrieval processes in the terminal. We have performed a sensitivity analysis in which we also study the relation between the selection of an indented berth and other design and control issues in the terminal.     

An optimal layout of container yards

This study presents a method for designing the layout of container yards where transfer cranes and yard trucks are used for stacking containers in the yard and delivering them between the yard and the quay. A method to determine the layout type, the outline of the yard, and the numbers of vertical and horizontal aisles is suggested. For estimating the effects of the design variables on operational cost terms, formulas for estimating the number of relocations by yard cranes and the expected travel distance of trucks are derived. Numerical examples are provided to illustrate the design procedure. It was also shown that the layout in which blocks are laid out parallel to the side with the gate or the quay outperforms that in which blocks are laid out perpendicular to the side with the gate or the quay.     

Optimizing the landside operation of a container terminal

This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three-stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short-term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most 8% above a lower bound on optimal RMG utilization. Research supported by Patrick Technology and Systems, the Australian Research Council Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS), and the German Research Foundation Research Center Mathematics for key technologies: Modelling, simulation, and optimization of real-world processes (Matheon).     

Robust cyclic berth planning of container vessels

We consider a container terminal operator who faces the problem of constructing a cyclic berth plan. Such a plan defines the arrival and departure times of each cyclically calling vessel on a terminal, taking into account the expected number of containers to be handled and the necessary quay and crane capacity to do so. Conventional berth planning methods ignore the fact that, in practice, container terminal operator and shipping line agree upon an arrival window rather than an arrival time: if a vessel arrives within that window then a certain vessel productivity and hence departure time is guaranteed. The contributions of this paper are twofold. We not only minimize the peak loading of quay cranes in a port, but also explicitly take into account the arrival window agreements between the terminal operator and shipping lines. We present a robust optimization model for cyclic berth planning. Computational results on a real-world scenario for a container terminal in Antwerp show that the robust planning model can reach a substantial reduction in the crane capacity that is necessary to meet the window arrival agreements, as compared to a deterministic planning approach.     

Development and simulation analysis of real-time yard crane control systems for seaport container transshipment terminals

As more and more container terminals open up all over the world, terminal operators are discovering that they must increase quay crane work rates to remain competitive. In this paper, we develop a real-time yard crane control system and show that a terminal’s long-run average quay crane rate depends on the portion of this system that dispatches yard cranes in the storage area in real time. Several real-time yard crane dispatching systems are evaluated by a fully-integrated, discrete event simulation model of a pure transshipment terminal that is designed to reproduce the multi-objective, stochastic, real-time environment at an RTGC-based, multiple-berth facility. Results indicate that yard cranes should prioritize the retrieval of containers from the stacks, rather than the storage of containers into stacks. Also, the yard crane dispatching system should not only consider the trucks already waiting for service in the yard, but also the trucks that are heading towards the yard. The experiments provide the first direct connection in the literature between real-time yard crane control systems and long-run performance at a seaport container terminal. We also make a qualitative comparison between rule-based and look-ahead yard crane dispatching schemes, and discuss deadlocking issues in detail.     

A decision-tree stacking heuristic minimising the expected number of reshuffles at a container terminal

Reshuffling containers, one of the daily operations at a container terminal, is time consuming and increases a ship’s berthing time. We propose a decision-tree heuristic to minimise the expected number of reshuffles when arriving containers should be stacked in a block of containers with an arbitrary number of piles. The heuristic algorithm uses the optimal solutions of a stochastic dynamic programming model. Since the total number of states of the dynamic programming model increases exponentially, the model can only solve small-scale problems in a reasonable time. To solve large-scale problems, the heuristic uses the results of the exact model for small-scale problems to generate generalised decision trees. These trees can be used to solve problems with a realistic number of piles. The numerical experiments show the effectiveness of the algorithm. For small-scale problems, the trees can quickly make optimal decisions. For large-scale problems, the decision-tree heuristic significantly outperforms stacking policies commonly used in practice. Using the decision trees, we can compare the performance of a shared-stacking policy, which allows containers of multiple ships to be stacked on top of each other, with a dedicated-stacking policy. Shared-stacking appears to outperform dedicated-stacking.