1 Introduction

The marine container industry has grown dramatically in the last three decades, and container transportation has become a predominant mode of inter-continental cargo traffic. Container terminals, which are multi-modal inter-faces that connect sea transportation with land transport, which plays an important role. To exploit economies of scale, the size of container ships has significantly increased during the last few decades. A large container ship typically re-quires the lifting of thousands of containers at the terminal during one call. Since running a container ship involves a major capital investment and significant daily operating costs, customer service has become the principal issue at container terminals. More and more container terminals are seeking to improve their throughput and reduce the turnaround time of vessels. With containerization increasing, the number of container terminals has increased substantially and stiff competition has developed grown among terminals.

As one of the busiest container ports in the world, the Shanghai Port has handled more than 162 million twenty-foot equivalent units (TEUs) in the past five years, making it the port with the highest total throughput in the world since 2010. In 2015, the Port of Shanghai handled an unprecedented 35.2 million TEUs, and it is expected to handle even more in 2016.

Table 1 Estimated operational capacity of Shanghai Port
Full size table

As shown in Table 1, based on current resource allocation strategy and handling technique, the designed capacity of Shanghai Port is approximately 33 million TEU. Actual container throughput at Shanghai Port exceeded this designed capacity by 3.2% in 2015, and this capacity gap will continue to increase with the number of handled containers. Efforts should be made to improve container through-put by expanding the port or optimizing its operation. Most ports generally prefer operating optimization because construction to expand a port requires huge investment and takes a long time.

Fig. 1
figure 1

Typical work flow at container terminal

Full size image

The typical work flow during a loading operation for container departure that are retrieved from the yard and loaded to a vessel (YV), is as follows. One yard crane (YC) picks up a container from a container block and loads it onto internal truck internal truck (YT). The YT then transports the container to a QC (quay crane), which loads the container onto the vessel. The unloading operation for arrival containers is the reverse of the foregoing: a container is unloaded from a vessel to the yard (VY). Minimizing vessel handling time is often a high priority for the quay cranes (QCs), which transship the containers between the vessels with terminal quay area. One method for increasing the productivity of QCs involves dual-cycle operations, which comprise both unloading and loading operations in one operation cycle. However, the QCs at most container terminals adopt the single cycle method, by which a QC performs all loading activities after all of its unloading activities have been finished. This single-cycle method provides lower QC productivity than the dual cycling model Fig. 1 since the moving of empty is unproductive.

Fig. 2
figure 2

Tandem lift QC

Full size image
Table 2 Tandem lift usage in December 2014 at SSICT
Full size table

The tandem lift quay crane effectively improves the efficiency of QC operations. A Tandem Lift is an extension of the twin lift, which can lift two 20\(^{\prime }\) containers end to end. The Tandem Lift quay crane can lift two 40\(^{\prime }\) containers or two pairs of twin lift containers side by side, as presented in Fig. 2. Following technological transformation, which takes some time, Tandem Lift crane can also lift a single 40\(^{\prime }\). Meanwhile, the pair of Tandem Lift containers combined by validating the position of selected containers in the vessel which must be in adjacent slots in the same tier and checking the weight of two containers of each pair of Tandem Lift, slot and tier denote the relative storage position of vessel as shown in Fig. 6. Both of the aforementioned methods improve the operational efficiency of a QC by reducing the number of working cycles of the QC. Theoretically, the Tandem Lift system can double the operating efficiency of a QC.

The tandem lift increases the complexity of determination of the container sequencing in the bay of a vessel. For example, Shanghai Shengdong International Container Terminal (SSICT) has already equipped its QCs with the Tandem Lift system, but only 11% of QC operations were Tandem Lift in December 2014, and those Tandem Lift operations improved efficiency by only approximately 30 percent, from 30.44 containers/hour (CPH) to 47.08 containers /hour, as indicated in Table 2.

The above results have the following causes. Firstly, minimizing the service time of a quay crane with a different lifting approach depends on the reasonable operating container sequence and manually determining the optimal sequence of operations of a Tandem Lift QC is extremely difficult/hard/complex. Secondly, converting QC lift technology from single lift to Tandem Lift may take a long time, and a poor container sequence solution may increase lift conversion frequency. Finally, container pairs for Tandem Lifting are limited by such factors as weight class, height, slot in vessel bay. /Hence, the container sequence has a strong impact on the utilization of Tandem-Lifted. Tandem Lift also requires the simultaneous quayside arrival of two trucks, potentially increasing the waiting time of the QC and reducing operating efficiency. This study proposes a two-stage model for container sequencing with Tandem Lift. The goal is to minimize the total time required to perform the container transshipments at the vessel bay. Only a single bay is considered, because terminal operators avoid frequent repositioning of the slow-moving cranes by requiring QCs to process one bay completely before moving to the next.

2 Literature review

In this section, we introduce some quay crane scheduling problems under different circumstances in container terminals and then briefly describe related methods proposed to solve these problems.

To improve practical QC scheduling in terms of assumed time windows during which QCs are assigned to a vessel. Kim and Park [1] developed an effective heuristic search algorithm, called greedy randomized adaptive search procedure (GRASP). GRASP successfully eliminate the computational difficulty of the previously branch and bound method. Subsequently, the interference among QCs was taken in to consider. Lee et al. [2] proposed a genetic algorithm (GA) to optimize the handling sequence for QCs with this premise.

