Seaside operations in container terminals: literature overview, trends, and research directions

Abstract

Seaside operations are considered the bottleneck operation in most container terminals around the world. This paper presents an in-depth updated overview of the seaside operations at container terminals and highlights current trends and developments. We review and classify scientific journal papers on container terminal seaside operations, published between 2004 and 2012. The paper also discusses and challenges the current operational paradigms on seaside operations. Lastly, the paper identifies new avenues for academic research based on current trends and developments in the container terminal industry.

1 Introduction

The total volume of containers handled per year has steeply increased in the past decades (UNCTAD 2011) and is expected to continue increasing in the future. As a consequence, container terminals are continuously challenged to increase their throughput capacity, giving way to many innovations in terms of container terminal design, material handling equipment, and Operations Research applications. This paper focuses on identifying new avenues for academic research based on current trends and developments in the seaside operations at container terminals.

Container terminals can be divided into five main areas, namely the berth, quay, transport, (storage) yard, and (terminal) gate, as illustrated in Fig. 1. The berth and the quay areas are considered seaside, while the yard and gate areas are considered landside. The transport area is at the intersection of the seaside and landside areas. In this paper we focus on the trends and developments on the seaside operations.

Fig. 1

Container terminal main areas

Arrival planning strategies are usually in place to manage the arrival of ships at ports (Lang and Veenstra 2009). The container unloading process at container terminals starts by assigning vessels to berths so they can moor upon arrival to the port. The number of berths that should be available at the quay is one of the decisions that has to be made at the strategic level. On the other hand, one of the decisions at the operational level is the allocation of berths to vessels. This problem is known as the Berth Allocation Problem (BAP). In general, the berth allocation is done considering the total vessel mooring times, the distance between the berthing area and the storage location for containers associated with the vessel, and the promised turnaround time for the vessel according to the stipulated contract. Figure 2 depicts the unloading and loading processes at container terminals.

Fig. 2

Unloading and loading processes

Once the vessel has moored, one or more quay cranes (QCs), i.e., large, typically rail-mounted, non-automated, gantry cranes located in the shore, unload the vessel following an unloading plan. The QCs retrieve outbound containers from the vessel’s hold or deck and deposit them on (internal) transport vehicles, which move the containers from the quay area to the yard area. The QCs are equipped with trolleys that can move along the crane arm to transport the container from the ship to the transport vehicle and vice versa. The containers are picked with a spreader, a pick up device attached to the trolley. Determining the number of QCs to purchase is a strategic decision. On the other hand, determining the assignment of QCs to vessel and scheduling of QCs are two operational level decisions. The Quay Crane Assignment Problem (QCAP) seeks to assign a predetermined number of cranes to vessels for unloading and loading. On the other hand, the Quay Crane Scheduling Problem (QCSP) seeks to optimize the assignment and sequencing of (unloading and loading) task distribution among a given number of cranes. The QCAP, QCSP, and the abovementioned BAP are the three main decision problems considered in the seaside, and hence, the focus of this paper.

The number of import containers that have to be unloaded at the terminal is in practice usually only known shortly before the arrival of the ship. Between one and six QCs are typically used to unload containers from the vessel according to an unloading plan. The unloading plan indicates the containers to be unloaded and their location in the ship. As expected, containers in the deck need to be unloaded before accessing the vessel holds. Within a hold, the QC driver is almost free to determine the order in which the containers are unloaded. The unloading time of a container depends on its place in the ship. Consequently, a large variance occurs in the container unloading times. In contrast with the unloading process, there is hardly any flexibility in the loading process. To ensure fast and efficient transshipment of containers, a good distribution of containers over the vessel is necessary. Therefore, at the operational level a stowage plan is made to indicate the storage location of each import container in the vessel.

Once the containers are loaded onto the transfer vehicle, they are transported to the storage yard where they are temporarily stored until they are either transported inland (by external trucks or rail) or transported to another vessel (by internal transport vehicles). Inland containers leave the container terminal through the terminal gates after verifying the paperwork and inspecting the container (if selected). Typically, the loading of the vessel occurs after all outbound containers have been retrieved and is the reverse of the unloading process.

The undisputed key performance metric for the efficiency of container terminal operations is the vessels’ turnaround time (i.e., how long it takes the container terminal to unload and load the vessel) which is a direct measure of the container terminal throughput. Historically, the bottleneck operation in container terminals is the QCs. Hence, to improve the throughput of a container terminal, one needs to improve the throughput of the QCs. The main reasons why QCs are the bottleneck operations include the complexity of the task, the speed of the QCs, the number of QCs, which is associated with the high investment and maintenance cost on one hand, and the safety concerns and interference between parallel QCs on the other hand.

In this paper, we focus on the seaside operations at container terminals by highlighting new avenues for academic research based on current trends and developments in the container terminal industry. We limit ourselves to literature published between 2004 and 2012, whereby the paper is a follow up of Vis and De Koster (2003). Previous other publications that provide a literature overview for container terminals include Steenken et al. (2004), and Stahlbock and Voß (2008).

The remainder of the paper is organized as follows. In Sect. 2 we describe the trends and developments in seaside operations. Section 3 presents an overall overview of the research output on seaside operations between 2004 and 2012. In Sects. 4–6 we present the classification scheme and literature overview pertaining the three main decisions made at the seaside, namely the Berth Allocation Problem (BAP), Quay Crane Assignment Problem (QCAP), Quay Crane Scheduling Problem (QCSP), and the combination of these problems. In Sect. 7 we take a step back to reconsider the seaside operations from an Industrial Engineering and Operational Excellence perspective to challenge the current operational paradigms on the seaside operations. Lastly, Sect. 8 presents research avenues based on current trends and developments in the container terminal industry.

2 Industry trends and developments

The recent industry trends and developments on seaside operations relate to the berth layout, material handling equipment, and operational strategies. Sections 2.1–2.3 present these trends and developments, respectively.

2.1 Trends and developments: berth layout

Traditionally, berths are located parallel to the shoreline as shown in Fig. 3a. We refer to this berth as the traditional berth although the term marginal berth has also been used to refer to this type of layout. The traditional berth arrangement has two downsides that affect their throughput: (1) since vessels are parallel to the shoreline, they occupy much valuable shoreline space, and (2) the arrangement only allows QCs to operate on one side of the vessel. The first downside limits the number of vessels that can be served at a given time. The effect of this downside is magnified by the fact that vessels continue to grow in size in order to transport more containers and benefit from economies of scale. The second downside (i.e., QCs operating only one side) is particularly important as the quay operation is typically the bottleneck operation in container terminals.

Fig. 3

Traditional (a) and indented (b) berths

Figure 3b presents an indented berth as an alternative to traditional berths. In the indented berth, vessels are moored perpendicular to the shoreline, which allows quay cranes to simultaneously operate on both sides of the vessel (and even on the aft). Indented berths are a very promising development in seaside operations as they overcome the two main downsides from traditional berths. The first indented berth was implemented in the Amsterdam Container Terminals (formerly the Ceres Paragon Terminal) in The Netherlands. Unfortunately, in order to implement indented berths a large investment needs to be made, possibly to extend the quayside to create the indentations. Also, indented berths limit the repositioning of QCs as it would require both horizontal and vertical movements.

Indented berths are related to a second trend on seaside operations in the port industry, recovered (or reclaimed) land. Recovered land is man-made land recovered from the sea. Given the increase in container demand and the dearth of port space, some seaports see recovered land as the only way to physically expand their operations in a contiguous manner. This phenomenon, although expensive and potentially damaging to the marine ecosystem, has been contemplated by many ports and already executed in several ports including the brand new terminals Maasvlakte II in Rotterdam, Netherlands. Recovered lands will allow seaports to be able to design or re-design their berth layouts. Although indented berths are very promising for seaside operations, the effect of an indented berth layout on the transport operations needs to be thoroughly investigated.

2.2 Developments in equipment: quay cranes

