Invited ReviewA survey of berth allocation and quay crane scheduling problems in container terminals
Introduction
In recent years, OR methods have received considerable importance for the operations management in container terminals (CTs). Comprehensive overviews on applications and optimization models in this field are given by Meersmans and Dekker, 2001, Vis and de Koster, 2003, Steenken et al., 2004, Vacca et al., 2007, Stahlbock and Voß, 2008. A significant amount of papers dealing with the application of OR methods addresses the planning of the seaside transshipment operations. Fig. 1 shows important relations of the strategic planning and the operations planning at the seaside area, the yard, and the landside area.
One issue of seaside operations planning is the assignment of quay space and service time to vessels that have to be unloaded and loaded at a terminal. This problem is commonly referred to as the berth allocation problem (BAP). The transshipment of containers between a vessel and the quay is generally performed by specialized cranes, which are mounted on rail tracks alongside the quay. The assignment of these quay cranes (QCs) to vessels and the determination of work plans for the cranes addresses two further problems, namely the quay crane assignment problem (QCAP) and the quay crane scheduling problem (QCSP). Solutions to these problems must respect the berth layout and the used equipment, whereas they impact the yard operations and the workforce planning, see Fig. 1.
Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for the BAP, the QCAP, and the QCSP. Moreover, a trend towards an integrated solution of these problems is observed in the recent literature. The large number of available models and proposed solution methods prevents an easy choice of a suitable approach in a specific situation. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper develops classification schemes for BAPs, QCSPs, and integrated approaches.
The paper is organized as follows. In Section 2 the focused operational planning problems are described in detail against the background of different terminal properties and objectives. A literature survey of BAP and QCAP formulations is presented in Section 3 which is derived from a new classification scheme for these problems. Accordingly, a classification scheme and a literature survey are presented for QCSP formulations in Section 4. Since future advances in the field are expected from integrated solution approaches, Section 5 provides a literature review of the state-of-the-art integration concepts. The paper is summarized in Section 6.
Section snippets
Berth allocation problem
In the BAP we are given the berth layout of a CT together with a set of vessels that have to be served within the planning horizon. For each vessel additional data like the vessel’s length including clearance, its draft, the expected time of arrival, and the projected handling time can be given. All vessels must be moored within the boundaries of the quay. They are not allowed to occupy the same quay space at a time. The problem is to assign a berthing position and a berthing time to each
Classification scheme
To show similarities and differences in the existing models for berth allocation, a classification scheme is developed in the following. Studies that concentrate on quay crane assignment either presuppose a particular type of BAP or integrate quay crane assignment decisions in the berth planning process. For this reason, QCAP approaches are captured by the classification scheme as well. Problems are classified according to four attributes. The spatial attribute concerns the berth layout and
Classification scheme
As for berth planning problems, there is no classification scheme existing for QC scheduling problems so far. The proposed scheme classifies problems according to four attributes. The task attribute concerns the definition of tasks that represent the workload of the considered vessel. The crane attribute describes the availability of QCs at the vessel and the consideration of the crane movement speed. The interference attribute addresses the spatial constraints that are defined in a problem.
Classification scheme
Recent integration approaches for seaside operations planning motivate a further classification scheme, based on the concepts briefly introduced in Section 2.4. To distinguish problem integration by monolithic models (deep integration), by problem preprocessing, and by feedback loops, the notation of Table 5 is used. In this table, capitals A and B stand proxy for a BAP, QCAP, or QCSP. If a planning problem involves multiple decision variables but not all of them are determined at once in the
Summary
In this survey we have reviewed all research streams which are known to us in the field of seaside operations planning. The provided classification of existing models shows that the determination and the consideration of vessel handling times is the most crucial yet difficult need for a proper planning of seaside operations. The impact of berthing positions on the handling times is well-established in discrete and hybrid BAP formulations, but hardly considered in the continuous case so far.
References (114)
A multiple-crane-constrained scheduling problem in a container terminal
European Journal of Operational Research
(2003)- et al.
A queuing network model for the management of berth crane operations
Computers and Operations Research
(2008) - et al.
A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal
European Journal of Operational Research
(2007) The crane scheduling problem
Transportation Research Part B
(1989)- et al.
Model integration and a theory of models
Decision Support Systems
(1993) - et al.
Crane double cycling in container ports: planning methods and evaluation
Transportation Research Part B
(2007) - et al.
A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis
Operations Research Letters
(2002) - et al.
Variable neighborhood search for minimum cost berth allocation
European Journal of Operational Research
(2008) - et al.
The simultaneous berth and quay crane allocation problem
Transportation Research Part E
(2008) - et al.
Berth allocation at indented berths for mega-containerships
European Journal of Operational Research
(2007)
The dynamic berth allocation problem for a container port
Transportation Research Part B
Berth allocation with service priority
Transportation Research Part B
Berthing ships at a multi-user container terminal with a limited quay capacity
Transportation Research Part E
Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks
European Journal of Operational Research
Berth allocation in a container port: using a continuous location space approach
Transportation Research Part B
Berth scheduling by simulated annealing
Transportation Research Part B
A crane scheduling method for port container terminals
European Journal of Operational Research
Quay crane scheduling with non-interference constraints in port container terminals
Transportation Research Part E
Berth planning and resources optimisation at a container terminal via discrete event simulation
European Journal of Operational Research
The berth planning problem
Operations Research Letters
Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents
European Journal of Operational Research
Heuristics for the integration of crane productivity in the berth allocation problem
Transportation Research Part E
Berth allocation planning in the public berth system by genetic algorithms
European Journal of Operational Research
A branch and bound solution method for the crane scheduling problem
Transportation Research Part B
Optimizing submarine berthing with a persistence incentive
Naval Research Logistics
Optimizing ship berthing
Naval Research Logistics
A berth allocation strategy using heuristics algorithm and simulation optimisation
International Journal of Computer Applications in Technology
Models and tabu search heuristics for the berth-allocation problem
Transportation Science
Intermodal transportation
Berth allocation planning optimization in container terminals
Ship-berth link performance evaluation: simulation and analytical approaches
Maritime Policy and Management
Simulation modelling of ship-berth link with priority service
Maritime Economics and Logistics
How useful are queue models in port investment decisions for container berths
Journal of the Operational Research Society
An optimization methodology for intermodal terminal management
Journal of Intelligent Manufacturing
Structured modeling: survey and future research directions
Interactive Transactions of ORMS
Double-cycling strategies for container ships and their effect on ship loading and unloading operations
Transportation Science
The berth allocation problem: models and solution methods
OR Spectrum
Cited by (702)
Integrated operation models with quay crane maintenance in a container terminal
2024, Ocean and Coastal ManagementDistributionally robust chance-constrained optimization for the integrated berth allocation and quay crane assignment problem
2024, Transportation Research Part B: MethodologicalIntegrated energy management and operations planning in oil-electric hybrid container terminals considering multi-energy supply
2024, Advanced Engineering InformaticsIntegrated planning model for two-story container ports
2024, Transportation Research Part C: Emerging Technologies