Stahlbock and Voß [3] emphasized that the operation plans in container terminals should be indispensably optimized. They studied various container terminal (CT) operation planning problems, Although the container sequence problem (CSP) has not yet been addressed directly, key related issues, such as crane operations planning, dual cycling, and container reshuffling, have been investigated in the context of stowage planning, yard crane scheduling, and QC scheduling. Zhu and Lim [4] took the non-crossing constraint into consider when arranging the QC scheduling plan. Liu et al. [5] also investigated the quay crane scheduling problem. They aimed to minimize the maximum relative tardiness of vessel departures.

Goodchild and Daganzo [6] firstly incorporated crane dual cycling issues into QC scheduling. Their approach concerns the operating process of a single QC at a bay of a container vessel. Every container stack in the considered bay is represented by two tasks that are related by precedence, the first of which is unloading the stack and the other of which is loading the stack. The processing time of these task are determined by the number of containers to be (un-)loaded. Crane dual cycling is realized by the parallelization of unloading and loading of different stacks. The purpose is to find a sequence for processing stacks that minimizes the make span of the schedule while maximizing crane dual cycling. Hence, this problem is formulated as a two-machine flow shop scheduling problem, which is solved exactly using the rule of Johnson (1954). Goodchild and Daganzo [7] proved the economic benefits of the QC dual cycling, which are increased crane productivity, berth utilization, and vessel utilization. Zhang and Kim [8] extended the approach of Goodchild and Daganzo by considering the effect of hatch covers on QC operations including local search to solve stack-based QC scheduling incorporates dual cycling. Frank and Matthias [9] proved the consideration of internal reshuffles shortens vessel handling time more than crane dual-cycling alone. Zhen [10] studies two tactical level decision problems arising in transshipment hubs: berth template planning that is concerned with allocating berths and quay cranes to arriving vessels, and yard template planning that is concerned with assigning yard storage locations to vessels. Chen [11] studied the interactions between crane handling and yard truck transportation in a maritime container terminal by considering them as simultaneous. They formulated the problem as a constraint programming model and developed a three-stage algorithm. Kaveshgar and Huynh [12] developed a mixed integer programming model for scheduling quay cranes and internal trucks jointly considering precedence relationships between containers, blocking, quay crane interference, and quay crane safety margin. This model solved the integrated optimization model with a genetic algorithm combined with a greedy algorithm. Delavar and Aryan [13] proposed a hybrid heuristic method (HSGA) to find a suitable scheduling for workflow graph, based on genetic algorithm to obtain the response quickly moreover optimizes makespan, load balancing on resources and speedup ratio.

About quay crane scheduling problems, Stahlbock and Voß [3] and Bierwirth and Meisel [14, 15] have an overview on applications and optimization models. Other studies integrated with berth allocation management [16,17,18,19,20].

This paper proposes a two-stage Tandem Lift container sequence model, in which containers are paired for Tandem Lifting containers in a manner that satisfies the relevant processing constraints. Container sequences are optimized to reduce the make-span service time of QCs in each vessel bay. The container sequence problem, as complex stack sequencing problem, becomes more difficult to solve as the number of container increases. Therefore, a two-level heuristic algorithm is developed for obtaining the optimal container sequence and the pairs of Tandem lift within feasible time. Accordingly, a decision support system (DSS), called the Tandem Lift Container Sequence System (TLCSS), that automatically generates container sequences with Tandem Lift is developed and implemented at SSICT in Shanghai Yangshan Port.

3 Problem description

In the Tandem Lift CSP, an arrival configuration and a departure configuration of containers in each bay are given. The problem is to find a sequence of container moves that converts the arrival configuration into the departure configuration in the shortest possible service time of the bay, each small square denote one container and these containers are positioned by units of bay, slot, tier, as presented in Fig. 3.The service time of the bay is defined as the total time to perform the required container moves and the empty crane moves, taking into account time required to shift switch between Single Lift and Tandem Lift. A solution to the problem must respect the stacking-dependent accessibility of the containers. The two most important types of container move that can be performed by QC are denoted as VY and YV.

Each QC action is called a move. One move of a single cycling can be a VY or an YV operation which must make an“empty move” before the next move. However, in dual cycling, VY and YV moves are successively made without an empty move in between. The two types of dual cycle are YV followed by VY or VY followed by YV, which have different transfer times. VY to YV requires more waiting by the internal trucks than YV to VY, because dual cycling from VY to YV requires two (pair of) trucks, whereas YV to VY requires only one (pair). The situation is the same when Tandem Lifts are used, except that double the number of containers are loaded and unloaded per move.

To evaluate a container move sequence based on the resulting service time of the bay, the time to move the containers, the number of empty lift moves and the time to transform lift technology must input to solve the Tandem Lift CSP. To simplify the formulation of the CSP, the slot-specific container move perform time is neglected. Rather, the time to processing a container move is assumed to depend merely on the type of the move. A rough estimate of processing time can be derived by assuming that a QC makes around 30 moves per hour, which value is typical nowadays. So Each VY and each YV operation are assumed to take 90 and 110 s, respectively (including lifting, moving, and loading). YV involves waiting for a truck with a specific container, as determined by the loading sequence, which increases potential waiting time for the trucks. A move of an empty crane lift is assumed to take 60s. The time required for an empty crane lift move between two consecutive container moves depends on whether dual cycling is being performed. The time to transform between a Tandem Lift and a Single Lift is long, averaging approximately 300 s. Table 3 presents estimated processing times for container moves and empty crane lift moves. Section 5 presents more accurate times that are estimated from historical operating data from the DSS.

