Keywords

Introduction

The container terminal plays a key role in the world trade and transportation industry. It is the link in the container transportation, and is also the container distribution center. Since the energy crisis, environmental protection and automation trends are increasing; the traditional container handling system urgently needs to be improved. Through a large number of studies on the modern container handling system over the world, Shanghai Zhenhua Port Machinery Company Limited (ZPMC) has proposed a new system, which has strong vitality, and is able to improve the core competition of the ports.

In the new container handling system, container yard is the logistic channel that lies between the sea side and the land side. The novel container storage space that connects the two sides is totally different from the scattered yards in the traditional container terminal. Instead of the operation of transport vehicles in the traditional terminal, a dispatching system similar to the inbound and outbound system of the automated stereoscopic warehouse is used.

The dispatching system consists of Dispatching Vehicle (DV) whose rail is parallel to quayside, Shuttle Vehicle (SV) whose rail is through the block and vertical to quayside, and Lifting Crane (LC) which is responsible for loading or unloading the containers before outbound and inbound. Since the handling equipment in the system are all running on the rail, they can move in a high speed and under a strong controllability. Then it is possible that the operations in the new container terminal can run automatically and more effectively (Fig. 43.1).

Fig. 43.1
figure 1

A new container terminal

Full size image

The storage space allocation problem (SSAP) has been first formulated by Zhang et al. (2003). They use a rolling horizon approach to solve the problem (Zhang et al. 2003). Then, an iterative improvement method proposed by Han et al. (2008) and a genetic algorithm put forward by Bazzazi et al. (2009) are used to resolve the storage space allocation problem, respectively, A hybrid algorithm, which applies heuristic rules and distributed genetic algorithm, is employed to resolve the space allocation model in the article published by Mi et al. (2009).

All the solutions mentioned in these papers are all focused on the traditional container terminal, and the relative approaches can provide some references to solve the problem in the new container terminal. However, there are essentially differences between the previous and the new container terminal operational strategies.

Problem Description

Based on the typical structure of the new container handling system, the processes of unloading containers from the vessels to the container storage space are: QC removes the container from the vessel that is berthing in the certain place to DV. Then with the container, DV which moves along the quayside to the point corresponds to the block of the storage space. LC is at this point to hold the container, and DV leaves for the next operation. Then LC puts down the held container on SV that is placed under the accepted point. SV turns the container 90°, puts the container in the direction that is correct for storage, then SV delivers the container to the point of the bay where it would be placed, and under RMGC. RMGC picks the container up and stacks it into a location in a bay of the block. The reverse flows of the above operations are the loading processes of the container.

According to the container handling processes described above, containers handled in the storage space can be assorted into four categories: Unloading Containers (ULC): Inbound containers that have not yet unloaded from the vessels or into the storage space; Loading Containers (LDC): Outbound containers that have arrived at the storage space waiting for shipment; Dispatching Containers (DPC): Inbound containers that have arrived at the storage space waiting for out; Receiving Containers (RVC): Outbound containers that have not yet brought into or stored in the storage space.

The number of containers can be adopted to judge the types of containers. The container flows in the terminal are caused by the arrival process of vessels. After being placed in the certain block, inbound ULC will convert to DPC, while RVC will change into LDC.

Since four types of containers will be operated at the same time, the loading and unloading containers must be mixed stored in one block. Based on the operation process principles, two LCs (i.e., LCd and LCl) have to use to realize the containers into and out of a block synchronously. So the restrictions on the number of LCs (the total number of LCds and LCls) are the focus in this article, and then it is the new space allocation problem under the limitation of transport channels.

There are many different performance indicators to evaluate the efficiency of the container terminal, such as QC operation time, RMGC operation time, the vessel berthing time, etc. (Kim et al. 2000; Preston and Kozan 2001; Stahlbock and Vob 2008; Steenken et al. 2004; Li et al. 2007). We choose a commonest one, minimize the average vessel berthing time, as the objective.

Problem Solving

The storage yard in the container terminal is a temporary storage space to place containers. It is a buffer to coordinate inbound and outbound containers.

From the perspective of improving the operating efficiency of the storage space, the leaving time has been known when the container arrived at the terminal. So, we use the planning time of containers arrive at the storage space to get the container storage space allocation plans through balancing the workload of RMGCs among different blocks. A fixed planning horizon is chosen. At each planning period, we use the newest information to formulate a plan for the nearest future and implement the schedule until the following planning note, then we re-enact and generate a new plan; this planning pattern is and repeated to satisfy the demand from the port. This planning method known as the rolling-horizon approach and an simple example is shown in Fig. 43.2(Liu et al. 2010).

Fig. 43.2
figure 2

The example of rolling horizon approach

Full size image

Notation