Quay Cranes (QCs) operating at the seaside are key to the container terminals’ performance as they are considered the bottleneck operation. The latest innovations in quay cranes include multi-lift spreaders, double-trolley QCs, and floating platforms with QCs. Multi-lift spreaders can simultaneously lift two or three forty feet containers (2–6 TEUs, i.e., twenty feet containers). A triple-spreader QC is currently implemented in the Mawan container terminal in the Shenzhen port in China. Double-trolley QCs use a platform to split the storage and retrieval requests into two at the expense of double-handling containers. The platform serves as an exchange point between a seaside and a landside trolley. As a result, additional challenges arise in designing (un-)loading plans, QC schedules, and yard operations to ensure that the right set of containers is available for pick-up to ensure efficient operations. Lastly, floating platforms with quay cranes can be used to perform (un-) loading operations in open sea (e.g., Nam and Lee 2012).

2.3 Trends in operations: quay crane operations

Traditionally, a QC completes the unloading process before starting the loading process. This forces quay cranes to operate in a single-cycle mode, where the QC either performs a retrieval (or a storage) to (from) the vessel. For a storage, this would require to pick up a container from the quayside, move it to the vessel, and store it. Then, the QC would return empty to the quayside to pick up the next container. On the other hand, if the QC operates in a double-cycle mode the retrievals and storages can be combined. For example, the QC picks up a container in the quay side and stores it in the vessel. However, instead of returning empty, the QC would move to a different location on the vessel to retrieve an inbound container before returning to the quayside. A well implemented double-cycle strategy reduces the total QC empty travel and hence the total QC travel distance and time (Goodchild and Daganzo 2006). Clearly, implementing a double-cycle strategy for the QC would lead to a double-cycle strategy for the transport equipment and the yard cranes. The idea of double-cycling has been used in the warehouse industry for many decades (known as single-command and double-command in the warehousing literature). To the best of our knowledge the only full scale implementation of this concept was in the Port of Tacoma, Washington, USA, as described by Goodchild and Daganzo (2006). Given the potential benefits of QC double-cycling it is worthwhile to further investigate this issue and tackle challenges in designing smart solution approaches.

In the next sections we will analyze the scientific journal papers between 2004 and 2012 and identify research opportunities considering the newest industry trends and developments. We start our analysis by studying the research output on seaside operations, including the main journals publishing papers on seaside operations and the demography of the authors.

3 Overview of research output

An extensive search in several scientific databases resulted in 80 scientific journal articles, published between January 2004 and December 2012, directly related to container terminal seaside operations. The keywords used for our search were container, container terminal, and port, from which we only selected the ones addressing the following three problems: Berth Allocation Problem, Quay Crane Assignment Problem, or Quay Crane Scheduling Problem. Survey papers, and other referenced work that do not meet the abovementioned requirements, are not included.

Analyses show that the number of journal papers published per year on seaside operations continues to increase on a yearly basis with a peak of 17 papers in 2010. Most papers (42) have their origin in Asia, mainly from China (including Hong Kong), Singapore, and Japan. In total we counted 20 different countries. A total of 236 authors contributed to the 80 papers considered in this analyses. The average number of authors per publications equals 2.95 with a standard deviation of 0.95. The maximum number of authors in a paper was 5. Only two of the papers were written by a single author.

The papers have been published in 26 different journals. On average each journal published 3.08 papers. The journals with the most number of publications are Transportation Research Part E, European Journal of Operational Research, OR Spectrum, and Naval Research Logistics. Several special issues on container terminal logistics have appeared in journals such as OR Spectrum, Transportation Research Part E, and Flexible Services and Manufacturing.

4 Berth allocation problem

As described in Sect. 1, the Berth Allocation Problem (BAP) seeks to assign incoming vessels to berth positions considering the basic characteristics of the berths (e.g., length, depth) and vessels (e.g., dimensions, draft). In recent years, two literature overview papers pertaining seaside operations have been published. Theofanis et al. (2009) present a literature review on the BAP. Papers related to the Quay Crane Assignment Problem or the Quay Crane Scheduling Problem were not considered by those authors. Bierwirth and Meisel (2010) propose a classification of the BAP based on Imai et al. (2005) and Cordeau et al. (2005), which is similar to Theofanis et al. (2009).

In this paper we will abide by the BAP classification scheme from Bierwirth and Meisel (2010) as it is a natural partition of the literature. By building upon that classification scheme, we hope to solidify the classification scheme to the point where authors would start to explicitly stating the classification for their papers. According to the classification scheme from Bierwirth and Meisel (2010), the BAP can be characterized according to spatial, temporal, handling times, and performance measure attributes.

The spatial attribute differentiates between discrete, continuous, or hybrid berth space. In the discrete berth space, berthing positions are predefined so that exactly one vessel can be assigned to each berth. On the other hand, the continuous berth allows for vessels to moor anywhere in the quay space. Lastly, in the hybrid berth space, berths are predefined (discrete), but vessels may occupy more than one berth or share a berth. In the hybrid berth space, the berthing area within a berth may be continuous or discrete. Additionally, for all three types it can be taken into account if vessels with a draft exceeding a minimum water depth cannot be berthed arbitrarily (which is denoted by draft). In the literature, the most common assumption is that the berth space is discrete.

The temporal attribute pertains the berthing and departure times of the vessel. Two cases are typically considered: static and dynamic arrival. The static case does not consider the vessels’ arrival time, but instead assumes that vessels are (or will be) available for berthing whenever they are assigned. The dynamic case considers the expected arrival time of the vessels within a given planning horizon, although it is assumed known. Clearly, the static arrival is a special case of the dynamic arrival where the expected arrival times are zero.

The handling times attribute describes the assumptions regarding the time required to unload and load a vessel. The most common handling times assumptions are that it only depends on: (1) the number of containers to handle, (2) on the berthing position (typically associated with the distance to the assigned storage location of containers in the yard), or (3) on the number or schedule of quay cranes assigned.

The last classification attribute for the BAP is by performance measure attribute, which describes the objective function to be minimized. As expected, most performance measures in the BAP literature are related to minimizing the total time the vessel spends in the port. Others are associated with the vessels’ waiting and total completion times. When the objective function is to be maximized it includes a negative coefficient. Further, if multiple objectives are considered, they are included under this attribute, separated by commas.

Table 1 presents the classification scheme for the BAP from Bierwirth and Meisel (2010), including four minor modifications. The modifications were made to better classify the literature given the newest publications and expected trends. As part of the modifications, the following attribute levels were added: Handling Time—TVSP, Handling Time—YCSP, Handling Time—stoch, and Performance Measure—yard. Handling Time—TVSP and Handling Time—YCSP describe the case where the handling time for a vessel depends on the transfer vehicles and yard cranes schedule, respectively. Handling Time—stoch reflects a recent trend where vessel handling times are stochastic. Lastly, Performance Measure—yard refers to the case where the objective is to minimize the distance between the assigned berth and the assigned yard block, which is particularly important for problems simultaneously solving the BAP and assigning yard blocks. Also, it is worth mentioning that Performance Measure—yard is different from Performance Measure—pos, included in Bierwirth and Meisel (2010), as it does not involve a preferred berthing location.

Table 1 BAP classification scheme modified from Bierwirth and Meisel (2010)

When classifying a paper, a tuplet notation can be used. For example, disc| dyn, due| fix|Max(compl) would specify that the paper deals with discrete berths, where the vessels must be served within a time window, the handling time for the vessels only depends on the number of containers that need to be handled, and the objective function is to minimize the maximum completion time (or makespan). Given a tuplet, it is easy to know what a paper focuses on. However, the main disadvantage of this strategy is that the attributes used are not mutually exclusive. Hence, given a tuplet it is not explicitly described what the papers do not address unless one goes back to Table 1 and examines all the values that could have been chosen for a given attribute. For example, the paper classified as disc| dyn, due| fix|Max(compl) does not consider vessel draft constraints. We also observed that the attribute value pos is used as a handling time and performance measure attribute, which could be confusing, yet we opted not to modify it for simplicity.

We now present the corresponding classification and an in-depth literature overview of the journal papers addressing the Berth Allocation Problem (BAP) published between 2004 and 2012. We also include those papers that combine the BAP with the Quay Crane Assignment Problem and the Quay Crane Scheduling Problem (i.e., BAP/QCAP and BAP/QCSP). Since Bierwirth and Meisel (2010), a total of 29 new papers addressing the BAP, BAP/QCAP, or BAP/QCSP were published. Seventeen (17) papers focused on the BAP, ten papers addressed the BAP/QCAP and two the BAP/QCSP. The classification of those 29 papers is presented in Table 2. We opted to reclassify two papers classified in Bierwirth and Meisel (2010) (i.e., Moorthy and Teo 2006; Chang et al. 2008). Appendix 1 contains the classification of all journal papers published between 2004 and 2012, which include the ones in Table 2 and the ones in Bierwirth and Meisel (2010).

