Sage Journals: Discover world-class research

Abstract

Integrated planning of berth allocation and quay crane assignment in multi-user container terminals has recently attracted much attention by researchers and terminal practitioners. In the literature, many modeling and algorithms in dealing with this integrated problem (e.g. evolution algorithm and greedy search) have been proposed, competing in the solution quality and computational time. However, it is found that holistically solving this integrated problem may not be efficient due to its complexity. Adequately decomposing the problem can increase the solution quality. Meanwhile, it can reduce the computational time required. In this connection, the main contribution of this article is to propose a new two-level genetic algorithm. This algorithm is different from the traditional genetic algorithm in modeling berth allocation and quay crane assignment in the encoding, decoding and evolution mechanisms. The proposed algorithm decomposes the integrated problem into a master problem and a sub-problem, representing the quay crane assignment and the corresponding vessel schedule in each berth. This decomposing approach is designed to enhance the local searching ability, while maintaining the global searching ability of the genetic algorithm. To test the solution quality, existing algorithm found in the literature has been compared. Furthermore, a set of numerical experiment has been carried out to compare the proposed algorithms with the optimal solution obtained by CPLEX. The result demonstrated the proposed algorithm outperforms the existing algorithm and can obtain near-optimal solution. We have also demonstrated the significance of decomposing the model by comparing with traditional single genetic algorithm approach in this field.

Keywords

Berth allocation quay crane assignment vessel scheduling terminal genetic algorithm

Introduction

Unlike dedicated terminals, multi-user container terminals do not dedicate berth for a particular vessel company. For every incoming vessel, terminals will plan to optimize its berthing position and the number of quay cranes (QCs) assigned in order to achieve a better utilization rate. As intercontinental container transshipments increase rapidly, the competition among terminals become fiercer.^1,2 Terminals strive to enhance their competitiveness in attracting more carriers by investing more on facilities (i.e. QCs and berths) to increase the potential servicing capacity and efficiency.³ However, these investments are usually huge and may encounter the difficulty of physical land space limitation. Therefore, applying optimization to increase terminal efficiency becomes more preferable. In this connection, berth allocation and quay crane assignment (QCA) problem have attracted much attention.

Berth allocation problem (BAP) deals with the allocation of vessels to the berths and the scheduling of the set of vessels in the same berth. It is well known as the leading problem in terminal operations because it directly influences the rest of the terminal operations. QCA refers to the allocation of a number of QCs to a vessel for handling containers. The more QCs assigned to a vessel, the shorter the handling time will be. Traditionally, these two problems are solved independently. In addition, vessel handling time in BAP is always assumed as a fixed value or depends on the berthing position. However, since QCA has a strong impact on the vessel handling time, some researchers have integrated BAP and QCA as a single problem and tackled them simultaneously.

Many methodologies have been proposed to deal with this integrated problem.^1,4–7 Among them, Liang et al.⁵ developed a hybrid evolutionary algorithm for solving a real case in one of the Shanghai container terminal companies in China. They found a solution that can be used in practical situations and provided a complete set of data for comparisons. Some articles applying genetic algorithm (GA) in dealing with this integrated problem will model as one single genetic algorithm (SGA). However, these approaches may be too complicated for GA to obtain a good solution and the number of evolutions required to obtain a steady solution may be very long.

In this connection, a new algorithm named two-level genetic algorithm (TLGA) is proposed to determine a vessel schedule that defines the berthing position and the berthing time of the vessels with QCA simultaneously. It aims to minimize the total waiting time, the total handling time and the total delay time. Compared to the existing algorithms, the proposed TLGA decomposes the integrated problem into a master QCA problem and a vessel scheduling sub-problem and solved them by two interrelated GAs. This approach can greatly reduce the problem complexity, improve the searching ability to enhance the optimization result and reduce computational time. The data set and the computational results provided by Liang et al.⁵ have been used as a comparison in one of the experiments to test the solution quality of the proposed algorithm. The traditionally used SGA has also been used as a second comparison in another experiment. The experimental results demonstrated that the proposed algorithm is efficient in solving the integrated problem. It obtains a better solution in a shorter period of time. The total vessel handling time, waiting time and delay time are reduced. In addition, the berth utilization is improved. As a result, the competitiveness of the container terminal can be enhanced. The rest of this article is organized as follows. Section “Literature review” gives a literature review in this area. The corresponding problem formulation and the methodology are presented in section “Problem formulation.” In section “Proposed methodology,” the results are described with explanation. Finally, section “Numerical experiments” concludes the article.

Literature review

Kim and Park⁸ mentioned BAP as the front step in terminal operations. It is used to determine the berthing position of vessels arriving at a terminal. A similar definition was drawn by Steenken et al.,⁹ Cordeau et al.,¹⁰ Imai et al.,¹¹ Wang and Lim¹² and so on. They pointed out that BAP involves two interrelated decisions: (1) where and (2) when the vessels should moor. Generally, vessels berth at an estimated arrival time according to a berthing plan. When a vessel is berthed, the containers will be unloaded to a temporary storage area by QCs. These containers will then be deposited to the designed storage location by internal tractors. After completion of the unloading tasks, export containers will be loaded on the vessel from the yard. The vessel will depart when loading operations are finished.^13,14