Fig. 3
figure 3

Configuration diagram of vessels

Full size image
Table 3 Time to empty crane lift movement and lift transform (s)
Full size table

4 Formulations

4.1 Fundamental assumptions

  1. A1.

    We have rewrite the A1(assumption 1) to add more details. The number of QC cycles is used as a unit for the time required by a QC to complete all loading or unloading operations in a vessel-bay. Fewer cycles correspond to a shorter operation time, or faster service: if one container is unloaded and one is loaded by a tandem spreader in one dual-cycle, then the number of cycles is one with both loading or unloading in one cycle; otherwise, if these operations are conducted separately, then the number of cycles is two, one cycle for loading and the other one for unloading, as shown in Fig. 1.

  2. A2.

    The operations of the QCs are the bottleneck during vessel loading and unloading process, so the throughput rate of QCs determines the throughput rate of the integrated handling system that is composed of QCs, transporters, and yard cranes. The waiting by QCs for (internal trucks) is ignored, so (internal trucks) are always immediately available to a QC.

  3. A3.

    The times to perform an operation vary negligibly among containers.

  4. A4.

    The sizes of all containers are approximately equal the total size of two 20ft containers equals that of one 40ft container.

  5. A5.

    The type of operation conducted on all containers are approximately the same in the tandem lift containers combination model, which means all containers are either loaded (YV) or unloaded (VY).

  6. A6.

    The operation sequence of each container is pre-decided before tandem lift containers combination model. The operate order could be decided by experiences such as unloading containers from landside to quayside and loading from opposite direction.

Indices

I:

Set of containers

K:

Set of maximum tandem lift container pairs

Parameters

\(d_{ij} \) :

Distance between container i and container j

D :

Positive integer, equals 1. The maximum distance between two containers with Tandem-Lifted

\({w}_{{ij}}\) :

The difference of the weights of container i and container j

W :

The maximum difference of the weights of two containers of Tandem Lift pair.

n :

The minimum sequential number of Tandem Lift container pairs combined

Q :

Number of containers

\({q}_{i}\) :

The loading or unloading sequence number (LUN) of container i

\({t}_{s}\) :

The handling time of a single lift

\({t}_{{t}} \) :

The handling time of a Tandem Lift

Decision values

$$\begin{aligned} \begin{array}{ll} {x}_{{ijk}} &{} \text {Binary, equals to 1 if container} i \text {and container} j \text {are}\\ &{}\text {combined by tandem lift, 0 otherwise} \\ {y}_{{ijk}}&{} \text {Binary, equals to 1 if container} i \,\text {and container} j \text {are}\\ &{} \text {combined with other containers, but they are}\\ &{} \text {in a same sequential tandem lift operation sequence,}\\ &{}\text {0 otherwise} \\ {z}_{{i}} &{} \text {Binary, equals to 1 if container} i \text {is combined by tandem}\\ &{}\text {lift, 0 otherwise}\\ \end{array} \end{aligned}$$

Objective function

$$\begin{aligned} min \left\{ {t_{s} Q+\left( {\frac{t_{t} }{2}-t_{s} } \right) \sum _{i=0}^Q {z_{i} } } \right\} \end{aligned}$$
(1)

The objective function is to minimize the sum of the handling times of both single-lifted and Tandem-Lifted containers.

Subject to

$$\begin{aligned} {x}_{ij} =x_{ji} ,\forall i,j\in I \end{aligned}$$
(2)
$$\begin{aligned} \sum _{i=0}^Q {\left| {\text {q}_{i} -q_{j} } \right| } x_{ij} \le 1,\forall j\in I \end{aligned}$$
(3)
$$\begin{aligned} \sum _{{i}={0}}^{{Q}} {{d}_{{ij}} } {x}_{ij} \le D,\forall j\in I \end{aligned}$$
(4)
$$\begin{aligned} \sum _{{i}={0}}^{{Q}} {{w}_{{ij}} } {x}_{ij} \le D,\forall j\in I \end{aligned}$$
(5)
$$\begin{aligned} \sum _{{j}={0}}^{{Q}} {{x}_{ij} } \le z_{i} ,\forall i\in I \end{aligned}$$
(6)
$$\begin{aligned} \sum _{k=min \left( {i,j} \right) }^{max \left( {i,j} \right) } {z_{k} } \ge \left( {\left| {{q}_{i} -q_{j} } \right| +1} \right) {y}_{ij} ,\forall i,j\in I \end{aligned}$$
(7)
$$\begin{aligned} \sum _{{j}={0}}^{{Q}} {{y}_{ij} } \le 2n*z_{i} ,\forall i\in I \end{aligned}$$
(8)
$$\begin{aligned} {x}_{ij} =0,1,\forall i,j\in I \end{aligned}$$
(9)
$$\begin{aligned} {y}_{ij} =0,1,\forall i,j\in I \end{aligned}$$
(10)
$$\begin{aligned} {z}_{i} =0,1,\forall i\in I \end{aligned}$$
(11)