Table 2 Newly classified and reclassified (marked with *) BAP publications, not in Bierwirth and Meisel (2010)

Interestingly, only one journal publication between 2004 and 2012 addressed the static BAP. Guan and Yang (2010) use simulation to study the relationship between several BAP methods and the necessary container inspection service rate. With data of the Keelung harbor in Taiwan, the paper concludes that the service rate of the security inspection center should be approximately nine times the QC service rate for a terminal with 12 berths, 12 QCs, and one service center.

The remaining publications deal with the dynamic BAP. Fifteen of the publications deal with the discrete-dynamic BAP (DDBAP), ten focused on the continuous-dynamic BAP (CDBAP), and three addressed the hybrid-dynamic BAP (HDBAP). The BAP literature can be subdivided into single and multi-objective approaches. The single objective approach typically combines several performance metrics and assigns weights (i.e., the relative importance) to each metric. On the other hand, multi-objective approaches consider the different performance metrics as independent objectives. Typically, the latter will seek an efficient frontier from which the user can select an assignment based on their preference. We describe the relevant literature on the DDBAP, CDBAP, and HDBAP, respectively, in the next paragraphs.

4.1 Discrete dynamic BAP (DDBAP)

In the single-objective literature for the DDBAP, we notice that authors present various mathematical models, sometimes even multiple ones in a single paper, to find the most efficient and effective one. Cordeau et al. (2005) incorporate time windows (i.e., hard arrival and departure times) for the vessels for both the DDBAP and the CDBAP to minimize the weighted service times. The authors present two mathematical models and Tabu Search (TS) heuristics. For that reason we made the decision to include this paper twice in the classification and indicated which classification corresponds to what model and heuristic. Monaco and Sammarra (2007) reformulate the model from Imai et al. (2001) into a stronger formulation and present a Lagrangian relaxation-based heuristic to minimize the total vessel turnaround time. Buhrkal et al. (2011) compare five different mathematical formulations using the problem instances of Cordeau et al. (2005). The authors conclude that the formulation in Cordeau et al. (2005), with a few improvements, is competitive with the one in Imai et al. (2001). Also, the authors conclude that the mathematical model in Christensen and Holst (2008), not discussed nor counted in this paper as it is not a journal paper, significantly outperforms Imai et al. (2001) and Cordeau et al. (2005), and are much faster than the previous state-of-the-art paper in Monaco and Sammarra (2007). De Oliveira et al. (2012) propose a hybrid clustering search method that uses simulated annealing to generate solutions to solve the same problem as Cordeau et al. (2005).

Hansen et al. (2008) propose a formulation to minimize costs associated with waiting, handling, and earliness or tardiness. Four heuristics were proposed and compared and the authors conclude that the Variable Neighborhood Search (VSN) heuristic outperforms the others. In Golias et al. (2010), the authors propose a mathematical formulation and the Defined Neighborhood Heuristic, an λ–optimal heuristic, to minimize the vessels’ total weighted service time. Their proposed heuristic iteratively solves a number of BAP sub-problems to optimality within the neighborhood defined. The proposed heuristic can be used as a stopping criterion for other heuristics. Arango et al. (2011) propose a method to minimize the total service time for all vessels using discrete event simulation combined with a GA-based heuristic. The proposed solution method improved the handling times at berths and maximum handling times in the Port of Seville by 14 and 21 %, respectively.

Several variants of the DDBAP have been studied. For example, Imai et al. (2008b) study the problem where vessels whose expected wait times at the terminal exceed an allowable time limit are reassigned to an external (secondary) terminal like the case of the Port of Colombo, Sri Lanka. The objective of the problem is to minimize the total service time of vessels at the external terminal. A mathematical formulation and a Genetic Algorithm (GA)-based heuristic are proposed. Golias et al. (2009b) study the situation where vessels arrival times are considered as variables to minimize the port-related emissions, and vessels’ waiting times and delayed departures. A mathematical formulation is presented and a GA-based heuristic is proposed to solve the problem. Xu et al. (2012a) consider BAP limitations by water depth and tidal conditions, which are particularly important for terminals located along a river. Tidal conditions are divided into low and high tide. The problem is formulated as a parallel-machine scheduling problem to minimize the total weighted service duration for all vessels, where water depth constraints are modeled as inclusive processing sets. Since the problems are shown to be NP-Hard, two heuristics are proposed, one for the static and another for the dynamic BAP.

In the multi-objective literature for the DDBAP, Imai et al. (2007b) present a bi-objective formulation to simultaneously minimize the weighted delay time of departure of vessels and the total service time. The authors solve the problem using two heuristics based on previously published solution methods for the single-objective BAP, namely subgradient optimization with the Langrangian relaxation and Genetic Algorithm (GA). Golias et al. (2009a) minimizes the total service time considering different vessel priority groups, where each vessel priority group has its own objective functions. The problem is solved with a GA-based heuristic which is used to identify the efficient frontier. Saharidis et al. (2010) use a hierarchical approach for vessel priority groups and two conflicting objectives, minimizing customer dissatisfaction and maximizing the terminal’s throughput. A bi-level formulation considering is presented and an interactive heuristic based on the k-th best algorithm is proposed. Golias (2011) formulates the problem as a bi-objective problem to maximize berth throughput and reliability of the schedule. The paper assumes that the vessel handling times are stochastic (with a known discrete distribution) depending on quay cranes downtime, transfer vehicles, and yard operations, among others. A GA-based heuristic is used to solve the problem.

4.2 Continuous dynamic BAP (CDBAP)

Guan and Cheung (2004) propose two linear mixed integer programming formulations to minimize the total weighted flow time where the vessel processing time is assumed fixed. A lower bound for the problem was derived, and an optimal tree-search and composite heuristic are presented. Imai et al. (2005) propose a non-linear mixed integer programming formulation to minimize the total service and wait times for vessels. It is assumed that the handling time for the vessels increases proportionally to the distance between the berthing location and the best berthing location. The paper derives a lower bound and a heuristic solution. In their formulations, both Guan and Cheung (2004) and Imai et al. (2005) discretized the time and berth space. Ganji et al. (2010) performed minor modifications to the non-linear formulation from Imai et al. (2005) and proposed a GA-based heuristic to solve the problem. The GA heuristic found close to optimal solutions in small-sized instances with three vessels and was able to solve larger instances with 30 vessels in 6 min using a personal computer. The method was not compared to other proposed methods on the larger instances.

Chang et al. (2008) present two models to minimize the vessel handling time and cost, respectively, assuming a continuous berth with handling times that increase proportionally to the distance between the berthing location and the best berthing location as in Imai et al. (2005). The vessel draft is considered in the model, which can be easily done to most BAP formulations by adding two parameters (water depth of a berth and vessels’ draft) and one set of constraints. Unfortunately, their MIP formulations seem to have several typos in some indices (e.g., Eq. (1) and Eq. (15)) and key omissions such as not including Eq. (14) in their second model. One constructive heuristics is presented for each objective function. The heuristics are compared using data from a container terminal in Shanghai to a real-time assignment strategy. This strategy assumes discrete berths, pre-defined berth assignment priority rules, and does not consider the storage location of containers. As expected, the proposed BAP (that does consider the storage location of containers) outperformed the rule of thumb strategy.

Wang and Lim (2007) present a non-linear mixed integer programming model (that can be easily linearized) and a stochastic beam search algorithm to minimize a combination of reallocation and delay costs. The proposed heuristic was tested using real data from Port of Singapore where it was able to solve problems with up to 400 vessels in less than an hour. Experimental results conclude that the proposed method outperformed a traditional beam search algorithm in terms of solution quality and the simulated annealing from an unpublished report that is claimed to be state-of-the-art in terms of solution time and quality. Lee et al. (2010) propose two Greedy Randomized Adaptive Search Procedures, GRASP_1 and GRASP_2, to minimize the total weighted flow time. For larger size instances with up to 200 vessels it was found that GRASP_1 statistically outperforms the stochastic beam search heuristic from Wang and Lim (2007) in terms of computational time and solution quality; whereas GRASP_2 found the best solutions among the three heuristics at the expense of longer runtimes.