In BAP, terminal berth layout is regarded as a spatial constraint. It can generally be categorized into three types: (1) discrete berth layout, (2) continuous berth layout and (3) hybrid berth layout. According to Bierwirth and Meisel,¹⁵ in a discrete layout, the entire quayside is partitioned into several berths and only one single vessel can be served at each berth at a particular time. The discrete approach has the advantage of ease in scheduling, but spatial usage cannot be fully utilized. A continuous berth layout presents completely the opposite characteristics to the discrete layout, which provides more flexible to berth allocation planning. For a hybrid berth layout, it is similar to the discrete berth layout. Since the quayside in a hybrid layout is alienated into berths, a berth can be shared by a number of small vessels, while a number of berths can be used by a large vessel.

Apart from the spatial constraint, Kim and Moon¹⁶ also mentioned that there are several factors that must be considered in BAP, that is, arrival time and handling time of vessels. In the literature, two types of vessel arrival can be found, namely, static arrival and dynamic arrival. In static arrival, it is assumed that all vessels arrive at the terminal before the starting time of the planning horizon. In this case, the arrival time of a vessel can be ignored. In dynamic arrival, an expected arrival time will be given to each vessel, such that the vessels cannot berth before the estimated arrival time.¹⁵ Imai et al.¹¹ stated that the waiting time and the requested departure time are both important because any delay in the departure time may cause late arrival at the next terminal. Therefore, meeting the requested departure time is one of the responsibilities for the terminal operators. Otherwise, not only the carriers are affected but also the terminal will suffer for penalties. To minimize the operating costs, it is necessary for a terminal operator to consider the requested departure time as a criterion for berth allocation.

In the early stage of the optimization methodologies’ development for BAP, first-come first-served (FCFS) was applied in terminals.¹⁷ In fact, GA is widely adopted for solving scheduling problems.^18,19 Same as in solving BAP, for example, Nishimura et al.²⁰ applied GA to solve the problem of Imai et al.²¹ with consideration of multi-water depth configuration. Imai et al.²² developed a GA-based heuristic to minimize the total service time of vessels at an external terminal. Han et al.,²³ Liang et al.,⁵ Chang et al.,⁴ Yang et al.,⁶ Fereidoonian and Mirzazadeh¹⁴ and Golias et al.²⁴ also used GA in their articles, with other heuristics, in solving their problems. Therefore, in this article, we proposed to use two GAs in our methodology.

In more detail, Imai et al.²⁵ studied the problem with dynamic vessel arrival time. They aimed to minimize the total waiting and handling time for vessels using mixed integer programming (MIP) and Lagrangian relaxation. However, it may not be applicable to most container terminals in major countries because the study is based on a public berth system. A discrete dynamic BAP with due dates was formulated by Cordeau et al.¹⁰ They proposed the tabu search (TS) method and demonstrated that it outperformed the FCFS rule. However, the tested problem size was relatively small because of the restrictions on computational time. Mauri et al.²⁶ designed a column generation approach for the problem of Cordeau et al.,¹⁰ which delivered a better solution in a shorter runtime than TS.

Deterministic handling time is always assumed in BAP studies, and most are based on berthing position.^10,11,22,27 This is because the berthing position correlates closely to the amount of the quay facilities (e.g. QC) involved in the operation and also the time of transporting containers between the yard and the berth. However, details of the determination procedure are always ignored. In practice, QCA directly influences the vessel handling time. Therefore, researchers nowadays have more interest in developing an integrated BAP and QCA algorithm. Imai et al.²⁸ studied a problem of simultaneous berth–crane allocation and scheduling with considering some physical constraints of QC. They mentioned that QCs cannot move freely among berths. A GA-based heuristic was developed to minimize the total servicing time. However, in this article, the relationship between the number of QCs assigned and the handling time was ignored. Liang et al.⁵ introduced a formulation for simultaneous berth and QC assignment problem and solved a dynamic scheduling problem by using a hybrid evolution algorithm. They aimed to minimize total waiting time, total handling time and delay time of vessels. Liang et al.²⁹ extended the study by investigating the number of QC movements among berths. They believed that too many movements may reduce the efficiency of loading and unloading operations. Therefore, they proposed a multi-objective mathematical model to trade-off between the numbers of movements and the total servicing time. A multi-objective hybrid GA approach was developed for solving the problem. Chang et al.⁴ first addressed green transportation in its integrated model. They aimed to minimize the deviation berthing position, total penalty and energy consumption of QCs by employing a hybrid algorithm which involves the heuristic rules and parallel genetic algorithm (PGA) to solve the integrated BAP and QCA problem. Giallombardo et al.³⁰ solved the integrated problem at the tactical level. They developed a heuristic algorithm by combining TS and mathematical programming techniques. They also introduced a QC profile in their model and assigned a certain QC profile to the incoming vessels. Raa et al.¹ presented a model for integrated BAP and QCA with consideration of vessel priorities, preferred berthing locations and vessel handling time. Yang et al.⁶ developed an evolutionary algorithm with nested loops to minimize the average service time of the incoming vessels. Mario et al.³¹ presented a model that took into account the QCs and the hold of vessel in determining the handling time. They proposed Greedy Randomized Adaptive Search Procedures (GRASP) meta-heuristic and compared it to some usual scheduling methods employed in container terminal, that is, FCFS, first-come maximum priority, maximum weighed waiting time and earliest weighed mooring time. The results showed great improvement was obtained by the proposed approach. In these approaches, the QCA is involved in calculating the vessel handling time. Therefore, the integrated approaches can generate more efficient schedules than separated ones.

Problem formulation

