Twin-crane scheduling during seaside workload peaks with a dedicated handshake area

Economies of scale in transportation coupled with modern, more fuel-efficient engines have led to increased ship sizes. In 2017, the largest container ships surpassed the 20,000 TEU (twenty-foot equivalent unit) capacity mark, and the currently largest vessels, the MSC Gülsün and its sister ships, transport up to 23,756 TEU (Schuler, 2019). Any additional hour of berth time in a port causes tremendous opportunity costs for these mega vessels. Thus, to keep these profitable ships returning, there is fierce competition among ports to offer the best cost–performance ratio to the shipping companies. To enable efficient port processes, all subsystems, starting with the huge quay cranes at the seaside, the intermediate storage yards for containers, up to the hinterland access (e.g., toward the railway system), and the automated guided vehicles (AGVs) or yard trucks connecting these subsystems, have to contribute. These subsystems, arranged in the so-called European setup with container blocks positioned perpendicular to the quay (Carlo et al., 2014a), are depicted in Fig. 1.

This paper focuses the storage yard subsystem, which has to ensure that it is not the bottleneck of the whole process, especially during peak hours with huge vessels berthed. Note that the great impact of an efficient crane operations schedule on total performance has for instance been shown by the extensive simulation study provided by Speer and Fischer (2017). A storage yard is subdivided into multiple blocks of containers each spanned by one or multiple automated gantry cranes. Figure 1 depicts container blocks each operated by two identical twin cranes, which is a common configuration in many ports worldwide [e.g., at Euromax terminal (Rotterdam) (Carlo et al., 2014a), Port of Virginia (Norfolk) (Briskorn et al., 2016), or Yangsha Terminal (Shanghai) (Hu et al., 2016)]. In this paper, we focus on a single container block operated by twin cranes during peak hours. In this crane configuration, the two identical cranes cannot pass each other, so that each of them exclusively serves one of the access points, also known as transfer points or input/output (I/O) points, at the seaside and landside, respectively.

During seaside workload peaks with huge vessels berthed, efficiently storing and retrieving inbound and outbound containers unloaded from ships and to be loaded onto them, respectively, is of utmost importance. To increase the container throughput during these peak times, the landside crane, although being blocked from direct access to the seaside transfer point, should support the seaside crane and share some of the workload. Cooperation between twin cranes is enabled if the seaside crane takes over an inbound container at the seaside access point but, instead of directly delivering the container toward its dedicated storage position in the block, places the box in an intermediate storage position between the seaside access point and final storage position. Then, the seaside crane can prematurely return to the seaside access point, whereas the landside crane completes the previous container move and delivers the box from its intermediate storage position to its dedicated storage position. We call this type of cooperation, where any open storage position is a potential intermediate storage position for a container move subdivided into two legs operated by different cranes, any-bay handover. Sophisticated scheduling procedures coordinating twin cranes with any-bay handover have, for instance, been introduced by Briskorn et al. (2016), Jaehn and Kress (2018) and Kress et al. (2019).

Because of the interference of the twin cranes when handing over boxes in arbitrary bays, these scheduling approaches are very challenging optimization tasks, especially when executed in a real-time environment where any change in the input data requires an (almost) instantaneous plan adaptation. Furthermore, monitoring the execution of such schedules in the real world, for example to avoid collisions, is more complicated if neither crane has a dedicated operating area. Consequently, in order to reduce this type of organizational complexity, a separation of blocks into dedicated crane areas interconnected by a so-called handshake area (see Fig. 2) has been discussed in the literature, e.g., Gharehgozli et al. (2017), XiaoLong et al. (2019), and is reported to be applied, for instance, in the port of Rotterdam (Carlo & Vis, 2010) and in practice in general (Dell et al., 2009). A handshake area restricts the handover of containers to a fixed, predefined bay within each block. Each crane has its dedicated area, which it operates exclusively without interference, and only when entering the handshake area to hand over or take over a container is it necessary to ensure that the cranes try not to do so simultaneously. Most scheduling approaches prioritize cranes simultaneously claiming access to the handshake area by simple decision rules, for example, by giving preference to the crane with the larger remaining workload (Gharehgozli et al., 2017). Consequently, existing research on handshake areas has mainly evaluated different rules for prioritizing cranes (Carlo & Martínez-Acevedo, 2015) embedded into simple heuristics for sequencing the container moves per crane in simulation studies (Gharehgozli et al., 2017; XiaoLong et al. 2019).