The three step heuristic approach of Lee and Chen (2009) allows shipping companies to select several preferred berthing sections in a continuous space, where each berthing section is a few times larger than the length of the vessel. The objective is to maximize the total utility index, which is a function of the vessels’ waiting, preferred section priority, and deviation between assigned position and the center of preferred section. Zhen et al. (2011b) consider the vessel arrival and handling times as stochastic to find a robust BAP. The problem is formulated to minimize the total vessel waiting and handling costs and the cost of recovering from a deviation in the schedule. A two-stage decision model is proposed to solve large instances of the problem. Xu et al. (2012b) also consider stochastic vessel arrival and handling times. The amount of buffer time to be left between vessels is derived to increase the robustness of the berth assignments. Their objective is to minimize the total departure delay and the length of buffer time used. A heuristic that combines branch and bound with simulated annealing is proposed.

Hendriks et al. (2012) study the BAP for cyclical calling vessels where berths are located in different terminals operated by the same terminal operator. The objective is to minimize the required QC capacity at each terminal and the inter-terminal transportation cost. The handling time of a vessel is said to depend of a variety of factors (processing rate, efficiency and number of QCs and total number of containers), which are linked to the quay crane assignment. A mixed integer linear formulation is presented and used as part of a two-step approach in a case study for PSA Antwerp, which operates three terminals in Port of Antwerp, Belgium. The first step uses the formulation to solve the BAP with 8 h-time slots, and a similar formulation is used to improve the time granularity to 1 h time slots.

4.3 Hybrid dynamic BAP (HDBAP)

Papers in this category focus on very different variants of the problem. Moorthy and Teo (2006) focus on identifying berth allocations that are robust to stochastic vessel arrival times, while balancing service levels and operational costs. Cheong et al. (2010) propose a multi-objective problem considering the makespan, total waiting time of vessels, and the deviation from a predetermined priority schedule. The paper assumes that the berths are discretized into sections, yet within each section the space is continuous. A mathematical formulation of the problem is presented and a multi-objective evolutionary algorithm is proposed to solve the problem.

Imai et al. (2007a) are the first to consider indented berths. The paper formulates the problem as a linear mixed integer program and uses a GA-based heuristic to solve the problem. Since the authors consider a hybrid berth (i.e., more than one vessel occupying a berth), a key assumption made in the paper is that in the indented berth the innermost vessel cannot leave until the outermost vessel leaves. This is not necessarily the case in this kind of practice. Given this assumption, the authors conclude that, while indented terminals served large vessels faster than traditional terminals, the total service time for all vessels was longer.

Between 2004 and 2012, 14 publications dealt with the integrative BAP/QCAP decision problem. Seven of the publications dealt with the discrete-dynamic BAP/QCAP (DDBAP/QCAP), Five focused with the continuous-dynamic BAP/QCAP (CDBAP/QCAP), and two addressed the hybrid-dynamic BAP/QCAP (HDBAP/QCAP). We describe the relevant literature on the DDBAP/QCAP, CDBAP/QCAP, and HDBAP/QCAP, respectively, in the next paragraphs.

4.4 Discrete dynamic BAP/QCAP (DDBAP/QCAP)

Zhou and Kang (2008) formulate a stochastic program and a GA-based heuristic to solve the problem. Imai et al. (2008a) provide a mathematical formulation and a GA-based heuristic without considering the relationship between vessel handling time and the number of quay cranes. It is also assumed that the unloading and loading of a vessel cannot start until all assigned quay cranes are available. Liang et al. (2009) formulate a non-linear mixed integer program and propose a GA-based heuristic to solve the problem. The paper ignores the transferring (i.e., setup) time of quay cranes. Giallombardo et al. (2010) formulate a linear MIP and use the Tabu Search scheme from Cordeau et al. (2005) to solve the problem. The paper is based on the concept of quay crane profiles, which indicate the number of quay cranes assigned to a vessel at each time step. Given a set of predefined quay crane profiles, the authors focus on simultaneously assigning the berths and quay crane profiles to vessels. Their objective is to maximize the total value of the chosen quay crane profile while minimizing the cost of handling the containers from the yard, represented as a piecewise linear function. Zhang et al. (2010) propose a mixed integer program and sub-gradient-based heuristic considering the coverage range of quay cranes. Their objective is to minimize the weighted sum of handling and penalty costs. Liang et al. (2011) formulate the problem as a non-linear bi-objective problem to minimize the sum of handling, waiting, and delay costs, and minimizing the number of quay crane movements between berths. The problem is solved with a GA-based heuristic. In the paper, the transfer time of quay cranes is not considered. Han et al. (2010) propose a stochastic formulation assuming vessel arrival and service times are stochastic. The objective is to minimize the expected value plus standard deviation of the total waiting and handling times by creating a robust berth assignment. The paper assumes that quay cranes are allowed to move between vessels as long as the total number of quay cranes serving a vessel remains unchanged. A GA-based heuristic is proposed to solve the problem. The paper states that survey and analysis of actual terminal operation data shows that the under ordinarily circumstances the vessel arrival time and task handling time are normally distributed.

4.5 Continuous dynamic BAP/QCAP (CDBAP/QCAP)

Meisel and Bierwirth (2009) formulate a Squeaky Wheel Optimization (SWO) heuristic as well as a Tabu Search-based heuristic to minimize service quality and operational costs. The two heuristics do not significantly differ in terms of solution quality and were shown to outperform various types of FCFS rules. Chang et al. (2010) solve the problem by minimizing the total berthing location deviation and the total penalty and energy consumption of quay cranes considering a rolling-horizon planning period. The paper presents a non-linear mathematical formulation and uses GA-based heuristic to solve the problem. Hendriks et al. (2010) consider the arrival time window for vessels as a variable and seeks to minimize the maximum number of quay cranes required to service all vessels in a cyclic berth environment. Blazewicz et al. (2011) formulate the problem as a non-preemptive moldable task scheduling problem by considering the tasks as vessels and processors as quay cranes assigned. Their objective was to minimize the maximum completion time of all vessels. The paper derives a solution to the problem by first solving the continuous version of the moldable task scheduling problem, where tasks are allowed to use fractional resources, and transforming it into the discrete version of the problem using a rounding-scheme. The paper does not require the total handling time of the vessel to be linear with respect to the number of cranes allocated. Zhen et al. (2011a) simultaneously solve the BAP/QCAP and the yard block assignment problem, where the latter seeks to assign storage areas to vessels. The paper uses the quay crane profile concept from Giallombardo et al. (2010). A linear MIP is proposed to simultaneously minimize the service quality and the distance from the assigned berth to the location of inbound and outbound containers. A lower bound is proposed by solving the berth and yard assignment problems independently. A heuristic that solves the problems separately and then integrates them is proposed. The authors conclude that the proposed solution is time consuming, yet capable of solving real-world-like instances.

4.6 Hybrid dynamic BAP/QCAP (HDBAP/QCAP)

Within the considered 8 year period between 2004 and 2012, the only journal papers found addressing the HDBAP/QCAP were Lokuge and Alahakoon (2007) and Salido et al. (2011). Lokuge and Alahakoon (2007) propose an artificial intelligence approach based on a new hybrid BDI (Belief-Desires-Intention) framework. The proposed methodology was compared with the current operations in the Jaya container terminal at the Port of Colombo in Sri Lanka, where the proposed approach provided better estimates of port productivity and significantly reduced the average waiting time of vessels, among other performance metrics. On the other hand, Salido et al. (2011) propose a solution method based on artificial intelligence to solve the BAP and the container stacking problem (i.e., how to rearrange containers to minimize the number of reshuffles required by the yard cranes during the loading process). The two problems are solved independently, as well as integrated. For the BAP the paper uses a GRASP-based heuristic to minimize the total waiting time. Results show that the proposed heuristic outperforms FCFS. For the combined problem the objective is to minimize a weighted function of vessels’ total waiting times and expected number of reshuffles required by the yard cranes.

4.7 BAP/QCSP