This section presents a mathematical model for explanation of the problem. We study the discrete berth layout, in which only one vessel is allowed to be served in each berth at a particular time. A fixed arrival time is given to each vessel. Hence, vessels cannot berth before the expected arrival time.

Notations used in the mathematical model are shown as follows:

Input:

a_j expected arrival time of the vessel j

B set of berths in terminal

C total number of QCs in terminal

d_j due departure time of vessel j

E QC productivity (volume/QC/min)

h_j handling volume of vessel j

Maxq maximum number of QCs that can be assigned to each vessel

Q set of QCs in terminal

V set of vessels

In addition, $o (i)$ and $e (i)$ are introduced as the starting node and ending node at berth $i \in B$ . $s_{o (i)}$ and $s_{d (i)}$ represent the starting time and ending time of the planning horizon of berth $i \in B$ , respectively.

Decision variables:

c_j completion time of vessel j

p_jz handling time of vessel j served with z number of QCs

QB_iz set to 1 if z number of QCs are assigned to berth i, and 0 otherwise

QV_ijz set to 1 if z number of QCs are assigned to vessel j at berth i, and 0 otherwise

s_j starting time of vessel j

w_j waiting time of vessel j

x_ijk set to 1 if vessel k is served after vessel j at berth i, and 0 otherwise

y_i number of QCs assigned to berth i

Min z = \sum_{j \in v} (\sum_{i \in B} \sum_{z \in Q} {QV}_{ijz} p_{jz} + w_{j} + \max {0, (c_{j} - d_{j})})

(1)

where $w_{j} = s_{j} - a_{j}$ and $p_{j z} = (h_{j} / E) \cdot y_{i}$

\sum_{i \in B} \sum_{k \in V \cup e (i)} x_{ijk} = 1, \forall j \in V

(2)

\sum_{k \in V \cup e (i)} x_{io (i) k} = 1, \forall i \in B

(3)

\sum_{j \in V \cup o (i)} x_{ije (i)} = 1, \forall i \in B

(4)

\sum_{j \in V \cup o (i)} \sum_{n \in V \cup e (i)} (x_{ijk} - x_{ikn}) = 0, \forall i \in B, \forall k \in V

(5)

c_{j} = s_{j} + \sum_{i \in B} \sum_{k \in Q} {QV}_{ijz} p_{jz}, \forall j \in V

(6)

s_{j} - a_{j} \geq 0, \forall j \in V

(7)

\begin{matrix} s_{k} \geq c_{j} - N \cdot (1 - x_{ijk}), \\ \forall i \in B, \forall j \in V \cup o (i), \forall k \in V \cup e (i) \end{matrix}

(8)

y_{i} \leq Maxq, \forall i \in B

(9)

\sum_{i \in B} y_{i} \leq C

(10)

\sum_{z \in Q} z \cdot {QB}_{iz} = y_{i}, \forall i \in B

(11)

\sum_{z \in Q} {QV}_{ijz} = \sum_{k \in V \cup e (i)} x_{ijk}, \forall i \in B, \forall j \in V

(12)

\begin{matrix} (1 - \sum_{k \in V \cup e (i)} x_{ijk}) N + {QV}_{ijz} \geq {QB}_{iz}, \\ \forall i \in B, \forall j \in V, \forall z \in Q \end{matrix}

(13)

\sum_{i \in B} \sum_{z \in Q} {QV}_{ijz} = 1, \forall j \in V

(14)

The scheduling of berth allocation that assigning vessel k to berth i after vessel j is determined by the binary decision variable $x_{ijk}$ . The number of QCs assigned to berth i is decided by decision variable $y_{i}$ .

Objective (1) minimizes the sum of the handling time, waiting time and the delay time for each vessel. Constraint (2) ensures each vessel must be served once at the berth and each berth serves up to one vessel at any time. Constraints (3) and (4) ensure the incoming and outgoing flows to each berth, and constraint (5) ensures the flow conservation for the remaining vessels at the berth. Constraint (6) defines the calculation of the completion time of each vessel, while constraints (7) and (8) ensure no vessel will berth before its arrival time and the completion time of the previous vessel. Constraint (9) ensures the number of QCs assigned to each berth will not exceed the maximum number of QCs that can be assigned to each vessel. Constraint (10) ensures the total number of QCs assigned to the berths cannot exceed the total number of QCs available in the terminal. Constraints (11)–(13) ensure the consistency of the variables. Constraint (14) ensures a number of QCs is assigned to each vessel.

Proposed methodology

The integrated planning problem mainly consists of two parts: (1) BAP and (2) QCA. BAP is a kind of two-dimensional (2D) stock-cutting problem.³² It is known that the 2D stock-cutting problem is an NP-hard problem (see references for detail), and the GA is widely used as an effective heuristic for solving this kind of problem.^5,32–34 Thus, a genetic-based algorithm called TLGA is designed to decompose this integrated problem into BAP and QCA problems and to solve them in an iterative approach. The framework of the proposed method is presented in Figure 1.

Figure 1.

Framework of the TLGA.

The TLGA consists of two levels. The first level determines the number of QCs assigned to each berth, hereafter called quay crane assignment genetic algorithm (QCAGA). It is the master problem since it directly confines the container handling capability for each berth. The QCA-chromosome will store the information of the QC assignments. The second level, hereafter called vessel scheduling genetic algorithm (VSGA), is used for vessel schedule and allocation solution. This will be the sub-problem and the solution determined will feedback into the master problem for further process. The following describes the procedure of the TLGA:

Step 1. To start with, a pool of initial solutions for the QCAGA will be formed (mechanism presented in section “Encoding and decoding of chromosome”). A number of QCA-chromosomes will be randomly generated according to a pre-defined solution pool size.

Step 2. Each QCA-chromosome, acting as input data, will be individually passed to the VSGA.

Step 3. In the VSGA, a number of VS-chromosomes will be randomly generated to form an initial solution pool (details in section “Encoding and decoding of chromosome”). Then, Steps 3a–3c will be carried out until the stopping condition is reached, and the best VS-chromosome for each QCA-chromosome will be recorded.

Step 3a. Fitness value evaluation for the VS-chromosomes with the corresponding QCA-chromosome (in section “Fitness evaluation”);

Step 3b. Formation of the mating pool using the traditional roulette wheel selection approach. To avoid the loss of the best chromosome, elitist strategy is also applied. Elitist strategy is to record the best chromosome and insert back into the mating pool to replace the weakest chromosome in the next evolution;

Step 3c. Genetic operations—uniform crossover and mutation for the VS-chromosome (in section “Genetic operations: crossover operation”).

Step 4. The best obtained VS-chromosome from Step 3 will be fed into the QCAGA.

Step 5. The fitness of the QCA-chromosomes is evaluated (in section “Fitness evaluation”).

Step 6. The mating pool for the QCAGA will be formed by randomly selecting a number of QCA-chromosomes using the traditional roulette wheel selection approach with elitist strategy.

Step 7. Genetic operation—uniform crossover and mutation for the QCAGA chromosome (in section “Genetic operations: crossover operation”).

Step 8. Check if the stopping condition is reached. If not, repeat Steps 2–7. Otherwise, record the best solution of the QC assignment with the vessel schedule.

For example, in Figure 2, five vessels are being assigned to three berths. The maximum number of QCs is eight with productivity rate=0.5 TEU/min. First of all, in QCAGA part, assuming the solution pool size is 4. Therefore, four QCA-chromosomes will be randomly generated to form the initial pool, such as 3-2-3, 4-3-2, 2-3-3 and 1-3-4. Then each of these chromosomes will pass to the VSGA to determine an optimal vessel scheduling. Assuming the solution pool size is also 4. Then, four VS-chromosomes will be randomly generated, such as 1-2-0-3-4-0-5, 4-0-2-3-5-0-1-0, 0-0-1-2-4-5-3-0 and 1-5-3-0-4-0-2-0. For example with the QCA information of the first QCA-chromosome (3-2-3), the fitness value of each VS-chromosome can be calculated. Then, formation of mating pool, crossover and mutation can be carried out until the stopping condition is met. After that, the best vessel sequencing solution (VS-chromosome, e.g. 1-2-5-0-4-0-3-0) can be found corresponding to the QCA-chromosome (3-2-3). After that, the second QCA-chromosome (4-3-2) will pass into the VSGA, and the aforementioned steps will be carried out again. The rest of the QCA-chromosome will be passed into VSGA one by one until all are passed.

Figure 2.

Example of the execution process of TLGA.

Encoding and decoding of chromosome

In the QCAGA, QCA-chromosomes are represented by character strings, as shown in Figure 3. It consists of Q genes. The position of each gene represents a berth number (berth i), increasing from the left to the right. The value of the gene represents the number of QCs being assigned to that berth. The example demonstrates the encoding of 18 QCs being assigned to three berths, that is, six cranes are assigned to Berth 1, eight cranes to Berth 2 and four cranes to Berth 3.

Figure 3.

Encoding of chromosome for QCAGA.

In the VSGA, VS-chromosomes are represented by character strings, as shown in Figure 4. It is used to represent the vessel–berth assignment and the service order of each vessel in the assigned berth. It consists of (T + Q) number of genes and is divided into Q segments separated by a character “0” to represent Q berths. The value of the gene represents the vessel number. In Berth 1, Vessel 1 is the first vessel being assigned. The service order is defined from the left to the right. The latter vessel has to wait until the previous vessel was completed its job.

Figure 4.

Encoding of chromosome for VSGA.

Fitness evaluation

Each chromosome is evaluated by a fitness value that is calculated by fitness function (equation (15)). This function is an inverse function of the objective function. Hence, the smaller the objective value, the higher the fitness value can be. The fitness value represents the relative strength of the chromosome to the others in the same solution pool

f (x) = 1 - (\frac{z (x)}{\sum_{n = 1}^{N} z (n)})

(15)

where $z (x)$ is the objective value of the chromosome x, and N is the initial solution pool size of GA.

Genetic operations: crossover operation

Uniform crossover is applied in both the QCAGA and the VSGA. In the QCAGA, two values ( $α$ and $β$ ) are involved. The first value ( $α$ ) represents the number of genes involved in crossover, which depends on the crossover rate of the QCAGA and should be smaller than Q. The second value ( $β$ ) represents the position of the gene for starting crossover. It is randomly generated within [1 to (Q − α + 1)]. Figure 5 shows an example for crossover in the QCAGA, in which $α = 2$ and $β = 2$ , so the second and third genes are selected for crossover between Chromosome (A) and Chromosome (B). After crossover, the number of QCs assigned to berths in Chromosome (A) changes to 6-6-8 and Chromosome (B) changes to 4-8-4. Since the total number of QCs is not equal to 18, a validation for QCAGA will be carried out to ensure the total number of QCs is the same as the original value. In the validation, the adjustment will start from the last gene of the chromosome. Therefore, the value of the third gene will be changed from 8 to 6 in Chromosome (A) and will be changed from 4 to 6 in the one in Chromosome (B) accordingly.