The organizational complexity of container handling is reduced when restricting handovers to a handshake area, because collisions can occur only in this area. This facilitates collision avoidance and interference handling. The scheduling task is further simplified because there is much less flexibility in the choice of where to hand over a container from one crane to another. Hence, the solution space decreases. Even with a handshake area, however, scheduling cooperative twin cranes and avoiding their interference in the shared area remains a complex and challenging optimization task. This paper introduces three alternative branch and bound approaches to solve the resulting optimization problem to optimality. Once a suitable exact solution procedure is available (and proven to solve instances of practical size), for the first time, we can quantify the price for planning simply. By benchmarking the simple rule-based approaches commonly applied in real-world terminals with our optimal algorithms, the optimality gaps of these simple rules can be quantified. Furthermore, we benchmark the application of a handshake area with an any-bay handover. In this way, practitioners under high competitive pressure to ensure fast and reliable container handling processes, especially during seaside workload peaks, receive some decision support on how to operate their twin cranes efficiently.

The remainder of the paper is structured as follows. Section 2 reviews the related literature. Section 3 defines our optimization problem (i.e., twin crane scheduling with a handshake area) and states its computational complexity. Three alternative branch and bound procedures are introduced in Sect. 4. Our computational study presented in Sect. 5 is subdivided into three parts. First, we evaluate the computational performance of our solution algorithms (see Sect. 5.1). We also explore where to position the handshake area under seaside workload peaks (see Sect. 5.2). We then benchmark our sophisticated optimization approaches with simple rule-based solution methods taken from the literature and with any-bay handover in Sect. 5.3. Finally, Sect. 6 concludes the paper.

Ocean-based container transport is the backbone of a globalized society. Therefore, it is anything but surprising that a huge body of scientific literature on container transport and port operations has accumulated during the past decades. Instead of trying to summarize this vast field, we only refer to the latest survey papers on port operations in general (Stahlbock & Voß, 2008; Steenken et al., 2004; Vis & de Koster, 2003), and on seaside operations (Bierwirth & Meisel, 2015; Carlo et al., 2015), intermediate storage in container yards (Carlo et al., 2014b), ground container transport in ports (Carlo et al., 2014c), and hinterland railway access (Boysen et al., 2013) in particular.

We concentrate our literature survey on workload sharing of multiple cooperative cranes in container yards. Cooperation is, obviously, not given if only a single gantry crane operates a container block. Crane scheduling approaches for this setting are provided for instance by Gharehgozli et al. (2014b) and Boysen and Stephan (2016). But twin cranes (without handshake area or any-bay handover) where one crane is fixedly assigned to all seaside-related container moves and the other to all landside-related moves, so that crane scheduling has to avoid interference whenever both cranes meet (e.g., see Boysen et al., 2015; Briskorn & Angeloudis, 2016; Gharehgozli et al., 2014a; Kovalyov et al., 2018), also do not cooperate in the strict sense we presuppose in this paper. Cooperation between cranes requires that there is (at least some) flexibility in the assignment of container moves to cranes, so that by varying these assignments the division of labor between cranes can be altered. This kind of cooperation, which is especially valuable during seaside workload peaks, can be achieved by the following settings:This paper is the first to derive exact solution approaches for scheduling the cooperation of twin cranes with a handshake area. The finding of our own literature search is supported by the recent survey paper on crane scheduling with interference by Boysen et al. (2017), who also establish a gap in the literature here.