The data known at the beginning of the schedule are: B is the number of blocks in the storage space; T is the number of planning periods in one planning horizon; S i is the storage capacity of block i; NLC is the total number of LCs; η is the allowable density for each block; V i0 is the initial inventory of block i; \( P_{it}^0 \) is the initial number of DPC that are stored in block i and will be took out in period t; \( L_{it}^0 \) is the initial number of LDC that are stored in block i and will be shipment in period t; G tk is the number of RVC that arrive at the container terminal in period t and will shipment in period t + k; D tk is the number of ULC that are loaded from vessels in period t and will be took out in period t + k.

The decision variables are: G itk is the number of RVC stored in block i that reach the terminal in period t and will shipment in period t + k; D itk is the number of ULC stored in block i that are loaded from vessels in period t and will be took out in period t + k; G it is the number of RVC stored in block i that reach the container terminal in period t; D it is the number of ULC stored in block ithat are loaded from vessels during period t; L it is the number of LDC that are stored in block iand will shipment in period t; P it is the number of DPC that are stored in block i and will be took out in period t; V it is the number of containers that are stored in block i at the end of period t; if LCd it is 1, the LC located in block i in period t for descent move, 0 for otherwise; if LCl it is 1, the LC located in block i in period t for ascent move, 0 for otherwise; V max, TPD it and TPL it are the temporary variables for calculation.

Modeling

The Objective Function

As mentioned above, we can balance the workload of RMGCs among different blocks to minimize the berthing time of vessels. Since the operations of RMGC are related to the both side of the container terminal: the seaside for loading or unloading containers from the vessels and the land side for picking up containers from blocks or sending containers to blocks. And we pay more attention on the containers that are related to vessels, thus, the objective is:

$$ \min \sum\limits_{t=1}^T {\left\{ \eqalign{ {\omega_{{_1}}}\left[ {\mathop{{\max \left( {D{}_{it }+{L_{it }}} \right)}}\limits_{{i\in B}}-\mathop{\min}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}} \right)} \right] \hfill \\+{\omega_2}\left[ \eqalign{ \mathop{\max}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}+{G_{it }}+{P_{it }}} \right) \hfill \\-\mathop{\min}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}+G{}_{it }+{P_{it }}} \right) \hfill \\}<!endgathered>\right] \hfill \\}<!endgathered>\right\}} $$
(43.1)

In this function (43.1), (D it  + L it ) is the number of loading and unloading containers that will be handled in block i during period t, and (D it  + L it  + G it  + P it ) is the number of containers that will be handled in block i during period t. Therefore (43.1) balances the containers that are related to vessels and the number of containers among blocks in each planning period. The weights of the two terms in function (43.1), ω 1and ω 2, are tuned according to the actual situation in the container terminal. Both of them are strictly positive.

Constrains

In order to ensure the problem practical feasibility, there are following constraints:

$$ {D_{tk }}=\sum\limits_{i=1}^B {{D_{itk }}} $$
(43.2)
$$ {G_{tk }}=\sum\limits_{i=1}^B {{G_{itk }}} $$
(43.3)
$$ {D_{it }}=\sum\limits_{k=1}^{T-t } {{D_{itk }}} $$
(43.4)
$$ {G_{it }}=\sum\limits_{k=1}^{T-t } {{G_{itk }}} $$
(43.5)
$$ {L_{it }}=L_{it}^0+\sum\limits_{k=1}^{t-1 } {{G_{i(t-k)k }}} $$
(43.6)
$$ {P_{it }}=P_{it}^0+\sum\limits_{k=1}^{t-1 } {{D_{i(t-k)k }}} $$
(43.7)
$$ {V_{it }}={V_{i(t-1) }}+\left[ {\left( {{G_{it }}+{D_{it }}} \right)-\left( {{P_{it }}+{L_{it }}} \right)} \right] $$
(43.8)
$$ {V_{it }}=\eta {S_i} $$
(43.9)
$$ {D_{it }}\le TP{D_{it }} $$
(43.10)
$$ {D_{it }} \geqslant TP{D_{it }}-{V_{\max}} \left({1-LC{d_{it }}}\right) $$
(43.11)
$$ {D_{it }}\le {V_{\max}}LD{d_{it }} $$
(43.12)
$$ {L_{it }}\le TP{L_{it }} $$
(43.13)
$$ {L_{it }}\ge TP{L_{it }}-{V_{\max}}\left( {1-LC{l_{it }}} \right) $$
(43.14)
$$ {L_{it }}\le {V_{\max} }LD{l_{it }} $$
(43.15)
$$ \sum\limits_{i=1}^B {\left( {LC{d_{it }}+LC{l_{it }}} \right)} =NLC $$
(43.16)