Figure 5.

Example of crossover of QCAGA chromosomes.

In the VSGA, $α$ and $β$ are also involved, in which $α$ depends on the crossover rate of the VSGA and should be smaller than (T + Q), while $β$ is randomly generated within [1 to (T + Q−α + 1)]. Figure 6 shows an example for the crossover in the VSGA, in which $α = 3$ and $β = 3$ , so the third, fourth and fifth genes are selected for crossover between Chromosome (C) and Chromosome (D). After crossover, Chromosome (C) represents three vessels assigned to Berth 1 in the order of Vessels 1, 3 and 4. In Chromosome (D), four vessels are assigned to Berth 1 in the order of Vessels 1, 2, 4 and 8. A validation for VSGA will then be conducted in these chromosomes to ensure all the vessels must be assigned only once. In Chromosome (C), Vessel 3 is assigned more than once, whereas Vessel 8 has not been assigned. Therefore, the duplicated Vessel 3 in Berth 1 will be replaced by the missing Vessel 8. Similarly, the duplicated Vessel 8 in Berth 3 will be replaced by the missing Vessel 3 in Chromosome (D).

Figure 6.

Example of crossover of VSGA chromosomes.

Genetic operations: mutation operation

Mutation is another genetic operation in both the QCAGA and the VSGA, in which only a single chromosome is involved. In QCAGA, a number of genes are selected for mutation based on the mutation rate of QCAGA, and the positions of the genes are randomly decided. The value stored inside these genes will then be randomly changed to a value within (1 − m). For example, in Figure 7, the second gene is randomly selected for mutation. A random number (e.g. 7) is generated to replace the value originally stored in the second gene. After mutation, if the total number of QCs assigned is not equal to 18, the chromosome becomes invalid. Validation will be carried out as in the crossover. Thus, in the example, the number of QCs assigned to Berth 3 will change from 8 to 5.

Figure 7.

Example of mutation of QCAGA chromosomes.

In VSGA, a number of genes are selected for mutation based on the mutation rate of VSGA, and the positions of these genes are randomly decided, but do not include the genes with character 0. The value stored inside the gene will then be randomly changed to a value within (1 − T). For example, in Figure 8, the sixth gene is randomly selected for mutation, and a random number (e.g. 3) is generated to replace the original value. After mutation, the chromosome becomes invalid because Vessel 3 has been assigned twice, and Vessel 5 has not been assigned. Therefore, validation will be carried out to change another Vessel 3 to the missing Vessel 5.

Figure 8.

Example of mutation of VSGA chromosomes.

Numerical experiments

The main objective of the numerical experiments is to test the optimization performance of our proposed TLGA. Accordingly, our TLGA approach will be compared with three existing approaches found in the literature, including (1) the traditional SGA, (2) the approach by Liang and Gen³⁵ and (3) the approach by Liang et al.⁵ TLGA, SGA and the approach by Liang and Gen³⁵ assigned QCs to berths, while the approach by Liang et al.⁵ assigned QCs to vessels. We will discuss the solution quality and demonstrate the improvement of the solution quality obtained by the proposed approach.

In this experiment, the benchmarking data set provided by the Shanghai container terminal companies in China is used, consisting of 11 vessels as summarized in Table 1.⁵ There are four discrete berths and seven QCs, and it is regarded as a small-scale problem. The QC productivity ( $E$ ) is 0.667 TEU/min. For the proposed TLGA, it is programmed in JAVA language and run on a PC with CPU 1.33 GHz and 4 GB RAM. The solution pool sizes for QCAGA and VSGA are both 10. The crossover and mutation rates of QCAGA and VSGA are set as 0.3 and 0.1, respectively. A low crossover rate is applied in order to avoid random searching. This is especially important for QCAGA since it is the master problem and is controlling the global search of the algorithm. Regarding this scale, 10 evolutions for QCAGA and 30 evolutions for VSGA are sufficient to obtain a steady solution, and the computational time is around 3 s.

Table 1.

Vessel information.

	Vessel name	Expected arrival time	Duedeparturetime	Total number ofloading/unloading containers (TEU)
1	MSG	9:00	20:00	428
2	NTD	9:00	21:00	455
3	CG	0:30	13:00	259
4	NT	21:00	23:50	172
5	LZ	0:30	23:50	684
6	XY	8:30	21:00	356
7	LZI	7:00	20:30	435
8	GC	11:30	23:50	350
9	LP	21:30	23:50	150
10	LYQ	22:00	23:50	150
11	CCG	9:00	23:50	333

Figure 9 and Table 2 show the optimization results obtained by different approaches. Figure 9 shows that the proposed approach reaches its steady state at around 80 evolutions, while the traditional single-level GA reaches its steady state at around 240 evolutions. In this example, our proposed approach can obtain a solution around three times faster than SGA.

Figure 9.

Optimization performance of different approaches.

Table 2.

Result comparisons.

	TLGA (QCs assigned to berths)	SGA (QCs assigned to berths)	Liang and Gen³⁵ (QCs assigned to berths)	Liang et al.⁵ (QCs assigned to vessels)
Total port staying time (min)	2088	2088	3080	2165
Total handling time (min)	1570	1570	2794	1555
Total waiting time (min)	518	518	286	610
Total delay time (min)	0	0	0	0