Only two papers, address the BAP/QCSP integrated problem between 2004 and 2012. All other papers studied the QCSP in isolation. Lee and Wang (2010a) presented two interdependent MIP formulations. The BAP seeks to minimize the completion time of all vessels, while the QCSP seeks to minimize the completion time for a vessel. The paper assumes that the number of quay cranes per berth is fixed. Furthermore, the quay crane travel time between vessels is ignored. A GA-based heuristic is presented where the BAP candidate solutions are evaluated after solving the QCSP with an approximation algorithm based on Dynamic Programming. Song et al. (2012) formulate the integrated problem as a bi-level program where the (discrete-static) BAP is the upper-level problem and the QCSP is the lower-level problem. GA is used to address the upper-level problem. For each candidate solution of the BAP in the GA, the QCSP is solved to optimality as an MIP.

5 Quay crane scheduling problem

As described in Sect. 1, the Quay Crane Scheduling Problem (QCSP) seeks to assign and sequence unloading and loading tasks to a predetermined number of QCs. The problem is typically addressed as a scheduling problem, where quay cranes are the machines and the jobs correspond to individual containers or sections of the vessel (e.g., holds).

Bierwirth and Meisel (2010) present a classification scheme for the QCSPs similar to the one for the BAP. As before, we will also abide by their classification scheme to solidify it to the point where authors would start to explicitly stating the classification for their papers. The classification scheme from Bierwirth and Meisel (2010) is based on four attributes: task, crane, interference, performance measure. The task attribute discriminates between what constitutes a “job”. The common levels for this attribute are vessel bays (bays), sections of bays (area), a stack of containers (stack, i.e., all the containers that are on top of each other), container groups (group, defined by the characteristics of the container), and individual containers (container). The crane attribute specifies the quay crane assumptions made regarding the quay cranes’ availability, position, etc. The interference attribute is used to describe the interference constraints imposed on multiple quay cranes to avoid crossing (cross) or for safety (safe). Lastly, the performance measure attribute specifies the objective function to be minimized when scheduling the cranes.

Table 3 presents the classification scheme for the QCSP. As with the BAP classification, we implemented some minor, yet important, modifications to the original classification scheme. Main reason is to be able to also classify papers that deal with important trends and developments in seaside operations. In Table 3, we added a new Crane Attribute called float, to be used when papers assume that one or more floating QCs are used to load/unload vessels. In addition, three new attribute levels for interference are incorporated. The original classification had an Interference—safe level which described the case where safety margins between quay cranes are considered. However, given an indented berth, more safety margin-related levels need to be defined. We redefine the original Interference—safe level to describe horizontal interference between cranes on the same side or different sides of the berth. The three interference levels that were added to the classification scheme are: Interference—safea, Interference—safeo, and Interference—platform. As illustrated in Fig. 4, Interference—safe has to do with horizontal safety distances between quay cranes, while Interference—safea considers the safety area required between cranes working on one side and the aft of the vessel, and Interference—safeo considers the vertical safety distance between quay cranes working on opposite sides of the vessel. On the other hand, Interference—platform is to be used when the interference constraint refers to platforms that carry floating QCs. In this case, the platforms are required to observe a safety distance. We also add a performance measure recognizing that the QCSP, the transfer vehicles, and yardside operations have already been and should continue to be coupled. We add Performance Measure—TV and Performance Measure—YS to represent performance measures regarding the utilization of transfer vehicles and yardside equipment, respectively.

Table 3 Modified QCSP classification scheme based on Bierwirth and Meisel (2010)

Fig. 4

New safety level restrictions for indented berths

We classify nineteen QCSP papers that did not appear in Bierwirth and Meisel (2010) in Table 4. Appendix 2 presents the QCSP classification for all journal paper published between 2004 and 2012, including those in Table 4 and the ones in Bierwirth and Meisel (2010). In the next Sub-sections, we describe the relevant QCSP literature according to their task attribute.

Table 4 Newly classified QCSP publications

5.1 Area

Lim et al. (2004) focus on assigning jobs to non-passing quay cranes in order to maximize the throughput. The problem is approached as a bi-partite graph matching problem and is shown to be NP-complete. A dynamic program, TS-based, and SWO-based heuristics are proposed. Based on experimental results, it is concluded that the SWO-based heuristic finds good solutions for both small and large problems in very short runtimes. Lu et al. (2012) solve the QCSP allowing vessel bays to be served by more than one QCs (i.e., shared bay). The number of containers in each bay to be assigned to each QC is left as a decision variable. A polynomial-time heuristic that generates conflict-free schedules is proposed and shown to have a small optimality gap for practical instances. (Note: The proposed classification of this paper in terms of its task attribute is “area”, although the authors propose to classify it as “bay”. We reserve “bay” for when bays are served by a single QC. We say that the area to be assigned to each QC is left as a decision variable in this paper. A similar analogy might be made to argue that the paper should be classified as container, although that would require the incorporation of precedence constraints.)

5.2 Bay

Most authors focus on bay-wise QC scheduling. Liu et al. (2006) propose a linear MIP formulation to minimize the maximum relative tardiness of vessels. Two heuristics based on a two-level decomposition are presented. The first (lower) level solves the QCSP for each vessel for various possible number of QCs assigned to it. This information is then used to solve the QCAP as the second (upper) level. Also, a lower bound for the problem is derived by relaxing the problem, including most crane and interference attributes. Based on experimental results with up to 12 QCs and 14 vessels, the paper concludes that the proposed heuristics yield effective solutions in a reasonable amount of time. Later, Chen et al. (2012) correct the formulation in Liu et al. (2006) and take advantage of the problem structure to use a combinatorial benders’ cut algorithm to solve the problem to optimality.

Zhu and Lim (2006) study the QCSP with non-crossing constraints with the objective to minimize the makespan. An integer programming formulation, a Branch & Bound (B&B), and an SA-based heuristic are proposed. The B&B algorithm outperformed CPLEX in small sized problems with up to four QCs and 20 jobs. The SA-based heuristic performed well in medium and large size problems when compared to a lower bound. Lim et al. (2007) also focus on the non-crossing spatial constraint of the QCSP to minimize the makespan. It is shown that the problem can be decomposed into determining the job-to-crane allocation and determining the starting time for QCs to bays. Further, they show that given a job-to-crane allocation, a strategy where each QC serves all assigned jobs from left to right (unidirectionally), and when cranes need to cross the priority is given to the rightmost crane, minimizes the makespan. Hence, the solution space for the problem can be limited to allocating jobs to cranes. A constraint programming model is proposed. The paper uses dynamic programming, backtracking exact algorithms, and Simulated Annealing-based heuristic to solve the problem. Zhang et al. (2008) study the on-line version of the QCSP in Zhu and Lim (2006). Two heuristics are proposed for the case where there is an on-line list and on-line time problems. In the former there is no information regarding the remaining jobs in the list, while in the latter the information regarding release dates is available.

Lee et al. (2008a) consider the vessel handling priorities for the QCSP and seeks to minimize the weighted completion time of the vessels. An MIP formulation and GA-based heuristic are presented. Experimental results with up to 30 bays and four QCs found that the GA was at most 1.38 % from a lower bound found by relaxing the non-passing constraint in the MIP. Lee et al. (2008b) is basically the same as Lee et al. (2008a) in terms of the figures, tables, formulation, GA, and lower bound, but with the objective to minimize the makespan. Lee and Wang (2010b) revisit the QCSP with handling priorities as in Lee et al. (2008a), except that priorities are considered between vessel bays. The paper uses the MIP formulation from Lee et al. (2008a) and includes use the NP-Complete proof from Lee et al. (2008b). An approximation algorithm is presented based on the Weighted Shortest Processing Time rule combined with Dynamic Programming. Hakam et al. (2012) proposes a simple genetic algorithm for the same problem as Lee et al. (2008b). The genetic algorithm was shown to outperform two greedy heuristics by up to 10 %.

Boysen et al. (2012) study the general problem of partitioning bays among QCs in an indented berth in order to balance the workload among the cranes. The paper considers QCs in the same berth side as non-passing, while QCs in opposite sides of the indented berth are considered as passing. The problem is formulated as a dynamic program and solved by using several heuristics. An iterated beam search algorithm, which finds guaranteed optimal solutions for practical-sized instances, was also presented.

