Research on Continuous Berth Allocation Problem based on Genetic-Harmony Search Algorithm

In order to solve the berth allocation problem and improve the efficiency of the dock, a mixed integer nonlinear programming model is built with the length of port stay. The genetic-harmony search algorithm is used to solve it for the first time. Finally, the algorithm and Lingo are used to solve the large-scale berth allocation problem at the same time. Under the same data of arrival ships, several groups of experiments are designed to verify the algorithm. The results show that the genetic-harmony search algorithm can be used to solve the berth allocation problem. On the basis of the consistency between the genetic-harmony search algorithm and Lingo, the genetic-harmony search algorithm is faster and more efficient.


Introduction
The berth system, one of the most important operations of container terminal, includes berthing and unberthing of ships and cargo handling. In addition, a reasonable berth allocation can make full use of water-front resources and improve the operational efficiency of berth system. In current research, berth allocation can be divided into static berth allocation and dynamic berth allocation according to the different arrival ways of ships. The former assumes that all ships have arrived at the port when the plan is executed. Its research significance is to be applied in busy ports with a large number of ships waiting to berth. However, the study is only applicable to some ports and still needs to be improved. [1,2]. Relatively speaking, the latter is more in line with the actual situation. According to berth space, the berth allocation problem can be divided into discrete berth and continuous berth. The former model is relatively simple and easy to analyze, but the berth resources are not sufficiently used [3,4]. In addition, with the increasing development of competitiveness, the discrete berth is not suitable for the actual situation of the port, therefore more and more scholars focus on the problem of continuous berth allocation. Because of the above analysis, this paper will study the dynamic continuous berth allocation.
The berth planning problem has been proved to be NP-Complete, which full name is the uncertainty problem of polynomial complexity [5].The characteristics of berth planning problem show that it is difficult to find the global optimal solution in polynomial time with accurate algorithm, so experts usually use heuristic algorithm to solve it. Imai et al. regarded the solution of discrete berth allocation as a guide and changed the limit of berth length. They proposed a heuristic algorithm which was able to obtain the approximate optimal solution by solving the continuous berth allocation model [6]. Giallombardo [7,8]. Ting et al. proposed a mixed integer programming model of the dynamic discrete berth planning problem, and particle swarm optimization algorithm was used [9]. Li used three types of heuristic algorithm to solve the combined scheduling of continuous berth and quay crane [10]. For the berth allocation problem, tabu search algorithm, genetic algorithm, particle swarm optimization algorithm and other kinds of heuristic algorithm are commonly used. In this paper, genetic-harmony search algorithm will be used to solve the dynamic continuous berth allocation and it will be proved to be an effective algorithm in solving the berth planning problem.

Problem statement of continuous berth allocation
The continuous berth allocation can be transformed into geometric form of the two-dimensional packing problem in which the length of the Quay Line is taken as the X-axis and the time as the Y-axis to constitute a two-dimensional space [6].The ship is represented in the form of a rectangle, the length of which is the length of the ship, and the width of which is the time of cargo handling, as shown in Fig  Take ship 1 as an example, t 1 is the berthing time of ship 1, t 2 is the departure time of ship 1, (p 1 , p 2 ) is the berth location of ship 1 on the quay. The continuous berth allocation can be described as how to put vessels (replace with rectangle) efficiently on this this two-dimensional space-time graph which aim is to determine the berthing time and berth location of ships.
To analyze the problem more simply and formulate the mathematical model more accurately, the following assumptions are made: (1) Each vessel must be serviced only once.
(2) Each vessel can only be served after arriving at the port.
(3) The quay depth meets the requirement for vessels to berth, which means vessels can berth at any location of the quay.
(4) Each vessel has a preferred berth location, and the actual time of cargo handling depends on the preferred berth location.

Model building
In formulating a mathematical model, we define the notations as follows: i, jV, ship A i , arrival time of vessel i L i , the length of vessel i Q, the length of quay (including inter-ship clearance) H, the planning duration M i , the preferred berth location of vessel i. Generally, the vessel would like to berth near a specific yard, which is the preferred berth location of the vessel [11].
CM i , the handling time of vessel i at the best quay location Tan i , a ratio of increasing handling time to the distance for vessel i The mathematical model is formulated as follows: (8) Function (1) minimizes the sum of service times for all vessels. Constraints (2)-(6) are the non-overlapping restriction both in time and space. Constraints (7)-(8) ensure that vessel i must be berthed within the length of the quay. Constraint (9) ensures that vessel i is berthed after its arrival. Constraint (10) defines the decision variables. Equation (11) indicates the handling time of vessel i that it consists of two pieces: the minimum handling time at the best quay location, and the increasing handling time.
Equation (12) indicates the time vessel i departs berth equals the time vessel i starts berthing plus the time vessel i operations berthing and unberthing plus the time of vessel i's cargo handling.  Harmony search algorithm (HS) imitates the music improvisation process where musicians improvise their instruments' pitch by searching for a perfect state of harmony [12]. HS analogizes the solution vector of the optimization problem to the harmony of the instrument's pitch, and finding the best state of harmony is to find the optimal value of the objective function. In order to prevent HS from falling into the local optimum and make the output more accurately, this paper uses genetic algorithm (GA) to optimize HS firstly. GA, a parallel random search optimization method, was proposed by Professor Holland. Its principle is to simulate the genetic mechanism of nature and the theory of biological evolution. The main operations of GA are selection, crossover and mutation.