Constraints (2) and (3) ensure that a container is combined with no more than one other container that follows or precedes it in the loading or unloading sequence. Constraint (4) ensures that the distance between two combined containers is less than an upper bound, D. Usually, D equals one. For example, in Fig. 4, the blue container may be combined with C as Tandem Lift pair with the distance restriction, but the red one may not be. Constraint (5) ensures that the difference between the weights of paired containers is less than an upper bound. Constraint (6) ensure that if a container is combined with another, then it is defined as a combined container. Constraint (7) ensures continuous tandem lift handling of containers whose handling on-going between that of container i and that of container j. Constraint (8) ensures that once a tandem lift is used, the QC must perform at least n tandem lift moves without interruption. Constraints (9)–(11) set the binary variables to zero or one.

Fig. 4
figure 4

Example of distance between containers

Full size image

4.2 Fundamental assumptions

Sets

I :

Set of loading containers including tandem lift container pairs which obtain from model I as one container task.

J :

Set of unloading containers including tandem lift container pairs which obtain from model I as one container task.

K :

Set of task sequence orders

H :

Set of loading container pairs (i, j), in which container i and j are located in the same bay slot and the precedence order number of container i is greater than that of container j

G :

Set of unloading container pairs (i, j), in which containeri and j are located in the same bay slot and the precedence order number of container iis greater than that of container j

L :

Set of loading and unloading container pairs (i, j), in which loading container i and unloading container j are located in the same bay slot

Parameters

\({d}_{ij}\) :

The difference distance of the slots of loading container i and unloading container j

\({h}_{i}\) :

The precedence order number of loading container i

\({g}_{j}\) :

The precedence order number of unloading container j

\({t}_{ij}\) :

The handling time of a dual cycling loading container i and unloading container j.

\(t_{l} \) :

A handling time of a loading container.

\({t}_{u} \) :

A handling time of an unloading container.

\({t}_{{s}}\) :

A time in-between query empty lift movement time of single cycle

\({t}_{{d}}\) :

A time in-between query empty lift movement time of dual cycling

N :

Number of loading containers

M :

Number of unloading containers

P :

Maximum moves of query crane

D :

The maximum difference distance of the slots of loading container and unloading container could be combined together as dual cycling.

Decision values

\({x}_{ijk} \) :

Binary, equals to1 if loading container i and unloading container j are combined in one cycle, which is the k cycle in order sequence, 0 otherwise The bit 0 of i and j is the virtual loading and unloading container, that a container combined to which means it will be operated without dual cycling.

Objective function

$$\begin{aligned} \min t_{l} \sum _{k=0}^P {\sum _{j=1}^M {x_{0jk} } } +\sum _{k=0}^P {\sum _{i=1}^M {x_{i0k} } } +\sum _{i=1}^N {\sum _{j=1}^M {t_{ij} } } \sum _{k=0}^P {x_{ijk} } \nonumber \\ +\,\, t_{s} \left( {\sum _{k=0}^P {\sum _{j=1}^M {x_{0jk} } } +\sum _{k=0}^P {\sum _{i=1}^M {x_{i0k} } } } \right) +t_{d} \sum _{k=0}^P {\sum _{j=1}^N {\sum _{i=1}^M {x_{ijk} } } } \nonumber \\ \end{aligned}$$
(12)

The objective function is to minimize the sum of the handling times of all containers and the times between all query crane lift movements.

Subject to

$$\begin{aligned}&\sum _{k=0}^P {\sum _{i=0}^N {{x}_{ijk} } } =1, \forall {j}\in J,j\ne 0 \end{aligned}$$
(13)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{{j}=0}^M {{x}_{ijk} } } =1, \forall {i}\in I,i\ne 0 \end{aligned}$$
(14)
$$\begin{aligned}&\sum _{{k}=0}^P {{x}_{00k} } =0, \forall {k}\in K \end{aligned}$$
(15)
$$\begin{aligned}&\sum _{i=0}^N {\sum _{{j}=0}^M {{x}_{ijk} } } \ge \sum _{i=0}^N {\sum _{{j}=0}^M {{x}_{ijk+1} } } , \forall {k}\in K \end{aligned}$$
(16)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{{j}=1}^M {{d}_{{ij}} {x}_{ijk} } } \le D, \forall {i}\in I,i\ne 0 \end{aligned}$$
(17)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{i=1}^N {{d}_{{ij}} {x}_{ijk} } } \le {D}, \forall {j}\in J,j\ne 0 \end{aligned}$$
(18)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{{j}=0}^M {{kx}_{ijk} } } \le \sum _{k=0}^P {\sum _{{j}=0}^M {{kx}_{qjk} } } ,\nonumber \\&\forall {i,q}\in I,i\ne 0,q\ne 0,\left( {i,q} \right) \in H \end{aligned}$$
(19)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{{i}=0}^{{N}} {{kx}_{ijk} } } \le \sum _{k=0}^P {\sum _{{i}=0}^N {{kx}_{ipk} } } ,\nonumber \\&\forall {j,p}\in J,j\ne 0,p\ne 0,\left( {j,p} \right) \in L \end{aligned}$$
(20)
$$\begin{aligned}&\sum _{k=0}^P {\sum _{{i}=0}^{{N}} {{kx}_{i{p}k} } } \le \sum _{k=0}^P {\sum _{{j}=0}^M {{kx}_{qjk} } } ,\nonumber \\&\forall {q}\in {I,q}\ne {0,p}\in J,j\ne 0,p\ne 0,\left( {p,q} \right) \in L \end{aligned}$$
(21)
$$\begin{aligned}&\sum _{i=0}^N {\sum _{{j}=0}^M {{x}_{ijk} } } \le 1,\forall {k}\in K \end{aligned}$$
(22)
$$\begin{aligned}&{x}_{ijk} =0,1,\forall {i}\in I,\forall {j}\in J,\forall {k}\in K \end{aligned}$$
(23)