TLGA: two-level genetic algorithm; QC: quay crane; SGA: single genetic algorithm.

Table 2 shows that the proposed TLGA and the traditional SGA obtained a new best solution with the shortest total waiting time and handling time. The TLGA outperforms the approach by Liang and Gen³⁵ and Liang et al.⁵ by 32% and 3%, respectively.

The solutions obtained by the Liang et al.⁵ approach and TLGA are plotted, as shown in Figures 10 and 11, respectively. The Liang et al.⁵ approach finished the tasks at 23:02 h, and the proposed TLGA finished at 23:01 h. Although the completion times for both approaches are close, the assignment of vessels by the Liang et al.⁵ approach occupies four berths. However, for the proposed TLGA, only two berths are required (Berths 1 and 3), and other two berths (Berths 2 and 4) can be reserved for other usage. Therefore, the solution obtained by the proposed TLGA approach shows good utilization of the berths.

Figure 10.

Solution obtained by Liang et al.⁵’s approach.

Figure 11.

Solution obtained by TLGA.

In the literature, some researchers applied the assigning QCs to vessel approach because they believed that such approach can increase the flexibility of the schedule and potentially improve the performance of the schedule. However, in this experiment, the proposed TLGA adopts the approach of assigning QCs to berths, but still can achieve good performance and an even better solution than the one proposed by Liang et al.⁵ Moreover, assigning QCs to vessels instead of berths, QCs may have to move from one berth to another berth after completion of a job. The movements consume energy and cause increasing operation cost. Sometimes, some uncertainties may occur, for example, breakdown of a QC may block the movement of other QCs, which affects the overall planned schedule.

To provide a more comprehensive analysis, 27 data sets representing small (T = 10), medium (T = 20) and large (T = 50) problem scales are systematically generated in a 24-h planning horizon (this new benchmarking data set is available from the authors on request). The problems have two characteristics in terms of the vessel arrival pattern and the vessel handling volume, reflecting different situations in a terminal. Each of the characteristics is further divided into three levels (for the arrival pattern: loose, normal and tight; for the handling volume: light, normal and heavy). To define the levels of the arrival pattern, the maximum arrival interval is first defined. It is equal to

Maximum arrival interval = \frac{the duration of the planning horizon \times the total number of berths}{the total number of the vessels}

(16)

For example, in a 24-h planning horizon for 10 vessels in four berths, the maximum arrival interval is 24 h/10 vessels × 4 berths = 9.6 h. After determining the maximum arrival interval, vessels are assigned to four berths. In each berth, the arrival interval between two vessels is 90% ± 10% of the maximum arrival interval and is classified as loose, 70% ± 10% of that as normal and 50% ± 10% of that as tight. To define the levels of the handling volume, the maximum handling capacity in a planning horizon is first determined

Maximum handling capacity = (the total QC productivity per time unit \times the duration of the planning horizon)

(17)

For example, in a 24-h planning horizon, a terminal with eight QCs and the QC productivity ( $E$ ) is assumed to take 0.667 × 60 = 40.2 TEU/h. The maximum handling capacity is 8 QCs × 40.2 TEU/h × 24 h = 7683.84 TEU. In this experiment, it is assumed that the terminal will not handle more than its maximum handling capacity. Hence, the maximum handling volume per each vessel (768.3 TEU/vessel) can be estimated by the maximum handling capacity (7683.84 TEU) over the total number of vessels (e.g. 10). A vessel with 90% ± 10% of the maximum handling capacity is regarded as having a heavy volume, 70% ± 10% as normal volume, and 50% ± 10% as light volume. A set of combinations of these characteristics are shown in Table 3 to represent different scenarios, and the data sets of the combinations are generated for each problem scale.

Table 3.

Different scenarios of terminal situation.

Scenario (S)	Arrival pattern	Handling volume
1	Loose	Light
2	Loose	Normal
3	Loose	Heavy
4	Normal	Light
5	Normal	Normal
6	Normal	Heavy
7	Tight	Light
8	Tight	Normal
9	Tight	Heavy

In this experiment, both the proposed TLGA and the traditional single-level GA are tested and compared with the optimal solution obtained by CPLEX. The results are summarized in Table 4. For small-scale problems (T = 10), all three approaches can obtain the same solutions. Both TLGA and SGA are able to obtain the optimal solution faster than CPLEX, and TLGA obtains it slightly faster than SGA in all scenarios. From the results, we can also observe that the problem complexity is greatly increased with the increase in handling volume, and the computational time used by CPLEX varies from 3.06 to 1196.2 s, while there is no increase in the GA-based approaches. For the medium-scale problems, CPLEX can only find the optimal solutions in Scenarios 1 (loose-light) and 4 (normal-light). For the remaining scenarios, no optimal solution can be found within 15 h. For Scenarios 1 and 4, the computational time required by CPLEX in solving the medium-scale problem is around 4000–5000 times more than that in solving the small-scale problems. Although the total handling volume does not change much, as it is limited by the maximum handling capacity, the problem complexity still can be enormously increased when the number of vessels is increased. This increment also affects the performance of TLGA and SGA, but the effect is relatively small.

Table 4.

Performance of TLGA and SGA.

T	Data set	(S)	CPLEX		SGA		TLGA
			Z (min)	Time (s)	Z (min)	Time (s)	Z (min)	Time (s)	(% Change) comparing to SGA
			Z (min)	Time (s)	Z (min)	Time (s)	Z (min)	Time (s)	Z	Time (s)