The QCSP has also been solved considering the operations of the transfer vehicles and the yard. Vis and Van Anholt (2010) use discrete event simulation to compare the performance of traditional and indented berths. The main performance measure was the total completion time for a single vessel. The QCSP was performed by bay following a unidirectional strategy, which was shown to be optimal in Lim et al. (2007). Self-lifting transport vehicles are integrated in the simulation model. It is concluded that vessel operation times at indented berths are lower than in traditional berths by approximately 30 %. Legato et al. (2010) use a discrete event simulation-based optimization approach to consider the transfer vehicles and other uncertain events. The QCSP is solved using an SA-based heuristic. However, the fitness of the QC schedule is evaluated using the simulation which considers the stochastic nature of the system. The proposed SA-based heuristic assuming a deterministic environment, which would be comparable to deterministic versions of the problem, was only compared to the lower bound from Lee et al. (2008b) for one instance of the problem. Lee et al. (2009) simultaneously solve the QCSP with the yard crane scheduling problem (YCSP) for the outbound operation. The latter seeks to find the best schedule for a set of yard cranes. The paper only considers a single QC and two yard cranes and assumes that only one type of container is stored in each bay, and that the QC and yard crane handling times are constant. An MIP formulation is presented. Two heuristics are used to solve the problem, a GA-based heuristic and a problem-specific heuristic. The problem-specific heuristic outperformed the GA in the ten problem instances considered. The problem-specific heuristic exhaustively enumerates all possible QC schedules, and for each schedule finds a yard crane schedule using a set of rules. Hence, the problem-specific heuristic is very sensitive to the number of containers to be loaded in each bay. Wang and Kim (2011) study the QCSP considering the assignment of yard blocks to vessels. The objective function is composed of six terms, including QC and yard crane operations. A GRASP heuristic is proposed, but given the number of constraints considered the heuristic generated discarded many unfeasible solutions that had to be discarded.

5.3 Stack

The two papers addressing the QCSP at the container stack level only consider routing a single QC. Goodchild and Daganzo (2006) study the single QCSP with double-cycling. In their approach, the loading and unloading of vessels is performed simultaneously in order to minimize the number of operations (i.e., cycles) necessary to complete unloading and loading. The double-cycling is considered within bays and it is assumed that containers that are to stay in the vessel are unloaded and then reloaded. The problem is formulated as a two-machine flow shop scheduling problem, where stacks are considered the jobs and the unloading and loading processes are considered the machines, and can be easily solved with the well-known Johnson’s rule. A lower bound and greedy heuristic for the number of cycles required to serve a bay is presented. Based on real data, the paper concludes that double cycles typically reduce the number of cycles by approximately 20 % and the operational time by 10 % when double cycles are performed only below deck. Zhang and Kim (2009) expand the approach of Goodchild and Daganzo (2006) to consider hatch sequencing in addition to the original stack sequencing within a hatch. The problem is reformulated as an MIP and a local search heuristic is proposed to solve the problem. Experimental results show that for small problems the heuristic performs well, while for larger problems it outperformed the real schedules constructed by human planners.

5.4 Group

Kim and Park (2004) propose a mathematical formulation to minimize the weighted makespan and the total completion time, although the weights were given recognizing that makespan is a more important objective. A Branch and Bound algorithm and a GRASP heuristic are proposed to solve the problem. Experimental results with up to three QCs and 20 tasks found that the GRASP solution was at most 10 % from the optimal solution and took only 3 % of the time. It was observed that the solution time using GRASP was proportional to the number of tasks and inversely proportional to the number of quay cranes. Moccia et al. (2006) propose a correction and improvement to the formulation in Kim and Park (2004) and device a Branch & Cut (B&C) algorithm for the problem. Experimental results show that the proposed B&C algorithm outperforms Kim and Park’s Branch and Bound. Sammarra et al. (2007) solve the same problem as Kim and Park (2004) and Moccia et al. (2006). The problem is viewed as a vehicle routing problem for which a TS-based heuristic is proposed. Experimental results show that the TS outperforms the GRASP heuristic from Kim and Park and provides a good compromise between solution quality and time when compared to the B&C from Moccia et al. (2006). Bierwirth and Meisel (2009) modify the proposed corrections in Sammarra et al. (2007) to the original formulation in Kim and Park (2004), as it still might yield infeasible solutions. A Branch & Bound strategy is used to solve the problem, using a search space that is limited to unidirectional schedules such as the one in Lim et al. (2007). Although the authors show that the unidirectional strategy is not necessarily optimal for the container group scheduling, their heuristic outperformed those of Kim and Park (2004), Moccia et al. (2006), and Sammarra et al. (2007). Lee and Chen (2010) also point out and correct one of the issues in the revised formulation of Kim and Park (2004), which had already been corrected in Bierwirth and Meisel (2009). The paper also highlights that the formulation could force a quay crane to be driven out of the space boundary of the vessel. This observation was not considered in Bierwirth and Meisel (2009). A revised formulation is presented. However, the proposed formulation does not take into account all the corrections in Bierwirth and Meisel (2009) to the original formulation. Hence, the formulation of Bierwirth and Meisel (2009) needs to be modified to avoid QCs to travel beyond the space boundary of the vessel. To address this issue, Lee and Chen (2010) propose to use two dummy QCs and two dummy bays, which can be easily incorporated to Bierwirth and Meisel’s (2009) reformulation. Lee and Chen (2010) also propose two approximation algorithms for the problem. Later, Chung and Choy (2012) and Kaveshgar et al. (2012) propose genetic algorithms to solve the QCSP problem. The genetic algorithm in Chung and Choy (2012) was compared with the heuristics from Kim and Park (2004), Moccia et al. (2006), and Sammarra et al. (2007), finding solution within 6 % of the best found by those methods in a fraction of the time. On the other hand Kaveshgar et al. (2012) compared favorably with the heuristic from Meisel and Bierwirth (2009) with a limited runtime as reported in Meisel and Bierwirth (2011), finding solutions that had an average gap of 0.6 %.

Ng and Mak (2006) propose a binary formulation for the problem. A lower bound is obtained by enhancing on an existing lower bound for the job scheduling problem with sequence independent process times on identical parallel machines. A decomposition heuristic is proposed where the vessel is partitioned into zones and dynamic programming is used to find optimal partitions. Based on experimental results with up to seven QCs and 50 vessels it is concluded that on average the proposed heuristic finds solutions within 4.8 % from the lower bound, 16 % in the worst case. Tavakkoli-Moghaddam et al. (2009) simultaneously solve the QCSP and the QCAP considering the vessel earliness, tardiness, and fixed and variable costs of the QCs assigned. The paper presents an MIP formulation for the problem and a GA-based heuristic. Experimental results show that the heuristic performs well in terms of solution time and quality when compared to LINGO. Meisel (2011) incorporates time windows to the QCSP and seeks to minimize the makespan. A linear MIP, a lower bound, and a heuristic that limits the search space to unidirectional schedules are proposed. Based on experimental results, it is concluded that the proposed heuristic converges quickly to a good solution and that it performs well in terms of solution quality (less than 4 % from the lower bound) and time. Legato et al. (2012) incorporate different QC processing times for container groups, in addition to time windows and unidirectional schedules,. A linear mixed integer program formulation and a Lagrangian relaxation for the problem is presented. The branch and bound from Bierwirth and Meisel (2009) is enhanced by refining the lower bounds, branching criteria, and the evaluation of partial and complete schedules, which is done through a timed petri net model. The heuristic outperformed the original heuristic and was on average within 3 % of the computed lower bound for all instance sets considered.

5.5 Container

Meisel and Wichmann (2010) study the QCSP considering double-cycling and (internal) reshuffling. In other words, the paper assumes that instead of unloading containers that are to stay in the vessel, as assumed in Goodchild and Daganzo (2006), those containers are repositioned within the vessel. A mathematical formulation, a new lower bound, and a GRASP-based heuristic are proposed. The average gap between GRASP and the proposed lower bound was less than 4 %.

In an effort to provide a practical way of comparing the performance of the different heuristics for the QCSP, Meisel and Bierwirth (2011) created a QCSP problem generator (QCSPgen) that can be used at different job levels, namely container groups, bays, or bay areas. QCSPgen is a Java application that can be downloaded free at http://prodlog.wiwi.uni-halle.de/qcspgen/. The heuristic from Bierwirth and Meisel (2009), which works at the container group level, was used with a limited runtime to solve 400 benchmark problem instances in terms of the vessel handling time. The individual results for the problem instances, as well as some lower bounds, are available on the abovementioned website. Further, the paper examines the tradeoff between solving some benchmark problems at different levels of jobs. It is concluded that under some conditions a smaller level of jobs yield significant improvements, but the improvement was unimpressive under other conditions. Some important assumptions made in the paper are that all vessel bays are of the same size, and that stacks, tiers, and hatches are not specified.