Constraints (13) and (14) ensure that each loaded and unloaded container is handled exactly once. Constraint (15) ensures that each virtual loaded or unloaded container is not combined with another virtual container. Constraint (16) ensures that no interrupt should exist in the middle of the tasks sequence. Constraints (17) and (18) ensure that the difference between two combined containers’ slot number is less than an upper bound. Constraints (19) and (20) ensure that the handling of all containers is consistent with their physical positions. Constraint (21) ensures that the loading and unloading of containers in a single bay slot follows First Unloaded, Then Loaded (FUTL) rule. Constraint (22) ensures that each cycle of each query crane should perform either a single container task or two du-al-cycling container tasks. Constraint (23) sets binary variables to one or zero.

CHS model provides the handling sequence of all containers. An iterative search is required because the output of the Model I might cut some better solution of model II. The following section proposes a two-level metaheuristic method for finding the optimal solution, which is designed according to the features of the Tandem Lift CSP, and this method forms the basis of an algorithm for the DSS system.

5 Heuristic approach to tandem lift CSP

The two-stage model is a master-slave model, in which parameters are transferred from master to the slave to obtain the optimal objective function value by slave stage. Finding the optimal solution is difficult owing to the complexity of the two-stage programming model. Therefore, a two-level heuristic approach for finding sub-optimal solutions within a short computational time is proposed, and then a DSS for the Tandem Lift CSP is developed based on this two-level heuristic, as described in Sect. 6.

Fig. 5
figure 5

Flow chart of the two-level heuristic

Full size image

5.1 Framework of two-level heuristic

The proposed heuristic for solving the Tandem Lift CSP is hierarchical, as shown by the heuristic flowchart in Fig. 5. The heuristic comprises two levels. Level 1 yields pairs of Tandem Lifting containers in a vessel bay. In this level, a neighborhood search technique is utilized to improve solutions throughout the search. Linear programming relaxation is performed to solve the Container handling sequence (Model 2) problem to evaluate efficiently the fitness of the solutions. At the end of level 1, a good Tandem Lift Containers Combination solution is output and passed into level 2. The obtained pairs of Tandem Lifting containers are input and a detailed container handling sequence is deter-mined in level 2. The sub-problem of Level 2 is a scheduling problem with precedence constraints whose processing time is affected by scheduling sequence [21]. A Tabu search-based heuristic method is proposed herein to find a good solution to the Tandem Lift CSP and the total cost of moving containers in a vessel bay is obtained.

5.2 Level-1 of heuristic

This Level begins with an initial container handling sequence that is obtained before making a pairs of Tandem Lifting containers solution. In the absence of dual cycling, the operator of a container terminal chooses a simple sequence in which to unload all import containers from the landside to the quayside slot by slot and then to load all export containers in the opposite direction, as presented in Fig. 6. Each container may be combined with two adjacent containers without consideration of the weight of each container, so the number of combinations of containers for Tandem Lifting is high.

Fig. 6
figure 6

Initial container handling sequence

Full size image

Basing on the simple initial container handling sequence, a set of feasible initial solutions to the Tandem Lift container combination problem is randomly generated including both an arrival configuration and a departure configuration for a vessel bay. The following straightforward encoding representation of the Tandem Lift Container combination problem is utilized herein. Let (\(t_{1} ,t_{2} ,\ldots ,t_{i} )\) represent chosen containers to be combined with container i where component \(t_{i}\) is denotes the container that is combined with container \(i\in Q\); \(t_{i} = \)1 or 2 specifies that container i is combined with the container to its left or right; \(t_{i} =\) 0 indicates no combination.

For example, \(T=\) (2,1,0,0,2,1,2,1,0) is a combination of nine containers, as presented in Fig. 6. In this solution, container 1 is combined with container 2 in a Tandem Lift task. The other two Tandem Lift container pairs are (5, 6) and (7, 8). Containers 3, 4 and 9 with values of 0 are not combined with any other container, and so cannot be Tandem Lifted.

Two neighborhood structures are utilized in the neighborhood search process, as displayed in Fig. 7; they are the pair-wise interchange and flipping patterns. In Pattern 1, two components of the solution are randomly selected and interchanged with each other. Pattern 2 only operations on one component. The value of this component is randomly generated and the component \(t_{i} \) randomly flipped to {0, 1, 2}. It is essential to adjust the relevant components to make the neighborhood reasonable in both Pattern 1 and Pattern 2. As presented by Fig. 7. Two patterns of neighborhood search are implemented with equal probability.

Fig. 7
figure 7

Two patterns of neighborhood search

Full size image