Note that another lever to equally distribute the workload between cranes is the storage assignment decision, which either assigns each inbound container an initial storage position in the block after arrival or reassigns a container during restacking, typically executed during off-peak hours. By assigning storage positions closer to either the seaside or landside, the workload division between twin cranes is affected. A survey paper on container stacking and the resulting decision problems is provided by Lehnfeld and Knust ( 2014). We assume that the dedicated stacking positions of all containers are fixed and given. Only the decision on the intermediate stacking positions in the rows of the handshake area is part of our optimization problem. A handshake area confines intermediate container storage to a restricted area, so that reshuffles may become necessary if the other crane does not remove some boxes early enough. Therefore, we also integrate the storage decision within the handshake area into our optimization task. Such an integrated approach of stacking and crane scheduling was recently introduced by Galle et al. (2018), although only in a single-crane setting.

For defining our twin crane scheduling problem (TCSP) in the presence of a dedicated handshake area, we consider a single yard block, two identical twin cranes, and two access points from sea- and landside, respectively. The storage positions of the yard block are arranged according to a two-dimensional grid (see Fig. 2). The slots in the first dimension are passed by the complete crane body, and we refer to them as bays \(b=1,\ldots ,B\). The slots in the second dimension, passed by a crane’s trolley and container spreader, are referred to as rows \(r=1,\ldots ,R\). Consequently, each storage position can be identified by a tuple \((b,r)\in P:=\{1,\ldots ,R\}\times \{1,\ldots ,B\}\). Additionally, we have multiple slots aligned at the smallest bay. They are located in positions \((0,1),\ldots ,(0,R)\) and determine the seaside access point. The handshake area is given by a single bay located at predefined position \(b^h\), \(1\le b^h\le B\) and, consequently, consists of positions \((b^h,1),\ldots ,(b^h,R)\). In the handshake area, containers may be handed over from one crane to the other. This is realized by one crane setting down the container in a position \((b^h,r)\), \(r=1,\ldots ,R\), and the other crane picking up the container in \((b^h,r)\) later on. Each stacking position \((b^h,r)\), \(r=1,\ldots ,R\), of the handshake area has a free capacity \(C^h_{r}\) defined by the maximum stacking height minus the number of containers fixedly stacked in this position. We assume that we have a partition of the positions in the handshake area into two subsets \(H_1=\{(b^h,1),(b^h,3),\ldots ,\left( b^h,2\left\lceil R/2\right\rceil -1\right) \}\) and \(H_2=\{(b^h,2),(b^h,4),\ldots ,\left( b^h,2\left\lfloor R/2\right\rfloor \right) \}\) being used exclusively by cranes 1 and 2 for dropping off a container.

We only consider moves to and from the seaside during workload peaks caused by one or multiple berthing vessels, such that we have two sets of container moves, inbound containers \(I^i\) and outbound containers \(I^o\), all being available at the beginning of the planning horizon. Note that crane scheduling is typically executed under a rolling planning horizon, so this assumption does not mean that we consider an unrealistically long time span. Each container i is associated with two positions. The origin position \(o_i=(o^b_i,o^r_i)\) is where the container needs to be picked up by a crane. Afterwards, it is transported to destination position \(d_i=(d^b_i,d^r_i)\), where it is dropped off. For an inbound container i, the origin position \(o_i\) is located at the seaside access point, such that it can be defined by \((0,o^r_i)\), \(o^r_i\in \{1,\ldots ,R\}\). The respective destination position \(d_i\) is then a position in P. An outbound container i has its origin position in P and its destination position at the seaside access point, i.e., in \((0,d^r_i)\).

Two identical gantry cranes operate on the yard block, each moving with the whole crane body along the bays of the first dimension. To reach a storage position, a trolley runs along the horizontal beam of the gantry and passes the rows of the second dimension. A spreader can be lowered from the trolley to pick up or drop off containers at a specific slot. We refer to the seaside crane and landside crane as crane 1 and crane 2 and assume that the operation areas are separated by the handshake area, so that they operate in bays \(0,\ldots ,b^h\) and \(b^h,\ldots ,B+1\), respectively. The only shared bay is the handshake area where, however, both cranes cannot be present at the same time. Thus, crane 1 (2) has to be located in a bay \(b\le b^h-1\) (\(b\ge b^h+1\)) while crane 2 (1) operates in \(b^h\).