Chao and Lin (2011) focus on selecting the best QC for a port. A two-phase approach that combines exploratory factor analysis (EFA) and fuzzy analytic hierarchy process (AHP) is applied to the Kaohsiung port in Taiwan. The study considers conventional QCs as well as twin lift spreader, double-trolley, and using indented berths.

Shin and Lee (2012) and Nam and Lee (2012) study the QCSP with a floating QCs concept called mobile harbors. A mobile harbor is a floating platform with a quay crane that allows loading and unloading of vessels from sea. The mobile harbor may be used to help load/unload a berthed vessel or it may be used to service a vessel without having the berth. In both scenarios, the mobile harbor docks to the vessel to perform the operations. The mobile harbor crane scheduling problem studied in Shin and Lee (2012) seeks to determine the sequence in which containers are handled, as well as the storage location within the mobile harbor, while maintain the mobile harbor’s stability. It is implicitly assumed that the problem is solved given a particular docking location of the mobile harbor to the vessel. An GA and a local search heuristic are proposed for solving single mobile harbor scheduling problem for the unloading operation. Nam and Lee (2012) study the multi-mobile harbor scheduling problem. It is assumed that a fleet of mobile harbors operating under double-cycling collaborates (while maintaining a safety distance) to unload and load a set of vessels in open sea. The mobile harbors are allowed to dock more than once in order to service the vessels. The decision variables for each crane are the schedule of tasks, the start time, and their docking position. The objective is to minimize the sum of the completion time of the vessels. The problem is modeled as an MIP and two heuristics are presented and evaluated.

6 Integration of seaside decision problems

As discussed in previous sections, some papers address multiple decision problems that involve seaside operations. In this Section we describe how the problems were integrated. To characterize how the problems were integrated, we once again use the scheme from Bierwirth and Meisel (2010), presented in Table 5.

Table 5 Seaside problem integration classification scheme in Bierwirth and Meisel (2010)

Table 6 presents our classification for the papers that are not included in Bierwirth and Meisel (2010). As before, we did minor modifications from the original classification by adding some decision problems that transcend the seaside operations. In Table 6, YSAP refers to the yard storage assignment problem, i.e., assigning storage yard locations to vessels. CSP refers to the container stacking problem, i.e., relocating containers in the yard to minimize the number of reshuffles required. YSAP refers to the yard space assignment problem and YCSP refers to the yard crane scheduling problem. TVSP refer to the transfer vehicle scheduling problem. Lastly, CI refers to the container inspection process. These papers have already been discussed above. Appendix 3 presents the classification of integrated problems that include seaside operations for all journal papers published between 2004 and 2012, including those in Table 6 and the ones in Bierwirth and Meisel (2010).

Table 6 Classification of new papers on integration of seaside decisions

7 Future seaside operations: challenging the paradigm

Up to this point, this paper has focused on understanding the current seaside operations and the latest trends and developments. This information is invaluable in order to narrow the gap between theory and practice in order to continue improving the operation of container terminals. However, this approach assumes that the current seaside operations paradigm (infrastructure, equipment, etc.) will continue to hold in the future. In this section we take a different approach by envisioning the container terminal of the future from an Industrial Engineering and Operational Excellence perspective.

In our approach, we intend to formulate characteristics of future seaside layout and material handling equipment by identifying opportunities for improvement and borrowing best practices from manufacturing, material handling, and warehousing. The ideas proposed in this section are not claimed to be unique but intended to challenge container terminals and material handling equipment designers.

7.1 Seaside layout

The seaside operations need to efficiently unload (load) vessels to (from) internal transfer vehicles. Hence, the futuristic layout must facilitate the loading and unloading of vessels. A futuristic layout should have the following four characteristics:

• L1. Capable of mooring many large vessels (high capacity);

• L2. Allows simultaneous loading and unloading from several sides of the vessels;

• L3. Provide flexibility for efficient real-time adjustments in the operations to allow for quick QC repositioning (minimize setup times);

• L4. Facilitate QC operations (reduce cycle times).

Layout characteristics L1 and L2 can be addressed with indented berths. Given the same number of cranes, traditional berths might be similar in performance to marginal berths. However, if the number of QCs is not limited, indented berths will be superior to traditional berths in terms of QC throughput. Indented berths can also be used under double-cycles or to load containers from one side, while unloading from the other side. The effects of these strategies in indented berths need to be further investigated, particularly as they pertain the other areas of the terminal.

At first sight it might appear that indented berths would not facilitate L3 as QCs would require vertical and horizontal movements to be repositioned. However, a layout such as the one in Fig. 5 would allow some repositioning of QCs under an indented berth. In Fig. 5, multiple QCs serve four indented berths. The dotted lines represent the travel path for the QCs. Notice that the proposed layout would only require horizontal or vertical movements for each (rail-mounted automated) QC.

Fig. 5

Repositioning QCs in indented berths

Another alternative for layout characteristics L2 and L3 is to use floating QCs. A similar concept has been considered by the Port of Rotterdam (Pielage et al., 2008). Kim and Morrison (2012) present an interesting classification and economic analyses for non-traditional off-shore structures that may be used as an alternative or to supplement traditional ports without significant dredging and construction costs.

Layout characteristic L4 suggests a relationship between the layout and the QC throughput. This relationship has to do with the third-dimension of the problem rather than the typical two-dimension vision of layout. Currently, in the unloading (loading) operations the containers need to be lifted over the vessel and then lowered back to the ground to be placed on a transfer vehicle (or in a hold). An alternative would be to reduce the cycle time of the QCs by not requiring them to lift containers over the vessel. Two possibilities immediately come to mind, either the vessel level is lowered to the same level as the quayside, or the quayside level is raised to the vessels’ level. The first option could be implemented by using water-locks, similar to the ones used throughout the Dutch canals. With the current technology, raising or lowering water levels is a very slow process. Further, berths would require additional depth to lower the vessels. A simpler approach would be to raise the level of the quayside. This can easily be done, although it would create a slope in some parts of the container terminal. Clearly, if the quayside level is raised considering the vessels served in each berth, QCs would experiment a significant reduction in their cycle times. For example, the new QC cycle time for the loading operation would be a very minor vertical lift, the horizontal travel to reach the appropriate vessel hold, and a vertical movement to place the container on the vessel.

7.2 Seaside material handling equipment

There are also some current paradigms regarding the current material handling equipment for seaside operations. The following paradigms are identified.

P1:

QCs should not double handle containers;

P2:

Containers are handled individually;

P3:

Locks are used to secure containers;

P4:

Vessels must be stationary to be unloaded and loaded

These four seaside paradigms may be limiting the throughput of container terminals. The first paradigm is in accordance to the general material handling principle. However, if the cycle time of the bottleneck operation can be reduced by double-handling it might be a good idea. Consider a QC with a mid-level platform. A smaller crane similar to the one used to load and unload non-automated transfer vehicles could work in series with the QC by loading and unloading containers from the platform to the ground.

The second paradigm suggests that a container (or two if using multi-lift spreaders) is the material handling unit. Would it be possible for a QC to unload and load entire holds at the same time? This would probably require designing some simple equipment for combining containers to create a larger material handling unit load. This is also related to the third paradigm, the locks. Containers use (standardized) locks on each of the four corners to secure them to the cranes and to other containers. These locks need to be manually removed from the containers. Typically, for a QC to release a container, four locks need to be removed. This requires a crew of four people (each removing one lock) and a supervisor to ensure the locks are off before releasing the containers for safety reasons. Designing a mechanism to insert, release, or hide these locks could save valuable time in the quayside.

The fourth paradigm states that vessels must remain stationary at the port. This concept is similar to the fixed position layout in manufacturing, where machines are moved to the part, mainly when parts are too large to be moved. However, if vessels can be slowly moved in a continuous berth, containers can be unloaded closer to different parts of the yard as shown in Fig. 6. Clearly, this would also affect the current storage yard paradigm. This concept, labeled Canal Berth, would also allow for an alternative berth configuration where there are two continuous berths on either side of the vessel. It would be similar to passing the vessel through a canal.