In the next step, sets I and J which respectively are loading and unloading containers including pairs of Tandem Lift Containers as operating tasks, obtained from level 1 of the heuristic. The overall optimization of Two-stage model is unfeasibly difficult, if dual cycling in Model 2 is taken into account in Model 1. To evaluate the combination of containers solution for Tandem Lifting, the linear programming relaxation is used by replacing the binary constraint in model 2 with a weaker constraint which belongs to the interval [0, 1]. The relaxed linear program of the remaining Container Handing Sequence problem (model 2) is as follows.

$$\begin{aligned} min \left( {12} \right) +F\left( {x_{ij} } \right) \end{aligned}$$
(24)
$$\begin{aligned} {S}t.\left( {13} \right) -\left( {23} \right) \end{aligned}$$
$$\begin{aligned} x_{ijo} \in \left[ {0, 1} \right] \end{aligned}$$

\(x_{ij}\) denotes the combination of containers for Tandem Lifting that is obtained using Model 1. If \(x_{ij}\) violates constraints (2)–(11) in model 1, then a penalty function is added to the fitness function. The objective function (12) and the penalty function \(F(x_{ij})\) yield the fitness function in the level-1 heuristic. The linear programming relaxation of model 2 indicates a possible lower bound on the processing time of Tandem Lift CSP problem based on a given combination solution of containers for Tandem Lifting.

The neighborhood search that is performed in solving the Tandem Lift container combination problem in Level 1, is terminated when the best solution does not change with a specified number of consecutive iterations. then the solution of Tandem Lifting or not for each container are transfer to Level-2 heuristic as input data.

5.3 Level-2 of heuristic

The Tandem Lift CSP is a deterministic single machine scheduling problem [14] in which the total processing time \({C}_{\min } \) is minimized considering container stacking precedence \({p}_{ij} \), which is determined by the stacking configuration, as presented in Fig. (3). The total processing time \({r}_{ij} \) is influenced by the scheduling sequence and consists of three parts, the processing time for container moves \({t}_{j}\), the empty crane movement \(time \cdot {t}_{ij} \), and the time to transform the Tandem Lift \(l_{ij}\).

$$\begin{aligned} {r}_{ij} =t_{j} +t_{ij} +l_{ij} \end{aligned}$$
(25)

Each i,j pair indicates a movement of a container or a pair of Tandem Lift containers (load or unload). The time to process container move \({t}_{j} \) is determined by the type of operation, and \(t_{ij} +l_{ij} \) depends on the container handling sequence; the objective is to minimize the total \(t_{ij} +l_{ij} \) for each vessel bay.

Above the hatch, no export containers can be loaded before all the import containers are unloaded, so dual cycling is not considered. Without dual cycling, the simple container sequence is obtained by the level-1 heuristic.

The Tandem Lift CSP below the hatch can be represented in very elegantly as a directed graph. Consider a directed graph G with a set of nodes \({N}'\) and two sets of arcs A and B; the nodes \({N}'\) correspond to all operations (\(i \quad {slot}_{{i}} )\) that must be performed on the \({M}\cup N\) loaded and unloaded containers, where i, and \({slot}_{{i}} \) is the slot number. The solid arcs A represent the routes of relative priorities for all containers. If A includes arc (i, \({slot}_{{i}} )\rightarrow \)(j, \({slot}_{{j}} )\), then container i must be processed in \({slot}_{{i}}\) before container j. If two containers are combined for Tandem Lifting, then they must be processed simultaneously after all preceding containers have been completed. Arc B indicates the container sequence of containers, which includes two types of container move (YV or VY). So the Arcs B could be represented both dual cycling operations and the Tandem Lift dual cycling operations.

This directed graph is denoted as G \(=\) (N\(^{\prime }\), A, B), and displayed in Fig. 8). A feasible sequence involves a selection of arcs B from which a directed graph is constructed such that relative priorities represented as arcs A are not broken. The minimization of the make-span of a feasible sequence is reduced to finding a selection of arcs B that is the shortest path in G (B) from the source U to the sink V. This shortest path comprises a set of arcs B of which the first begins at time 0 and the last finishes after the period of the make-span.

In level-2 of heuristic, Tabu-Search, which is used to find a better feasible sequence of Tandem Lift CSP. The Tabu-Search begins with an initial solution, which may be generated arbitrarily, and tries to improve upon the current solution. Tabu-search moves from one sequence of the Tandem Lift CSP to another for a potential candidate such that the next sequence may be worse than the one before. In all stages of the process, a Tabu-list of mutations, which the procedure is not allowed to make, is kept.

Fig. 8
figure 8

Directed graph represents tandem lift CSP

Full size image

The initial solution could be generated constructed by extending a partial solution to the tandem lift CSP. Moves that could feasibly extend the current partial solution are identified and stored in a so-called candidate list (CL). Initially, when the partial solution is empty, CL includes un-loading moves for import containers that are located on top of slots in the arrival configuration and moves for loading export containers into empty slots. More precisely, a move for unloading a container is added to CL as soon as all containers on top of this container in the arrival configuration have been removed. A move for loading a container is added to CL as soon as all containers that are stacked below this container in the departure configuration have been loaded. Since slots cannot begin to load before its unloading is completed, frequent switching among slots to unload slows service. Therefore, if the QC has begun to unload from a slot, then the unloading of containers from other slots will be postponed by eliminating the corresponding moves from CL, but the moves for loading containers will be added to the CL to increase the probability of dual cy-cling. As soon as the slot has been completely unloaded, all unloading moves are again added to CL, enabling the selection of a new slot form which a container can be unloaded. Based on the CL, the initial solution is gradually constructed step by step by adding one container at a time, taken at random from CL.