Because of the separate areas in which the two cranes operate, it is implied for each container whether or not it is intermediately dropped off in the handshake area. We, consequently, refer to the set of inbound (outbound) containers that need to be handled by the landside crane as \(I^{i,l}\subseteq I^i\) (\(I^{o,l}\subseteq I^o\)) and to the set of remaining containers as \(I^{i,s}=I^i\setminus I^{i,l}\) (\(I^{o,s}=I^o\setminus I^{o,l}\)).

For each container, we derive one or two transport jobs that are necessary to transport it from its origin to its destination, depending on whether it is intermediately stored in the handshake area. Let \(J_c\) be the set of transport jobs of crane c. For each container i in \(I^{i,s}\) and \(I^{o,s}\), we have a single transport job j(i) in \(J_1\). It consists of two operations, the pickup operation in position \({\hat{o}}_{j(i)}=({\hat{o}}^b_{j(i)},{\hat{o}}^r_{j(i)})=o_i\) and the drop-off operation in \({\hat{d}}_{j(i)}=({\hat{d}}^b_{j(i)},{\hat{d}}^r_{j(i)})=d_i\). For each container i in \(I^{i,l}\) (\(I^{o,l}\)), we have two transport jobs \(j^1(i) \in J_1\) and \(j^2(i) \in J_2\) (\(j^1(i) \in J_2\) and \(j^2(i) \in J_1\)), referred to as the storage job and the retrieval job. Storage job \(j^1(i)\) corresponds to the transport from \({\hat{o}}_{j^1(i)}=o_i\) to \({\hat{d}}_{j^1(i)}=(b^h,{\hat{d}}^r_{j^1(i)})\), \({\hat{d}}^r_{j^1(i)} \in H_1\) (\({\hat{d}}^r_{j^1(i)} \in H_2\)). Retrieval job \(j^2(i)\) has its pickup position in \({\hat{o}}_{j^2(i)}={\hat{d}}_{j^1(i)}\) and the drop-off position in \({\hat{d}}_{j^2(i)}=d_i\). Note that the row \({\hat{d}}^r_{j^1(i)}={\hat{o}}_{j^2(i)}\) of the intermediate storage position in the handshake area is not given in advance but is part of the optimization.

At the beginning of the planning horizon, crane \(c\in \{1,2\}\) is located in \(o^0_c=(o^{0,b}_c,o^{r,0}_c)\). We assume that both trolleys can move one row per period and both gantries can move one bay per period, and they can do so simultaneously. Hence, if no interference of cranes occurs, then moving gantry and trolley from position (b, r) to position \((b',r')\) takes \(\max \left\{ |b-b'|,|r-r'|\right\} \) periods. The spreader can be lowered only after the gantry and trolley are in their intended position, and it has to be fully up before the trolley and gantry can move. We assume that lifting and lowering takes p time periods independent of the current stacking height.