(10) Vessels = small	1	1	1644.25	4.31	1644.25	3.72	1644.25	2.12	0.00	−43.01
	2	2	2615.02	4.43	2615.02	3.54	2615.02	2.28	0.00	−35.59
	3	3	3619.16	63.41	3619.16	3.57	3619.16	2.31	0.00	−35.29
	4	4	1512.95	3.06	1512.95	3.42	1512.95	2.08	0.00	−39.18
	5	5	2364.99	5.69	2364.99	3.59	2364.99	2.27	0.00	−36.77
	6	6	3523.17	56.96	3523.17	4.01	3523.17	2.34	0.00	−41.65
	7	7	1669.50	14.58	1669.50	3.51	1669.50	2.23	0.00	−36.47
	8	8	2798.31	185.28	2798.31	3.53	2798.31	2.30	0.00	−34.84
	9	9	4462.33	1196.23	4462.33	3.56	4462.33	2.28	0.00	−35.96
(20) Vessels = medium	10	1	1825.59	18617.14	1825.59	18.87	1825.59	7.93	0.00	−57.98
	11	2	–	–	3075.22	17.98	3075.22	7.84	0.00	−56.40
	12	3	–	–	3913.89	18.91	3845.30	7.25	−1.75	−61.66
	13	4	1786.36	17595.32	1786.36	18.23	1786.36	7.23	0.00	−60.34
	14	5	–	–	3337.89	18.18	3328.46	7.8	−0.28	−57.10
	15	6	–	–	8272.20	18.81	8272.20	7.67	0.00	−59.22
	16	7	–	–	2003.35	18.39	2003.35	7.24	0.00	−60.63
	17	8	–	–	6506.99	18.43	6492.48	7.23	−0.22	−60.77
	18	9	–	–	12067.13	18.51	12018.57	7.29	−0.40	−60.62
(50) Vessels = large	19	1	–	–	8094.47	1082.70	7827.47	42.45	−3.30	−96.08
	20	2	–	–	11387.25	1090.32	11010.16	43.84	−3.31	−95.98
	21	3	–	–	17389.96	1076.52	16429.28	40.10	−5.52	−96.28
	22	4	–	–	8290.043	1075.08	8050.12	42.62	−2.89	−96.04
	23	5	–	–	13604.51	1093.98	13114.38	43.02	−3.60	−96.07
	24	6	–	–	22948.72	1086.66	22060.28	43.60	−3.87	−95.99
	25	7	–	–	9477.28	1080.18	9161.86	42.28	−3.33	−96.09
	26	8	–	–	18340.12	1099.50	17641.07	42.17	−3.81	−96.16
	27	9	–	–	32619.81	1090.74	30671.30	43.88	−5.97	−95.98

SGA: single genetic algorithm; TLGA: two-level genetic algorithm.

Compared to the small-scale problems, both TLGA and SGA in the medium-scale problems (T = 20) require more evolutions to achieve a steady solution state, and their computational times are increased by three and five times, respectively. From the results, TLGA and SGA are able to obtain optimal solution in Scenarios 1 and 4, and TLGA is 2.44 times faster than SGA on average. However, for Scenarios 3, 5, 8 and 9, SGA cannot find solutions as good as TLGA.

For the large-scale problems (T = 30), clearly it is the most complicated problem set, and CPLEX is not able to find a solution. It is also more difficult for the SGA to achieve its steady solution state, and therefore, the computational time increases exponentially. The results show that TLGA outperforms SGA in both the computational time and solution quality by 2%–6% and 94%–97%, respectively. Generally speaking, these experiments demonstrate that the proposed TLGA outperforms the traditional SGA in all scenarios in terms of computational time and solution quality.

Conclusion

In general, BAP determines a berthing position and a berth time for each incoming vessel, while QCA determines a suitable number of QCs to a vessel for handling containers. In many traditional approaches, BAP and QCA are planned separately, and vessel handling time is always assumed as a fixed value. In fact, it can be directly affected by the number of QCs assigned to the vessel. With this relationship, integrated planning of BAP and QCA becomes more important. Researchers and terminal practitioners need a good solution for integrated planning, and therefore, the integrated model with a TLGA approach is proposed to minimize the total vessel waiting time, handling time and delay time by simultaneously adjusting QC assignment with berth allocation. The proposed TLGA is composed of two genetic-based algorithms at different levels. One is used to decide on the QCA and the other is used to decide on the corresponding vessel schedule. Since these decisions are interrelated, the two algorithms interact in for determining the final solution. The optimization reliability of the proposed approach has been tested in numerical experiments based on a set of real data from the literature and the optimal results were found by CPLEX. The results show that the proposed TLGA is an effective approach, which can generate a solution with better quality in a fast time, and this computation time is affordable for practical use. The efficiency of the terminal operations can be enhanced by reducing the total vessel service time and improving the berth utilization.

Footnotes

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This study was financially and technically supported by The Hong Kong Polytechnic University (account code: RPWB).

References

Raa

Dullaert

Schaeren

. An enriched model for the integrated berth allocation and quay crane assignment problem. Expert Syst Appl 2011; 38: 14136–14147.

Trappey

AJC

Lin

GYP

. Business and logistics hub integration to facilitate global supply chain linkage. Proc IMechE, Part B: J Engineering Manufacture 2007; 221: 1221–1233.

Rashidi

Tsang

EPK