Fig. 9
figure 9

Framework of the TLCSS

Full size image

High-quality solutions to a Tandem Lift CSP include a high proportion of crane dual cycles for loading and un-loading containers, including Tandem Lift dual cycles, and they minimize the make-span without violating the feasibility of the relative priorities that were defined by arcs A. Therefore, heuristic solutions may be improved by shifting one container move to another sequence position, which is limited by the containers stacked above and below the considered container. The improvement procedure examines the shift-neighborhood of a given solution by considering the moves in the sequence solution one by one. The overall procedure of the Tabu-Search algorithm for solving the Tandem Lift CSP is as follows.

  1. Step 1.

    Input directed graph G \(=\) (N\(^\prime \), A, B) for a vessel bay where B is empty.

    Set k \(=\) 1.

    Select an initial sequence B\(_{\mathrm {1}}\) at random from a list of candidates, one item at a time.

    Set B \(=\) B1.

  2. Step 2.

    Select a candidate sequence \({B}_{c} \) from the shift-neighborhood of Bk without violating constraints of arcs A.

    If the shift B\(_{\mathrm {k}} \quad \rightarrow \) B\(_{\mathrm {c}}\) is prohibited by a mutation in the Tabu-list,

    Then set B\(_{\mathrm {k}}+\)1 \(=\) Bk and go to Step 3.

    If the shift B\(_{\mathrm {k}} \quad \rightarrow \)B\(_{\mathrm {c}}\) is not prohibited by any mutation in the Tabu-list,

    Then set B\(_{\mathrm {k+1}} \quad =\) B\(_{\mathrm {c}}\) and Add reverse mutation to the top of the Tabu-list. Push all other entries in the Tabu-list one position down and

    Delete the entry at the bottom of the Tabu-list.

    If G (B\(_{\mathrm {c}}\)) < G (B),

    set B \(=\) B\(_{\mathrm {c}}\);

    Go to Step 3.

  3. Step 3.

    Increase k by 1.

    If k \(=\) N, then STOP and return B as Tandem Lift CSP solution.

    Otherwise go to Step 2.

6 Decision support system

To support practical Tandem Lift container sequencing for a QC, a DSS, called a tandem lift container sequence system (TLCSS) whose embedded kernel is above two-level heuristic algorithm, is implemented to yield the optimal solution; it can be rapidly adjusted to suit operational requirements.

Shanghai container terminals have a modular terminal operating information system (TOS) that provides a full range of functions in support of the planning and control operations. The TOS is directly connected to the operational database (ODB) and provides information required for the management of the operations department.

Fig. 9 shows the integrated framework of the TLCSS and the data flows among the module components. All the input data for the optimizer are taken from two data-bases-the ODB and the historical data warehouse. The ODB stores general terminal configurations (the number of available QCs, their attributes, the length of the quay and others), operations data information concerning operating containers, arrival configuration, departure configuration, vessel structure, and so on, which are filtered and organized in the TOS modules to be input to the optimizer, and the parameters of the algorithm (weight and height settings for Tandem Lift, and so on). Historical operational data are extracted from the ODB and transferred to the data ware-house periodically (nightly) by ETL tool. These historical data are analyzed by using a statistical toolkit to generate the QC productivity profiles that are described in Table 2, which are fed to the DSS to generate the QC make-span of the vessel bay and the Tandem Lift container sequencing solution. Before the optimizer is executed, all input data are preprocessed by a preprocessor, which validates and checks these input data. The preprocessor standardizes the data that are required for the developed algorithm and ensures the successful execution of the optimizer.

The TLCSS uses some software architecture with the TOS that is based on the Microsoft.Net framework. Accordingly, without complicated data adapters, the TOS vessel operation modules can easily be obtained the solutions that are generated by the TLCSS and display them on a UI with which the operator is familiar. Hence, the operator can conveniently modify and evaluate their Tandem Lift container sequences for loading and unloading operations.

7 Case study

The DSS developed above has been implemented at Shanghai Shengdong International Container Terminal (SSICT) which is the largest container terminal in the Shanghai port, through which pass import, export and transshipment (domestic and international) containers, as displayed in Fig. 10. SSICT is part of the Yangshan Deep-water Port (YDP), which is located on the Yang-Shan Island to the southeast of Shanghai. It has 34 quay cranes (QCs), has a 3000 m-long straight-lined quay, and a container yard with an area of 15 hectares. Every month, these resources serve more than 550 deep-sea and feeder vessels, yielding an average throughput of 0.45 million TEUs. This case study demonstrates the effect of the DSS on container terminal operations at SSICT.

Fig. 10
figure 10

Shanghai Shengdong International Container Terminal (SSICT)

Full size image
Fig. 11
figure 11

Tandem lift container sequencing for a vessel bay

Full size image

7.1 Tandem Lift CSP for a vessel bay