In the setup described above, we have four simplifying assumptions (in addition to those already explained in Sect. 1, i.e., given handshake area and container movement related to the seaside only), which need further justification. We consider a continuous time horizon where both cranes can move to adjacent bays in a single time unit, and refer to the time interval \([t-1, t]\) with \(t \in {\mathbb {N}}\) as period t. Note that periods refer to parts of the planning horizon but do not imply a discretization of the planning horizon. Within this problem setting, we seek crane schedules defining the activities of both cranes for any period. In order to constitute a crane schedule, we have to make a four-part decision. We aim at a minimum makespan schedule; that is, the point in time when the last container is dropped off at its destination position should be as early as possible. This objective frees the cranes as early as possible from the current workload, so that they are readily available to process the next set of container moves of the subsequent planning run. Furthermore, this objective also tends to reduce energy consumption (Speer & Fischer, 2017). Note that He et al. (2015) benchmark time-efficient and energy-efficient schedules and their impact on either objective. Their computational study, which however treats another yard crane setting, concludes that the two objectives are strongly related. Further research is certainly required here. We, however, follow the majority of papers—see the review papers of Boysen et al. (2017), Carlo et al. (2014a)—and target an efficient crane utilization enabled by the minimum makespan objective. But there are also alternative objectives, such as minimizing the lateness of jobs in relation to predetermined handover times to external transport devices (e.g., AGVs). We focus on the makespan, but would like to emphasize that extending crane scheduling with a handshake area to other objectives is a valid task for future research. We can assume that each crane proceeds along its sequence of operations (see points 2 and 3) as rapidly as possible (given the travel times between each pair of positions), which may be delayed only by interference from the other crane. That is, crane 1 (2) may have to wait for crane 2 (1) to complete one or more operations in the handshake area before proceeding to the handshake area itself. Moreover, it may be necessary to leave the handshake area between two operations in order to prioritize the other crane. However, these two types of delay are determined by the prioritization sequence of decision 4. Thus, once all four parts of the decision are made, we can easily determine the minimum makespan. The TCSP is to make our four-part decision such that an overall minimum makespan can be achieved. We provide a MIP model representing the TCSP in Appendix C.

We abstain from a formal proof and refer to Gharehgozli et al. (2014b) instead. Note that the problem setting of Gharehgozli et al. (2014b) assumes pickup and drop-off time \(p=0\), considers only a single crane, and addresses container movement via both access points. However, our setting with \(I^{i,l}=I^{o,l}=\emptyset \) renders crane 2 irrelevant, which leaves us with crane 1 only. Furthermore, Gharehgozli et al. (2014b) show (although they do not emphasize it) that their problem is NP-hard even if only a single access point on one side of the block is used only. This setting is equivalent to a special case of our problem with \(I^{i,l}=I^{o,l}=\emptyset \) and \(p=0\). Clearly, our problem setting is more involved due to the need to coordinate the operations of both cranes with respect to both physical and temporal interference in the handshake area. Obviously, these issues do not simplify the problem setting.

Note that the proof of Gharehgozli et al. (2014b) relies on the number of rows being part of the input of the problem. Clearly, in the real world, the number of rows in blocks is rather small. In the following, we thus show that TCSP is strongly NP-hard even for \(R=2\).

Note that Theorem 2 covers the cases where capacity in the handshake bay is not tight or stacking is not allowed due to \(C^h_1=C^h_2=1\).

We present three branch and bound (B&B) approaches in order to solve our TCSP. These approaches determine the stacking positions of jobs in \(I^{i,l}\cup I^{o,l}\) and the sequences of jobs for both cranes (parts 1 to 3 of the decision) in the course of branching. Decision part 4, i.e., the prioritization of pickups and drop-offs in the handshake area, is determined by a polynomial-time routing algorithm.

In the B&B approach of Sect. 4.1, we simultaneously consider the job sequences and the possible stacking positions of handshake operations. The approach in Sect. 4.2.1 proceeds by determining job sequences completely before deciding stacking positions, while the B&B approach in Sect. 4.2.2 determines these decisions in reverse.

Our computational study presented in this section consists of three parts. First, we benchmark the solution performance of our three B&B procedures in Sect. 5.1. Here, we determine which of them is best suited for solving real-world TCSP instances. Then, in Sect. 5.2, we explore the best position of the handshake area and its impact on throughput performance. Finally, we challenge our best B&B procedure with simple heuristic approaches taken from the literature. By determining the optimality gaps of these straightforward solution methods, we quantify the price of simple planning. Introducing a handshake area is an operational simplification by itself compared with a more flexible any-bay handover (see Sect. 2), where any available stacking position is a possible intermediate stacking position for a preemptive container processing. Therefore, we also quantify the gap of our optimization approach with handshake area with a previous algorithm from the literature for any-bay handover. Both competitors are benchmarked with our best B&B procedure in Sect. 5.3.