Constraint (43.2) ensures the number of ULC waiting for distribution is the sum of the containers that are allocated to all the blocks. Constraint (43.3) implies similar constraint for RVC. Constraint (43.4) ensures that the number of ULC allocated to block i in period t is the sum of the containers assigned to block i that will shipment in period t. Constraint (43.5) implies similar constraint for RVC. Constraint (43.6) shows that the number of LDC containers handled in block i during period t, is the sum of the initial LDC that are stored in block i will shipment in period t in the current plan period and the containers that changed from RVC that are arrived in the current period. Constraint (43.7) implies similar constraint for DPC. Constraint (43.8) describes the container inventory updating. Constraint (43.9) ensures that in each planning period the number of container stored in each block will not exceed the actual available capacity Shen et al. (2007). Constraints (43.10), (43.11), (43.12), (43.13), (43.14), and (43.15) ensure the number of containers that are loading and unloading from the vessels is the sum of inbound and outbound containers in the container terminal. Constraint (43.16) ensures the number of LC is the sum of the number of LCds and LCls.

Conversion to a Linear Model

Because of the objective function, the above model is non-linear. Thus, it cannot be solved by the existing optimization tools. To convert it to a linear model, there are some definitions:

$$ {A_t}=\mathop{\max}\limits_{{i\in B}} \left( {{D_{it }}+{L_{it }}} \right) $$
(43.17)
$$ {B_t}=\mathop{\min}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}} \right) $$
(43.18)
$$ {M_t}=\mathop{\max}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}+{G_{it }}+{P_{it }}} \right) $$
(43.19)
$$ {N_t}=\mathop{\min}\limits_{{i\in B}}\left( {{D_{it }}+{L_{it }}+{G_{it }}+{P_{it }}} \right) $$
(43.20)

Then the model can be rewritten as the linear integer programming (LIP) model below.

$$ \min \sum\limits_{t=1}^T {\left[ {{\omega_1}\left( {{A_t}-{B_t}} \right)+{\omega_2}\left( {{M_t}-N{}_t} \right)} \right]} $$
(43.21)

Modeling Evaluation

The space allocation equality rate (SAER) matrix C = [C 1, C 2,…, C T ] is used to evaluate the model. C t is the SAER in period t. B it is the number of containers that are allocated to block i in period t. When C t is more closer to 1, the allocation in period t is more balanced. It means that when the elements in column matrix C are all closer to 1, the allocations in all periods are more balanced.

$$ {C_t}=1-\frac{1}{{B*{B_{0t }}}}\sum\limits_{i=1}^B {\left( {{B_{0t }}-{B_{it }}} \right)} $$
(43.22)
$$ {B_{0t }}=\mathop{\max}\limits_{{i\in B}}{B_{it }} $$
(43.23)

The ranges of the variables mentioned above are: B, T, NLC ∊ N +, and i = 1, 2, …, B, t = 1, 2, …, T, k = 0, 1, 2, …, T − t.

Model Application

CPLEX solver 12.2 is used to solve the LIP model in this paper. According to the actual operations in the container terminal, we take the 1 day duration in which containers remain in the terminal as an example. One day (24 h) is divided into 6 periods, and the planning horizon is 3 days, so the total number of planning periods in one planning period T is 18. Suppose there are 7 blocks (B = 7) with different storage capacities.

Since the loading and unloading of container mixture operation is used in the new container terminal, two LC are needed to realize containers into and out of a block synchronously. So we consider the impact on the space allocation when the number of handling containers is fixed and the number of transport channels can be changed. The quantity of the channels is determined by the number of LC (NLC).

The computational results are as shown in Tables 43.1and 43.2. Due to the discreteness of the number of containers, the space allocation equality rate in every period will not equals 1. We can find that there is a very high SAER 0.9988. The results in Tables 43.1and 43.2show that even in different NLC, the allocation strategies are both optimal. The equilibrium allocation represents that the number of containers handled in different blocks, i.e., the workload among blocks are balanced.

Table 43.1 The allocation strategy in period 6 when NLC = 14
Full size table
Table 43.2 The allocation strategy in period 6 when NLC = 12
Full size table

The computational results demonstrate that a high SAER can be got in every period. That is to say, in all periods of the planning horizon we can maximize the operational capability of the equipment in the storage space.

Table 43.3shows the distribution of LC when NLC is 12. It is observed from Table 43.3that the model can be adopted to make the storage space allocation strategy under the limitation of transport channels.

Table 43.3 The distribution of LC (LCD, LCL) in period 6 when NLC = 12
Full size table

Conclusion

Based on the characteristics of the new container handling system, we establish a non-linear optimization model to solve the space allocation problem when considering imitated transport channels of containers. Some definitions are introduced to linearize the model. Some mathematical solvers, e.g., CPLEX can be used to solve it. The method proposed in this paper can also provide an allocation strategy of the transport channels to the terminal. Therefore, the further promotion can provide some references to the operation of the automated stereoscopic warehouse with multilane.