In Fig. 11, 127 containers are under the hatch cover of one vessel bay (THALASSA AXIA), containing 68% import containers and 32% export containers. A heuristic solution to the Tandem Lift CSP is obtained from the two-level heuristic in the TLCSS, yielding a make-span of 164.2 min (9854 s). The number of node in the solution simply indicates the sequence of moves for a particular bay, that containers of each Tandem Lifting pair have some number of sequence. The solution to the Tandem Lift CSP could be evaluated in terms of various indicators, including the dual cycling ratio (DCR), the Tandem Lift ratio (TLR), the Tandem Lift dual cycling ratio (TLDCR), the make-span time (MT) and the QC efficiency (QCE) which are 51, 88, and 50% and 164.2 min, 47 containers/hour, respectively, in this instance. The DCR include TLDCR and normal dual cycling operation without Tandem Lift, the higher TLR, TLDCR, DCR cause the higher QCE and lower MT. The two-level heuristic algorithm has a strong tendency to increase the dual cycling ratio and the Tandem Lift ratio. The computational time of the two-level heuristic algorithm on an application server with a Xeon E5 2600 CPU and 32 GB DDR of memory is around 23s in this case.

7.2 Performance of TLCSS in solving tandem lift CSP

To prove the effectiveness of the two-level heuristic implemented in the TLCSS system, the operational data concerning 136 vessel bays in ten vessels are collected from SSICT. The sizes of the vessel bays range from 10 to 24 slots. These instances are distinguished by their proportions of import and export containers in the arrival and departure configurations, which drastically affect the up-per bound on the dual cycling ratio. Hence, an indicator of the number of import containers to the number of export containers (IER) is proposed, which increases the probability of dual cycling when reaches a proportion of 1:1. The quality of solutions that are obtained using the heuristic algorithm in the TLCSS system is evaluated in terms of the relative error (RE) of the ratio of the objective function value Z to the lower bound ZCPLEX, where RE \(=\) (Z -ZCPLEX)/ ZCPLEX\(\times \)100. ARE represents the average relative error (RE) of all bays in one vessel.

The use of multithread technology for parallel computing enables solutions to the Tandem Lift CSP for all bays in each vessel to be obtained almost simultaneously. The results of this application are summarized in Table 4.

One-hundred and thirty-six Tandem Lift CSPs that involved ten vessels in Table 4 were solved using both CPLEX and the developed two-level heuristic. Fig. 12. shows the computational times in all instances. The computational time of the CPLEX increased rapidly with the total number of handled containers. However, the two-level heuristic approach yielded the sub-optimal solutions with-in reasonable time. The range of ARE was from 0.89 to 1.97% for different size of vessels. The CPU time was less than 30s. These results reveal that two-level heuristic in the TLCSS generates solutions of high quality and is effective for instances of various vessel’s sizes. The developed two-level heuristic approach yields sub-optimal solutions within a relatively short computational time, and the heuristic algorithm was not overly sensitive to the size of the problem, so it can be applied to solve the Tandem Lift CSP for even larger vessels.

Table 4 Time to empty crane lift movement and lift transform (s)
Full size table

To provide insight into the structure of the solutions that were obtained by the two-level heuristic, Table 4 presents several performance measures for instances of various sizes and workloads. The reported double cycling ratio TLDCR is the number of Tandem Lift loading and unloading moves that are performed in dual cycling divided by the total number of loading and unloading moves. The average IER, TLR, DCR and TLDCR were 0.67, 28.81, 49.25, and 11.14%, respectively.

The benefit of Tandem Lift technology in QCs operation is obvious, and the balanced numbers of import and export containers enabled high-frequency dual cycling in the handling of containers. The QCE reaches 58.39 containers/h; the average QCE equals to 44.71 containers/hour, and has the potential to be further improved. This result demonstrates that the proposed approach can greatly increases the QCE in terminals. Also, as the total number of containers increases (for unloading and loading), the operational efficiency can be improved by reducing the total number of cycles of QC operations with dual cycling. However, thus improvement depends on a balance between the numbers of import and export containers. Unbalanced IER or vessel stowage con-figuration that ignores the possibility of combining containers for Tandem Lifting reduce the utilization ratio of the Tandem Lift and dual cycling, lowering the efficiency of QC operations. We recommend that shipping companies and terminals increase the probability of using Tandem Lift and dual cycling by implementing with the vessel stowage configuration and tandem lift container sequence cooperatively that enable even faster vessel loading and unloading at container terminals.

Fig. 12
figure 12

The computational time for different number of handing containers

Full size image

8 Conclusions

Container terminals are equipped with tandem lift QCs for the efficient servicing container vessels. A two-stage mathematical optimization model was formulated for solving the tandem lift problem, which reduces the make-span of vessel bays by combining containers for Tandem Lifting and the dual cycling operating containers. Since the model is too complex to be solved optimally analytically, a two-level heuristic algorithm is proposed. A case study of a large set of real vessel’s instances is presented to demonstrate the effectiveness of the developed approach, based on a DSS system, called TLCSS. The results reveal that, on average, approximately 49.25% of loading and unloading operations can be performed in dual cycles (DCR) and that 28.81% of containers in vessel bays can be combined in Tandem Lift pairs (TLR), with 11.14% Tandem Lift dual cycles (TLDCR). The peak efficiency of QC is 58.39 containers/hour, and the mean QCE is 44.71 containers/hour, with room for improvement.

Future works should consider QC operation assignment under uncertainty [11] with the optimization of the integration of the QCs and yard machines to improve the coordination between vessel bay container sequencing and yard operations.