Harmony search algorithm and genetic algorithm
The parameters of HS are: harmony memory size (HMS), harmony memory size (HMZ), harmony memory considering rate (HMCR), pitch adjusting rate (PAR), band width (BW), Tmax which means the stopping criteria. The procedure of HS is shown in Fig.2.

The procedure of genetic-harmony search algorithm
In this paper, genetic-harmony search algorithm is used to solve the berth allocation problem. First of all, GA is used to select and cross the initial population so as to get a new suboptimal population with a certain quality. Then, HS is used to iteratively search for the optimal solution of the new suboptimal population. The procedure of genetic-harmony search algorithm is: Step 1: Initialize parameters: HMS, HMCR, PAR, BW, the range of value, [XMIN, XMAX], the probability of crossover operator pc in GA and so forth.
Step 2: Initialize harmony memory HM: Randomly select solution vectors in the range of the objective function to fill in the matrix HM, and calculate the objective function value of each solution vector. The generation mode of initial population is shown in formula (13). (13) Step 3: Select the initialization harmony memory: this paper uses roulette wheel selection to select the individuals, and a New Harmony memory called HMSelect is generated.
Step 4: make the crossover on HMSelect: All individuals of the population are paired in pairs, and whether they need to cross is judged according to the probability of crossover operator pc. The crossover mode is shown in formula (14) and formula (15), and new population HMNew is generated. (14) (15) c1, c2 represent the newly generated solution vector, and x1, x2 represent the original solution vector in the population.
Step5: HS is used to iteratively search for the optimal solution of HMNew so as to find the optimal solution of the problem.

Specific example
In this paper, the data is from the reference [13], the length of quay is 1200m, the planning period is 24h, the time that each vessel operations berthing and unberthing is 0.5h respectively, tan i is 0.005, and other relevant data is shown in Table 1. We have implemented our heuristic using MATLAB, and the parameters are the size of HM=200, HMCR=0.98, PAR=0.3, BW=0.5, pc=0.9, and Tmax=10000. The solution is shown in Table 2  The results show that the sum of service times for all vessels is 63. 85h.The distance deviation of V1, V2, V3, V4, V5, V6, V7 and V8 is 29m, 22m, 38m, 47m, 478m, 172m, 62m and 82m respectively. In addition, V4 needs to be berthed and the waiting time is 0.2h.

Test example
In order to verify the effectiveness of genetic-harmony search algorithm, we have designed 5 test sets to conduct experiments. The number of vessels in each set is 10,15,20,25, and 30 respectively. The length of vessel (m) is randomly selected from [100, 400], the arrival time (h) is selected randomly from [0,24], the minimum handling time (h) is selected randomly from [4,8], the length of quay is 1000m, 1400m, 1800m, 2200m and 2600m respectively. Other data are the same as the data of example 3.1. According to the method of verification from reference 14, we set the maximum time of Lingo's calculating to 10800s.That means when calculating time of Lingo is over 10800s, the operation is terminated, and the feasible solution is obtained. The parameters are that the size of HM is 200, Tmax which ensures the running time of genetic-harmony search algorithm is more than 300s. At the same time, the running time of genetic-harmony search algorithm is set to 300s.When the program runs for 300s, it stops running and outputs the current optimal solution. The results and running time of Lingo and genetic-harmony search algorithm are shown in Table 3, while the error percentage is shown in Fig  3.  Figure 3. Error percentage It can be seen from Table 3, the optimal solution can be obtained within 10800s by Lingo in first example. However, the running time of latter four examples has exceeded 10800s and the feasible solutions are obtained. From the solutions, from the result, the solution of genetic-harmony search algorithm is basically the same as that of Lingo. It can be seen from Fig.3, the maximum error percentage is 2.38%, the minimum is 0.11%, and the average error percentage is 1.08%, which proves that the genetic-harmony search algorithm can be used to solve the berth allocation problem. Meanwhile, in terms of computing time, the running time of Lingo is much longer than that of the genetic-harmony search algorithm with the increase of the number of vessels. Therefore, we can draw a conclusion that when the number of vessels is too large, the running time of genetic-harmony search algorithm is faster and more efficient than that of Lingo on the basis of basically consistent results.

Conclusion
This paper establishes a mixed integer nonlinear programming model with the minimum total service time of vessels at the port as the objective function. To facilitate the solution procedure, genetic-harmony search algorithm that harmony search algorithm is optimized by genetic algorithm is used to solve the mathematical model and the berth allocation plan is obtained. Furthermore, the effectiveness of geneticharmony search algorithm is verified by test examples of a large number of vessels. This paper compares the results and running time of the algorithm with those of Lingo. The result shows that genetic-harmony search algorithm is faster than lingo when there are many vessels arriving at the port. However, the preferred berth location of vessels is set as 300m, 600m, and 900m in this paper. But the preferred berth location of the ship is closely related to the location of the yard in reality. In the future research, the berth and yard can be jointly scheduled to calculate the preferred berth location of vessels so as to make it more conducive to guiding the actual work of the port in the future.