. Novel constraints satisfaction models for optimization problems in container terminals. Appl Math Model 2013; 37: 3601–3634.

Chang

Jiang

Yan

. Integrating berth allocation and quay crane assignments. Transport Res E: Log 2010; 46: 975–990.

Liang

Huang

Yang

. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Comput Ind Eng 2009; 56: 1021–1028.

Yang

Wang

. An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. Comput Ind Eng 2012; 63: 243–253.

Zhang

Zheng

Zhang

. The allocation of berths and quay crane by using a sub-gradient optimization technique. Comput Ind Eng 2010; 58: 40–50.

Kim

Park

. A crane scheduling method for port container terminals. Eur J Oper Res 2004; 156: 752–768.

Steenken

Vob

Stahlbock

. Container terminal operation and operations research—a classification and literature review. OR Spectrum 2004; 26: 3–49.

10.

Cordeau

Laporte

Legato

. Models and tabu search heuristics for the berth allocation problem. Transport Sci 2005; 39: 526–538.

11.

Imai

Zhang

Nishimura

. The berth allocation problem with service time and delay time objectives. Marit Econ Logist 2007; 9: 269–290.

12.

Wang

Lim

. A stochastic beam search for the berth allocation problem. Decis Support Syst 2007; 42: 2186–2196.

13.

Mak

. Yard crane scheduling in port container terminals. Appl Math Model 2005; 29: 263–276.

14.

Fereidoonian

Mirzazadeh

. A genetic algorithm for the integrated scheduling model of a container-handling system in a maritime terminal. Proc IMechE, Part M: J Engineering for the Maritime Environment 2012; 226: 62–77.

15.

Bierwirth

Meisel

. A survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 2010; 202: 615–627.

16.

Kim

Moon

. Berth scheduling by simulated annealing. Transport Res B: Meth 2003; 37: 541–560.

17.

Lee

Chen

. An optimization heuristic for the berth scheduling problem. Eur J Oper Res 2008; 196: 500–508.

18.

Chan

FTS

Tibrewal

Prakash

. A biased random key genetic algorithm approach for inventory-based multi-item lot-sizing problem. Proc IMechE, Part B: J Engineering Manufacture, in press.

19.

Dong

Yang

. Cross-docking centre operation optimization using simulation-based genetic algorithm. Proc IMechE, Part B: J Engineering Manufacture 2011; 225: 1175–1187.

20.

Nishimura

Imai

Papadimitriou

. Berth allocation planning in the public berth system by genetic algorithm. Eur J Oper Res 2001; 131: 282–292.

21.

Imai

Nagaiwa

Tat

. Effective planning of berth allocation for container terminals in Asia. J Adv Transport 1997; 31: 75–94.

22.

Imai

Sun

Nishimura

. Berthing ships at a multi-user container terminal with a limited quay capacity. Transport Res E: Log 2008; 44: 136–151.

23.

Han

Sun

. The algorithm for berth scheduling problem by the hybrid optimization strategy GASA, Singapore, 5–8 Dec 2006. In: IEEE computer society, Washington, DC, 2006, pp.1–4. New York: IEEE.

24.

Golias

Portal

Konur

. Robust berth scheduling at marine container terminals via hierarchical optimization. Comput Oper Res 2014; 41: 412–422.

25.

Imai

Sun

Nishimura

. The dynamic berth allocation problem for a container port. Transport Res B: Meth 2001; 35: 401–417.

26.

Mauri

Oliveira

ACM

Lorena

LAN

. A hybrid column generation approach for the berth allocation problem. In: Van Hemert

Cotta

(eds) Evolutionary computation in combinational optimisation: eighth European conference. Berlin, Heidelberg: Springer, 2008, vol. 4292, pp.110–122.

27.

Golias

Boile

Theofanis

. Berth scheduling by customer service differentiation: a multi-objective approach. Transport Res E: Log 2009; 49: 878–892.

28.

Imai

Chen

Nishimura

. The simultaneous berth and quay crane allocation problem. Transport Res E: Log 2008; 44: 900–920.

29.

Liang

Guo

Yang

. Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning. J Intell Manuf 2011; 22: 471–479.

30.

Giallombardo

Moccia

Salani

. Modeling and solving the Tactical Berth Allocation Problem. Transport Res B: Meth 2010; 44: 232–245.

31.

Mario

Miguel

Federico

. A GRASP-based metaheuristic for the Berth Allocation Problem and the Quay Crane Assignment Problem by managing vessel cargo holds. Appl Intell 2013; 40: 273–290.

32.

Park

Kim

. A scheduling method for Berth and Quay cranes. OR Spectrum 2003; 25: 1–23.

33.

Kozan

Preston

. Genetic algorithms to schedule container transfers at multimodal terminals. Int Trans Oper Res 1999; 6: 311–329.

34.

Tavakkoli-Moghaddam

Makui

Salahi

. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports. Comput Ind Eng 2009; 56: 241–248.

35.

Liang

Gen

. Hybrid genetic algorithm for considering quay crane scheduling in berth allocation planning problem. In: Proceedings of the 10th Asia-Pacific workshop on intelligent and evolutionary systems (APWIES), Seoul, South Korea, 25–26 November 2006.

A fast approach for the integrated berth allocation and quay crane assignment problem

Abstract

Keywords

Introduction

Literature review

Problem formulation

Proposed methodology

Encoding and decoding of chromosome

Fitness evaluation

Genetic operations: crossover operation

Genetic operations: mutation operation

Numerical experiments

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References