We have executed all tests on an Intel Core i7-4790 CPU with 3.6 GHz and 32 GB of RAM running Windows 7, and all approaches have been implemented in Java 8. All tests in our computational study are based on randomly generated instances, applying the widely accepted data generator of Briskorn et al. (2019) for container yards. According to their definition of widespread real-world block settings, we assume 30 bays and 10 rows. Initially, crane 1 (2) is positioned in bay 0 (30), and the initial trolley positions are in row 1. The time to pick up or drop off a container is \(p=3\) time units.

To obtain different-sized test instances, we vary the number of containers to be processed. They are set to 10, 20, 30, and 40 containers, where we assume an equal share between inbound and outbound containers, i.e., \(|I^i|=|I^o|\) holds for any instance. The storage positions of all containers are randomly drawn with uniform distribution from the complete block, except for the handshake area, where no containers can be stored permanently. Note that we also experimented with other test instances where the probability of the bays decreases the farther they are from the seaside access point. This could, for instance, arise in practical situations if outbound containers have been pre-marshaled into advantageous positions the night before (Lehnfeld & Knust, 2014). However, the optimization results obtained for these deviating bay distributions were not substantially different, so we decided to keep the test design as clear as possible and opted for the most basic way of generating data, i.e., based on a uniform distribution of container bays. For each number of containers, instance generation has been carried out 30 times, so that in total 120 different container sets have been obtained. These instances can be retrieved from the internet by replacing placeholder “INSTID” with the IDs provided in Table 1 within the following URL: instances.​de/​dfg/​loadinstance.​php?​id=​INSTID&​instances=​30.

For further details on the instance generator we refer the reader to Briskorn et al. (2019). Each of the instances is to be processed by the twin cranes with five different positions of the handshake area, i.e., \(b^h \in \{5,10,15,20,25\}\), and in two capacity situations in the handshake area. We distinguish between a low-capacity setting, where the free capacity of each storage position in the handshake area is randomly drawn from \(\{1,2,3\}\), and a high-capacity setting where the capacity is drawn from \(\{3,4,5\}\) (with uniform distribution). In total, we have obtained 1200 instances.

Note that in addition to our B&B procedures, we also developed a time-based MIP model and solved it using CPLEX 12.6 (see Appendix C). During some preliminary testing, the model was clearly outperformed by our algorithmic approaches, and optimal solutions were not obtainable within a time limit of 1 hour even for the smallest test instances. Even when providing the default solver with tight upper bounds, this result did not improve. Thus, we abstain from further benchmarking of our model in the following computational study.

In this paper, we treat crane scheduling in a container block where twin cranes share container processing during seaside workload peaks via a handshake area. We develop three alternative branch and bound approaches to minimize the makespan of container processing. One of them in particular is shown to deliver either optimal solutions for instances up to 40 container moves if enough computational time is available, or near-optimal solutions if less time is at hand. This paper is the first to derive optimal solution approaches for a handshake setting, which allows us to derive the following take-home messages from our computational study:The main challenge we see for future research is a systematic comparison of all kinds of workload sharing in container blocks. In Sect. 2, we elaborate the four basic kinds of workload sharing, i.e., front evasion, cross-over cranes, any-bay handover, and handshake area. For each of these organizational approaches, different exact and heuristic solution algorithms have been introduced in the literature, and some of these procedures have also been compared with one or two alternatives of workload sharing. A systematic comparison with exact methods (to exclude heuristic gaps) and with state-of-the-art heuristics (whenever computational results have to be obtained quickly) of all kinds of workload sharing on a unique dataset is still lacking. Such a benchmark test would provide great practical decision support for port managers having to set up their container yards for a competitive processing of today’s mega vessels.

Another viable direction for future research is to extend our research in order to use a dedicated handshake area in a more flexible manner. Specifically, we see four opportunities to do so:Each of these four opportunities promises an improvement in container handling efficiency but adds much complexity to the solution process. Thus, a handshake area remains a challenging field for the port operations community in the foreseeable future.