Fig. 6

Canal berth layout

8 Conclusions and new research avenues

In this paper we discussed the current trends and developments for seaside operations, described and classified the scientific literature, and challenged the current seaside operational paradigm by proposing innovative ideas that can be implemented in the future. In this Section, we provide constructive criticism of the literature and identify new research avenues based on the current and future trends and developments. For convenience and future reference, the new research avenues are identified with “RA”.

With regard to the traditional literature on the three key decisions for seaside operations (BAP, QCAP, and QCSP) we propose the following research avenues.

RA1:

The literature should only focus on the dynamic BAP and devote attention to solving it dynamically

RA2:

The QCAP needs to be solved assuming that QCs are not identical. For example, it may be assumed that only some of the QCs are equipped with twin-load spreaders. In this case, the QCAP would depend on the size, number, and location of containers

RA3:

The number of QCs per berth (or vessel) should not be considered a given parameter

RA4:

Most of the QCSP literature is limited to a single vessel. However, the QCSP should be done considering multiple vessels

RA5:

It should be explicit in the literature what are the practical differences and implications of using single-weighted-objective and multi-objective models in container terminals

RA1 is based on the observation that although the dynamic BAP is extensively studied in the literature, most of the existing solution approaches are still static. In other words, the problem is solved off-line, once, before vessels arrive. The dynamic (on-line) approach for this problem would consider the actual operational situation of the container terminal when a vessel arrives (or a berth becomes available) in the solution of the dynamic BAP. Some authors may advocate for using their static solution method for the DBAP every time a vessel arrives. Classic rolling horizon frameworks might be valid for practical usage, as long as previous decisions can be altered in new steps. Numerical experiments can be performed to demonstrate the robustness of these approaches for practical usage. Currently, the quality of most solution methods for the dynamic BAP is compared with the static optimal BAP.

In the literature, the QCAP is typically considered a trivial mathematical problem. However, as proposed in RA2, if the throughput of QCs is different, dependent on the size of the containers, or if there are limitations on the tasks it can be assigned, the QCAP will not be trivial. Further, RA2 will create new incentives for integrating the BAP, QCAP, and QCSP. In general, integrating the BAP, QCAP, and QCSP is not trivial due to the mathematical complexity of the problems. Needless to say, more efforts need to be made in this direction. However, it is observed that the combined BAP/QCAP and QCAP/QCSP is often overlooked by assuming the number of QCs is known (RA3). This assumption is convenient as it justifies decomposing seaside operations. However, if one focuses on complying with the stipulated vessel schedules, the number of QCs may change over time. A solution to this scenario would require a QCSP that consider inter-vessel scheduling as proposed in RA4. Currently, most of the literature assumes that the number of QCs is known and that (un)loading does not start until all necessary QCs are in place. RA2, RA3, and RA4 will ultimately thrust research toward the integration of seaside problems.

New research avenue RA5 is in response to an apparent division in the container terminals’ scientific literature with respect to single versus multi-objective optimization. The only argument found in the seaside literature as of why multi-objective optimization is more adequate than single objective optimization (where the objectives of the multi-objective problem are transformed into a single objective with weights) is that in the former the user does not need to know the corresponding weights. In turn, the multi-objective approach presents an efficient frontier for the decision maker, whereas the single-objective provides a single solution. Our claim is that for the three problems found on seaside operations, and their integration, the multi-objective solution can be obtained from solving the single-weighted-objective approach for different weight combinations. This claim is of course only valid for problems where all the weighted terms in the single objective formulation are associated with constraints in the mathematical formulation, which is the case for the vast majority of operational problems in seaside operations. It would be interesting to compare the two approaches and test their applicability both for operational and tactical decision problems.

The non-traditional berths (e.g., indented, canal) also create new opportunities for new research avenues. In general, it needs to be investigated if the existing mathematical models are applicable to these non-traditional berths. The following new research avenues related to non-traditional berths are identified:

RA6:

In which configuration should vessels moor in non-traditional berths?

RA7:

What is the best layout for non-traditional berths (e.g., how should indented berths be positioned with respect to one another)?

RA8:

When vessels are served from more than one side simultaneously, what is the effect of allowing QC preemptions?

RA9:

When vessels are served from more than one side simultaneously, how can the new QC safety restrictions (in Fig. 5) be implemented in the models?

RA10:

What is the effect of the mobility restrictions for QCs on non-traditional berths with respect to the BAP and the QCAP (see Fig. 6)

RA11:

When vessels are served from more than one side simultaneously there is a possibility to split holds between cranes on different sides of the vessel (while obeying the safety constraints). The multi-crane QCSP needs to be solved for this problem

RA12:

How do the unloading and loading plans change for non-traditional berths?

RA13:

Would QC double-cycling benefit non-traditional berths?

RA14:

Compare the traditional and non-traditional layouts in terms of the vessel turnaround time

The research avenue RA14 focuses on comparing the different traditional and non-traditional layouts. Perhaps, the appropriate means of comparison is an extensive simulation study. However, before one can appropriately simulate non-traditional berths, solution models for the decisions to be made in these berths need to be investigated. Therefore, before RA14 can be done fairly, research avenues RA6-RA13 need to be investigated. Unfortunately, most simulation studies found in the literature limit their contribution to a mere simulation study. The actual scientific contribution of these studies is very limited. Instead, simulation papers should focus on exploring new concepts, where the simulation study is used to evaluate the proposed ideas. Very few simulation studies provided any insight that was either counterintuitive or new.

In the literature, a lot of attention has been given to discrete berths. On the other hand, continuous berth layouts are superior by definition to discrete berth layouts. Although solving a continuous berth layout is more complex than the discrete berth case, future literature should focus on solution methods for the former. However, how the berth is configured (independent of it being continuous or discrete) could have an effect on the quality of the non-traditional berth (RA6). For example, if it is assumed that vessels block each other on indented berths, then one would be able to moor more vessels than without the assumption, at the expense of lower QC utilization. This research avenue is also related to RA7, where the berth location with respect to each other and with respect to the storage yard is investigated.

Serving vessels from more than one side creates new interesting research avenues like the ones in RA8-13. The ultimate question is if the existing models can be modified to include non-traditional berths, or if new models are required. We understand that new models, specifically designed for non-traditional berths, are required.

The last set of new research avenues seek to challenge the current operational paradigm.

RA15:

If recovered lands are used, one may design a container terminal in many different ways. What is the best layout for a container terminal?

RA16:

Under which conditions do mid-level platforms for double trolley QCs reduce the vessel turnaround time?

RA17:

How can containers be loaded and unloaded as one unit and what would be the benefit of such a strategy?

RA18:

How can quaysides be designed so the vessel is not stationary when unloading and loading?

RA19:

Are multi-spreader QCs (double/triple) efficient?

New research avenues 15–19 are interesting in terms of the operational efficiency, but are particularly interesting for multi-disciplinary research as these technologies either do not exist or present challenges that transcend traditional OR.

A general unwritten assumption for seaside operations is that QCs are the bottleneck operation of container terminals. Hence, metrics that address QC efficiency are said to directly translate to vessel turnaround times. However, in some container terminals, particularly those automated layouts using AGVs and Automated Stacking Cranes (ASCs), the yardside has been reported to be the bottleneck operation. The last new research avenue identified in this paper is then:

• RA20. How does the approach to the BAP, QCAP, and QCSP changes if the QCs are not the bottleneck operation?

For most container terminals, seaside operations continue to be the bottleneck operation. However, as seaside operations continue to improve, the bottleneck operation of container terminals might shift to transport or yardside operations. Furthermore, there is a trend toward automation of transport and yardside operations. The automation in these operations seeks to minimize the operational costs, sometimes at the expense of a slower throughput (e.g., automated stacking cranes). A slower throughput of the transport or yardside operations jeopardizes the assumption that seaside operations will continue to be the bottleneck operation.

Appendices

Appendix 1

See Table 7.

Table 7 The classification of all BAPs published in scientific journals between 2004 and 2012

Appendix 2

See Table 8.

Table 8 The classification of all QCSPs published in scientific journals between 2004 and 2012

Appendix 3

See Table 9.

Table 9 The classification of the journal papers from 2004 to 2012 that propose solution methodologies that integrate the seaside decisions